Codeforces/Round939Div2

本场摘要

这一场无功无过，rank 为 411，rating 加了 55，来到了 1889。比赛时通过了 ABCD 四个题目。

感觉这一场题目难度在中等偏上，思路上虽然非常清晰直接，但是实现难度比一般场次大。E、F 题的 idea 较为新颖，作为拓展思路的场次还是很不错的。出题老哥是个华南师范大学附属中学的初三学生这么小就是红名了，反观我这个老古董却越来越菜了。。。，不得不说出题水平相当可以。

这一场的 D 题很早就有了 idea，但是写的时候非常坎坷，先是 DP 写错调半天，然后再是递归写挂。。。可见退役久了水平下降得十分明显——放在本科的时候应该能 1h 内写完前四个题的。。。不过这也是应该的，毕竟很久没有系统训练过了，以后想上分还是得多多补题。天天空想着上个红名，不脚踏实地是不可能的。

这两天几乎听完了肖斯塔科维奇的弦乐四重奏，然后又在B站上看了很多他的故事，发现天才如他其实也是位卷王，在圣彼得堡音乐学院读书的时候几乎门门功课都卷到了 5 分。既然我只是一个普通人，要做成事情需要更加努力才是，继续加油吧。

传送门：

题目

C.

题目大意：

给出一个大小为 $n * n$ 的方阵，方阵的每个位置上都是 0。题目定义了两种操作：

• 操作一，把一行中的所有数字变成一个大小为 n 的排列，排列的顺序可以自定义。
• 操作二，把一列中的所有数字变成一个大小为 n 的排列，排列的顺序可以自定义。

要求最多进行 $2 * n$ 此操作，要求使得最后的结果方阵中，每个位置上的数字之和最大。

题解：

构造题虽然变化万千，但是还是有一定套路的。一般来说，拿到问题后先构造找出理论最大值，一般来说这种情况是有对应解的，然后我们再去构造这个解。

观察可知，一个相同的数字，不能同时出现在一个矩形的四个顶点的位置上。既不存在这样的四个点 $(i, j), (i, j + m), (i + n, j), (i + n, j + m)$ 上的值相等。所以一个数字在方阵中最多出现 $2 * n - 1$ 次，即反“L 型”地排列在方阵的右下角。大的数字肯定要出现尽量多次，所以越大的数字要约放在右下。形如（以 $n = 4$ 为例）：

1 2 3 4
2 2 3 4
3 3 3 4
4 4 4 4

在想出构造的期望样式后，我们就能有的放矢了。先放最后一行，排列为 $1, 2, ..., n$，然后是倒数第二行和倒数第二列，排列依然是 $1, 2, ..., n$。这样一直做下去，直到放完第一行和第一列，总共操作 $2n - 1$ 次。

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <vector>
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
const int maxn = 2e5 + 5;
int n, sum[maxn];
void print(int c, int index) {
    std::cout << c << ' ' << index << ' ';
    for (int i = 1; i <= n; ++i) {
        std::cout << i << ' ';
    }
    std::cout << '\n';
}
int main() {
    freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    int T = 1;
    std::cin >> T;
    sum[0] = 0;
    for (int i = 1; i <= 500; ++i) {
        sum[i] = i * (2 * i - 1) + sum[i - 1];
    }
    while (T--) {
        std::cin >> n;
        std::cout << sum[n] << ' ' << 2 * n - 1 << '\n';
        print(1, n);
        for (int i = n - 1; i >= 1; i--) {
            print(1, i);
            print(2, i);
        }
    }

    return 0;
}

D.

题目大意：

题目给定一个大小为 n 的整数序列，其中 $n \leq 18$。每次操作可以选择一个 $[l, r]$ 的区间，然后将这个区间中的整数变成 $Mex(l, r)$，$Mex(l, r)$ 定义为「区间中最小的未出现的非负整数」。可以进行不限次这样的操作，要求使得最后的整数序列和最大，并输出构造出该序列过程中选取的一系列区间

题解：

考虑一个长度为 m 的初始全为 0 的区间，经过观察可知，题目中定义的构造后最大的可能结果就是区间的数字全部变为 m（可以从从 $m = 1$，$m = 2$ 等大概递推出任意长区间的构造方式）。

