题目链接

A

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N = 1e4 + 10;int main()
{int T;cin >> T;while(T--){int mx = 0;int a[3];cin >> a[0] >> a[1] >> a[2];mx = max(max(a[0], a[1]), a[2]);int cnt = 0;for(int i = 0; i < 3; i++) if(a[i] == mx) cnt++;for(int i = 0; i < 3; i++){printf("%d ", a[i] == mx && cnt == 1 ? 0 : mx + 1 - a[i]);}puts("");}return 0;
}

B

这题需要美剧后面的两位，看看是否可以%25==0整除，然后前面的数组随意

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long LL;
const int N = 1e4 + 10, INF = 0x3f3f3f3f;
LL k, n;
int nums[29], cnt, mx;//len已经选择的数字
int get(int arr[])
{int res = 0;int i = cnt - 1, j = 1;while(i >= 0 && j >= 0){// printf("arr[j]=%d ", arr[j]);while(i >= 0 && nums[i] != arr[j]) i--, res++; // printf("del=%d ", nums[i + 1]);// puts(""); if(i >= 0 && nums[i] == arr[j]){i--, j--;// printf("i=%d,j=%d\n", i, j);}}if(j >= 0) return res = INF;// printf("n=%lld, %d%d, %d\n", k, arr[0],arr[1], res);return res;
}int main()
{
// #ifdef ONLINE_JUDGE
// #else 
//     freopen("in.txt", "r", stdin);
// #endifint T;cin >> T;while(T--){cin >> n;k = n;cnt = 0;while(n) nums[cnt++] = n % 10, n /= 10;reverse(nums, nums + cnt);// for(int i = 0; i < cnt; i++) printf("%d ", nums[i]);// puts("");int res = INF;int arr[2] = {0, 0};res = min(res, get(arr));arr[0] = 2, arr[1] = 5;res = min(res, get(arr));arr[0] = 5, arr[1] = 0;res = min(res, get(arr));arr[0] = 7, arr[1] = 5;res = min(res, get(arr));printf("%d\n", res);}return 0;
}

C

二分即可

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 4e5 + 10;
typedef long long LL;int n, k;
int a[N];bool check(int mid)
{LL sum = 0;for(int i = mid; i < k; i++){if(sum >= a[i]) return false;sum += n - a[i];}return true;
}
int main()
{
// #ifdef ONLINE_JUDGE
// #else 
//     freopen("D.txt", "r", stdin);
// #endifint T;cin >> T;while (T--){cin >> n >> k;for(int i = 0; i < k; i++) cin >> a[i];sort(a, a + k);int l = 0, r = k - 1;while(l < r){int mid = l + r >> 1;if(check(mid)) r = mid;else l = mid + 1;}cout << k - l << endl;}return 0;
}

D1

如果不是全部相等，则求一个最大公约数就可以了

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
typedef long long LL;
const int N = 4e5 + 10, M = N + N;
int n;
int a[N];
int gcd(int a, int b)
{return !b ? a : gcd(b, a % b);
}
int main()
{
// #ifdef ONLINE_JUDGE
// #else 
//     freopen("G.txt", "r", stdin);
// #endifint T;cin >> T;while(T--){scanf("%d", &n);for(int i = 0; i < n; i++)scanf("%d", &a[i]);sort(a, a + n);n = unique(a, a + n) - a;if(n == 1) puts("-1");else {int mx = a[1] - a[0];for(int i = 2; i < n; i++)mx = gcd(mx, a[i] - a[i - 1]);cout << mx << endl;}}return 0;
}

D2

如果都能变到某一个数，则必定某个差值的约数d1出现的次数>=n/2

#include <iostream>
#include <cstring>
#include <map>
#include <unordered_map>
using namespace std;
const int N = 100;
typedef pair<int,int> PII;int n;
int a[N];
PII p[N];map<int,int> S;
unordered_map<int,int> cnt;
void get(int x, int k)
{for(int i = 1; i * i <= x; i++){if(x % i == 0) {cnt[i] += k;if(x / i != i) cnt[x / i] += k;}}
}
int main()
{
#ifdef ONLINE_JUDGE
#else freopen("D.txt", "r", stdin);
#endifint T;cin >> T;while (T--){S.clear();cin >> n;int mx = 0;for(int i = 0; i < n; i++) cin >> a[i], mx = max(mx, ++S[a[i]]);if(mx >= n / 2) {puts("-1");continue;} int len = 0;for(auto&[k, v]: S) p[len++] = {k, v};int ans = 0;for(int i = 0; i < len; i++){cnt.clear();for(int j = i + 1; j < len; j++){get(p[j].first - p[i].first, p[j].second);}for(auto&[k, v]: cnt){if(v + p[i].second >= n / 2)ans = max(ans, k);}}cout << ans << endl;   }return 0;
}

E

从度数为1的点开始bfs，简单模拟一下就可以

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
typedef long long LL;
const int N = 4e5 + 10, M = N + N;
int n, k;
int h[N], e[M], ne[M], idx;
int d[N], q[N], p[N];
bool st[N];void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}int main()
{
// #ifdef ONLINE_JUDGE
// #else 
//     freopen("G.txt", "r", stdin);
// #endifint T;cin >> T;while (T--){cin >> n >> k;idx = 0;if(n == 1) {puts("0");continue;}memset(h, -1, (n + 1) * 4);memset(d, 0, (n + 1) * 4);for(int i = 0; i < n - 1; i ++){int a, b;cin >> a >> b;add(a, b), add(b, a);d[b]++, d[a]++;}int hh = 0, tt = -1;int tot = 0;for(int i = 1; i <= n; i++) if(d[i] == 1) q[++tt] = i;while(k && tot < n) {  int cnt = 0;while(hh <= tt){//删除当前点int t = q[hh++];tot++;for(int i = h[t]; ~i; i = ne[i]){int j = e[i];if(--d[j] == 1) p[cnt++] = j;}}hh = 0, tt = -1;for(int i = 0; i < cnt; i++) q[++tt] = p[i];k--;}printf("%d\n", n - tot);}return 0;
}

