Discuz! Board

 找回密碼
 立即註冊
搜索
熱搜: 活動 交友 discuz
查看: 139|回復: 0
打印 上一主題 下一主題

進阶博弈 : 略微复杂の状压分裂遊戲

[複製鏈接]

2679

主題

2681

帖子

8139

積分

管理員

Rank: 9Rank: 9Rank: 9

積分
8139
跳轉到指定樓層
樓主
發表於 2023-8-23 16:07:51 | 只看該作者 回帖獎勵 |倒序瀏覽 |閱讀模式
起首是本身dp根本很差,然後是状压写的少,好不易碰到赶快記下来。

另有就是近来在學latex了,写了好几個月發明這個問题一向没解决,井底之蛙了属因而。

原题链接:C. More Reclamation

题意:

有一條 2 \, \cdot n 的运河。這條运河是首要的商業通道,是以运河必需连结连通(4连通)。两個國度起頭争取地皮,他們争取地皮的方法是填河造陸,可是填河造陸的限定是不克不及让运河堵上。河中存在一些石頭,有石頭的處所是不克不及填埋的。不克不及填河的國度會以失败了结,請問谁會获胜。

阐發:

每次咱們在填入一块地的時辰[i, j],對面的持续三块 [i \oplus 1, j - 1], [i \oplus 1, j], [i \oplus 1, j + 1] 都不克不及被填埋,如圖所示:一块完备的圖被朋分成為了两块。

而且每次填入一块城市發生朋分,是以,這道题的本色實在就是割裂遊戲。咱們必要求出每種块的sg函数,最後异或起来便可。

状况紧缩:

咱們描写一個方块必要三個参数:kubet, len,up,down。 len  暗示块的长度, up 暗示上真個状况, down 暗示下真個状况。此中上下的状况一共有三種:两块都没被占,左侧没被占,右侧没被占,咱們别離用 0/1/2 暗示,那末终极 sg[len][up][down] 便可以暗示状况的sg函数了。

状况割裂:

罗列上下状况和填入的状况,填入的状况對付新發生的两块的上下状况要末是1要末是2,對付不克不及填的部門要判掉。然後暴力异或赛到set里便可。

S.insert(sg[j][up][k]\oplus sg[i - j - 1][k][刷卡換現金,down]);

代码:

  1. int r, n, m, q;
  2. int a[N][2];
  3. int sg[N][3][3];
  4. int get_sg() {
  5. for(int i = 1; i < N ; i ++ )
  6. for(int up = 0 ; up < 3; up ++ )
  7. for(int down = 0 ; down < 3; down ++ ) {
  8. set<int> S;
  9. for(int j = 0 ; j < i ; j ++ )
  10. for(int k = 1; k <= 2; k ++ ) {
  11. if((j == 0 && k != up && up) || (j == i - 1 && k != down && down)) continue;
  12. S.insert(sg[j][up][k] ^ sg[i - j - 1][k][down]);
  13. }
  14. int ans = 0;
  15. while(S.count(ans)) ans ++ ;
  16. sg[i][up][down] = ans;
  17. }
  18. }
  19. signed main() {
  20. get_sg();
  21. // cin >> r >> n;
  22. r = read(), n = read();
  23. for(int i = 1; i <= n ; i ++ ) {
  24. int x, y;
  25. x = read(), y = read();
  26. y -- ;
  27. a[x][y] = 1;
  28. a[x - 1][y ^ 1] = 1;
  29. a[x + 0][y ^ 1] = 1;
  30. a[x + 1][y ^ 1] = 1;
  31. }
  32. int len = 0,去疤藥膏, up = 0, down = 0, res = 0;
  33. for(int i = 1; i <= r ; i ++ ) {
  34. if(a[i][0] + a[i][1] == 2) continue;
  35. int j = i;
  36. while(j <= r && a[j][0] + a[j][1] < 2) j ++ ;
  37. len = j - i;
  38. up = (a[i][0] + a[i][1] == 0) ? 0 : (a[i][0] ? 2 : 1);
  39. down = (a[j - 1][0] + a[j - 1][1] == 0) ? 0 : (a[j - 1][小琉球精選酒吧,0] ? 2 : 1);
  40. // cout << i << " " << j << " " << len << " " << up << " " << down << endl;
  41. res ^= sg[len][up][down];
  42. i = j;
  43. }
  44. if(res) cout << "WIN";
  45. else cout << "LOSE";
  46. }
複製代碼
回復

使用道具 舉報

您需要登錄後才可以回帖 登錄 | 立即註冊

本版積分規則

Archiver|手機版|小黑屋|台灣運動娛樂論壇  

娛樂城, 百家樂, 真人百家樂, 中醫推薦, 現金板, 彰化當舖, 彰化汽車借款, 彰化機車借款, 現金版, 刷卡換現金, 娛樂城, 運彩玩法, 7M足球即時比分, NBA即時比分, 發發發老虎機, 百家樂, 歐冠杯歐冠杯決賽歐冠盃歐冠盃決賽LEO娛樂財神娛樂財神娛樂城娛樂城註冊送娛樂城體驗金線上娛樂線上娛樂城賭博場所運彩場中運動彩券場中台灣運動彩券首頁運動彩券單場運彩單場運動彩場中投注場中投注表場中投注時間表場中投注時刻表台灣運彩足球賠率台灣運彩場中

GMT+8, 2024-11-1 10:22 , Processed in 0.066852 second(s), 5 queries , File On.

Powered by Discuz! X3.3

© 2001-2017 Comsenz Inc.

快速回復 返回頂部 返回列表