这样一来，问题就分成了两个部分，第一部分是将原序列划分成若干个区间，对于一个长度为 m 的区间，其内部可以全部变成数字 m，也可以保持原状，要使得结果最大；第二部分是给定一个长度为 m 的区间，将区间中的所有数字变成 m。

前者是一个非常经典的区间DP，后者显然需要递归实现。这道题的解法非常清晰直观，剩下的就是手速的比拼了。

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <vector>
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
const int maxn = 2e5 + 5;
int n, a[maxn];
std::vector<pii> operations;
void update(int l, int r) {
    std::vector<int> vec;
    for (int i = l; i <= r; ++i) {
        vec.push_back(a[i]);
    }
    std::sort(all(vec));
    int mex = 0;
    for (int i = 0; i < r - l + 1; ++i) {
        if (mex == vec[i]) ++mex;
        else break;
    }
    for (int i = l; i <= r; ++i) {
        a[i] = mex;
    }
}
void pushOperation(int l, int r) {
    operations.push_back({l, r});
    update(l, r);
}
void clear(int l, int r) {
    pushOperation(l, r);
    if (a[l]) pushOperation(l, r);
}
void fromZero2Sequence(int l, int r){
    if (l == r) {
        return;
    }
    fromZero2Sequence(l, r - 1);
    pushOperation(l, r);
    clear(l, r - 1);
    fromZero2Sequence(l, r - 1);
}
void addOperations(int l, int r, int isFirstDivIn) {
    if (l == r && isFirstDivIn) {
        if (!a[l]) pushOperation(l, l);
        else return;
    } else {
        clear(l, r);
        fromZero2Sequence(l, r);
        pushOperation(l, r);
    }
}
int main() {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    int T = 1;
    // std::cin >> T;
    while (T--) {
        operations.clear();
        std::cin >> n;
        for (int i = 1; i <= n; ++i) {
            std::cin >> a[i];
        }
        pii dp[20][20];
        dp[0][0] = {0, 0};
        for (int i = 1; i <= n; ++i) {
            int val = 0;
            int pos = 0;
            for (int j = 1; j <= i; ++j) {
                dp[i][j] = dp[i - 1][j - 1];
                int newVal = 0;
                if (j > 1) {
                    newVal = dp[i - 1][j - 1].first + j * j;
                } else {
                    newVal = dp[i - 1][0].first + std::max(1, a[i]);
                }
                if (val < newVal) {
                    val = newVal;
                    pos = i - 1 - (j - 1);
                }
            }
            dp[i][0] = {val, pos};
        }
        int pos = n;
        while(pos) {
            int next = dp[pos][0].second;
            addOperations(next + 1, pos, 1);
            pos = next;
        }
        std::cout << dp[n][0].first << ' ' << operations.size() << '\n';
        for (auto it : operations) {
            std::cout << it.first << ' ' << it.second << '\n';
        }
        // std::cout << "=======\n"; 
        // for (int i = 1; i <= n; ++i) {
        //     std::cout << a[i] << ' ';
        // }
        // std::cout << '\n';
    }

    return 0;
}

E.

题目大意：

给定长度为 n 的一个序列 a。从前往后，从 $i = 1$ 开始，让 $a_{i + 1} = \max\left\{a_{i + 1} - a_i, 0\right\}$。i 的取值依次递增，当 $i = n$ 时，使 $a_1 = \max\left\{a_1 - a_n, 0\right\}$，然后再让 $i = 1$。如此循环往复，无限次地操作下去。直到这样的操作不能让序列中的元素产生变化。求最后“尘埃落定”后的序列中所有不为零的元素的下标。

题解：

显然，操作的次数最多能达到 Int32 次。例如仅有三个元素的序列：$0, 1, 1e9$。问题到这里似乎就走进了死胡同，因为如果序列短一点还好说，可以构造式子求解，但是面对大小为 n 的序列，除了暴力模拟就别无他法了——于是尝试分析这个序列的性质，我们可以发现，如果一个数字前面的连续非零数字越多，它被减的值的数量级就会越大。

例如，假设序列为 $0, a_1, a_2, a_3, ...$。经过 m 轮操作后，假设 $a_2, a_3$ 仍非 0，不妨设 $a_2 \bmod a_1 = 0$，那么新的序列为$0, a_1, a_2 - a_1 * n, a_3 - (a_2 * 2 - a_1 * (n + 1)) * n / 2, ...$。观察到 $a_3$ 减少值比 $a_2$ 大了至少 $O(n)$ 倍。