F

f[i][j][a][b]表示，考虑了前i位，选了j位红色的数字，且红色数字modA=a，mod B = b的方案集合
属性：是否可以到达这个状态，true表示可以，false表示不行
状态转移
第i+1位红色：f[i][j][a][b] -> f[i + 1][j + 1][(a * 10 + x) % A][b]
黑色: f[i][j][a][b] -> f[i + 1][j][a][(b * 10 + x) % b]
刚开始的状态是f[0][0][0][0] = true
要输出方案，所以记录每个状态由哪几个状态转移而来, 由状态转移可以发现，后一个状态只需要记录前一个的余数，以及前一个被染成啥颜色即可

这里提供两种不同的写法，一种是倒推，一种是开一个数组记录上一个状态

记录上一个状态

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;
const int N = 45;bool f[N][N][N][N];
pair<bool, int> pre[N][N][N][N];
int n, A, B;
char s[N];
int main()
{
#ifdef ONLINE_JUDGE
#else freopen("in.txt", "r", stdin);
#endifint T;cin >> T;while(T--){cin >> n >> A >> B >> s;for(int i = 0; i <= n; i++)for(int j = 0; j <= n; j++)for(int a = 0; a < A; a++)for(int b = 0; b < B; b++) f[i][j][a][b] = false;f[0][0][0][0] = true;for(int i = 0; i < n; i++)for(int j = 0; j <= i; j++)for(int a = 0; a < A; a++)for(int b = 0; b < B; b++)if(f[i][j][a][b]){int x = s[i] - '0';f[i + 1][j + 1][(a * 10 + x) % A][b] = true;pre[i + 1][j + 1][(a * 10 + x) % A][b] = {true, a};f[i + 1][j][a][(b * 10 + x) % B] = true;pre[i + 1][j][a][(b * 10 + x) % B] = {false, b};}int red_cnt = 50, d = 50;for(int i = 1; i < n; i++){int b = n - i;if(f[n][i][0][0] && abs(i - b) < d) red_cnt = i, d = abs(i - b);}if(red_cnt == 50) puts("-1");else {string ans = "";int x = 0, y = 0;for(int i = n; i; i--){auto t = pre[i][red_cnt][x][y];if(t.first) {ans.push_back('R');red_cnt--;x = t.second;}else {ans.push_back('B');y = t.second;}}reverse(ans.begin(), ans.end());cout << ans << endl;}}return 0;
}

倒推

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;
const int N = 45;
bool f[N][N][N][N];
int n, A, B;
char s[N];
string ans;void get_pre(int n, int& cnt, int& x, int& y)
{for(int j = 0; j <= cnt; j++)for(int a = 0; a < A; a++)for(int b = 0; b < B; b++){int v = s[n] - '0';if((a * 10 + v) % A == x && b == y && j + 1 == cnt && f[n][j][a][b] == f[n + 1][cnt][x][y]){ans.push_back('R');cnt--;x = a;return;}else if((b * 10 + v) % B == y && a == x && j == cnt && f[n][j][a][b] == f[n + 1][cnt][x][y]){ans.push_back('B');y = b;return;}}
}
int main()
{
#ifdef ONLINE_JUDGE
#else freopen("in.txt", "r", stdin);
#endifint T;cin >> T;while(T--){cin >> n >> A >> B >> s;for(int i = 0; i <= n; i++)for(int j = 0; j <= n; j++)for(int a = 0; a < A; a++)for(int b = 0; b < B; b++) f[i][j][a][b] = false;f[0][0][0][0] = true;for(int i = 0; i < n; i++)for(int j = 0; j <= i; j++)for(int a = 0; a < A; a++)for(int b = 0; b < B; b++)if(f[i][j][a][b]){int x = s[i] - '0';f[i + 1][j + 1][(a * 10 + x) % A][b] = true;f[i + 1][j][a][(b * 10 + x) % B] = true;}int red_cnt = 50, d = 50;for(int i = 1; i < n; i++){int b = n - i;if(f[n][i][0][0] && abs(i - b) < d) red_cnt = i, d = abs(i - b);}if(red_cnt == 50) puts("-1");else {ans = "";int x = 0, y = 0;for(int i = n - 1; ~i; i--)get_pre(i, red_cnt, x, y);reverse(ans.begin(), ans.end());cout << ans << endl;}}return 0;
}