"Wei Lai Cup" 2022 Niuke summer multi school training camp 2 supplementary problem solution (g, J, K, l)

---

If you think it's helpful, give it a compliment ！

Address of the competition
Refer to the big guy's problem solution

G Link with Monotonic Subsequence

It's the previous question , But this road signing is very painful , It took teammates a long time to list the data before finding the rule

#include<bits/stdc++.h>
using namespace std;
int main()
{
    
    int T;
    cin>>T;
    while(T--)
    {
    
         int n;
        cin>>n;
        int x=sqrt(n);
        if(n-x*x>0) x++;
        int ge=x;
        int zu=n/ge;
        int yu=n%ge,tt=yu;
        for(int i=yu;i>=1;i--)
        {
    
            cout<<i<<" ";
        }
            
        
        for(int i=1;i<=zu;i++)
        {
    
        
            for(int j=ge;j>=1;j--)
            {
    
                cout<<tt+j<<" ";
            }
            tt+=ge;
        }
        puts("");
    }
    return 0;
}

J Link with Arithmetic Progression

Refer to the solution of a big man ：
Content of linear regression , If you know the formula, you can set it directly , Obviously this is a unipolar quadratic function , But there are two variables . We can divide one third first a1, And then through a1 Calculation d, You can find the error of . I'll put one a1 Calculation d Hand push formula of your fine products .

Here I would like to add an explanation , In the figure f(x)（ In fact, it should be f(d)） Namely t, That is, the sum of difference products , Our aim is to make t Minimum , That is to say f(x)（f(d)） Minimum , Think about Primary School （ Maybe high school is ） How to get the minimum value of a quadratic equation in one variable , Is to take the derivative of the equation , Let the derivative f’(x)=0, This x That is, the entire univariate quadratic equation is 0 Value of time independent variable , In the picture f(d) When you take the minimum d The value of should be the pile to the right of the equal sign , Because of the ai Not fixed value , therefore d The value should be for each ai Find a value x,x The sum is d Value （ This one won't push , But it's easy to remember ）
Those who don't understand the least square method can take a look at this ： Just look at the front 9 Just a minute

#include<bits/stdc++.h>
#include <cstdio>
#include <cctype>

#define db double

using namespace std;

const int N = 1e5 + 10;

namespace GTI
{
    
    char gc(void)
       {
    
        const int S = 1 << 16;
        static char buf[S], *s = buf, *t = buf;
        if (s == t) t = buf + fread(s = buf, 1, S, stdin);
        if (s == t) return EOF;
        return *s++;
    }
    int gti(void)
       {
    
        int a = 0, b = 1, c = gc();
        for (; !isdigit(c); c = gc()) b ^= (c == '-');
        for (; isdigit(c); c = gc()) a = a * 10 + c - '0';
        return b ? a : -a;
    }
}
using GTI::gti;

int n, m;
int a[N];

db sxnb(db b1){
      // Function name ： mathematics nb | b1 It's the first term of the arithmetic sequence , It is also the intercept of the linear regression line  
	db q = 0, p = 0;
	// Here's an explanation , This formula is based on the least square method （ The above explanation ） 
	// If you understand , Each a[i]-b1 Think of it as the difference between two terms of an arithmetic sequence , except i-1 It is a part of finding the average value of the difference of this arithmetic sequence  
	// Will all p/q The sum is the difference of this arithmetic sequence , Why don't you eliminate it here (i-1) and 2 Because the formula deduced according to the least square method is like this , If it is eliminated, some data will not pass （ It may be because of the accuracy problem ） 
	for(int i = 1; i <= n; i ++ ){
    
		p += 2.0 * (a[i] - b1) * (i - 1);
		q += 1.0 * (i - 1) * (i - 1);
	} 
	db d = p / (2 * q);
	db res = 0;
	for(int i = 1; i <= n; i ++ ){
    
		res += (a[i] - b1 - 1.0 * (i - 1) * d) * (a[i] - b1 - 1.0 * (i - 1) * d);
	}
	return res;
}

