蔚来杯_2022牛客暑期多校训练营（加赛） E.Everyone is bot

原题链接

https://ac.nowcoder.com/acm/contest/38727/E

题目大意

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

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

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

若一轮中，没有任何人复读，则游戏结束。
第 $i$ 个人如果在第 $j$ 次复读，则其可以获得 $a_{i,j}$ 瓶冰红茶。但如果总复读人数不小于 $p$ 个人，则倒数第 $p$ 个人会倒扣 $154$ 瓶冰红茶，即获得 $-154$ 瓶冰红茶，且无法获得 $a_{i,j}$ 瓶冰红茶。
每个人都想最大限度的获得冰红茶，求最终每个人能获得多少冰红茶。

题解

容易得到，因为每个人都不想亏这 $-154$ 瓶冰红茶，而 $p\le n$
所以前面的人如果能取冰红茶，则尽量会选，不然剩下的数量就轮不到他了，
所以前 $n\%p$ 个人会优先取自己的一部分，即 $a_{i,i}$ ，
当 $i>n\%p$ 时，如果该成员选取了一部分，则当前的第一个位成为亏的这一方，并留给后面的人空位，
此时我们可以发现，每个 $p-1$ 位内，第一位总是亏的，
后手必定将第一位变为亏的那一方，并自己有所盈，所以这第一位必然不选，没得赚总比亏了好，输出 $0$ 即可。

参考代码

#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++)
        printf("%d ",i<=n%p?a[i][i]: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