"Wei Lai Cup" 2022 Niuke summer multi school training camp 2, sign in question GJK

Question no title Passed code Passing rate The status of the team
A Falfa with Polygon Click to see 56/445
B light Click to see 50/326
C Link with Nim Game Click to see 192/1035
D Link with Game Glitch Click to see 831/6211
E Falfa with Substring Click to see 264/3287
F NIO with String Game Click to see 52/412
G Link with Monotonic Subsequence Click to see 1667/7564
H Take the Elevator Click to see 290/769
I let fat tension Click to see 204/454
J Link with Arithmetic Progression Click to see 1407/7990
K Link with Bracket Sequence I Click to see 996/3057
L Link with Level Editor I Click to see 564/2616

G.Link with Monotonic Subsequence

The question ：

• official
  

Ideas ：

• I began to think about the structure （1, 2, 3, 4）（9, 8, 7, ,6 , 5） This arrangement , such The front group forms at most one of the following groups LIS, The answer is n/2+1, Then think about it Get more groups , Can become smaller .
• The structure is like （3, 2, 1）,（ 6, 5, 4）,（ 9, 8, 7） Permutation , In this way, each group and the latter group can only choose one , And then if More groups , The length will also increase , On this basis, we should Make each group of elements relatively more , So it is to continue to find the root of the average n, namely Each radical n Elements that will do .
• Pay attention to Rounding up , Because, for example 7 When , Be situated between 2~3 Between , We must choose 3 To reduce the number of groups .

#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;
}

J.Link with Arithmetic Progression

The question ：

• official ：
  

Ideas ：

• official ：
  

• Let's talk about linear regression
  Least square method , That is to minimize the sum of squares of residuals , Is the value required by this question , The square of the difference between the arithmetic sequence and the current sequence .
  The proof process can refer to ：https://zhuanlan.zhihu.com/p/73494604,
  The formula can refer to ：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;  // coordinate (i,a[i]) 
        for(int i = 1; i <= n; i++){
    
            cin>>a[i];
            x += i;  y += a[i];
        }
        x /= n;  y /= n;     // expect E(x),E(y), namely x,y mean value 
        LD s1 = 0, s2 = 0;   
        for(int i = 1; i <= n; i++){
    
            s1 += (i-x)*(a[i]-y); // covariance ：Cov(X,Y) = E[(X-E[X])(Y-E[Y])]?
            s2 += (i-x)*(i-x);    // variance ：D(x) = E[(X-E[X])(X-E[X])]
        }
        LD k = s1/s2, b = y-k*x;  // The formula 
        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;
}

• Three point approach
  It is known that f(x) stay l,r Single peak and continuous , Find the extreme value . Each iteration reduces the length of the current interval 1/3 Until we find the extreme value .
  We know that the arithmetic sequence is a straight line , This line and all given points （i,a[i]） Finding the smallest variance is the point to find .
  So let's set a straight line y = kx+b , namely b^2=(y-kx)^2, Make y=a[i], x=i, At this point, we just need to minimize b The variance of .
  b About k Single peak and continuous ,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 The variance of 
    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;
}

K.Link with Bracket Sequence I

The question ：

• official ：
  

Ideas ：

• official
  

#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 front i position ,'(' Than ')' many j individual ,a front k The number of schemes of bit 

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++){
    
                    // about b[i+1], a[k+1] Choose or not 
                    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;
}