“蔚来杯“2022牛客暑期多校训练营（加赛） E题: Everyone is bot

E题: Everyone is bot

原题链接:https://ac.nowcoder.com/acm/contest/38727/D

题目大意

有 $n$ 个人玩复读游戏，如果复读的人不小于 $p$ ，则倒数第 $p$ 个复读的人会受到惩罚。

复读的规则如下:
会有好几轮行动，每一轮中， $n$ 个人依次执行以下动作:

1. 如果该群员之前复读过，则不能再复读。
2. 否则，他可以选择是否复读。

若一轮中，没有任何人复读，则游戏结束。

第 $i$ 个人如果其是第 $j$ 个复读的人，则其可以获得 $a_{i,j}$ 瓶冰红茶。但如果总复读人数不小于 $p$ 个人，则倒数第 $p$ 个人不会获得原有的冰红茶且倒扣 $154$ 瓶冰红茶，换句话说，即获得 $-154$ 瓶冰红茶。

每个人都想最大限度地获得冰红茶，求最终每个人能获得多少冰红茶。

题解

考虑如果所有 $n$ 个人都参与复读。
在此情况下， $n-p+1$ ~ $n$ 这 $p$ 个人中任意一个人作为第 $n-p+1$ 个复读者参与复读，那么剩下的 $p-1$ 个人一定不会受到惩罚，也一定会参与复读，导致第 $n-p+1$ 个复读者受到惩罚，因此没有人会选择成为第 $n-p+1$ 个复读者，所以 $n-p+1$ ~ $n$ 一定不会参与复读游戏。
去掉这 $p$ 个人后，设 $n^{\prime }=n-p$ ，同样可以得到 $n^{\prime }-p+1$ ~ $n^{\prime }$ 也不会参与游戏，反复该过程，最终参与游戏的只会有 $n\mathrm{mod}p$ 个人参与复读游戏。
在此前提下，对于每个人而言，参与复读一定优于不参与复读，因此第一轮能参与复读的都会参与，总轮数只会有 $1$ 轮，参与的恰好是最先的 $n\mathrm{mod}p$ 个人，第 $i$ 个人的收益是 $a_{i,i}$ ，剩下的人无收益。

参考代码

#include
using namespace std;

template<class T>inline void read(T&x){
	char c,last=' ';
	while(!isdigit(c=getchar()))last=c;
	x=c^48;
	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+(c^48);
	if(last=='-')x=-x;
}

const int MAXN=1e3+5;
int n,p;
int a[MAXN][MAXN];

int main()
{
	read(n),read(p);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			read(a[i][j]);
		}
	}
	for(int i=1;i<=n;++i){
		if(i<=n%p)cout<<a[i][i]<<' ';
		else cout<<0<<" \n"[i==n];
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29