https://atcoder.jp/contests/agc049/tasks
B - Flip Digits
题意：给定两个长为n的01串s，t，每次操作对于s串，选择一个为1的位置，并同时翻转该位置和左边一位，问最少操作次数使得两串相同。
贪心
画几个能发现每次操作相当于把1往左移动一位。
从左向右遍历，当 s 不等于 t 时，找到该位右边最近的1，移动到该位右边，翻转这个1，使得 s 在该位等于 t 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
int n;
char s[N], t[N];
queue<int>q;
int main() {
scanf("%d", &n);
scanf("%s%s", s, t);
for (int i = 0; i < n; i++) {
if (s[i] == '1')q.push(i);
}
ll ans = 0;
for (int i = 0; i < n; i++) {
if (s[i] != t[i]) {
while (!q.empty() && q.front() <= i)q.pop();
if (q.empty()) { puts("-1"); return 0; }
s[q.front()] = '0';
ans += q.front() - i;
q.pop();
}
}
printf("%lld\n", ans);
return 0;
}
|
A - Erasing Vertices
题意：给定一张有向图，每次操作选择一个点，删除它以及所有由该点可达的点（包括涉及的边），问期望几次删除所有点。
期望可加
独立计算每个点被删除的期望，由于操作次数一次就能删除，所以期望就是它被选择的概率。
对于一个操作序列，点 u 被手动删除当且仅当所有可以到达它的点都排在它的后面。
设可到达 u 的点数为 m。则点 u 被手动删除的概率为 m1.
本题要注意的点在于要知道所有操作序列出现的概率都是一样的，即使该序列不能够完整实现。所以应该把所有操作序列都视为长度为 n 的排列，即操作序列的全集为全排列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
int n;
char s[N];
vector<int>G[N];
int vis[110];
void dfs(int u) {
vis[u] = 1;
for (int v : G[u]) {
if (!vis[v]) {
dfs(v);
}
}
}
double ans;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%s", s + 1);
for (int j = 1; j <= n; j++) {
if (s[j] == '1') {
G[j].push_back(i);
}
}
}
for (int i = 1; i <= n; i++) {
memset(vis, 0, sizeof(vis));
dfs(i);
int t = 0;
for (int j = 1; j <= n; j++)if (vis[j])t++;
ans += 1.0 / t;
}
printf("%.10lf\n", ans);
return 0;
}
|
C - Robots
题意：在一个数轴上，从 0 到 INF ，每个整点上都有一个机器人。有 n 种球，第 i 种上有数字 Ai，第 i 种有 Bi 个。先选一些球，任意修改球上的数字为新的正整数。修改结束后，再进行操作，当操作一个球时，如果初始在 Ai 处的那个机器人还在，则把它向左移动一格，如果新位置处有机器人，则那个机器人被摧毁。现在要求把所有球排列，按顺序操作每个球。要求 0 处的机器人不能被摧毁，问初始时最少要修改几个球。1≤A1<A2<…<AN≤109,1≤Bi≤109
Bi 代表 Ai 号机器人必须移动的次数，除非它被摧毁了。
如果某个机器人会移动到 0 处，则它必须被摧毁，定义它为“不安全的”。否则不需要摧毁，定义它为“安全的”。
要用安全的机器人摧毁掉不安全的。
对于一个不安全的机器人，把一个 Ai 球变为 Ai+1，则可以摧毁这个机器人，相当于花费代价 1 自毁。
考虑最终情况是怎样的。一定是第 Ai 号机器人走到 1 处，沿途摧毁所有机器人，而右边的所有不安全的机器人自毁。
也可能所有不安全的机器人都自毁。
枚举 Ai，答案取最小。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
int n;
int a[N], b[N], dp1;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)scanf("%d", &b[i]);
int L = INF, cnt = 0, dp1 = INF;
for (int i = n; i >= 1; i--) {
if (b[i] < a[i]) {
L = min(L, a[i] - b[i]);
if (L == 1)dp1 = min(dp1, cnt);
}
else {
if (L <= a[i]) {
dp1 = min(dp1, b[i] - a[i] + 1 + max(0, cnt - (b[i] - a[i] + 1)));
}
else {
dp1 = min(dp1, b[i] - a[i] + 1 + max(0, cnt - (b[i] - a[i] + 1)));
cnt++;
}
}
}
printf("%d\n", min(dp1, cnt));
return 0;
}
|
D - Convex Sequence
题意：给定 n,m，要求构造长度为 n，每个元素为非负数的数列，且对 2≤i≤N−1，有 2Ai≤Ai−1+Ai+1。问有几种数列。
差分思想+完全背包
转化为 Ai−Ai−1≤Ai+1−Ai。也就是说，差分数组递增。
要构造递增的数组，可以通过不断地向后缀+1，或者前缀-1，或者整个数组+1.
后缀+1在原数组上反映为 ai,ai+1,ai+1,⋯,an 分别加上 1,2,3,⋯。
前缀-1反映为 ai,ai−1,ai−2,⋯,a1 分别加上 1,2,3,⋯。
这三种操作各自都可以进行任意次，且操作顺序无关。
所以可以把 “整个数组+1” ， “长度为 1 的后缀+1”，“长度为 2 的后缀+1”，······，“长度为 1 的前缀-1”，“长度为 2 的前缀-1”，······。分别视为物品，每种物品可以拿任意个，背包大小为 m，求所有物品总质量为 m 的方案数。
完全背包计算方案数，就和普通的完全背包一样，不会有重复。
但是如果只是这样做，会使得前缀可能与后缀重叠，导致差分数组不递增，所以必须设定一个分割点，限制前缀后缀不能超过该点。且该点必定是整个数组的最小值。
再枚举分割点，每次计算完全背包，由于物品的质量都是 O(n2) 的，所以物品数为 O(m)。单次完全背包复杂度 O(mm)。
再转移分割点，由于分割点处不能被碰到，所以转移时去掉 “长度为 n-i 的后缀+1” 这种物品，再加上 “长度为 i 的前缀-1” 这种物品。
这时就可能产生重复，例如可能在分割点 i，j 时都不取物品或都只取 “长度为 1 的前缀-1”。所以必须限定至少要取 “长度为 i-1 的前缀-1” 这种物品。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
int n, m;
ll dp[N];
ll val(int x) { return 1ll*(1 + x)*x / 2; }
void ins(ll x) {
for (ll i = x; i <= m; i++) {
dp[i] = (dp[i] + dp[i - x]) % mod;
}
}
void del(ll x) {
for (ll i = m; i >= x; i--) {
dp[i] = (dp[i] - dp[i - x] + mod) % mod;
}
}
ll qry(ll x) {
if (x<0 || x>m)return 0;
return dp[x];
}
ll ans;
int main() {
scanf("%d%d", &n, &m);
dp[0] = 1;
ins(n);
for (int i = 1; i < n; i++) {
ins(val(i));
}
for (int i = 1; i <= n; i++) {
ans = (ans + qry(m - val(i - 1))) % mod;
ins(val(i));
del(val(n - i));
}
printf("%lld\n", ans);
return 0;
}
|
