九至十一月 Codeforces 题目选作

进入 NOIP 计划后期，开始针对性地刷一些 CF 题。

构造与其它技巧

也就是杂题，包括构造，简单方法（如双指针）和思维题等。

1400~1500

Rating 值为 1400~1500 的杂题。

[CF1697C] awoo’s Favorite Problem

Portal.

可以发现 a 只能往后走，而 c 只能往前走，而且 a, b 与 b, c 的相对位置不变。

查看代码

#include <iostream>
#include <string>
#include <cstring>

using namespace std;

int n;
int suma[2][100005], sumc[2][100005];
string a, b;

int main(void)
{
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n >> a >> b;
        bool flag = true;
        int b0 = 0, b1 = 0, i = 0, j = 0;
        for (; i < n; ++i)
        {
            while (b[j] == 'b') ++b1, ++j; // 找到 t 中第一个不是 b 的，以匹配当前字符
            if (a[i] == 'b') ++b0; // 当前的 s 的这个字符是 b，跳过
            else 
            {
                if (a[i] != b[j] || a[i] == 'a' && i > j || a[i] == 'c' && i < j)
                {
                    flag = false;
                    break;
                }
                ++j; // 这个字符匹配过了
            }
        }
        while (j < n) b1 += (b[j] == 'b'), ++j;
        if (b0 != b1) flag = false;
        cout << (flag ? "YES" : "NO") << '\n';
    }
    return 0;
}

[CF1728C] Digital Logarithm

Portal.

使用两个大根堆贪心地维护即可。

查看代码

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

int calc(int x)
{
    if (x == 0) return 1;
    int res = 0;
    while (x) 
    {
        ++res;
        x /= 10;
    }
    return res;
}

void solve(void)
{
    int n;
    priority_queue <int> a, b;
    cin >> n;
    for (int i = 1, x; i <= n; ++i) cin >> x, a.push(x);
    for (int i = 1, x; i <= n; ++i) cin >> x, b.push(x);
    int ans = 0;
    while (!a.empty())
    {
        int x = a.top(), y = b.top();
        if (x == y) a.pop(), b.pop();
        else if (x < y) b.pop(), b.push(calc(y)), ++ans;
        else a.pop(), a.push(calc(x)), ++ans;
    }
    cout << ans << endl;
}

int main(void)
{
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

[CF1722G] Even-Odd XOR

Portal.

$a=b \iff a~\text{xor}~ b=0$ ，也就是序列的异或和为 $0$ ，根据此构造即可。

查看代码

#include <iostream>
#include <cstdio>

using namespace std;

void solve(void)
{
	int n = 0, w = 0, a[2];
	cin >> n;
	for (int i = 1; i < n - 2; ++i)
		cout << i << ' ', w ^= i;
	cout << (1 << 28) << ' ' << (1 << 29) << ' ';
	w ^= (1 << 28); w ^= (1 << 29);
	cout << w << endl;
}

int main(void)
{
	int T;
	cin >> T;
	while (T--) solve();
	return 0;
}

DP

这里是一些动态规划的题目。

1900~2100

这个档的 DP 题一般都比较基础。

[CF229D] Towers

Portal.

令 $f(i,j)$ 代表考虑前 $i$ 个，将 $(j,i]$ 合并起来的最小代价。写好方程后发现具有单调性，然后就只剩一维了。

查看代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int n, s[5005];
int f[5005], g[5005];

int main(void)
{
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
	{
		scanf("%d", s + i);
		s[i] += s[i - 1];
	}
	memset(f, 0x3f, sizeof(f));
	f[0] = 0;
	for (int i = 1; i <= n; ++i)
		for (int j = 0; j < i; ++j)
			if (s[i] - s[j] >= s[j] - s[g[j]])
			{
				f[i] = f[j] + i - j - 1;
				g[i] = j;
			}
	printf("%d\n", f[n]);
	return 0;
}

单调队列可以将其优化到 $O(n)$ 。

[CF9D] How many trees?

Portal.

求高度不超过 $h$ ，有 $n$ 个点的二叉树个数。

直接 $f(i,j)$ ，然后递推。

查看代码

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long i64;

int n, h;
i64 f[40][40];

int main(void)
{
    scanf("%d%d", &n, &h);
    for (int i = 0; i <= n; ++i) f[0][i] = 1;
    for (int i = 1; i <= n; ++i) // loop h
        for (int j = 1; j <= n; ++j)
            for (int k = 0; k < j; ++k)
                f[j][i] += f[k][i - 1] * f[j - k - 1][i - 1];
    printf("%lld\n", f[n][n] - f[n][h - 1]);
    return 0;
}

[CF1012C] Hills

Portal.

设 $f(i,j,k)$ 为当前考虑到 $i$ ， $k$ 代表当前是不是需要满足的， $j$ 代表总共满足的个数即可。

查看代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int n;
int a[5005];
int f[5005][2505][2];

int main(void)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);

    memset(f, 0x3f, sizeof(f));
    f[0][0][0] = f[1][0][0] = f[1][1][1] = 0;
    for (int i = 2; i <= n; ++i)
    {
        f[i][0][0] = 0;
        for (int j = 1; j <= (i + 1) / 2; ++j)
        {
            f[i][j][0] = min(f[i - 1][j][0], f[i - 1][j][1] + max(0, a[i] - a[i - 1] + 1));
            f[i][j][1] = min(f[i - 2][j - 1][0] + max(0, a[i - 1] - a[i] + 1), 
                             f[i - 2][j - 1][1] + max({0, a[i - 1] - a[i - 2] + 1, a[i - 1] - a[i] + 1}));
        }
    }

    for (int i = 1; i <= (n + 1) / 2; ++i)
        printf("%d ", min(f[n][i][0], f[n][i][1]));
    putchar('\n');
    return 0;
}

