CF1877 Codeforces Round 902（div2A - div2F）

可惜赛时被 E 恶心死了，过了 E 就开摆了。

A.Goals of Victory

题目描述：

有 $n$ 支球队参加足球比赛。每对球队对阵一次。每场比赛结束后，Pak Chanek 会收到两个整数作为比赛结果，即两队在比赛中的进球数。一支球队的效率等于该队在每场比赛中的总进球数减去对手在每场比赛中的总进球数。

比赛结束后，Pak Dengklek 会统计每支球队的效率。结果他忘了其中一支球队的效率。给定 $n-1$ 支球队的效率 $a_1,a_2,a_3,\ldots,a_{n-1}$。求缺少的那支队伍的效率是多少？可以证明，缺失队伍的效率是唯一确定的。

$2 \le n \le 100$，$-100 \le a_i \le 100$

题目分析：

通过手玩样例以及手摸可以发现，答案就等于：

$$-\sum_{i=1}^{n-1} a_i$$

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int a[N];
int main(){
	int T;scanf("%d",&T);
	while(T--){
		int n;scanf("%d",&n);
		int sum = 0;
		for(int i=1; i<n; i++)	scanf("%d",&a[i]),sum += a[i];
		printf("%d\n",-sum);
	}
	return 0;
}

B.Helmets in Night Light

题目描述：

Pak Chanek 是一个名叫坤甸（Khuntien）的村庄的村长。在一个灯火通明的夜晚，Pak Chanek 突然接到一个重要通知，需要通知坤甸村的所有 $n$ 居民。

首先，Pak Chanek 将公告直接发给一位或多位居民，每人的费用为 $p$。之后，居民可以使用一个神奇的头盔状装置将公告分享给其他居民。但是，使用头盔形装置需要付费。如果第 $i$ 个居民已经至少得到过一次公告（直接从 Pak Chanek 那里或从其他居民那里），他/她最多可以将公告分享给 $a_i$ 个其他居民，每次分享的成本为 $b_i$。

如果 Pak Chanek 也可以控制居民向其他居民分享公告的方式，那么 Pak Chanek 通知坤甸所有 $n$ 居民公告的最小成本是多少？

$1 \le n \le 10^5$

题目分析：

我们肯定是把消息每次分享给 $b$ 尽可能小的，因为以后由他们继续向其他人分享的成本是最低的。

所以可以直接将所有的人按 $b$ 排序，从小到大分享消息，注意就是如果当前最优的 $b$ 都不如 $p$ 优，那么显然直接用 $p$ 的花费即可，可以使用双指针维护最优的位置。

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
using namespace std;
const int N = 1e5+5;
bool cmp(PII a,PII b){
	if(a.second != b.second)	return a.second < b.second;
	return a.first > b.first;
}
PII a[N];
bool flag[N];
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int T;scanf("%lld",&T);
	while(T--){
		int n,p;scanf("%lld%lld",&n,&p);
		for(int i=1; i<=n; i++)	scanf("%lld",&a[i].first);
		for(int i=1; i<=n; i++)	scanf("%lld",&a[i].second);
		sort(a+1,a+n+1,cmp);
		int pos = 1,ans = 0;
		for(int i=1; i<=n; i++){
			while(flag[pos] && !a[pos].first)	++pos;
			if(flag[pos] && a[pos].second <= p)	ans += a[pos].second,a[pos].first--;
			else if(flag[pos] && a[pos].second > p)	ans += p;
			if(!flag[pos]){
				ans += p;
			}
			flag[i] = true;
		}
		printf("%lld\n",ans);
		for(int i=1; i<=n; i++)	flag[i] = false;
	}
	return 0;
}

C.Joyboard

题目描述：

游戏少年 Chaneka 发明了一种名为 joyboard 的新型游戏控制器。有趣的是，她发明的游戏板只能用来玩一种游戏。

