2023NOIPA层联测14-选举

Byteland \texttt{Byteland} Byteland 的选民们要进行选举。一共有位 n n n 选民和 m m m 位候选人，编号分别从 1 1 1 到 n n n 和从 1 1 1 到 m m m。

每位选民有一个非空的喜欢的候选人的列表，这个列表是按照喜欢程度排序的。比如说一位选民的列表是 { 2 , 4 , 7 } \{2,4,7\} {2,4,7}，那么他最喜欢的候选人是 2 2 2 号候选人，次喜欢的是 4 4 4 号候选人，再次是 7 7 7 号候选人，其余候选人都不喜欢。

选举会进行若干轮，具体规则如下：

每一轮，每位选民会投给某位在自己列表中的候选人恰好一票。第一轮，每位选民会投给自己最喜欢的候选人。从第二轮开始，每位选民会投给自己列表中上一轮票数最多的候选人。如果有多位在列表中的候选人票数都是最多的，那么会投给这些人中最喜欢的那一位（即按照票数为第一关键字，喜欢程度为第二关键字排序）。如果每位选民在第 i i i 轮 ( i > 1 ) (i>1) (i>1) 投给的候选人都和在第 i − 1 i-1 i−1 轮投给的候选人一样，那么选举会在第 i i i 轮结束后停止，并且 random \textbf{random} random 一位候选人。

聪明的你一定发现了这个选举没有什么用，但是你只关心选举进行的轮数。

你需要构造出 n , m n,m n,m，和每一位选民的喜欢的候选人的列表，使得最终选举进行的轮数尽可能多。

由于 Byteland \texttt{Byteland} Byteland 人数并不多，所以你还需要保证 n , m ≤ 1000 n,m\le1000 n,m≤1000。由于不想让某位候选人得到 0 0 0 票，你还需要保证 n ≥ m n\ge m n≥m，但是不必要保证在实际选举中每位候选人的票数都 > 0 >0 >0（也就是说这句话存在的意义仅仅就是要让 n ≥ m n\ge m n≥m）。你还需要保证所有人的喜欢的候选人的列表大小之和 ≤ 100000 \le 100000 ≤100000。

本题仅有一个测试点。 如果输出不合法，得分为 0 0 0 。 设 a a a 为选举进行的轮数， S = { 5 , 10 , 20 , 35 , 50 , 95 , 145 , 195 , 240 , 490 } S=\{5,10,20,35,50,95,145,195,240,490\} S={5,10,20,35,50,95,145,195,240,490}，设 x x x 为 S S S 中 ≤ a \le a ≤a 的元素个数，那么得分 为 10 x 10x 10x。

---

题解是这么构造的，感性理解吧。

999 501 2 1 2 1 2 1 2 2 2 1 2 3 4 2 3 2 2 4 5 2 4 3 2 5 6 2 5 4 2 6 7 2 6 5 2 7 8 2 7 6 2 8 9 2 8 7 ...

这里给出一种可能正常的思路（from Dengduck）

首先每个候选人每一轮的票数不能相等，否则进行 2 2 2 轮就结束了。

要选举能一直进行下去，每一轮都要有与前一轮不一样的地方（指每个候选人的票数）

要想每一轮都产生“变化”，就要人为制造“差距”。

一开始，令 n = 999 , m = 500 n=999,m=500 n=999,m=500。

每个选民的最喜欢候选人分别是 1 , 2 , 3 , ⋯ 499 , 500 , 1 , 2 , 3 , ⋯ 498 , 499 1,2,3,\cdots 499,500,1,2,3,\cdots 498,499 1,2,3,⋯499,500,1,2,3,⋯498,499。

这样，候选人 1 ∼ 499 1\sim499 1∼499 都有两票，而候选人 500 500 500 只有一票。如果在选民 500 500 500 的列表后面加任意一个候选人，那么第二轮就会选他（产生了变化），不妨令他为 1 1 1。

这样做，到第三轮就结束了。所以我们要人为制造票数差距。在选民 499 499 499 的列表后面加候选人 1 1 1。这样，候选人 499 499 499 就只有一票了，那么选民 999 999 999 后面就可以放别的候选人进去，比如说放候选人 2 2 2。这样做，到第四轮就结束了。

就这样递归的进行下去，就可以满足条件。最终可以进行 501 501 501 轮。

具体输出参照代码

#include<bits/stdc++.h> using namespace std; int main() { freopen("t.in","r",stdin); freopen("t.out","w",stdout); int n=999,m=500; printf("%d %d\n",n,m); for(int i=1;i<=500;i++){ if(i==max(1,500-i)) printf("1 %d\n",i); else printf("2 %d %d\n",i,max(1,500-i)); } for(int i=1;i<500;i++){ if(i==500+1-i) printf("1 %d\n",i); else printf("2 %d %d\n",i,500+1-i); } }