[CF533B] Work Group

Portal.

设 $f[x][0/1]$ 代表奇数或偶数。

查看代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long i64;
const i64 INF = 1e18;

int n, root, a[200005];
i64 f[200005][2], ans = 0;
vector <int> G[200005];

void dp(int x) {
    f[x][0] = 0, f[x][1] = -INF;
    for (auto y : G[x]) {
        dp(y);
        i64 p = f[x][0], q = f[x][1];
        f[x][0] = max(p + f[y][0], q + f[y][1]);
        f[x][1] = max(p + f[y][1], q + f[y][0]);
    }
    f[x][1] = max(f[x][1], f[x][0] + a[x]);
    ans = max({ans, f[x][0], f[x][1]});
}

int main(void)
{
    scanf("%d", &n);
    for (int i = 1, x; i <= n; ++i) {
        scanf("%d%d", &x, a + i);
        if (x != -1) G[x].push_back(i);
        else root = i;
    }
    dp(root);
    printf("%lld\n", ans);
    return 0;
}

[CF1060E] Sergey and Subway

Portal.

不加边的答案很容易计算，加边之后长度应该除以 $2$ ，但是奇数长度是需要修正的，应该加上奇数长度的路径数再除。奇数长度的路径数利用深度的奇偶性就能简单计算。

查看代码

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;
typedef long long i64;

i64 ans = 0;
int n, dep[200005], siz[200005], cnt[2];
vector <int> G[200005];

void dfs(int x, int fa) {
    dep[x] = dep[fa] + 1; siz[x] = 1;
    cnt[dep[x] & 1] += 1;
    for (auto y : G[x]) {
        if (y == fa) continue;
        dfs(y, x);
        siz[x] += siz[y];
        ans += 1ll * siz[y] * (n - siz[y]);
    }
}

int main(void) {
    scanf("%d", &n);
    for (int i = 1, x, y; i < n; ++i) {
        scanf("%d%d", &x, &y);
        G[x].push_back(y), G[y].push_back(x);
    }
    dfs(1, 0);
    printf("%lld\n", (ans + 1ll * cnt[0] * cnt[1]) / 2);
    return 0;
}

DS

这里是一些数据结构的题目。

2000

Rating 值为 2000~2100 的简单数据结构。

[CF242E] XOR on Segment

Portal.

由于 xor 的每一位可以分开计算，而且数的值域很小，可以开 20 棵线段树对每一位进行统计。

查看代码

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long i64;

int n, m;
int a[100005];
int T[400005][20], tag[400005];

inline void maintain(int o)
{
	for (int i = 0; i < 20; ++i)
		T[o][i] = T[o << 1][i] + T[o << 1 | 1][i];
}

void build(int o, int l, int r)
{
	if (l == r)
	{
		for (int i = 0; i < 20; ++i)
			if ((a[l] >> i) & 1) T[o][i] = 1;
		return;
	}
	int mid = l + r >> 1;
	build(o << 1, l, mid);
	build(o << 1 | 1, mid + 1, r);
	maintain(o);
}

inline void pushdown(int o, int l, int r)
{
	if (!tag[o]) return;
	int mid = l + r >> 1, ls = o << 1, rs = o << 1 | 1;
	for (int i = 0; i < 20; ++i)
		if ((tag[o] >> i) & 1)
		{
			T[ls][i] = mid - l + 1 - T[ls][i];
			T[rs][i] = r - mid - T[rs][i];
		}
	tag[ls] ^= tag[o], tag[rs] ^= tag[o];
	tag[o] = 0;
}

void update(int o, int l, int r, int x, int y, int k)
{
	if (x <= l && r <= y)
	{
		for (int i = 0; i < 20; ++i)
			if ((k >> i) & 1) T[o][i] = r - l + 1 - T[o][i];
		tag[o] ^= k;
		return;
	}
	pushdown(o, l, r);
	int mid = l + r >> 1;
	if (x <= mid) update(o << 1, l, mid, x, y, k);
	if (mid < y) update(o << 1 | 1, mid + 1, r, x, y, k);
	maintain(o);
}

i64 query(int o, int l, int r, int ql, int qr)
{
	if (ql <= l && r <= qr)
	{
		i64 res = 0;
		for (int i = 0; i < 20; ++i)
			res += 1ll * T[o][i] * (1 << i);
		return res;
	}
	pushdown(o, l, r);
	int mid = l + r >> 1;
	i64 res = 0;
	if (ql <= mid) res += query(o << 1, l, mid, ql, qr);
	if (mid < qr) res += query(o << 1 | 1, mid + 1, r, ql, qr);
	return res;
}