游戏板有一个屏幕，上面有 $n+1$ 个插槽，从左到右依次为 $1$ 到 $n+1$。$n+1$ 个插槽将被一个 $[a_1,a_2,a_3,\ldots,a_{n+1}]$ 的序列填满。玩家 Chaneka 必须在 $a_{n+1}$ 中指定一个介于 $0$ 和 $m$ 之间的整数。然后，对于从 $n$ 到 $1$ 的每个 $i$，$a_i$ 的值将等于 $a_{i+1}$（右边相邻的值）除以 $i$ 的余。换句话说，就是 $a_i = a_{i + 1} \bmod i$。

Chaneka 希望每个插槽都分配一个整数后，整个屏幕（所有 $n+1$ 插槽中）正好有 $k$ 个不同的值。将一个非负整数赋值给插槽 $n+1$ 的有效方法有多少种？

$1 \le n \le 10^9$，$0 \le m \le 10^9$，$1 \le k \le n+1$

题目分析：

考虑我们这个过程是什么样的，首先 $m$ 会模 $n$ 也就是会变成一个小于 $n$ 的数 $x$，在我们从大到小遍历的时候，如果当前没有遍历到 $x$ 那么显然所有的数都大于 $x$ 也就是取模之后没有影响，当我们遍历到 $x$ 时就会直接变成 $0$，所以整个段就是一个类似 $0-x-m$ 的样子。

也就是说如果 $k > 3$ 则必然无解，只需要考虑 $k \le 3$ 的情况。

如果 $k = 1$ 也就是必然满足 $x = 0$ 且 $m = 0$，也就是只有一种情况。

如果 $k = 2$ 也就是必然满足 [$x = 0$ 且 $m \not= x$] 或者 [$x \not= 0$ 且 $x = m$]，也就是 $[1,n]$ 加上 $(n,m]$ 中 $n$ 的倍数。

如果 $k = 3$ 其实就是 $(n,m]$ 中不是 $n$ 的倍数的数。

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
	int T;scanf("%lld",&T);
	while(T--){
		int n,m,k;scanf("%lld%lld%lld",&n,&m,&k);
		if(k > 3)	printf("0\n");
		else if(k == 3){
			int l = n + 1,r = m;
			if(l > r)	printf("0\n");
			else	printf("%lld\n",(r-l+1) - ((r/n) - ((l-1)/n)));
		}
		else if(k == 2){
			int l = 1,r = min(n,m);
			if(l > r)	printf("0\n");
			else{
				int tmp = m / n - n / n;
				printf("%lld\n",r-l+1+(tmp > 0 ? tmp : 0));
			}
		}
		else if(k == 1){
			printf("%lld\n",1ll);
		}
	}
	return 0;
}

D.Effects of Anti Pimples

题目描述：

Chaneka 有一个数组 $[a_1,a_2,\ldots,a_n]$。最初，所有元素都是白色的。Chaneka 将选择一个或多个不同的位置，并将这些位置上的元素染成黑色。然后，她会选择所有位置是至少一个黑色元素位置倍数的白色元素，并将这些元素染成绿色。之后，她的得分就是所有黑色和绿色元素中 $a_i$ 的最大值。

假设当前选择了位置 $i$ 变成黑色，则位置 $i,2i,3i,\cdots$ 里为白色元素的位置均会被染成绿色。

Chaneka 有 $2^n-1$ 种方法来选择黑色指数。求 Chaneka 选择黑色位置的所有可能方式的得分之和。由于答案可能很大，请打印答案的模数 $998\,244\,353$。

$1 \le n\le 10^5$，$1\le a_i \le 10^5$

题目分析：

其实就是对于所有黑色的位置，下标为这个位置倍数的位置均被染绿，其实将染绿看作染黑也没有任何问题。

可以考虑钦定某个位置就是最大值，这样的话限制就是相当于：比它大的数的位置的所有约数都不能被选择，它的位置的约数至少有一个被选择。