int main()
{
    
	int T;
	T = gti();
	while(T -- ){
    
		n = gti();
		for(int i = 1; i <= n; i ++ ){
    
			a[i] = gti();
		}
		
		db l = -2e10, r = 2e10;
		// The formula of arithmetic sequence a1+(n-1)*d Analogy to b+ k * x
		// So when two points are left a1 It is worth coming out and more than two points on the right a1 When the value of , It means that the sum of the straight line on the top is smaller than that of the straight line on the bottom （ Imagine a straight line with constant slope b Value moves up and down ）
		// So if sxnb(mid_l) >= sxnb(mid_r), Let's discard the left part between the two partitions , Is to let the straight line 
		//else Let the straight line move down 
		// Finally find the right position of the straight line , That is, the product of the difference is the smallest  
		while(r - l > 1e-5){
    
			db mid = r - l;  
			db mid_l = l + mid / 3, mid_r = r - mid / 3;  // Three points （ Reference dichotomy ） 
			if(sxnb(mid_l) >= sxnb(mid_r)) l = mid_l;
			else r = mid_r;
		}
		printf("%.20lf\n", sxnb(r));
	}
	return 0;
}

K Link with Bracket Sequence I

Dynamic programming , Time is too tight. There is a little thought on the court, but I didn't think of it , In the future, remember that the number of left parentheses is more than that of right parentheses when matching parentheses

remember f[i][j][k] The length is i, The successful matching part is k, There are more left parentheses than right parentheses j Number of alternatives

#include<bits/stdc++.h>

using namespace std;

const int N = 210, mod = 1e9 + 7;

int dp[N][N][N];  //f[i][j][k] The length is i, The successful matching part is k, There are more left parentheses than right parentheses j Number of alternatives 
int n, m;
char str[210];
int T;

void add(int& a, int b){
      // add & It can make a The value of the original address changes directly  
	a = (a + b) % mod;
}

int main()
{
    
	cin>>T;
	while(T -- ){
    
		scanf("%d%d%s", &n, &m, &str[1]);  // Read the string from the subscript 1 Start reading , Because the traversal starts from 1 To traverse the ,k We have to start from 0 Only at the beginning can we undertake the state transition  
		memset(dp, 0, sizeof(dp[0]) * (m + 1));
		
		dp[0][0][0] = 1;
		
		for(int i = 0; i < m; i ++ ){
      // Enumeration string length  
			for(int j = 0; j <= i; j ++ ){
      // Enumerate the number of left parentheses more than right parentheses  
				for(int k = 0; k <= i; k ++ ){
      // Enumerate the length of successful matching  
					if(j > 0){
      // To guarantee m String method , When the number of left parentheses is greater than the number of right parentheses , To match the right parenthesis  
						if(str[k + 1] == ')'){
      // The match is successful , Add one to the length of successful matching , Subtract one from the number of left parentheses  
							add(dp[i + 1][j - 1][k + 1], dp[i][j][k]);  
						}
						else{
      // The next thing to match is the left parenthesis , But it still matches the right parenthesis , No match succeeded , But this kind of quantity still needs to be counted  
							add(dp[i + 1][j - 1][k], dp[i][j][k]);
						} 
					}
					if(str[k + 1] == '('){
      // You can match the left parenthesis at any time , If the next one to match happens to be the left parenthesis  
						add(dp[i + 1][j + 1][k + 1], dp[i][j][k]); 
					}
					else add(dp[i + 1][j + 1][k], dp[i][j][k]);
				}
			}
		}
		cout<<dp[m][0][n]<<endl;
	}
	return 0;
} 

L Link with Level Editor I

dp[i][j] It means that i A world （i It's a scrolling presentation ） Arrival point j, The minimum number of worlds passed

#include<bits/stdc++.h>

using namespace std;

const int N = 1e4 + 10, INF = 0x3f3f3f3f;

int dp[2][N];  // Because the first i The first state only depends on i-1 state , So the first dimension can use the rolling array to accept the previous state  
int n, m;
int ans = INF;

int main()
{
    
	cin>>n>>m;
	for(int i = 2; i <= m; i ++ ) dp[0][i] = dp[1][i] = n + 1;  // initialization  
	
	for(int i = 1, t = 1; i <= n; i ++ , t ^= 1){
    
		//f[1][2]=min(f[0][2]+1, n+1)
		// The first one is equivalent to from f[0][2] The state shifts , So I will undertake 0 
		int cnt;
		cin>>cnt;
		for(int u =2; u <= m; u ++ ) dp[t][u] = min(dp[t^1][u] + 1, n + 1);  // Update the shortest number of steps by the same point in the previous world i Transferred  
		for(int j = 1; j <= cnt; j ++ ){
    
			int u, v;
			cin>>u>>v;
			dp[t][v] = min(dp[t][v], dp[t ^ 1][u] + 1);  //f[t^1][u]+1 It means that the last world arrived u The price of points 
		}
		ans = min(ans, dp[t][m]);  // The second dimension represents the point , The first dimension is used to record the world in a rolling manner 
	}
	if(ans > n) ans = -1;
	cout<<ans<<endl;
	return 0;
}