2022牛客多校（加赛）

2022牛客多校（加赛）

一、比赛小结

比赛链接："蔚来杯"2022牛客暑期多校训练营（加赛）

二、题目分析及解法（基础题） E、Everyone is bot

题目链接：E-Everyone is bot

题意：

复读游戏，有 n 个人打算在群里复读。

一次复读的过程如下：

每一轮，n 个人按照编号从小到大依次执行以下操作。

如果这个人在前几轮已经进行过复读，他不会再次复读。也就是说，每

个人最多只会复读一次。

否则他可以选择是否进行复读。

如果某一轮没有人进行复读，那么复读的过程结束。

题解：

对于第 i 个人，如果他是所有人中第 j 个进行复读的，他会获得 ai,j 瓶冰红茶。

但是如果他是所有进行了复读的人当中倒数第 p 个进行复读的人，那么

他不会获得任何冰红茶，并且需要交给咩噗特雷格博 bot 154 瓶冰红茶（即获得 −154 杯冰红茶）。

每个人都想最大化自己获得的冰红茶数量，求所有人一共会拿到多少冰红茶。

总复读人数是 n mod p。

如果当前已经有 n − p 个人复读了，那么后面不会有任何人复读。一旦有人复读，剩下的人必然都会参与复读，那么这个人就会被禁言。所以他不会这么做。

同样，如果有 n − 2p 个人复读了，那么后面不会有任何人复读，因为一旦他复读了，接下来一定有 p − 1 个人加入复读，而这时候是 n − p 个人复读的状态，剩下 p 个人一定不会复读，那么他就被禁言了。

同样可以推出，如果当前复读人数是 n − kp 那么后面不会有人复读。

前 n mod p 个人必然一上来就复读。可以考虑如果有人不复读，后面本来没有机会的人必然会抓住机会，那么前面有人就会失去机会。

代码：

#include 
using namespace std;
const int maxn = 1e3 + 5;
int n, p;
int a[maxn][maxn];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> p;
  for (int i = 1; i  a[i][j];
  for (int i = 1; i