Educational Codeforces Round 161 (Rated for Div. 2)

比赛链接

A

定义 s 和 t 匹配，当且仅当对于所有 $s_i$ ：

1. 若为小写字母，则 $t_i = s_i$
2. 若为大写字母，则 $t_i \neq lower(s_i)$

给你字符串 a, b, c, 询问是否存在字符串与 a, b 都匹配且与 c 不匹配

两个字符串如果想匹配上的话，得要每个位置都匹配上。

显然如果只匹配 a, b 的话是一定可以匹配上的，2 个字符串的限制太少了

假如匹配失败的话，只要有一个位置不匹配就行了。

所以只要判断是否存在一个位置匹配不上 c 且能匹配上 a, b 就行了

[Codeforces 1922A] Tricky template.cpp >folded

#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <set>
#include <map>
int read(int x = 0, int f = 0, char ch = getchar())
{
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
const int N = 1e6 + 5;
int n, a[N];

void solve()
{
    std::string a, b, c;
    int n = read();
    std::cin >> a >> b >> c;
    bool flag = 0;
    for (int i = 0; i < n; i++)
        if (a[i] != b[i])
            flag |= (a[i] != c[i] && b[i] != c[i]);
        else
            flag |= (a[i] != c[i]);
    puts(flag ? "YES" : "NO");
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("A.in", "r", stdin);
#endif
    for (int T = read(); T--; solve());
    return 0;
}

B

一个二次幂的性质加简单组合数学

[Codeforces 1922B] Forming Triangles.cpp >folded

#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define int long long
int read(int x = 0, int f = 0, char ch = getchar())
{
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
const int N = 3e5 + 5;
int n, a[N];
int b[N];

void solve()
{
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 0; i <= n; i++) b[i] = 0;
    for (int i = 1; i <= n; i++) b[a[i]]++;
    long long ans = 0, cnt = 0;
    for (int i = 0; i <= n; i++)
    {
        if (b[i] == 2)
            ans += cnt;
        if (b[i] > 2)
            ans += b[i] * (b[i] - 1) / 2 * cnt +
            b[i] * (b[i] - 1) * (b[i] - 2) / 6;
        cnt += b[i];
    }
    printf("%lld\n", ans);
}

signed main()
{
#ifndef ONLINE_JUDGE
    freopen("A.in", "r", stdin);
#endif
    for (int T = read(); T--; solve());
    return 0;
}

C

数轴上 n 个点，一个点跳到另外一个点的代价是 数轴上的距离

但是可以花费 1 的代价跳到最近的点

多次询问从某个点到另一个点的最小代价

正着反着预处理下即可

[Codeforces 1922C] Closest Cities.cpp >folded

#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <set>
#include <map>
int read(int x = 0, int f = 0, char ch = getchar())
{
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
const int N = 1e5 + 5;
int n, m, a[N], b[N];
int c[N], d[N];

void solve()
{
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    b[1] = 2, b[n] = 1;
    for (int i = 2; i < n; i++)
        b[i] = a[i] - a[i - 1] > a[i + 1] - a[i] ? 2 : 1;
    c[1] = a[1];
    for (int i = 1; i < n; i++)
        c[i + 1] = b[i] == 1 ? c[i] + a[i + 1] - a[i] : c[i] + 1;
    d[n] = a[n];
    for (int i = n; i >= 2; i--)
        d[i - 1] = b[i] == 1 ? d[i] - 1 : d[i] - a[i] + a[i - 1];
    for (int q = read(); q--; )
    {
        int x = read(), y = read();
        printf("%d\n", x > y ? d[x] - d[y] : c[y] - c[x]);
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("A.in", "r", stdin);
#endif
    for (int T = read(); T--; solve());
    return 0;
}

D

非常有启发性的一道题

如果在这一轮中这个怪没死，而且他的两个邻居也没死，那下一轮就不用检查这个怪了。

这个性质有什么用呢？

• 维护一个集合：下一轮可能会死亡的怪物。

如何维护？

• 每一轮处理时如果一个怪物死了就把他的邻居加入集合

集合的复杂度？

• 第一轮集合大小为 n。一轮中，杀死一个怪物最多让集合大小 +2，最多就是 n + 2n = 3n。和 n 同阶。

再想个办法维护每个怪物的邻居即可，这里有多种实现方式。e.g. dsu, set.

[Codeforces 1922D] Berserk Monsters.cpp >folded

#include <bits/stdc++.h>
#define ins insert
int read(int x = 0, int f = 0, char ch = getchar())
{
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
const int N = 3e5 + 5;
int n, a[N], d[N];

void solve()
{
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= n; i++) d[i] = read();
    d[0] = d[n + 1] = INT32_MAX, a[0] = a[n + 1] = 0;
    std::set<int> lft, cur;
    for (int i = 0; i <= n + 1; i++) lft.ins(i), cur.ins(i);
    for (; n--; )
    {
        std::set<int> del, ncur;
        for (int i : cur)
        {
            auto it = lft.find(i);
            if (it == lft.end()) continue;
            int L = *std::prev(it);
            int R = *std::next(it);
            if (a[L] + a[R] > d[i]) del.ins(i), ncur.ins(L), ncur.ins(R);
        }
        std::cout << del.size() << ' ';
        for (auto it : del) lft.erase(it);
        cur = ncur;
    }
    puts("");
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("D.in", "r", stdin);
#endif
    for (int T = read(); T--; solve());
    return 0;
}

E

逆天 cf 放了个 apio2022 原题削弱版

给定 m，要求你构造一个长度在 200 以内的序列，满足刚好有 m 个上升子序列

m <= 10 ^ 18

首先，1, 2, 3, 4, …. n - 1, n 这样的序列可以产生 2 ^ n 的贡献

赛时在想用若干个这样的东西凑，然后爆长度了。

其实不需要。

例如，[1…..10] 后面添加一个 3，就会多产生 2 ^ (3 - 1) 的贡献，二进制拆分即可

或者，在 [min…….max] 后面加上一个 min 可以 +1，加上一个 max 可以 *2，递归即可

cf 上 tutorial 的 implement 很简洁

[Codeforces 1922E] Increasing Subsequences.cpp >folded

#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define int long long
int read(int x = 0, int f = 0, char ch = getchar())
{
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}

std::vector<int> go(int x)
{
    std::vector<int> res;
    if (x == 2) res.push_back(0);
    else if (x & 1)
        res = go(x - 1),
        res.push_back(*std::min_element(res.begin(), res.end()) - 1);
    else
        res = go(x / 2),
        res.push_back(*std::max_element(res.begin(), res.end()) + 1);
    return res;
}

void solve()
{
    auto ans = go(read());
    std::cout << ans.size() << '\n';
    for (auto x : ans) std::cout << x << ' ';
    puts("");
}

signed main()
{
#ifndef ONLINE_JUDGE
    freopen("A.in", "r", stdin);
#endif
    for (int T = read(); T--; solve());
    return 0;
}