【算法竞赛】Codeforces Round #829 (Div. 2) A-F

Livinfly

发布于 2022-10-26 16:09:38

2690

发布于 2022-10-26 16:09:38

文章被收录于专栏：Livinfly

闲言

赛时A-D, C2卡了很久，思路有点糊了，其实还好，D感觉更简单，很容易看出，切了。

A

前面的Q至少后面要有一个A对应。

用cnt来记，是Q就cnt ++, 是A就cnt = max(cnt-1, 0)

B

其实我乱搞构造的，证明的话可以看cf官方题解，大概就是先反证法证明答案不大于[n/2]，再证明[n/2]可构。

n/2, n, n/2-1, n-1, ...

分奇偶稍微讨论下即可

for (int i = 0, t = n / 2 + n % 2; i < n; i += 2, t--) a[i] = t;
for (int i = 1, t = n; i < n; i += 2, t--) a[i] = t;
for (int x : a) cout << x << ' ';
cout << '\n';

C

首先，若|x|==1的个数为奇数位，显然是不可构的。

然后，可以贪心的让每两个非0数，和为0。

当[1,1]，取区间[1, 2]；

当[1,-1]，取区间[1,1]；

有0也是一样的，分类讨论“端点”两数是否相等与中间的0的个数即可。

注意后缀0即可。

我的代码并不简洁，跑了两边一样的，一次统计res，一次过程中输出结果，可以存在vector中

cnt0 = last = lastp = 0;
for (int i = 0; i < n; i++) {
    if (!a[i])
        cnt0++;
    else {
        if (!last) {
            if (i) cout << lastp + 1 << ' ' << i << '\n';
            last = a[i];
            lastp = i;
            cnt0 = 0;
            continue;
        }
        if (cnt0 % 2 == 0 && a[i] == last || cnt0 % 2 && a[i] != last)
            cout << lastp + 1 << ' ' << i + 1 << '\n';
        else {
            cout << lastp + 1 << ' ' << lastp + 1 << '\n'
                << lastp + 2 << ' ' << i + 1 << '\n';
        }
        cnt0 = 0;
        last = a[i + 1];
        lastp = i + 1;
        i++;
    }
}
if (!a[n - 1]) cout << lastp + 1 << ' ' << n << '\n';

D

注意到n! = n(n-1)!

考虑记录cnt，从小到大递推求能否令cnt[x]有值即可

并且因为是相加，所以，cnt不能有余项，都需要是整除

for (int &x : a) cin >> x, cnt[x]++;
for (int i = 1; i < x; i++) {
    if (cnt[i] % (i + 1)) {
        cout << "No\n";
        return;
    }
    cnt[i + 1] += cnt[i] / (i + 1);
}
if (cnt[x])
    cout << "Yes\n";
else
    cout << "No\n";

E

想要达到sorted的状态，需要前面为0，后面为1

先统计下0的个数cnt0，再统计前cnt0位上1的个数

每次的有效操作就是把前面的1与后面的0交换

这个操作的概率是p = \frac{2(g-k)^2}{n(n-1)}

i为前cnt0位上的1的数量

f[i] = 1+f[i]·(1-p)+f[i-1]·p

化简得

f[i] = \frac{1}{p}+f[i-1]

LL tot = n * (n - 1) / 2 % P, ans = 0;
for (LL i = cnt; i >= 1; i--) ans = (ans + tot * qpm(i * i, P - 2) % P) % P;
cout << ans << '\n';

F

将移动床的操作变化为移动空格的操作。

将原问题就可以转变为一个建立虚拟原点的最短路问题。

bool ok(int x, int y) {
  if (x < 0 || x >= n || y < 0 || y >= m) return false;
  return true;
}
void add(int x, int y, int u, int c) {
  if (!ok(x, y)) return;
  int v = x * m + y;
  ver[idx] = u, w[idx] = c, ne[idx] = h[v], h[v] = idx++;
}
// 建图
for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
        int u = i * m + j;
        if (g[u] == 'L')
            add(i - 1, j + 1, u, p), add(i + 1, j + 1, u, p), add(i, j + 2, u, q);
        else if (g[u] == 'R')
            add(i - 1, j - 1, u, p), add(i + 1, j - 1, u, p), add(i, j - 2, u, q);
        else if (g[u] == 'U')
            add(i + 1, j - 1, u, p), add(i + 1, j + 1, u, p), add(i + 2, j, u, q);
        else if (g[u] == 'D')
            add(i - 1, j - 1, u, p), add(i - 1, j + 1, u, p), add(i - 2, j, u, q);
        else if (g[u] == '.')
            ver[idx] = u, ne[idx] = h[n * m], h[n * m] = idx++;
    }
dijkstra(n * m);
for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
        int u = i * m + j;
        if (j < m - 1) res = min(res, d[u] + d[u + 1]);
        if (i < n - 1) res = min(res, d[u] + d[u + m]);
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年10月25日，如有侵权请联系 cloudcommunity@tencent.com 删除

max