所以经过至多 $1e9^{\frac{1}{3}}$ 轮后，则原序列的连续非零子串长度最大为 3。

发现这个性质之后，这个题就完全没有思维难度了，只需要暴力计算后，把原序列划分成若干个子序列，然后分别求解即可。但是这道题实现过程较为繁琐，且在 E2 进行了卡常，即使是 std 的耗时也来到了 1000ms 左右，而笔者实现的代码会在 E2 的第 22 个点 TLE。。。这里还是放 std 吧。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=2e5+5;
int n,a[MAXN];bool b[MAXN];
bool check(){
	a[n+1]=a[1],a[n+2]=a[2],a[n+3]=a[3];
	for(int i=1;i<=n;i++)
		if(a[i]&&a[i+1]&&a[i+2]&&a[i+3]) return true;
	return false;
} 
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	if(n==2){
		while(a[1]&&a[2]){
			a[2]=max(0,a[2]-a[1]);
			a[1]=max(0,a[1]-a[2]);
		}
		b[1]=(a[1]>0);b[2]=(a[2]>0);
	}else if(n==3){
		while(a[1]&&a[2]&&a[3]){
			a[2]=max(0,a[2]-a[1]);
			a[3]=max(0,a[3]-a[2]);
			a[1]=max(0,a[1]-a[3]);
		}
		b[1]=(!a[3]&&a[1]);
		b[2]=(!a[1]&&a[2]);
		b[3]=(!a[2]&&a[3]);
	}else{
		while(check()){
			for(int i=1;i<=n;i++) a[i%n+1]=max(0,a[i%n+1]-a[i]);
		}
		for(int i=1;i<=n;i++) b[i]=false;
		auto attack=[&](ll x,ll y){
			ll k=x/y;
			return (2*x-(k+1)*y)*k/2;
		};
		for(int p=1;p<=n;p++) 
			if(a[p]&&a[p%n+1]) a[p%n+1]=max(0,a[p%n+1]-a[p]);
			else break;
		for(int i=1;i<=n;i++) if(!a[i]&&a[i%n+1]){
			b[i%n+1]=true;
			b[(i+2)%n+1]=(a[(i+2)%n+1]>attack(a[(i+1)%n+1],a[i%n+1]));
		}
	}
	int cnt=0;
	for(int i=0;i<=n;i++) if(b[i]) cnt++;
	cout<<cnt<<endl;
	for(int i=1;i<=n;i++) if(b[i]) cout<<i<<' ';
	cout<<endl;
}
int main(){
	ios::sync_with_stdio(false);
	int _;cin>>_;
	while(_--) solve();
}

F.

题目大意：

操场上 n 个学生站成一排（其中 $n \leq 1e6$），每个学生有一个抛球的力度区间 $[l_i, r_i]$，对于两个学生 i 和 j 而言，如果满足 $|i - j| < [l_i + l_j, r_i + r_j]$，则 i 和 j 可以互相抛球。体育老师在一次活动开始时，可以给某个同学一个球，然后这个同学再传给其他同学，每个同学只要能接到球，就可以传给其他人或者扔掉这个球，且每个人在单次活动中可以接球多次。体育老师在下课后还有一个约会，很赶时间，所以期望能通过尽量少次的活动，让每个同学都能至少接到一次球。问这样的活动至少需要多少次。

题解：

说来惭愧，拿到这道题后我几乎是直奔题解，根本没指望能自己想出来。但看完题解后发现其实也不是“不可做”，甚至说是一个很经典的前缀建边。如果是初见这类题目的话，参考价值非常大。即使是知道题解，我在实现的过程成依然花费了不小的功夫。

言归正传，琢磨这道题目的条件，看到“一个同学可以接球多次”，“$|i - j| < [l_i + l_j, r_i + r_j]$”的字眼，容易联想到利用图的联通性，然后加点连边。显然，这是开了“上帝视角”的马后炮。。。乐

对于那个看起来非常怪异的不等式条件，有一个很合乎直觉的理解方法，即：我们可以把 $[i + l_i, i + r_i]$ 看作是 i 同学的“右手”，把 $[i - r_i, i - l_i]$ 看作是 i 同学的“左手”。不妨设 $i < j$，如果满足 $[i + l_i, i + r_i] \cap [j - r_j, j - l_j] \neq \varnothing$，则说明能 i 同学和 j 同学能相互通过右手拉左手的方式够到彼此。

