【2021杭电多校赛】2021“MINIEYE杯”中国大学生算法设计超级联赛（9）签到题4题

Solved Pro.ID Title Ratio(Accepted / Submitted)

1001 NJU emulator 23.27%(37/159)

1002 Just another board game 24.38%(569/2334)（博弈）

1003 Dota2 Pro Circuit 28.72%(664/2312)（双指针，模拟）

1004 Into the woods 40.00%(2/5)

1005 Did I miss the lethal? 21.69%(36/166)

1006 Guess the weight 25.00%(120/480)

1007 Boring data structure problem 17.04%(445/2611)（双端队列，模拟）

1008 Integers Have Friends 2.0 10.16%(129/1270)

1009 Little prince and the garden of roses 6.12%(3/49)

1010 Unfair contest 12.40%(254/2049)（贪心，模拟，分类讨论）

1011 ZYB’s kingdom 17.50%(7/40)

题意：

给出一个n*m的棋盘，每个位置上有一个数字，默认棋子在（1,1），n*m<1e5。

A和B轮流操作，A可以将棋子移动到同一行的任何位置（也可以不移动），B可以将棋子移动到同一列中的任何位置。

第k轮游戏结束，或者A和B也可以在每一轮选择立刻结束游戏。

A想最大化结束时的值，B想最小化，求两人都是最优策略下，最后的数字。

思路：

如果不允许随时结束，考虑A的策略为，B下一轮肯定会给它找一个列最小，所以我要找跳到所有列中列最小值最大的位置，B同理会选择所有行中最大值最小的行，这样下一轮的A就不能获得更大的值。这样，对于k是偶数次的情况，最后一次是B操作，那么A的最佳方案就是列最小的最大，如果k是奇数，那么就是行最大的最小。

考虑随时可以结束，因为都是最佳方案，所以最后的值已经定下了。那么如果最开始的位置比自己后手的方案更优的话，我就可以在一开始就结束掉以获得对自己更有利的值，加一个特判就行。

#include typedef long long LL; using namespace std; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int T; cin>>T; while(T--){ LL n, m, k; cin>>n>>m>>k; vector >vc; for(int i = 1; i <= n; i++){ vectortmp; for(int j = 1; j <= m; j++){ int x; cin>>x; tmp.push_back(x); } vc.push_back(tmp); } if(k==1){ //A在第1行最大化 int ans = 0; for(int x : vc[0])ans = max(ans, x); cout<

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

30

31

32

33

34

35

36

37

38

39

40

41

42

43

题意：

n只队伍参加两轮比赛，给出第一轮结束后每个队的分数，以及第2论第i名能获得的分数。

求第i只队伍的最好名次和最差名次（允许同分名次并列）

思路：

对于最高排名，先给它最大的得分，再给剩下的n-1个队，去找能否让其得分<=sc，把所有的都找出来，答案就是补集。

对于最低排名，先给它最小的得分，在去剩下的n-1个队里找，如果得分直接比它大，那没救了直接更新，如果得分比sc小，就去分数里从大到小找，知道第一个加起来都比sc小的就用它即可。

#include typedef long long LL; using namespace std; const LL maxn = 5050; LL a[maxn], b[maxn]; LL r[maxn]; void init(LL n){for(LL i = 1; i <= n; i++)r[i]=i;} bool cmp(LL x, LL y){ return a[x]>a[y]; } bool cmp2(LL x, LL y){ return x>y; } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); LL T; cin>>T; while(T--){ LL n; cin>>n; for(LL i = 1; i <= n; i++)cin>>a[i]; for(LL i = 1; i <= n; i++)cin>>b[i]; init(n); sort(r+1,r+n+1,cmp); sort(b+1,b+n+1,cmp2); for(LL i = 1; i <= n; i++){ LL hi = 0, mi = 0; //最高排名 LL sc = a[i]+b[1], k = 2; //给它最大的分 for(LL j = n; j >= 1; j--){//得分从小到大枚举剩下的 LL jj = r[j]; if(jj==i)continue; while(a[jj]+b[k]>sc && k<=n)k++;//找得分<=sc的 if(k<=n)hi++; //找得到就++,让hi尽可能多 k++; if(k>n)break; } hi = n-hi;//剩下的分都比它高 //最低排名 sc = a[i]+b[n]; k = n-1; for(LL j = 1; j <= n; j++){ LL jj = r[j]; if(jj==i)continue; if(a[jj]>sc){mi++; continue;} else{ while(k>=1 && a[jj]+b[k]<=sc)k--; if(k<=0)break; mi++; k--; } } cout<

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

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

