CF 943 (Div. 3) A~E

本文主要是介绍CF 943 (Div. 3) A~E，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

A Maximize?（模拟/枚举）
B Prefiquence(贪心/双指针)
C Assembly via Remainders（构造）
D Permutation Game （枚举/贪心）
E Cells Arrangement（构造）

A Maximize?（模拟/枚举）

题意：
给定 $x$ ，找一个 $y$ ( $\leq y \leq x$ )，使得 $g c d (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,6......n+n-2}$ ，能表示所有偶数距离，但不是最大数量，因此可以把(2,2)换成(1,2)，则集合是 ${0,1,3,4,5,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;
}