可以直接从大到小枚举最大值，然后增量地维护出可以选择的位置是哪些，因为枚举约数可以实现 $O(\sqrt{n})$，所以复杂度为 $O(n \sqrt{n})$。

对于值相同的位置，我们可以钦定位置更靠后的更大就好了。

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
using namespace std;
const int N = 2e5+5;
const int MOD = 998244353;
PII a[N];
int pw[N];
bool flag[N];
bool cmp(PII a,PII b){
	return a.first > b.first;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n;scanf("%lld",&n);
	pw[0] = 1;
	for(int i=1; i<=n; i++)	pw[i] = pw[i-1] * 2 % MOD;
	for(int i=1; i<=n; i++)	scanf("%lld",&a[i].first),a[i].second = i;
	sort(a+1,a+n+1,cmp);
	int sz = n;
	int ans = 0;
	for(int i=1; i<=n; i++){
		int tmp = 0;
		for(int j=1; j*j<=a[i].second; j++){
			if(a[i].second % j != 0)	continue;
			if(!flag[j])	++tmp;
			if(j * j != a[i].second && !flag[a[i].second/j])	++tmp;
		}
		ans = (ans + a[i].first * (pw[tmp]-1)%MOD * pw[sz-tmp]%MOD)%MOD;
		for(int j=1; j*j<=a[i].second; j++){
			if(a[i].second % j != 0)	continue;
			if(!flag[j])	flag[j] = true,--sz;
			if(!flag[a[i].second/j])	flag[a[i].second/j] = true,--sz;
		}
	}
	printf("%lld\n",(ans%MOD+MOD)%MOD);
	return 0;
}

E.Autosynthesis

题目描述：

Chaneka 写下了一个由 $n$ 个正整数元素组成的数组 $a$。最初，所有元素都没有圈起来。在一次操作中，Chaneka 可以圈出一个元素。同一元素可以圈定多次。

完成所有操作后，Chaneka 按照下标顺序，将 $a$ 中所有未被圈出的元素组成一个序列 $r$。

Chaneka 还制作了另一个序列 $p$，其长度等于所执行的操作次数，并且 $p_i$ 是在第 $i$ 次操作中被圈出的元素的下标。

Chaneka 希望进行若干次操作，使序列 $r$ 等于序列 $p$。请帮助她实现这个目标，如果不可能，请报告！请注意，如果有多个解决方案，您可以输出其中任何一个。

$1 \le n \le 2\cdot 10^5$，$1 \le a_i \le n$

题目分析：

为了方便，下文如果元素如果被留在序列 $r$ 中我们称其为被选择。

看到是下标和值之间的相等，所以一个想法就是从 $i$ 连向 $a_i$，这样的话如果 $i$ 被选择则 $a_i$ 一定不被选择，因为如果选择 $a_i$ 就找不到一个数能与 $i$ 匹配。

因为一个命题的逆否命题与其是等价的，所以如果 $a_i$ 被选择，则 $i$ 一定不被选择，也就是说对于建出来的这棵基环树如果节点 $i$ 被选择，则与它相邻的所有节点都不能被选择。

同理如果节点 $i$ 不被选择，则连向 $i$ 的点里至少有一个被选择，不然的话 $i$ 也没有匹配的点了。

这个东西一看就是可以 $dp$ 解决的，我们可以对于基环树断环为链然后钦定好相邻的这两个点是否选择，然后做 $dp$ 就好了，只不过细节有亿点点多，反正我是调了一个多小时才过。

具体的 $dp$ 状态就是设 $dp[i][0/1]$ 表示考虑 $i$ 为根的子树，$i$ 是否被选择的情况下，是否存在一种解。

