• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            算法學(xué)社
            記錄難忘的征途
            posts - 141,comments - 220,trackbacks - 0
            題目描述:
               給一個(gè)(N<10,000)的有向無(wú)環(huán)圖,有M個(gè)物體坐落在若干個(gè)點(diǎn)上。A和B每次可以將某物體沿著某條邊移動(dòng)一次。多個(gè)物體可以重合。不能移動(dòng)者算輸。
            算法分析:
               SG定理,可以先拓?fù)渑判蛉缓笤賁G。
             1 #include<algorithm>
             2 #include<cstdio>
             3 #include<iostream>
             4 #include<bitset>
             5 using namespace std;
             6 int n,m;
             7 const int N = 10005;
             8 const int M = 100005;
             9 int head[N],nxt[M],pnt[M],e,dp[N];
            10 inline void add(int u,int v){
            11     nxt[e] = head[u]; head[u] = e; pnt[e++] = v;
            12 }
            13 struct node{int id,pre;} tmp[N];
            14 int tim,vis[N];
            15 void dfs(int u){
            16     vis[u] =1;
            17     for(int i = head[u]; i!= -1; i=nxt[i]){
            18         if(!vis[pnt[i]]) dfs(pnt[i]);
            19     }
            20     tmp[u].id = u;
            21     tmp[u].pre=tim++;
            22 }
            23 bool cmp(node a,node b){return a.pre < b.pre;}
            24 void process(){
            25     tim =0;
            26     for(int i = 1; i <= n; i++) vis[i] = 0;
            27     for(int i = 1; i <= n; i++) if(!vis[i]) dfs(i);
            28     sort(tmp+1,tmp+n+1,cmp);
            29     bitset<2*N> mp;
            30     for(int p = 1; p <= n; p++) {
            31         int u = tmp[p].id;
            32         mp.reset();
            33         for(int i = head[u]; i!=-1; i=nxt[i]){
            34             int v = pnt[i];
            35             mp[dp[v]] = 1;
            36         }
            37         for(int i = 0; i < mp.size(); i++) if(!mp[i]){
            38             dp[u] = i;
            39             break;
            40         }
            41     }
            42 }
            43 int main(){
            44     int ctest = 1;
            45     while(scanf("%d",&n)!=EOF){
            46         for(int i = 1; i <= n; i++) head[i] = -1;
            47         e = 0;
            48         for(int i = 1; i < n; i++ ){
            49             int t,v;
            50             scanf("%d",&t);
            51             while(t--){
            52                 scanf("%d",&v);
            53                 add(i,v);
            54             }
            55         }
            56         process();
            57         int t; scanf("%d",&t);
            58         printf("Case %d:\n",ctest++);
            59         while(t--){
            60             int val = 0,c,v;
            61             scanf("%d",&c);
            62             while(c--) {
            63                 scanf("%d",&v);
            64                 val ^= dp[v];
            65             }
            66             puts(val?"Alice":"Bob");
            67         }
            68     }
            69 }
            70 
            posted on 2012-12-23 14:04 西月弦 閱讀(420) 評(píng)論(0)  編輯 收藏 引用

            只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


            97久久国产综合精品女不卡| 97精品久久天干天天天按摩| 亚洲精品tv久久久久久久久| 一97日本道伊人久久综合影院| 国产成人香蕉久久久久| 久久婷婷五月综合色奶水99啪| 少妇熟女久久综合网色欲| 久久人妻少妇嫩草AV蜜桃| 国产精品99久久久久久董美香| 久久久久久综合一区中文字幕| 99久久国产综合精品麻豆| 国产日产久久高清欧美一区| 国产成人久久精品激情| 久久久久久a亚洲欧洲aⅴ| 国产精品久久自在自线观看| 久久精品国产免费一区| 精品无码久久久久久久动漫| 久久国产成人| 2021最新久久久视精品爱 | 色综合久久88色综合天天 | 久久精品成人免费观看97| 欧美亚洲另类久久综合婷婷 | 国产精品久久久久免费a∨| 18禁黄久久久AAA片| 无码人妻久久一区二区三区免费| 亚洲综合伊人久久综合| 成人妇女免费播放久久久| 91超碰碰碰碰久久久久久综合| 久久亚洲高清综合| 久久久久免费精品国产| 99久久99这里只有免费的精品| 久久国产香蕉视频| 久久伊人五月丁香狠狠色| 99久久精品毛片免费播放| 精品无码久久久久久国产| 97精品伊人久久久大香线蕉| 青青草原综合久久| 色播久久人人爽人人爽人人片AV| 国产精品18久久久久久vr| 亚洲AV伊人久久青青草原| 99久久国语露脸精品国产|