“蔚来杯“2022牛客暑期多校训练营2,签到题GJK

举报
小哈里 发表于 2022/07/28 00:57:14 2022/07/28
【摘要】 题号 标题 已通过代码 通过率 团队的状态 A Falfa with Polygon 点击查看 56/445 B light 点击查看 50/326 C Link with Nim Game 点击查看 ...

题号 标题 已通过代码 通过率 团队的状态
A Falfa with Polygon 点击查看 56/445
B light 点击查看 50/326
C Link with Nim Game 点击查看 192/1035
D Link with Game Glitch 点击查看 831/6211
E Falfa with Substring 点击查看 264/3287
F NIO with String Game 点击查看 52/412
G Link with Monotonic Subsequence 点击查看 1667/7564
H Take the Elevator 点击查看 290/769
I let fat tension 点击查看 204/454
J Link with Arithmetic Progression 点击查看 1407/7990
K Link with Bracket Sequence I 点击查看 996/3057
L Link with Level Editor I 点击查看 564/2616

G.Link with Monotonic Subsequence

题意:

  • 官方
    在这里插入图片描述

思路:

  • 开始想的是构造(1, 2, 3, 4)(9, 8, 7, ,6 , 5)这样的排列,这样前面一个组最多与后面的组中的一个形成LIS,答案就是n/2+1,然后再想可以多弄几个组,就可以变得更小
  • 构造形如(3, 2, 1),( 6, 5, 4),( 9, 8, 7) 的排列,这样每个组与后一个组都只能选一个,然后如果组数变多,长度也会变大,在此基础上要让每组元素相对更多,所以就是继续求平均的根号n,即每组根号n个元素即可。
  • 注意要向上取整,因为比如7的时候,介于2~3之间,我们肯定是选3来让组数变得更少。
#include<bits/stdc++.h>
using namespace std;

int main(){
    int T;  cin>>T;
    while(T--){
        int n;  cin>>n;
        int sq = ceil(sqrt(n));
        for(int i = n; i > 0; i -= sq){//(7 8 9 )(4 5 6) (1 2 3)
            for(int j = max(1,i-sq+1); j <= i; j++)
                cout<<j<<" ";
        }
        cout<<"\n";
    }
    return 0;
}



  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

J.Link with Arithmetic Progression

题意:

  • 官方:
    在这里插入图片描述

思路:

  • 官方:
    在这里插入图片描述

  • 讲一下线性回归
    最小二乘法,即最小化残差的平方和,就是本题要求的值,等差数列和当前数列的差值平方。
    证明过程可以参考:https://zhuanlan.zhihu.com/p/73494604,
    公式可以参考:https://blog.csdn.net/snowdroptulip/article/details/79020590
    在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double LD;
const int maxn = 1e6+10;
int a[maxn];

int main(){
    int T;  cin>>T;
    while(T--){
        LD n;   cin>>n;
        LD x = 0, y = 0;  //坐标(i,a[i]) 
        for(int i = 1; i <= n; i++){
            cin>>a[i];
            x += i;  y += a[i];
        }
        x /= n;  y /= n;     //期望E(x),E(y),即x,y均值
        LD s1 = 0, s2 = 0;   
        for(int i = 1; i <= n; i++){
            s1 += (i-x)*(a[i]-y); //协方差:Cov(X,Y) = E[(X-E[X])(Y-E[Y])]?
            s2 += (i-x)*(i-x);    //方差:D(x) = E[(X-E[X])(X-E[X])]
        }
        LD k = s1/s2, b = y-k*x;  //公式
        LD ans = 0;
        for(int i = 1; i <= n; i++){
            ans += (a[i]-k*i-b)*(a[i]-k*i-b);
        }
        printf("%.15Lf\n",ans);
    }
    return 0;
}



  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 三分做法
    已知f(x)在l,r上单峰且连续,求极值。每次迭代将当前区间的长度缩小1/3直到找到极值。
    前面我们知道等差数列是一条直线,这条直线与所有给出的点(i,a[i])求方差最小时就是要找的点。
    所以设直线y = kx+b ,即b^2=(y-kx)^2,令y=a[i], x=i,此时我们只需要最小化b的方差即可。
    b关于k单峰且连续,b=f(k)。
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
typedef long long LL;
typedef long double LD;
const LL maxn = 1e6+10;
const LD eps = 1e-10;
LD a[maxn], b[maxn], n;

LD check(LD k){//b=y-kx的方差
    LD sum = 0, res = 0;
    for(int i = 1; i <= n; i++){
        b[i] = a[i]-k*i;
        sum += b[i];
    }
    sum /= n;
    for(int i = 1; i <= n; i++){
        res += (b[i]-sum)*(b[i]-sum);
    }
    return res;
}

int main(){
    IOS;
    int T;  cin>>T;
    while(T--){
        cin>>n;
        LD sum = 0;
        for(int i = 1; i <= n; i++){
            cin>>a[i];  sum += a[i];
        }
        LD l = -1e15, r = 1e15, ans = 1e100;
        while(r-l > eps){
            LD mt = (r-l)/3;
            LD m1 = l+mt, m2 = r-mt;
            LD v1 = check(m1), v2 = check(m2);
            if(v1 >= v2){
                ans = min(ans, v2);
                l = m1;
            }else{
                ans = min(ans, v1);
                r = m2;
            }
        }
        printf("%.15Lf\n",ans);
    }
    return 0;
}



  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50

K.Link with Bracket Sequence I

题意:

  • 官方:
    在这里插入图片描述

思路:

  • 官方
    在这里插入图片描述
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
typedef long long LL;
const int maxn = 210;
const int mod = 1e9+7;

LL f[maxn][maxn][maxn];//b前i位,'('比')'多j个,a前k位的方案数

int main(){
    IOS;
    int T;  cin>>T;
    while(T--){
        int n, m;  cin>>n>>m;
        string a;  cin>>a;
        a = "0"+a;
        // memset(f,0,sizeof(f));  //TLE 70%
        for (int i = 0; i <= m; ++ i) {
            for (int j = 0; j <= m; ++ j) {
                for (int k = 0; k <= m; ++ k) {
                    f[i][j][k] = 0;
                }
            }
        }
        f[0][0][0] = 1;
        for(int i = 0; i < m; i++){
            for(int j = 0; j <= i; j++){
                for(int k = 0; k <= i; k++){
                    //对于b[i+1], a[k+1]选或不选
                    if(a[k+1]==')'){
                        if(j>0)(f[i+1][j-1][k+1] += f[i][j][k]) %= mod;
                        (f[i+1][j+1][k] += f[i][j][k]) %= mod;
                    }else if(a[k+1]=='('){
                        (f[i+1][j+1][k+1] += f[i][j][k]) %= mod;
                        if(j>0)(f[i+1][j-1][k] += f[i][j][k]) %= mod;
                    }else {
                        (f[i+1][j+1][k] += f[i][j][k]) %= mod;
                        if(j>0)(f[i+1][j-1][k] += f[i][j][k]) %= mod;
                    }
                }
            }
        }
        cout<<f[m][0][n]<<"\n";
    }
    return 0;
}



  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48

文章来源: gwj1314.blog.csdn.net,作者:小哈里,版权归原作者所有,如需转载,请联系作者。

原文链接:gwj1314.blog.csdn.net/article/details/125960058

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。