转移的话就是根据上面的这个限制转移就好了。

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
bool dp[N][2],vis[N],flag[N];
vector<int> son[N];
int fa[N],pos1,pos2,opt1,opt2,a[N],tmp;
//dp[now][1] 代表在 r 里，dp[now][0] 代表不在 r 里 
void get_dp(int now,int fath){
	vis[now] = true;
	for(auto to : son[now]){
		if(to == fath || to == pos1)	continue;
		get_dp(to,now);
	}
	dp[now][1] = 1,dp[now][0] = 0;
	for(auto to : son[now]){
		if(to == fath || to == pos1)	continue;
		dp[now][1] &= dp[to][0];
		dp[now][0] |= dp[to][1];
	}
	for(auto to : son[now]){
		if(to == fath || to == pos1)	continue;
		if(!dp[to][1] && !dp[to][0]){
			dp[now][0] = 0;
		}
	}
	if(now == pos2){
		dp[now][0] |= (opt1 == 1);
		dp[now][opt2^1] = 0;
	}
}
void get(int now){
	dp[now][1] = 1,dp[now][0] = 0;
	for(auto to : son[now]){
		dp[now][1] &= dp[to][0];
		dp[now][0] |= dp[to][1];
	}
	for(auto to : son[now]){
		if(!dp[to][1] && !dp[to][0]){
			dp[now][0] = 0;
		}
	}
	dp[now][1] &= dp[fa[now]][0];
}
void get_ans(int now,int fath,int opt){
	flag[now] = opt;
	if(opt == 0){
		for(auto to : son[now]){
			if(to == fath || to == pos1)	continue;
			if(to == pos2)		get_ans(to,now,opt2);
			else if(dp[to][1])	get_ans(to,now,1);
			else 				get_ans(to,now,0);
		}
	}
	else if(opt == 1){
		for(auto to : son[now]){
			if(to == fath || to == pos1)	continue;
			if(to == pos2)	get_ans(to,now,opt2);
			else 	get_ans(to,now,0);
		}
	}
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n;scanf("%d",&n);
	for(int i=1; i<=n; i++){
		scanf("%d",&a[i]);
		son[a[i]].push_back(i);
		fa[i] = a[i];
	}
	int ans = true;
	for(int i=1; i<=n; i++){
		if(!vis[i]){
			int res = 0;
			int now = i;
			while(!vis[now]){
				vis[now] = true;
				now = fa[now];
			}
			pos1 = now,pos2 = fa[now];
			
			opt1 = 1,opt2 = 0;
			get_dp(now,0);
			get(now);
			if(dp[now][opt1] && dp[pos2][opt2]){
				get_ans(pos1,0,opt1);
				res = true;
			}
			
			opt1 = 0,opt2 = 1;
			get_dp(now,0);get(now);
			if(!res && dp[now][opt1] && dp[pos2][opt2]){
				get_ans(pos1,0,opt1);
				res = true;
			}
			
			opt1 = 0,opt2 = 0;
			get_dp(now,0);get(now);
			if(!res && dp[now][opt1] && dp[pos2][opt2]){
				get_ans(pos1,0,opt1);
				res = true;
			}
			
			if(!res)	ans = false;
		}
	}
	if(ans){
		int tot = 0;
		for(int i=1; i<=n; i++)	tot += flag[i];
		printf("%d\n",tot);
		for(int i=1; i<=n; i++){
			if(flag[i])	printf("%d ",a[i]);
		}
	}
	else	printf("-1\n");
	return 0;
}

F.Lexichromatography

题目描述：

Pak Chanek 热爱他所在的系–印度尼西亚大学（Fasilkom）计算机科学系。他想利用系徽的颜色–蓝色和红色–进行创作。

数组 $a$ 由 $n$ 个元素组成，元素 $i$ 的值为 $a_i$。Pak Chanek 希望给数组中的每个元素涂上蓝色或红色，从而满足以下条件：

• 如果所有的蓝色元素组成一个子序列，所有的红色元素也组成一个子序列，则蓝色子序列在字典序上严格小于红色子序列。

