【题解】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 long
using 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;
else
sum = 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;
else
sum = 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 long
using 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;
}
Problem E.Haystacks
** 注：该题难度高达 2800，作者也没能独立完成QAQ**