题意：

维护一个队列，初始为空。1e7次操作，每次可以在左端或右端插入一个数（保证所有数不重复），或者从队列中删除一个指定的数值，或者询问ceil（m+1）/2的值。

思路：

1e7相当于所有操作都要满足O(1)，对于查询中间位置，容易想到开两个双端队列维护，因为每次只插入一个数，不难维护前者和后者长度一样，中间位置就是答案。

对于删除操作，因为插入的值是1-1e7的，可以用数组记录每个队中的数属于哪个队列，删除的时候直接从vis里改成0并更新对应队列的长度即可，并不用真的去队列里找在什么地方去删，查询的时候提前把vis==0的值去掉就行。注意删除后也要维护长度一样，不然G后面直接Q查询的话就会WA。

#include typedef long long LL; using namespace std; const int maxn = 1e7+10; int vis[maxn], tot; dequelq, rq; int lc, rc; void del(){ //每次修改长度后，维护lc==rc或lc+1==rc while(lc>rc){ while(vis[lq.back()]==0)lq.pop_back(); rq.push_front(lq.back()); lq.pop_back(); rc++; lc--; vis[rq.front()]=2; } while(rc-1>lc){ while(vis[rq.front()]==0)rq.pop_front(); lq.push_back(rq.front()); rq.pop_front(); lc++; rc--; vis[lq.back()]=1; } } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int T; cin>>T; while(T--){ string op; cin>>op; if(op[0]=='L'){ lq.push_front(++tot); vis[tot]=1; lc++; del(); }else if(op[0]=='R'){ rq.push_back(++tot); vis[tot]=2; rc++; del(); }else if(op[0]=='G'){ int x; cin>>x; if(vis[x]==1)lc--; if(vis[x]==2)rc--; vis[x] = 0; del(); }else if(op[0]=='Q'){ while(vis[rq.front()]==0)rq.pop_front(); cout<

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

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

题意：

两个人比赛，n个裁判给分，给分范围为[1-h]，去掉s个最高分和t个最低分，剩下的为得分。

给出n-1个裁判的给分，第n个裁判想让第1个人赢得比赛，并且最小化给1的分数a[n]-给2的分数b[n]。

思路：

首先不难想到，对a和b数组从小到大排序，然后取区间[t+1, n-1-s]的和，即去掉最大值最小值的原始分sc1和sc2。

对于增加的第n个值，有三种情况，要么比a[t]还小，那么不计入分数，会把a[t]挤出来计入分数。要么比a[n-s]还大，把a[n-s]挤出来替换分数，要么就在这之间保持原状，此时新增的值的取值范围必须在[ a[t], a[n-s] ]之间。然后分类讨论即可。

#include typedef long long LL; using namespace std; const int maxn = 1e5+10; LL a[maxn], b[maxn]; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int T; cin>>T; while(T--){ int n, s, t, h; cin>>n>>s>>t>>h; for(int i = 1; i < n; i++)cin>>a[i]; for(int i = 1; i < n; i++)cin>>b[i]; sort(a+1,a+n); sort(b+1,b+n); a[0] = b[0] = 1; a[n] = b[n] = h; int l = t+1, r = n-1-s; LL sc1 = 0, sc2 = 0; for(int i = l; i <= r; i++){ sc1 += a[i]; sc2+=b[i]; } //给1尽可能小，2尽可能大 LL ami = sc1+a[l-1], amx = sc1+a[r+1]; LL bmi = sc2+b[l-1], bmx = sc2+b[r+1]; if(amx <= bmi)cout<<"IMPOSSIBLE\n"; //1打最大，2打最小都不行，没救了 else if(ami > bmx)cout<<1-h<<"\n"; //1打最小，2打最大，那最好了 else{ LL ans = 0; if(ami > bmi)ans = max(ans, a[l-1]-1);//给1打1分，新的分可以比2大，那就打 if(bmx < amx)ans = max(ans, h-b[r+1]);//给2打满分，新的分可以比1小，那就打 cout<

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

30

31

32

33

34

35

36

37

视频接入服务 VIS

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。