• 数组 $a$ 中没有不平衡的子数组。当且仅当有一个值 $k$ 使得该子数组中值为 $k$ 的蓝色元素个数与值为 $k$ 的红色元素个数的绝对差值为 $2$ 或更大时，该子数组才是不平衡的。

• 请注意，可以将数组中的每个元素都染成相同的颜色。

有多少种不同的颜色满足所有这些条件呢？由于答案可能非常大，请打印答案的模数 $998\,244\,353$。当且仅当至少有一个元素在一种着色中是蓝色，而在另一种着色中是红色时，两种着色才是不同的。

设 $p$ 和 $q$ 是两个不同的序列。当且仅当 $p$ 是 $q$ 的前缀，或者存在一个位置 $i$，使得 $p_j=q_j$ 对每个 $1\leq j<i$ 和 $p_i<q_i$ 都成立时，序列 $p$ 在字典序上小于序列 $q$。尤其是，空序列在字典序上总是小于任何非空序列。

题目分析：

首先可以考虑一个个限制来看，看看可以发现什么性质。

对于第一个限制，可以发现其实限制严格大于并不简单，而因为严格小于是与它本质相同的一个问题，所以可以使用总方案数 $2^n$ 减去两者完全相同的方案数，最后除以 $2$ 就是答案。

对于第二个限制，就是对于值相同的元素其按下标排序之后染色必然是红蓝交替的，也就是 …红蓝红蓝红…

可以发现如果要使得两个序列相同，也就是说在任意时刻均满足某一个序列是另一个序列的前缀，所以他们相同的部分我们其实是不用管的，我们只需要在意长的那个串多出来的部分即可。

当我们第一次插入某个元素的时候，因为较长串内必然没有和它匹配的位置，所以我们只能插入到较长串内，而第二次插入的时候因为上一次插入到了较长串内这一次就不能插入了，就只能插入较短串内与上一次插入匹配。

以此类推，我们在奇数次插入某个元素的时候必然插入到较长串的末尾，而偶数次则必然插入到较短串的末尾与对应的位置匹配，所以我们可以唯一地确定每个元素该插入到哪个串中。

而因为在同一个串中仅仅只是颜色相同并未指定哪种颜色，所以可以我们就是相当于可以把元素划分成若干个集合，每个集合内颜色必须相同，设有 $m$ 个集合，答案其实就是 $2^n - 2^m$。

以及在操作的过程中也要时刻判断是否合法，如果不合法也就是不存在相等的方案，答案就是 $2^n$。

最终的答案不要忘记除以 $2$ 啊。

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6+5;
const int MOD = 998244353;
int fa[N],a[N],cnt[N];
int power(int a,int b){
	int res = 1;
	while(b){
		if(b & 1)	res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}
int find(int x){
	if(fa[x] == x)	return x;
	return fa[x] = find(fa[x]);
}
signed main(){
	int n;scanf("%lld",&n);
	for(int i=1; i<=n; i++)	scanf("%lld",&a[i]);
	deque<int> q;
	for(int i=1; i<=200000; i++)	fa[i] = i;
	bool flag = true;
	for(int i=1; i<=n; i++){
		cnt[a[i]]++;
		if(cnt[a[i]] % 2 == 0 && q.front() != a[i])	flag = false;
		if(!q.empty() && q.front() == a[i])	q.pop_front();
		else{
			if(!q.empty())		fa[find(q.front())] = find(a[i]);
			q.push_back(a[i]);
		}
	}
	int ans1 = 0,ans2 = 0;
	for(int i=1; i<=200000; i++){
		if(cnt[i]) ++ans1;
		if(cnt[i] && find(i) == i)	++ans2;
		if(cnt[i] & 1)	flag = false;
	}
	if(!flag)	printf("%lld\n",power(2,ans1-1));
	else	printf("%lld\n",(power(2,ans1-1) - power(2,ans2-1) + MOD)%MOD);
	return 0;
}