【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小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。