五月杂题记

又鸽了一个月。OwO

5.4

CF1969B

先考虑将相同颜色的缩成一块。这样，串一定是 010101... 或 101010...，我们同时记录一个块内字符的个数，记为 \(len_i\)。

题目要求将所有的一放在零的后面。

我们从第一个 \(1\) 块开始遍历，每次 \(i += 2\)。那么 \(i + 1\) 一定是 \(0\)。题目中的操作相当于将 \(1\) 块与一个 \(0\) 拼在一起，然后将 \(0\) 移至最前段，总共移 \(len_{i+1}\) 次到下一块 \(1\) 或末尾。

当我们移至下一块一后，两段一拼在了一起。后面便一起移动。那么我们当前操作的序列长为 \(\sum_{j=1}^i len_j \times col_j\)，用个变量 \(now\) 记着就行。

每一完整的移动代价为 \((now+1)\times len_{i+1}\)，答案累加即可。

点击查看代码

// Author : Lucky_Cloud
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define db double
using namespace std;int read() {int res = 0, f = 1; char c = getchar();while (c < '0' || c > '9') {if (c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9') {res = (res << 1) + (res << 3) + (c ^ 48);c = getchar();}return f == -1 ? -res : res;
}const int N = 2e5 + 5;
int t, len[N], cnt;
char s[N];void solve() {scanf("%s", s + 1);int n = strlen(s + 1);for (int i = 1; i <= n + 1; ++i) len[i] = 0;len[cnt = 1] = 1;int p = 1;for (int i = 2; i <= n; ++i) {if (s[i] != s[p]) cnt++, p = i;len[cnt]++;}int be = 1;if (s[1] == '0') be++;int ans = 0;// cout << cnt << ' ' << be << ' ';int now = 0;for (int i = be; i <= cnt; i += 2) {now += len[i];ans += (now + 1) * len[i + 1];}cout << ans << endl;
}signed main() {t = read();while (t--) solve();return 0;
}