【题解】Codeforces Round 996 C.The Trail D.Scarecrow

Codeforces Round 996

比赛地址：https://codeforces.com/contest/2055

Problem C.The Trail

1.从数学上看，未知的数有 n+m-1 个位置的 a[i] 值，和行列总和x，解出他们需要n + m个独立的方程。对每一个未知的位置，有行和等于列和的方程，共n+m-1个，还有一个行和/列和 = x的方程，恰好可解。所以只需要找到一种易于用代码表达的解方程方法即可。

2.从（1，1）开始，按字符串的顺序依次将每个空余位置表示成 ax + b 的形式。对于每行的最后一个未知数，此行仅剩该数未被表示，用 x - 行和(不含该数）表示该数。对于每行的其他未知数，此列仅剩该数位被表示，用 x - 列和(不含该数）表示。写代码时用矩阵a[i][j]、b[i][j]表示i，j位置的a、b值，分别处理即可，详见AC代码。

3.现在所有未知数均被表示成ax+b的形式，如果最后一个未知数(n,m)，由 x-行和得到，那用第m列的列和 = x解出x；反正，由 x-列和得到，就用行和 = x解方程。写代码时注意x系数为0的情况，不能除以0，此时特判。

#include <bits/stdc++.h>
#define int long longusing namespace std;typedef pair<int, int> PII;const int N = 2e3 + 10, M = 20;string s;
int n, m;
int a[N][N];
int b[N][N];void solve() {cin >> n >> m >> s;for (int i = 1; i <= n; i ++)for (int j = 1; j <= m; j ++) {cin >> a[i][j];b[i][j] = 0;}int x = 1, y = 1;for (auto i : s) {if (i == 'D') {int sumb = 0, suma = 0;for (int j = 1; j <= m; j ++) {sumb += b[x][j];suma += a[x][j];}b[x][y] = 1 - sumb;a[x][y] = 0 - suma;x ++;} else {int sumb = 0, suma = 0;for (int j = 1; j <= n; j ++) {sumb += b[j][y];suma += a[j][y];}b[x][y] = 1 - sumb;a[x][y] = 0 - suma;y ++;}}long long sum;if (s.back() == 'D') {{int sumb = 0, suma = 0;for (int j = 1; j <= n; j ++) {sumb += b[j][y];suma += a[j][y];}b[x][y] = 1 - sumb;a[x][y] = 0 - suma;}int sumb = 0, suma = 0;for (int i = 1; i <= m; i ++) {suma += a[n][i];sumb += b[n][i];}if (sumb == 1)sum = 0;elsesum = suma / (1 - sumb);} else {{int sumb = 0, suma = 0;for (int j = 1; j <= m; j ++) {sumb += b[x][j];suma += a[x][j];}b[x][y] = 1 - sumb;a[x][y] = 0 - suma;}int sumb = 0, suma = 0;for (int i = 1; i <= n; i ++) {suma += a[i][m];sumb += b[i][m];}if (sumb == 1)sum = 0;elsesum = suma / (1 - sumb);}for (int i = 1; i <= n; i ++) {for (int j = 1; j <= m; j ++) {cout << sum *b[i][j] + a[i][j] << ' ';}cout << '\n';}
}signed main() {ios::sync_with_stdio(false);cin.tie(0);int t = 1;cin >> t;while (t --) {solve();}return 0;
}

Problem D.Scarecrow

1.赶鸟的第一步，肯定是让最近的稻草人走到0，把鸟赶出来; 赶鸟的最后一步，是最远的稻草人把鸟一直赶到终点（当l较大，ai较小时）。
2.所有稻草人速度一样，所以稻草人不可能超过彼此。
3.每次鸟跳跃之后，只需要考虑离瞬移之后的鸟之前和鸟之后最近的两个稻草人，分别成为前稻草人和后稻草人。
4.考虑维护每个稻草人的活动范围，在时刻t，第i个稻草人可以在[ai - t,ai + t]的范围。首先让最近的稻草人把鸟赶出来，花费时间a1，然后判断鸟和前后两个稻草人的位置关系。位置关系分为4种：
a.鸟 < ai-t;
b. ai-t<=鸟<=ai+t;
c. ai + t< 鸟 < ai+t+k;
d. 鸟 > ai + t + k；
对于情况a，由前稻草人推，后稻草人往回赶，触发瞬移之后鸟到后稻草人+k的位置，耗时距离差/2，更新该机器人为前稻草人；
对于情况b, 后稻草人在鸟处等着，鸟瞬移过来直接顶走，耗时0，更新该机器人为前稻草人；
对于情况c，后稻草人值走到尽可能大的位置，鸟瞬移过来直接顶走，耗时0，更新该机器人为前稻草人；
对于情况d，此处不操作，该机器人不可能作为后稻草人，更新该机器人为前稻草人，看下一个稻草人；
5.当稻草人使用完，还没有到达l处，最后一个稻草人推过去即可。

#include <bits/stdc++.h>
#define int long longusing namespace std;typedef pair<int, int> PII;const int N = 2e5 + 10;int n, k, l;
int a[N];void solve() {cin >> n >> k >> l;k = k << 1;l = l << 1;for (int i = 1; i <= n; i ++) {cin >> a[i];a[i] = a[i] << 1;}int ans = 0;ans += a[1];int idx = k;int p = 2;int last = 0;while (idx < l) {if (p == n + 1) {ans += l - k - last;break;}if (idx < a[p] - ans) {int now = a[p] - ans;int t = (now - last - k) >> 1;idx = now - t + k;ans += t;last = idx - k;} else if (idx >= a[p] - ans && idx <= a[p] + ans) {last = idx;idx += k;ans += 0;} else if (idx - (a[p] + ans) < k) {idx = k + a[p] + ans;last = a[p] + ans;ans += 0;} else {last = max(last, a[p] + ans);}p ++;}cout << ans << '\n';
}signed main() {ios::sync_with_stdio(false);cin.tie(0);int t = 1;cin >> t;while (t --) {solve();}return 0;
}