2021 百度之星初赛第二场，记一下这几题。
A. 签到
题意
每次把 同时变成 。求做完 次后的两个数，对 取模。
思路
连续变换两次就变成 。先用快速幂算出 ，如果 是奇数，再做一次变换就行。减法记得补一下模数。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mo = 998244353;
int T, a, b, k;
int fpow(int y, int x) {
int res = 1; for(; x; x >>= 1, y = 1ll * y * y % mo) if(x & 1) res = 1ll * res * y % mo; return res;
}
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%d%d", &a, &b, &k);
int tmp = k / 2;
int f2 = fpow(2, tmp);
// cout << f2 << endl;
int A = 1ll * a * f2 % mo, B = 1ll * b * f2 % mo;
if(k & 1) printf("%d %d\n", (A + B) % mo, (A - B + mo) % mo);
else printf("%d %d\n", A, B);
}
return 0;
}B. 随机题意
题意
给定 个整数，每个数都可以加上一个 内的整数。求修改后最多能有多少个不同的数。
思路
从小到大处理。一个数能放的位置是 ，尽量占最靠左的空位置，给后面的数留空间。相同的数一起统计，直接算这一段还能塞下几个，不用一个个枚举。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 17;
const int oo = 0x3f3f3f3f;
int T, n, k, a[maxn], L, ans;
map<int, int> mp;
int main() {
scanf("%d", &T);
while(T--) {
L = -oo;
ans = 0;
mp.clear();
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i++) mp[a[i]]++;
for(auto &it : mp) {
int d = it.first, cnt = it.second;
int l = d - k, r = d + k;
l = max(l, L);
r = min(r, l + cnt - 1);
ans += max(0, r - l + 1);
L = max(L, r + 1);
}
printf("%d\n", ans);
}
return 0;
}C. 魔怔
题意
完全无向图的边有黑白两种颜色。从 出发，每经过一条边就把它的颜色翻转，要求最后所有边都变黑。求最少走多少条边，无解输出 。
思路
白边要走奇数次，黑边要走偶数次，所以先看白边图的欧拉路条件：奇度点只能有零个或两个；有两个时，起点必须是其中一个。
白边先各算一次。不同的白边连通块之间需要往返连接，每多接一个块加两步；起点如果不在任何白边块里，还要额外往返一次。用并查集数一下块数就行。
代码
/*
2
5 1
0
11
110
1100
4 1
0
00
000
2
5 1
1
11
110
1100
4 1
0
00
000
*/
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 17;
int T, n, s;
int du[maxn];
int ans, fa[maxn], vis[maxn];
char str[maxn];
int getf(int x) {
return fa[x] == x ? x : fa[x] = getf(fa[x]);
}
void merge(int x, int y) {
int fx = getf(x), fy = getf(y);
if(fx != fy) fa[fx] = fy;
}
int main() {
scanf("%d", &T);
while(T--) {
memset(du, 0, sizeof(du));
memset(vis, 0, sizeof(vis));
ans = 0;
int flg1 = 1, flg2 = 1;
scanf("%d%d", &n, &s);
for(int i = 1; i <= n; i++) fa[i] = i;
for(int i = 2; i <= n; i++) {
scanf("%s", str + 1);
for(int j = 1; j < i; j++) {
if(str[j] == '0') {
ans++;
merge(i, j);
du[i]++, du[j]++;
}
else du[i] += 2, du[j] += 2;
}
}
ans -= 2;
for(int i = 1; i <= n; i++) {
if(getf(i) != i) {
if(!vis[getf(i)]) ans += 2;
vis[getf(i)] = 1;
}
}
if(!vis[getf(s)]) ans += 2;
for(int i = 1; i <= n; i++) if(du[i] & 1) flg1 = 0;
for(int i = 1; i <= n; i++) {
if(du[i] & 1 && i != s) {
if(flg2 == 1) flg2++;
else if(flg2 == 2) flg2 = 0;
}
}
if(!(du[s] & 1)) flg2 = 0;
if(flg1 || flg2) {
printf("%d\n", ans);
}
else printf("-1\n");
}
return 0;
}D. 净化
题意
初始数值为 ，每轮依次加上 ，每次加完如果小于 就变成 。求最早在哪一轮能达到至少 ，永远达不到就输出 。
思路
先把前两轮模拟出来，不能只看一轮结束时的值，中间也可能已经达到 。
设第一轮结束值为 ，一轮总和为 。如果 ，第二轮结束后就稳定了，再往后不会出现新值。如果 ，从第二轮开始就不会再被截到零，每轮都比上一轮多 。枚举轮内前缀和 ，算出 还差多少个 ，取最小轮数。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 17;
const ll oo = 2e18;
int T, n, tot;
ll m, a[maxn], s[maxn], b[maxn];
inline void add(int x, ll k) {
for(; x <= n; x += x & -x) b[x] += k;
}
inline ll ask(int x) {
ll res = 0; for(; x; x -= x & -x) res += b[x]; return res;
}
ll work() {
memset(b, 0, sizeof(b));
memset(s, 0, sizeof(s));
for(int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
for(int i = 1; i <= n; i++) b[i] = s[i] - s[i - (i & -i)];
for(int i = 1; i <= n; i++) {
ll tmp = ask(i);
if(tmp >= m) return 1;
if(tmp < 0) {
add(i, -tmp);
}
}
ll x = ask(n);
ll res = oo;
ll cur = x;
for(int i = 1; i <= n; i++) {
cur = max(0ll, cur + a[i]);
if(cur >= m) return 2;
}
if(s[n] <= 0) return -1;
for(int i = 1; i <= n; i++) {
ll diff = m - x - s[i];
if(diff <= 0) return 2;
res = min(res, (diff - 1) / s[n] + 1);
}
if(res == oo) return -1;
return res + 2;
// tot = 0;
// ll mx = 0;
// int p = 1;
// for(int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i], mx = max(s[i], mx);
// for(int i = 1; i <= n; i++) if(s[i] < 0) v[++tot] = s[i];
// sort(v + 1, v + 1 + tot, greater<int>());
// ll t = 1, x = 0;
// while(1) {
// for(int i = 1; i <= n; i++) b[i] = s[i] - s[i - (i & -i)];
// for(int i = 1; i <= n; i++) {
// ll tmp = ask(i);
// if(x + tmp == m) return t;
// if(x + tmp < 0) {
// add(i, -x - tmp);
// }
// }
// ll tmp = ask(n);
// if(tmp == 0) return -1;
// x += tmp, t++;
// while(v[p] + x >= 0 && p <= tot) p++;
// if(p > tot) {
// ll diff = m - x - mx;
// t += (diff / s[n]);
// if(diff % s[n]) t++;
// return t;
// }
// ll diff = 0 - (x + v[p]);
// t += (diff / tmp), x += (diff / tmp) * tmp;
// }
}
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%lld", &n, &m);
for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
printf("%lld\n", work());
}
return 0;
}