int main(void)
{
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", a + i);
	build(1, 1, n);
	scanf("%d", &m);
	while (m--)
	{
		int op, l, r, x;
		scanf("%d%d%d", &op, &l, &r);
		if (op == 1) printf("%lld\n", query(1, 1, n, l, r));
		else
		{
			scanf("%d", &x);
			update(1, 1, n, l, r, x);
		}
	}
	return 0;
}

数学

这里是一些数学题。

图论

这里是图论题。

1600~1800

这个范围内的图论题在 OI 中都不会很难，就是经典算法的简单运用。

综合问题

不止一种算法的题目，或者考验思维。

1700~1900

Rating 值为 1700~1900 的综合性题目。

[CF223B] Two Strings

Portal.

我们扫描 $s$ ，然后贪心地配对，详见代码。

查看代码

#include <cstdio>
#include <cstring>

int n, m, f[30]; // f 记录 t 中每一个字母的位置 +1
int l = 1, cnt = 1; // l 记录当前在 t 中的配对标号
char s[200005], t[200005];

int main(void)
{
	scanf("%s%s", s + 1, t + 1);
	n = strlen(s + 1), m = strlen(t + 1);
	for (int i = 1; i <= n; ++i)
	{
		// 可以配对就配对
		if (s[i] == t[l]) ++l; 
		if (s[i] == t[cnt]) f[s[i] - 'a'] = ++cnt;
		// 这个字母在 t 中扫不到
		// 即使后面有，前面的也不够构成子序列
		if (f[s[i] - 'a'] == 0) return puts("No"), 0; 
		// 当 l > 这个字母最后一次的位置+1 时，说明当前的 l 根本不可能匹配上
		// 我们将它移到最后一次出现的位置，这样 t 中最后出现的位置之前都是可以与 s 的匹配的，这样只需要匹配 t 中的剩余内容，由于选的是子序列所以肯定是剩的越少越好，所以移到最后一次出现的位置。
		if (f[s[i] - 'a'] < l) l = f[s[i] - 'a'];
	}
	if (l <= m) puts("No"); // 没有配完
	else puts("Yes");
	return 0;
}

[CF959D] Mahmoud and Ehab and another array construction task

Portal.

给定一个长度为 $n$ 的数列 $\{a_n\}$ 。
要求构造一个数列 $\{b_n\}$ 满足 $\forall \ i\neq j$ ， $b_i$ 与 $b_j$ 互质（即 $(b_i,b_j)=1$ ），且 $\{b_n\}$ 的字典序 $\ge$ $\{a_n\}$ 的字典序，且 $\{b_n\}$ 的字典序是所有满足条件的数列中最小的。
$1\leq n\leq 10^5$ ， $2\leq a_i\leq 10^5$ 。

一开始所有数都能选，然后找到第一个大于等于 $a_i$ 的，杀掉它的所有倍数，如果此时已经大于 $a_i$ 了，那么后面就随便选了。

查看代码

#include <iostream>
#include <cstdio>
#include <set>

using namespace std;
const int N = 2000000;

int n;
int a[100005];
set <int> s;

void kill(int x) {
    for (int i = x; i <= N; i += x)
        if (s.count(i)) s.erase(i);
}

void del(int x) {
    for (int i = 2; i * i <= N; ++i) {
        if (x % i == 0) {
            while (x % i == 0) x /= i;
            kill(i);
        }
    }
    if (x > 1) kill(x);
}

int main(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    for (int i = 2; i <= N; ++i) s.insert(i);
    bool flag = false;
    for (int i = 1; i <= n; ++i) {
        auto it = flag ? s.begin() : s.lower_bound(a[i]);
        printf("%d ", *it);
        del(*it);
    }
    putchar('\n');
    return 0;
}

[CF1718A2] Burenka and Traditions (hard version)

Portal.

给定一个长度为 $n$ 的数组 $A$ ，一次操作可以选择一个区间 $[l,r]$ ，将所有数异或上 $x$ ，代价为 $\lceil \frac{r-l+1}{2}\rceil$ 。问将所有数变成 $0$ 的最小代价。

由于向上取整的性质，可以发现所有操作都可以拆分成区间长度为 $1\sim 2$ 的操作。一开始 $ans=n$ ，当一段子段的异或和为 $0$ 时，可以连着用区间长度为 $2$ 的操作， $ans$ 可以减小 $1$ ，贪心即可。

查看代码

#include <iostream>
#include <cstdio>
#include <map>

using namespace std;

int n;
int a[100005];

void solve(void) {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    int ans = n, S = 0;
    map <int, int> s;
    s[0] = 1;
    for (int i = 1; i <= n; ++i) {
        S ^= a[i];
        if (s.find(S) != s.end()) {
            --ans;
            s.clear();
            s[S = 0] = 1;
        }
        else s[S] = 1;
    }
    cout << ans << '\n';
}

int main(void) {
    int T; cin >> T;
    while (T--) solve();
    return 0;
}