Solution. Codeforces Round #829
C. Make Nonzero Sum
这个题真的是无话可说了，赛时不知道怎么想的做了一步自以为很 nb 的转化，先对偶数位取相反数，操作就变成了区间取反。想的倒是挺好，但是这个区间取反要求区间开头必须也得是偶数位，硬是把一道性质优美的题目变得无比复杂。
不难发现段长是没有意义的，我们可以把所有长段拆成长度为 1 或 2 的小段，其中，长度为 1 的段不会对原串进行任何修改，长度为 2 则会对后一个数取相反数。
我们每对一个数取反，都意味着它前面的数被锁定不能更改，但是这没有关系，假如我们有 $a$ 个 1 和 $b$ 个 -1，不妨设 $a\ge b$，那么我们要将 $\frac12(a-b)$ 个 1 改成 -1，还剩 $\frac12(a+b)$ 个 1，所以就算全都锁定 1 也无所谓，肯定有解，随便分都行。
Code
namespace Main{
const int N = 200005;
int t, n, a[N];
void Main(){
input(t);
while(t--){
input(n);
int cnt = 0, sum = 0;
for(int i = 1; i <= n; i++) input(a[i]), cnt += a[i] != 0, sum += a[i];
if(cnt & 1){
puts("-1");
continue;
}
int req = sum > 0 ? 1 : -1;
sum = abs(sum) / 2;
vector<pair<int, int>> ans;
for(int i = n; i >= 1; i--){
if(sum && a[i] == req) ans.emplace_back(i - 1, i), sum--, i--;
else ans.emplace_back(i, i);
}
reverse(ans.begin(), ans.end());
write(ans.size()), puts("");
for(pair<int, int> x: ans){
write(x.first), putchar(' '), write(x.second);
puts("");
}
}
return;
}
} // namespaceE. Wish I Know How to Sort
看到交换两个数，看到排序，想到逆序对，如果你也是这样，恭喜你死得惨。
状态的设计要方便转移，这话说起来倒是简单，但是如果要我总结究竟应该怎么思考，我好像也不太知道，大概需要一些灵感和一些感觉。
总而言之，在这个题目中，最终数组会变为前面一部分为 0，后面一部分为 1 的形式，不妨设 0 的个数为 $k$。
设 $f_i$ 表示达到前 $k$ 位中有 $i$ 个 1 的状态，期望需要多少步，显然，只有交换前 $k$ 位中的 1 和其余部分中的 0 这样的操作是有效的，有转移：
$$
f_i=f_{i+1}+\frac{\binom{n}{2}}{(i+1)^2}
$$
赛时纠结了一下，如果我交换了前缀中的 1 和 0 怎么办，实际上这没有任何影响，因为定义下的状态没有改变，可选操作也没有改变。
Code
namespace Main{
const int N = 200005;
const int MOD = 998244353;
int t, n, a[N], cnt, s;
ll ans, fac[N], ifac[N];
ll qpow(ll n, ll k){
ll res = 1;
while(k > 0){
if(k & 1) res = res * n % MOD;
n = n * n % MOD;
k >>= 1;
}
return res;
}
ll c(ll n, ll k){
return fac[n] * ifac[n-k] % MOD * ifac[k] % MOD;
}
void Main(){
fac[0] = 1;
for(int i = 1; i < N; i++) fac[i] = fac[i-1] * i % MOD;
ifac[N-1] = qpow(fac[N-1], MOD - 2);
for(int i = N - 2; i >= 0; i--) ifac[i] = ifac[i+1] * (i + 1) % MOD;
input(t);
while(t--){
input(n);
cnt = s = 0;
for(int i = 0; i < n; i++) input(a[i]), cnt += a[i] == 0;
for(int i = 0; i < cnt; i++) s += a[i] == 0;
ans = 0;
for(int i = s; i < cnt; i++){
ans = (ans + c(n, 2) * qpow(1ll * (cnt - i) * (cnt - i) % MOD, MOD - 2) % MOD) % MOD;
}
write(ans);
puts("");
}
return;
}
} // namespaceF. The Beach
我猜想每张床最多只会被移动一次，如果有这个结论，这个题就很好做了，过程就像是在模拟寻找增广路。
对于每张床，每次移动可以被视作是，固定一个端点，释放一个格子，再占用一个格子，那么我们考虑枚举这个端点，将占用的格子向释放的格子连长度为移动费用的边，这样从任意一个空闲格到某个被占用格子的最短路长度就是释放这个空闲格的代价。
那么我们可以将图建出来后，将所有空闲点丢到队列里一起跑 Dijkstra，注意这不是多源最短路，是到任意一点的最短距离，所以可以一起跑。
于是我们可以枚举新来的床放的位置，将释放两个格子的费用加起来，取最小值即可。
复杂度 $O(nm\log(nm))$。
问题在于，释放这两个格子对应的路径又没有可能冲突。
考虑对网格黑白染色，不难发现我们的连边都在同色格子之间，而一张床占用的两个格子是异色的，所以释放路径一定不会冲突。
另外我们考虑能不能感性证明一下每张床最多只会被移动一次。
对于两次平移或者一次平移加上一次旋转的组合，也就是这样的情况：
我们想要将橙色块移到蓝色块处，如果蓝色块本身没有被占用，那么我们的移动很劣，因为新床可以被直接放到蓝色块处。
如果蓝色块中任意部分被占用，我们就要将其释放，然后将橙色块移过去，容易发现这还是劣，因为蓝色块释放后就能够放新床了。
接下来考虑最复杂的 T 型情况：
我们希望把 AB 通过两次旋转转到 BD 去，因为两次旋转的费用可能低于一次平移，我们的目的显然是释放 A。
假如 C 原本空闲，那么 AB 可以用一次移动旋转到 BC，这样更优。
假如 C 原本被占用，那么 AB 旋转到 BC 前，我们首先要释放 C。接下来，我们有必要将 BC 再旋转到 BD 当且仅当 C 再次被其他床占用，这种情况是不合法的，我们对格子的操作必须是一条链而不能是环，否则就构造不出有效的操作序列。所以 AB 还是可以用一次移动旋转到 BC。
我不知道以上证明是否严谨，但是我已经说服我自己相信这个结论了，如果有什么问题请务必告诉我。
Code
namespace Main{
const int N = 300005;
int n, m, p, q;
ll dis[N];
string s[N];
vector<pair<int, int>> g[N];
int m1[] = {0, 0, 1, -1};
int m2[] = {1, -1, 0, 0};
int bel[] = {0, 0, 1, 1};
string dir = "RLDU";
vector<int> free;
bool vis[N];
struct node{
int u;
ll dis;
node() {}
node(int u, ll dis): u(u), dis(dis) {}
bool operator < (const node &b) const{
return dis > b.dis;
}
};
inline int id(int x, int y){
return x * m + y;
}
void dijkstra(){
priority_queue<node> q;
memset(dis, 0x3f, sizeof(dis));
for(int x: free){
dis[x] = 0;
q.emplace(x, 0);
}
while(!q.empty()){
int u = q.top().u; q.pop();
if(vis[u]) continue;
vis[u] = true;
for(pair<int, int> e: g[u]){
int v = e.first, w = e.second;
if(dis[u] + w < dis[v]){
dis[v] = dis[u] + w;
q.emplace(v, dis[v]);
}
}
}
}
void Main(){
input(n, m, p, q);
for(int i = 0; i < n; i++) cin >> s[i];
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
if(s[i][j] == '.') free.push_back(id(i, j));
if(s[i][j] == '.' || s[i][j] == '#') continue;
int d = -1;
for(int k = 0; k < 4; k++) if(dir[k] == s[i][j]) d = k;
int x = i - m1[d], y = j - m2[d];
for(int k = 0; k < 4; k++){
if(k == d) continue;
int nx = x + m1[k], ny = y + m2[k];
if(nx < 0 || nx >= n || ny < 0 || ny >= m || s[nx][ny] == '#') continue;
if(bel[d] == bel[k]) g[id(nx, ny)].emplace_back(id(i, j), q);
else g[id(nx, ny)].emplace_back(id(i, j), p);
}
}
dijkstra();
ll ans = 1e18;
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
if(s[i][j] == '#') continue;
if(s[i][j] != 'L' && j != m - 1 && s[i][j+1] != '#'){
ans = min(ans, dis[id(i, j)] + dis[id(i, j + 1)]);
}
if(s[i][j] != 'U' && i != n - 1 && s[i+1][j] != '#'){
ans = min(ans, dis[id(i, j)] + dis[id(i + 1, j)]);
}
}
if(ans == 1e18) puts("-1");
else write(ans);
return;
}
} // namespace本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