每个学生都可以看成是白点，然后再构造 n 个黑点来表示每个坐标，如果一个学生 i 的手能伸到点 x，则在白点 i 和黑点 x 之间连一条边。即：如果满足 $x \in [i - r_i, i - l_i] \lor x \in [i + l_i, i + r_i]$，则连接 i 和 x。

但是我们仍然会面临两个问题：

• 可能会存在两个学生同时用左手拉左手，或者右手拉右手，这样是不符合不等式约束要求的。
• 上述的解法显然要加 $O(n^2)$ 条边，在 n 如此巨大的情况下，明显无法通过题目。

对于问题一，我们可以注意到这样一条性质，如果有若干个学生能够到同一个点，且满足这些学生中既有使用左手的，也有使用右手的，那么这些学生一定能在一次传球活动中同时接到球——比如，可以选定某个使用右手的学生作为支点，在使用左手的学生之间来回传球，这样就能遍历完这个点相连的所有使用左手的学生（右手亦然）。假如一个点 x 上连接的只有都使用左手（右手）的学生，那我们就舍弃掉这个点，则问题解决。

对于问题二，假如一个学生的左（右）手能够到区间 $[i, j]$，其实不必对区间内每个点都连边，可以仅连到 i 点，然后再依次连接 $(i, i + 1), (i + 1, i + 2), ..., (j - 1, j)$。这样下来总的连边数是 $n + n - 1$，即可通过题目。

笔者写的代码一直收到 WA，且对比 std 后发现写的十分臃肿，改了改去也远不如标程，索性干脆不改了，这里建议直接看 std。once again, 我好菜啊

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
const int MAXN=2e6+5;
int n,tot,le[MAXN],ri[MAXN];
int fa[MAXN<<1],s[MAXN],t[MAXN],pre[MAXN],suf[MAXN];
inline int find(int x){
	while(x^fa[x]) x=fa[x]=fa[fa[x]];
	return x;
}
void solve(){
	cin>>n;
	for(int i=1;i<=2*n+1;i++) fa[i]=i;
	for(int i=0;i<=n+1;i++) s[i]=t[i]=pre[i]=suf[i]=0;
	for(int i=1;i<=n;i++){
		cin>>le[i]>>ri[i];
		s[max(1,i-ri[i])]++;s[max(0,i-le[i])+1]--;
		t[min(n+1,i+le[i])]++;t[min(n,i+ri[i])+1]--;
	}
	tot=n;
	for(int i=1;i<=n;i++){
		s[i]+=s[i-1],t[i]+=t[i-1];
		if(s[i]&&t[i]) suf[i]=pre[i]=++tot;
	}
	suf[n+1]=0;
	for(int i=1;i<=n;i++) pre[i]=(pre[i]?pre[i]:pre[i-1]);
	for(int i=n;i>=1;i--) suf[i]=(suf[i]?suf[i]:suf[i+1]);
	for(int i=1;i<=n;i++){
		int l=max(1,i-ri[i]),r=max(0,i-le[i]);
		if(l<=r){
			l=suf[l],r=pre[r];
			if(l&&r&&l<=r) for(int i=find(l);i<r;i=find(i)) fa[i]=i+1; 
		}
		l=min(n+1,i+le[i]),r=min(n,i+ri[i]);
		if(l<=r){
			l=suf[l],r=pre[r];
			if(l&&r&&l<=r) for(int i=find(l);i<r;i=find(i)) fa[i]=i+1; 
		}
	}
	for(int i=1;i<=n;i++){
		int l=max(1,i-ri[i]),r=max(0,i-le[i]);
		if(l<=r){
			l=suf[l],r=pre[r];
			if(l&&r&&l<=r) fa[find(i)]=find(l);
		}
		l=min(n+1,i+le[i]),r=min(n,i+ri[i]);
		if(l<=r){
			l=suf[l],r=pre[r];
			if(l&&r&&l<=r) fa[find(i)]=find(l);
		}
	}
	int ans=0;
	for(int i=1;i<=tot;i++) if(fa[i]==i) ans++; 
	cout<<ans<<'\n';
}
int main(){
	ios::sync_with_stdio(false);
	// freopen("Otomachi_Una.in","r",stdin);
	// freopen("Otomachi_Una.out","w",stdout);
	int _;cin>>_;
	while(_--) solve();
	return 0;
}