Commendation for the seniors

"Mock Trial" Summer Intensive CSP Improvement Mock 17 (8.10)

Didn't play well in the tournament, but liked the questions the seniors came up with this time.

Summarize the writing ahead:

Signing questions is to pull off the ranking, signing questions are generally not difficult, depends on want not to think of that step, to determine which is a signing question after setting aside time to play the right solution;
Each question thought for too long no positive solution idea rush to hit on the violent jump, leaving time for the check-in questions, check-in questions hit and then go to consider the optimization or positive solution of other questions;
Note the way the 2D backpack is written
T4 Ideas for more review, DP due to the excessive number of dimensions (but the answer is very small), so take out one dimension and the answer swap, i.e., the answer is made one-dimensional, the DP array maintains the original one-dimensional.

A. A Primer on Symbolization Methods 55pts

Original: ABC 081D

Because of this question was pulled away from the score, the construction of the question, began to think of 40min, did not think of the correct solution, first jumped. Later, I came back to the time is not much, and then think of 10min, too anxious (at that time only played the T2, T4 violence), did not think again, directly played the\(55pts\) Violence slipped out.

Partially divided:

\(5pts\): Sample 1;
\(25pts\): Maintains a maximum value when all numbers are positive, from 1 to\(n\) Iterate so that all numbers less than the previous number are added to the maximum and the maximum is updated;
\(25pts\)： \(|a_i| \le 1\) If there is no 1, it will be set to 0, and if there is 1, it will be set to 1.

Positive solution:

The second part of the partition leads to a positive solution. Obviously, when the sequence of numbers are all non-negative or all non-positive each number requires at most 1 operation to satisfy the condition, so consider changing all numbers to the same number.

Maintaining a maximum value\(max\) and the minimum value\(min\)(Remember to update after each operation):

(coll.) fail (a student)\(max > -min\) When adding all negative numbers to\(max\) It is possible to make all numbers non-negative; after that it is sufficient to follow the second partial division;
Otherwise, add all positive numbers to\(min\) (which is definitely negative) can make all books non-positive, after which the number of books from the\(n\) To 1 let all numbers greater than the next add the minimum value.

code：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;

const int N = 2e5 + 10;

int n, axid, inid, l[N], r[N];
ll a[N], amx, imn = 2e9;

void output(int e){
    cout<<e<<"\n";
    for(int i=1; i<=e; i++){
        cout<<l[i]<<" "<<r[i]<<"\n";
    }
}

int main(){
    // freopen("", "r", stdin); freopen("", "w", stdout);
    ios::sync_with_stdio(false), (0), (0);

    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>a[i];
        if(amx < a[i]){
            amx = a[i], axid = i;
        }
        if(imn > a[i]){
            imn = a[i], inid = i;
        }
    }

    int cnt = 0;
    if(amx > -imn){
        for(int i=1; i<=n; i++){
            if(a[i] >= 0) continue;
            a[i] += amx, l[++cnt] = axid, r[cnt] = i;
        }

        for(int i=1; i<=n; i++){
            if(a[i] >= a[i-1]) continue;
            a[i] += amx, l[++cnt] = axid, r[cnt] = i;
            if(amx < a[i]) amx = a[i], axid = i;
        }

        output(cnt);
    }
    else{
        for(int i=1; i<=n; i++){
            if(a[i] <= 0) continue;
            a[i] += imn;
            l[++cnt] = inid, r[cnt] = i;
        }

        a[n+1] = 2e9;
        for(int i=n; i>=1; i--){
            if(a[i] <= a[i+1]) continue;
            a[i] += imn, l[++cnt] = inid, r[cnt] = i;
            if(imn > a[i]) imn = a[i], inid = i;
        }

        output(cnt);
    }

    return 0;
}

B. Unlabeled Sequence Constructs 50pts

~~I just learned the matrix a week ago.~~I'm not very proficient in some properties of matrices and stuff, so I didn't come up with a question that wasn't that hard to think of, but it's excusable, at least I didn't get hung up on the violence score, unlike the indisputable T4 (well actually I was too good at it).

Partially divided:

\(50pts\) matrix multiplication\(n^3\) Violence.

Positive solution:

We know that for the matrix\(A、B、C、ra\)if\(A\times B=C\)So.\(ra\times A\times B=ra\times C\); and\(1\times n\) The matrix of the\(n\times n\) The matrix multiplication of\(1\times n\) of the matrix.

So we construct a\(1\times n\) matrices\(ra\), so that the time complexity of matrix multiplication becomes\(O(1\times n^2)\)I can do it.

code：

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int N = 3005;
const int mod = 998244353;

int T, n, a[N][N], b[N][N], c[N][N];ll ra[N], temp[N];
ll ans1[N], ans2[N];

unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 rand_num(seed);
uniform_int_distribution<long long> dist(1, 998244353);

int main(){
	// freopen("", "r", stdin); freopen("", "w", stdout);
    ios::sync_with_stdio(false), (0), (0);

    cin>>T;

    while(T--)
    {
    	cin>>n;
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				cin>>a[i][j];

		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				cin>>b[i][j];

		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				cin>>c[i][j];

		bool f = 1;

		for(int i=1; i<=n; i++) ra[i] = dist(rand_num);

		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				temp[i] = (temp[i] + ra[j] * a[j][i] % mod) % mod;

		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				ans1[i] = (ans1[i] + temp[j] * b[j][i] % mod) % mod;

		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				ans2[i] = (ans2[i] + ra[j] * c[j][i] % mod) % mod;

		for(int i=1; i<=n; i++){
			if(ans1[i] != ans2[i]){f = false; break;}
		}

		for(int i=1; i<=n; i++) temp[i] = ans1[i] = ans2[i] = 0;
		

		cout<< ( f ? "Yes\n" : "No\n" ) ;

    }
	

	return 0;
}

