补题链接：https://codeforces.com/gym/104337
原文链接：https://www.eriktse.com/algorithm/1136.html
M. Different Billing
签到题，写几个柿子而后枚举B或C即可。
#include <bits/stdc++.h>#define int long longusing namespace std;signed main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int x, y;cin >> x >> y; for(int c = 0;c <= x; ++ c) { int b = (y - 2500 * c) / 1000; if(b < 0 || 1000 * b + 2500 * c != y)continue; int a = x - b - c; if(a >= 0) { cout << a << ' ' << b << ' ' << c << '\n'; return 0; } } cout << -1 << '\n'; return 0;}C. Darkness I
这题是对Minecraft中有限水的拓展过程为背景的一道思维题。
先考虑一下n, m均为奇数的状况：
而后从这种状况开始，减少一列，或者减少一行，都须要多加一个黑棋子，如果同时减少一行一列，那也是只须要减少一个棋子，减少到右下角的地位即可。
所以咱们依照这种构造方法输入答案即可。
#include <bits/stdc++.h>#define int long longusing namespace std; signed main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n, m;cin >> n >> m; int res = (n + 1) / 2 + (m + 1) / 2 - 1; if(n % 2 == 0 || m % 2 == 0)res ++; cout << res << '\n'; return 0;}J.Expansion
这题能够转化为以下题意：
一开始身上资源为0，从1号点走到n号点，每个点上有一些资源（可能为正数），每秒钟能够抉择走或者不走，且每秒会失去以后点上的资源（此时的资源曾经做了前缀和），为了保障每时每刻身上的资源都不为正数，请问从1走到n所需的最小工夫。
咱们模仿一下这个过程，如果到了某个点发现如果在以后点停留1秒会使得资源变为正数，就阐明“我应该在右边的某个正数点多停留一会儿”，而为了使得停留时间起码，我会抉择最大的点进行停留。
留神一些特判，题意须要保障最初在n始终停留都不会使得资源为正数，所以prefix[n]须要大于等于零，还有为了使得能够走到n，须要保障第一个非0的数为负数。
#include <bits/stdc++.h>#define int long longusing namespace std;const int N = 1e6 + 9, p = 998244353;int a[N], prefix[N];signed main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n;cin >> n; for(int i = 1;i <= n; ++ i)cin >> a[i]; for(int i = 1;i <= n; ++ i)prefix[i] = prefix[i - 1] + a[i]; if(prefix[n] < 0) { cout << -1 << '\n'; return 0; } //遇到的第一个是正数 for(int i = 1;i <= n; ++ i) { if(prefix[i] != 0) { if(prefix[i] < 0) { cout << -1 << '\n'; return 0; } break; } } int ans = 0, res = 0, mx = 0; //后面一步步推动 for(int i = 1;i <= n; ++ i) { mx = max(mx, prefix[i]); res += prefix[i]; ans ++;//走一秒 if(res < 0)//阐明走快了，应该在后面多停留一段时间的 { //补几秒钟 int ti = (-res + mx - 1) / mx; ans += ti; res += ti * mx; } } cout << ans << '\n'; return 0;}H.Binary Craziness
赛时卡这道题了，始终在想拆位的做法（造成惯性思维了......蹩脚）。
其实这题咱们能够这样想，最多m条边，也就是所有点的出度之和肯定是2m，而后咱们最多n个点，也就是说出度的品种数不会超过 $\sqrt{2m}$ 种。因为如果要使得品种数最多，那么就是每一种都只有一个，且从小到大，出度数组排序后（长度为t）将会是1, 2, 3, 4, 5, ...其和为$\frac{t(t + 1)}{2} \le 2m$，所以长度t不会很大。
咱们就能够依据这个原理做一个桶记录一下某个数字呈现的次数，而后间接双重循环暴力写！
#include <bits/stdc++.h>#define int long longusing namespace std;const int N = 1e6 + 9, p = 998244353;int cnt[2 * N], a[N];int f(int x, int y){ return (x ^ y) * (x | y) * (x & y);}signed main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n, m;cin >> n >> m; for(int i = 1;i <= m; ++ i) { int x, y;cin >> x >> y; a[x] ++, a[y] ++; } for(int i = 1;i <= n; ++ i)cnt[a[i]] ++; vector<int> v; for(int i = 1;i <= 2 * m; ++ i)if(cnt[i])v.push_back(i); int res = 0; for(int i = 0;i < v.size(); ++ i) { for(int j = i + 1;j < v.size(); ++ j) { res = (res + cnt[v[i]] * cnt[v[j]] % p * f(v[i], v[j]) % p) % p; } } cout << res << '\n'; return 0;}F.Inverse Manacher
这题甚至不须要会马拉车。
题目给定一个“回文半径”的数组，要你还原还原出一种可能的字符串（仅蕴含ab）。数据保障至多存在一种解。
只须要了解回文半径的含意即可。
当咱们走到i时，如果a[i] > 1，阐明咱们要把i右边的一部分堆成到左边去，为了优化复杂度，咱们能够用双指针，r示意此时b数组（也就是答案数组）的大小，也就是咱们更新到的右端，当r < i + a[i] - 1时，咱们就拓展失去b[r]，如果此时i > r，再依据一些状况来确定b[i]即可（交替的取a, b）。
留神数组开大一点，马拉车个别是两倍空间。
#include <bits/stdc++.h>#define int long longusing namespace std;const int N = 3e6 + 9;int a[N];char b[N];signed main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n;cin >> n; for(int i = 0;i <= 2 * n + 1; ++ i)cin >> a[i]; char ch = 'a'; for(int i = 0, r = 0;i <= 2 * n + 1; ++ i) { while(i + a[i] - 1 > r)++ r, b[r] = b[2 * i - r]; if(i == 0)b[i] = '&'; else if(i & 1)b[i] = '|'; else if(b[i] == 0)b[i] = ch, ch = (ch == 'a' ? 'b' : 'a'); } for(int i = 2;i <= 2 * n + 1;i += 2)cout << b[i]; return 0;}K.Dice Game
这题次要难在剖析出n个事件互相独立。
当x确定时，对于n集体当中的某一个人，他胜利的概率是$p = \frac{m-x}{m-1}$，这个有两种了解，第一个理性的了解就是，当投出y = x是没有意义的，所以无效的y一共是m个，其中m - x个是能够赢的。
数学的了解是，这个人可能在第一次赢，也可能第二次赢，也可能第三次赢...，设平局概率为t，胜利概率为q。
$$ p= q + t * q + t^{2} * q + .... + t^{inf} * q $$
其中$t=\frac{1}{m}$, $q = \frac{m-x}{m}$。
依据等比数列求和咱们能够晓得：
$$p = \frac{m-x}{m-1}$$
而后对于某个x，一共有n集体，那么答案就是$p^n = (\frac{m-x}{m-1}) ^ n$。
#include <bits/stdc++.h>#define int long longusing namespace std;const int N = 1e6 + 9, p = 998244353;int qmi(int a, int b){ int res = 1; while(b) { if(b & 1)res = res * a % p; a = a * a % p, b >>= 1; } return res;}int inv(int x){return qmi(x, p - 2);}signed main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n, m;cin >> n >> m; int res = 1; for(int i = 1;i <= m; ++ i) { cout << qmi((m - i) * inv(m - 1) % p, n) << ' '; } return 0;}I.Step
已知$2t | k(k+1)$，求最小的$k$，其中$t=lcm(p_1,p_2...,p_n)$。
无妨设$2t=a*b$，且$a|k,b|(k+1)$，且$ax=k,by=(k+1)$，那么咱们能够失去:
$$ax+1=by$$
转换一下失去：
$$a(-x)+by=1$$
枚举a，能够算出b，而后exgcd搞出最小的x，即失去了k=ax答案。
当初问题是如何枚举a，咱们看这个exgcd式子能够发现咱们须要保障gcd(a, b) = 1，且有2t = a * b，所以咱们能够对2t进行惟一合成，而后选取不同质因子品种调配给a和b。
调配计划能够通过二进制间接做。
#include <bits/stdc++.h>#define int long longusing namespace std;const int N = 1e6 + 9, inf = 8e18;int p[N];int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);}int lcm(int a, int b){return a / gcd(a, b) * b;}map<int, int> mp;vector<int> v;void func(int x){ for(int i = 2;i <= x / i; ++ i) { if(x % i)continue; v.push_back(i); mp[i] = 1; while(x % i == 0)mp[i] *= i, x /= i; } if(x > 1)v.push_back(x), mp[x] = x;}int exgcd(int a, int b, int &x, int &y){ if(!b)return x = 1, y = 0, a; int d = exgcd(b, a % b, y , x); y -= a / b * x; return d;}signed main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n;cin >> n; for(int i = 1;i <= n; ++ i)cin >> p[i]; int lc = p[1]; for(int i = 2;i <= n; ++ i)lc = lcm(lc, p[i]); //对2 * lc进行质因数分解 func(2 * lc); int res = inf; for(int i = 0;i < (1ll << v.size()); ++ i) { //依据i失去a int a = 1; for(int j = 0;j < v.size(); ++ j) if(i >> j & 1)a = a * mp[v[j]]; int b = 2 * lc / a; int x, y, d = exgcd(a, b, x, y); x = -x; x = (x % (b / d) + (b / d)) % (b / d); if(a * x)res = min(res, x * a); //cout << "a = " << a << ' ' << "ax = " << a * x << '\n'; } cout << res << '\n'; return 0;}