A Maximize?（模拟/枚举）

题意：
给定$x$，找一个$y$($1\le y\le x$)，使得$gcd(x,y)+y$尽量大。
思路1： 枚举$y$，找满足条件的最大值。
思路2： 输出x-1即可。
标程1：

#include <bits/stdc++.h>
using namespace std; 
int main() {
	int T; cin >> T;
	while (T--) {
		int x; cin >> x;
		int ans = 0, y = 0;
		for (int i = 1; i < x; i++) {
			if (__gcd(x, i) + i > ans) {
				ans = __gcd(x, i) + i;
				y = i;
			}
		}
		cout << y << "\n";
	}
	return 0;
}

标程2：

#include <bits/stdc++.h>
using namespace std; 
int main() {
	int T; cin >> T;
	while (T--) {
		int x; cin >> x;
		cout<<x-1<<"\n";
	}
}

B Prefiquence(贪心/双指针)

题意：给定字符串$a$ $b$, 要使$a$的前$k$项，恰好是$b$的子序列，请问$k$最大是多少？
思路： 用$j$遍历字符串$b$，只要$b_j$中跟$a_i$相等，则优先选择此$i$，$j$，同时$i++$看是否还存在相等的。
标程1：

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

int main() {
	int T; cin >> T;
	while (T--) {
		int n, m, ans = 0; 
		cin >> n >> m;
		string a, b;
		cin >> a >> b;
		int i = 0, j = 0;//a字符串 b字符串 
		for (; i < n && j < m; j++ ) {
			if(b[j] == a[i]) {
				i++;
			}
		}
		cout << i << "\n";
	}
	return 0;
}

C Assembly via Remainders（构造）

题意：给定数组$x_2,x_3...x_n$，构造一个数组$a_1,a_2...a_n$，使得$a_i$ % $a_{i-1}=x_i$。
思路： $x_i$范围是0~500,因为要取模运算，所以$a_i>500$，我们把第1项设为501，剩下的可倒推，余数$x_i$+模$a_{i-1}$ = $a_i$。
标程1：

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

int main() {
	int T; cin >> T;
	while (T--) {
		int n, last = 501; 
		cin >> n ;
		cout << 501 << " ";
		for(int i = 2; i <= n; i++){
			int t; cin >> t;
			last += t;
			cout << last << " ";
		}
		cout << '\n';
	}
	return 0;
}

D Permutation Game （枚举/贪心）

题意：给定排列$p$，数组$a$，和两个人的初始位置，玩k轮游戏，问两人胜负情况，假设二人足够聪明。每轮游戏定义如下：玩家在位置$x$，获得$a_x$分，然后选择留在原地或者跳到$p_z$位置。
思路： 枚举所有情况，计算最大的分，比较二人分数。 因为$p$是一个排列，可以跳一圈回来，也就是最终会在一个好位置上一直原地跳，所以枚举这个好位置即可，也就是可能在$p_b$位置跳$k$次，也可能在$p_b$位置跳1次再到下一个位置跳$k-1$次…
标程：

#include <bits/stdc++.h>
using namespace std;
long long p[200005], a[200005];
int main(){
	int q;
	cin >> q;
	while(q--) {
		int n, k, pb, ps;
		cin >> n >> k >> pb >> ps;
		for(int i = 1; i <= n;i ++) cin >> p[i];
		for(int i = 1; i <= n;i ++) cin >> a[i];
		long long zq1 = 1, i1 = pb, max1 = a[pb] * k, sum1 = a[pb];
		i1 = p[i1];
		while(i1 != pb&& k > zq1){			
			max1 = max(max1, sum1 + (k-zq1)*a[i1]);
			zq1++, sum1 +=  a[i1]; 
			i1 = p[i1];
		} 
		long long zq2 = 1, i2 = ps, max2 = a[ps] * k, sum2 = a[ps];
		i2 = p[i2];
		while(i2 != ps && k > zq2){	
//			cout << i2 << '*';		
			max2 = max(max2, sum2 + (k-zq2)*a[i2]);
			zq2++, sum2 +=  a[i2]; 
			i2 = p[i2];
		} 
//		cout << max1 << " " << max2 << '\n'	 ;
		if(max1 > max2) cout << "Bodya\n";
		if(max1 < max2) cout << "Sasha\n";
		if(max1 == max2) cout << "Draw\n";
		
	}
	return 0;
} 

E Cells Arrangement（构造）

题意：给定$n\times n$的矩阵，寻找$n$个点，使得任意两点曼哈顿距离构成的非重复集合数量最大。
思路： 按照对角线选点$(1,1),(2,2)....,(n,n)$，则任意两点构成的距离集合$0,2,4,\mathrm{6......}n+n-2$，能表示所有偶数距离，但不是最大数量，因此可以把(2,2)换成(1,2)，则集合是$0,1,3,4,5,\mathrm{6.....}$，
标程1：

#include <bits/stdc++.h>
using namespace std; 
int main() {
	int T; cin >> T;
	while (T--) {
		int x; cin >> x;
		int ans = 0, y = 0;
		for (int i = 1; i < x; i++) {
			if (__gcd(x, i) + i > ans) {
				ans = __gcd(x, i) + i;
				y = i;
			}
		}
		cout << y << "\n";
	}
	return 0;
}