C. Unlabeled Multiset Constructs 5 pts

It hasn't been changed yet.

D. Constructions with limitations 20 pts

Original: ABC 364E

match\(5+15+20=40 pts\) Violence, and as a result, the 2D backpack also hit the pot, leading to a score\(5+15+0=20pts\)。

Partially divided:

\(5 pts\): Sample 1;
\(15pts\): For\(n=8\) The data, just explode the search;
\(20pts\): For\(v\le 100\) The data for the 2D backpack DP.

Code of Violence (40pts)

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int N = 85;

int n, A, B, a[N], b[N];

namespace case3
{	
	int f[85][605][605];
	int main(){
		
		for(int i=1; i<=n; i++)	{
			for(int j=0; j<=A; j++){
				for(int k=0; k<=B; k++){
					f[i][j][k] = f[i-1][j][k];
				}
			}
			for(int j=a[i]; j<=A; j++){
				for(int k=b[i]; k<=B; k++){
					f[i][j][k] = max({f[i][j][k], f[i-1][j-a[i]][k-b[i]]+1, f[i-1][j][k]});
				}
			}
		}
		cout<<( (f[n][A][B]==n) ? n : (f[n][A][B]+1) );

		return 0;
	}
	
}

bool vis[N];
int dfs(int x, int cnt, int Aa, int Bb){
	if(Aa > A or Bb > B) return cnt;
	if(cnt == n) return n;

	int ans = 0;
	for(int i=1; i<=n; i++){
		if(vis[i]) continue;
		vis[i] = true;
		ans = max(ans, dfs(i, cnt+1, Aa+a[i], Bb+b[i]));
		vis[i] = false;
	}
	return ans;
}

int main(){
	// freopen("", "r", stdin); freopen("", "w", stdout);
    ios::sync_with_stdio(false), (0), (0);

    cin>>n>>A>>B; int v = max(A, B);
    for(int i=1; i<=n; i++){
    	cin>>a[i]>>b[i];
    	v = max({v, a[i], b[i]});
    }

    if(n < 12){
    	cout<<dfs(0, 0, 0, 0);
    	return 0;
    }	
	if(v <= 600){
		return case3::main();
	}

	return 0;
}

Note the 2D backpack DP writing:

Since there will be cases where one of the two conditions of a 2D backpack is satisfied and the other is not, look at the code.

for(int i=1; i<=n; i++) {
for(int j=0; j<=A; j++){ //note the cyclic range of j and k at this level
for(int k=0; k<=B; k++){
f[i][j][k] = f[i-1][j][k];
}
}
for(int j=a[i]; j<=A; j++){
for(int k=b[i]; k<=B; k++){
f[i][j][k] = max({f[i][j][k], f[i-1][j-a[i]][k-b[i]]+1, f[i-1][j][k]});
}
}
}

Positive solution:

Since the answers are small (up to 80) and the DP array is open too large, consider swapping the position of one dimension of our 2D backpack DP array with the answers.

found\(f_{i,j,k}\) ahead\(i\) Choose from a list of games\(j\) The sum of the picture qualities is\(k\) The sum of the smallest unplayable degrees at time, what to do next is obvious.

DP Code for the state transfer section:

memset(f, 0x3f, sizeof f);
int ans = 0;
for(int i=0; i<=n; i++) f[i][0][0] = 0;
for(int i=1; i<=n; i++){
    for(int j=1; j<=i; j++){
        for(int k=A; k>=0; k--){
            f[i][j][k] = f[i-1][j][k];
            // if(f[i][j][k] <= B) ans = max(ans, j);
        }
        

        for(int k=A; k>=a[i]; k--){
            f[i][j][k] = min(f[i-1][j][k], f[i-1][j-1][k-a[i]]+b[i]);
            if(f[i][j][k] <= B) ans = max(ans, j);
        }

    }
}

code：

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int N = 85;

int n, A, B, a[N], b[N];
int f[81][81][10001];

int main(){
	// freopen("", "r", stdin); freopen("", "w", stdout);
    ios::sync_with_stdio(false), (0), (0);

    cin>>n>>A>>B; 
    for(int i=1; i<=n; i++){
    	cin>>a[i]>>b[i];
    }

    memset(f, 0x3f, sizeof f);
    int ans = 0;
    for(int i=0; i<=n; i++) f[i][0][0] = 0;
    for(int i=1; i<=n; i++){
    	for(int j=1; j<=i; j++){
			for(int k=A; k>=0; k--){
				f[i][j][k] = f[i-1][j][k];
				// if(f[i][j][k] <= B) ans = max(ans, j);
			}
    		

    		for(int k=A; k>=a[i]; k--){
    			f[i][j][k] = min(f[i-1][j][k], f[i-1][j-1][k-a[i]]+b[i]);
    			if(f[i][j][k] <= B) ans = max(ans, j);
    		}

    	}
    }

    cout<<((ans == n) ? n : ans + 1);


	return 0;
}