• <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>

            superman

            聚精會(huì)神搞建設(shè) 一心一意謀發(fā)展
            posts - 190, comments - 17, trackbacks - 0, articles - 0
               :: 首頁(yè) :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理

             1 /* Accepted 1119 C++ 00:00.03 1832K */
             2 #include <iostream>
             3 
             4 using namespace std;
             5 
             6 const int N = 1001;
             7 
             8 int maxTo; bool map[N][N];
             9 int low[N], visited[N], subset[N], cnt;
            10 
            11 void dfs(int u)
            12 {
            13     low[u] = visited[u] = ++cnt;
            14     for(int v = 1; v <= maxTo; v++)
            15         if(map[u][v])
            16         {
            17             if(visited[v] == 0)
            18             {
            19                 dfs(v);
            20                 low[u] <?= low[v];
            21                 if(low[v] >= visited[u])
            22                     subset[u]++;
            23             }
            24             else
            25                 low[u] <?= visited[v];
            26         }
            27 }
            28 
            29 int main()
            30 {
            31     int s, t, network = 0;
            32     cin >> s;
            33     while(s)
            34     {
            35         maxTo = 0, cnt = 0;
            36         memset(map, falsesizeof(map));
            37         memset(low, 0sizeof(low));
            38         memset(visited, 0sizeof(visited));
            39         memset(subset, 0sizeof(subset));
            40         
            41         if(s == 0)
            42             break;
            43         while(s)
            44         {
            45             cin >> t;
            46             maxTo >?= s;
            47             maxTo >?= t;
            48             map[s][t] = true;
            49             map[t][s] = true;
            50             cin >> s;
            51         }
            52         
            53         dfs(1);
            54         if(subset[1])
            55             subset[1]--;
            56         cout << "Network #" << ++network << endl;
            57         bool flag = false;
            58         for(int i = 1; i <= maxTo; i++)
            59             if(subset[i])
            60             {
            61                 flag = true;
            62                 cout << "  SPF node " << i << ' '
            63                      << "leaves " << subset[i] + 1 << " subnets" << endl;
            64             }
            65         if(flag == false)
            66             cout << "  No SPF nodes" << endl;
            67         cin >> s;
            68         if(s)
            69             cout << endl;
            70     }
            71     
            72     return 0;
            73 }
            74 

            posted @ 2008-04-09 09:32 superman 閱讀(313) | 評(píng)論 (0)編輯 收藏

             1 /* Accepted 0.001 196 KB */
             2 #include <iostream>
             3 
             4 using namespace std;
             5 
             6 int main()
             7 {
             8     int n, k;
             9     unsigned long long cnt[20][2= {0};
            10     
            11     cin >> n >> k;
            12     cnt[1][1= k - 1;
            13     for(int i = 2; i <= n; i++)
            14     {
            15         cnt[i][0= cnt[i - 1][1];
            16         cnt[i][1= (cnt[i - 1][0+ cnt[i - 1][1]) * (k - 1);
            17     }
            18     cout << cnt[n][0+ cnt[n][1<< endl;
            19     
            20     return 0;
            21 }
            22 

            posted @ 2008-04-08 15:52 superman 閱讀(307) | 評(píng)論 (0)編輯 收藏

             1 /* Accepted 1.968 204 KB */
             2 #include <string>
             3 #include <iostream>
             4 
             5 using namespace std;
             6 
             7 int main()
             8 {
             9     int n;
            10     cin >> n;
            11     string word;
            12     while(cin >> word)
            13     {
            14         if(word.size() == n - 1)
            15             for(int i = 0; i < n; i++)
            16             {
            17                 int sum = 0;
            18                 for(int j = 0;j < i; j++)
            19                     sum += (word[j] == '1' ? j + 10);
            20                 for(int j = i; j < n - 1; j++)
            21                     sum += (word[j] == '1' ? j + 20);
            22                 if(sum == 0 || sum % (n + 1== 0 || (sum + i + 1% (n + 1== 0)
            23                 {
            24                     for(int j = 0;j < i; j++)
            25                         cout << word[j];
            26                     cout << (sum % (n + 1== 0 ? '0' : '1');
            27                     for(int j = i; j < n - 1; j++)
            28                         cout << word[j];
            29                     cout << endl;
            30                     break;
            31                 }
            32             }
            33         if(word.size() == n)
            34         {
            35             for(int i = 0; i < n; i++)
            36                 if(word[i] == '1')
            37                 {
            38                     int sum = 0;
            39                     word[i] = '0';
            40                     for(int j = 0; j < n; j++)
            41                         sum += (word[j] == '1' ? j + 1 : 0);
            42                     if(sum == 0 || sum % (n + 1== 0)
            43                         break;
            44                     word[i] = '1';
            45                 }
            46             cout << word << endl;
            47         }
            48         if(word.size() == n + 1)
            49             for(int i = 0; i < n + 1; i++)
            50             {
            51                 int sum = 0;
            52                 for(int j = 0; j < i; j++)
            53                     sum += (word[j] == '1' ? j + 1 : 0);
            54                 for(int j = i + 1; j < n + 1; j++)
            55                     sum += (word[j] == '1' ? j : 0);
            56                 if(sum == 0 || sum % (n + 1== 0)
            57                 {
            58                     for(int j = 0; j < i; j++)
            59                         cout << word[j];
            60                     for(int j = i + 1; j < n + 1; j++)
            61                         cout << word[j];
            62                     cout << endl;
            63                     break;
            64                 }
            65             }
            66     }
            67     
            68     return 0;
            69 }
            70 

            posted @ 2008-04-08 14:20 superman 閱讀(252) | 評(píng)論 (0)編輯 收藏

              1 /* Accepted 0.015 212 KB */
              2 #include <queue>
              3 #include <cctype>
              4 #include <string>
              5 #include <iostream>
              6 
              7 using namespace std;
              8 
              9 struct pixel { int x, y; };
             10 
             11 int main()
             12 {
             13     int n, x, y;
             14     bool map[12][12= {false};
             15     
             16     cin >> n;
             17     if(cin.get() == '\n')
             18     {
             19         int sx, sy;
             20         cin >> sx >> sy;
             21         cout << sx << ' ' << sy << endl;
             22         
             23         map[sx][sy] = true;
             24         while(cin >> x >> y)
             25             map[x][y] = true;
             26         
             27         pixel cur = {sx, sy};
             28         queue <pixel> q;
             29         q.push(cur);
             30         
             31         while(q.empty() == false)
             32         {
             33             n--;
             34             cur = q.front(); q.pop();
             35             map[cur.x][cur.y] = false;
             36             if(map[cur.x + 1][cur.y])
             37             {
             38                 cout << 'R';
             39                 map[cur.x + 1][cur.y] = false;
             40                 pixel tmp = {cur.x + 1, cur.y};
             41                 q.push(tmp);
             42             }
             43             if(map[cur.x][cur.y + 1])
             44             {
             45                 cout << 'T';
             46                 map[cur.x][cur.y + 1= false;
             47                 pixel tmp = {cur.x, cur.y + 1};
             48                 q.push(tmp);
             49             }
             50             if(map[cur.x - 1][cur.y])
             51             {
             52                 cout << 'L';
             53                 map[cur.x - 1][cur.y] = false;
             54                 pixel tmp = {cur.x - 1, cur.y};
             55                 q.push(tmp);
             56             }
             57             if(map[cur.x][cur.y - 1])
             58             {
             59                 cout << 'B';
             60                 map[cur.x][cur.y - 1= false;
             61                 pixel tmp = {cur.x, cur.y - 1};
             62                 q.push(tmp);
             63             }
             64             cout << (n ? ',' : '.'<< endl;
             65         }
             66     }
             67     else
             68     {
             69         int x = n, y, cnt = 0; cin >> y;
             70         pixel cur = {x, y};
             71         
             72         queue <pixel> q;
             73         q.push(cur);
             74         
             75         string s;
             76         while(q.empty() == false)
             77         {
             78             cnt++;
             79             cin >> s;
             80             cur = q.front(); q.pop();
             81             map[cur.x][cur.y] = true;
             82             for(int i = 0; isalpha(s[i]); i++)
             83             {
             84                 if(s[i] == 'R')
             85                 {
             86                     pixel tmp = {cur.x + 1, cur.y};
             87                     q.push(tmp);
             88                 }
             89                 if(s[i] == 'T')
             90                 {
             91                     pixel tmp = {cur.x, cur.y + 1};
             92                     q.push(tmp);
             93                 }
             94                 if(s[i] == 'L')
             95                 {
             96                     pixel tmp = {cur.x - 1, cur.y};
             97                     q.push(tmp);
             98                 }
             99                 if(s[i] == 'B')
            100                 {
            101                     pixel tmp = {cur.x, cur.y - 1};
            102                     q.push(tmp);
            103                 }
            104             }
            105         }
            106         cout << cnt << endl;
            107         for(int i = 1; i <= 10; i++)
            108         for(int j = 1; j <= 10; j++)
            109             if(map[i][j])
            110                 cout << i << ' ' << j << endl;
            111     }
            112     
            113     return 0;
            114 }
            115 

            posted @ 2008-04-08 13:05 superman 閱讀(378) | 評(píng)論 (0)編輯 收藏

            Ural can not use <?= operator :(
             1 /* Accepted 0.031 200 KB */
             2 #include <iostream>
             3 
             4 using namespace std;
             5 
             6 int n, w[20], cnt, best = 0X7FFFFFFF;
             7 
             8 void search(int i, int sum)
             9 {
            10     if(i == n)
            11         return;
            12     if(best > abs(cnt - 2 * sum))
            13         best = abs(cnt - 2 * sum);
            14     search(i + 1, sum);
            15     search(i + 1, sum + w[i]);
            16 }
            17 
            18 int main()
            19 {
            20     cin >> n;
            21     for(int i = 0; i < n; i++)
            22     {
            23         cin >> w[i];
            24         cnt += w[i];
            25     }
            26     search(00);
            27     cout << best << endl;
            28     
            29     return 0;
            30 }
            31 

            posted @ 2008-04-08 00:18 superman 閱讀(324) | 評(píng)論 (0)編輯 收藏

             1 /* Accepted 1103 C++ 00:00.08 1188K */
             2 #include <queue>
             3 #include <iostream>
             4 
             5 using namespace std;
             6 
             7 struct Rec { int p1, p2, p3, cnt; };
             8 
             9 int main()
            10 {
            11     int n, p1, p2, p3;
            12     while((cin >> n) && n)
            13     {
            14         cin >> p1 >> p2 >> p3;
            15         
            16         char m[51][51];
            17         for(int i = 1; i <= n; i++)
            18             for(int j = 1; j <= n; j++)
            19                 cin >> m[i][j];
            20         
            21         Rec cur = {p1, p2, p3, 0};
            22         queue <Rec> rec;
            23         rec.push(cur);
            24         
            25         bool isRepeat[51][51][51= {false};
            26         isRepeat[p1][p2][p3] = true;
            27         bool find = false;
            28         
            29         while(rec.empty() == false)
            30         {
            31             cur = rec.front(); rec.pop();
            32             
            33             if(cur.p1 == cur.p2 && cur.p2 == cur.p3)
            34             {
            35                 cout << cur.cnt << endl;
            36                 find = true;
            37                 break;
            38             }
            39             
            40             for(int i = 1; i <= n; i++)
            41                 if(cur.p1 != i && m[cur.p1][i] == m[cur.p2][cur.p3])
            42                     if(isRepeat[i][cur.p2][cur.p3] == false)
            43                     {
            44                         isRepeat[i][cur.p2][cur.p3] = true;
            45                         Rec tmp = {i, cur.p2, cur.p3, cur.cnt + 1};
            46                         rec.push(tmp);
            47                     }
            48             for(int i = 1; i <= n; i++)
            49                 if(cur.p2 != i && m[cur.p2][i] == m[cur.p1][cur.p3])
            50                     if(isRepeat[cur.p1][i][cur.p3] == false)
            51                     {
            52                         isRepeat[cur.p1][i][cur.p3] == true;
            53                         Rec tmp = {cur.p1, i, cur.p3, cur.cnt + 1};
            54                         rec.push(tmp);
            55                     }
            56             for(int i = 1; i <= n; i++)
            57                 if(cur.p3 != i && m[cur.p3][i] == m[cur.p1][cur.p2])
            58                     if(isRepeat[cur.p1][cur.p2][i] == false)
            59                     {
            60                         isRepeat[cur.p1][cur.p2][i] = true;
            61                         Rec tmp = {cur.p1, cur.p2, i, cur.cnt + 1};
            62                         rec.push(tmp);
            63                     }
            64         }
            65         if(find == false)
            66             cout << "impossible" << endl;
            67     }
            68     
            69     return 0;
            70 }
            71 

            posted @ 2008-04-07 10:58 superman 閱讀(432) | 評(píng)論 (0)編輯 收藏

             1 /* Accepted 1152 C++ 00:00.32 836K */
             2 #include <iostream>
             3 
             4 using namespace std;
             5 
             6 int main()
             7 {
             8     int N, n, m, Case = 0;
             9     
            10     cin >> N;
            11     while(N)
            12     {
            13         cin >> n >> m;
            14         if(n == 0)
            15         {
            16             N--;
            17             Case = 0;
            18             if(N)
            19                 cout << endl;
            20             continue;
            21         }
            22         int count = 0;
            23         for(int a = 1; a < n - 1; a++)
            24             for(int b = a + 1; b < n; b++)
            25                 if((a * a + b * b + m) % (a * b) == 0)
            26                     count++;
            27         cout << "Case " << ++Case << "" << count << endl;
            28     }
            29     
            30     return 0;
            31 }
            32 

            posted @ 2008-04-06 21:06 superman 閱讀(295) | 評(píng)論 (0)編輯 收藏

             1 /* Accepted 1113 C++ 00:00.00 832K */
             2 #include <iostream>
             3 
             4 using namespace std;
             5 
             6 int main()
             7 {
             8     cout << "n e" << endl
             9          << "- -----------" << endl;
            10     
            11     cout.setf(ios_base::showpoint);
            12     cout.setf(ios_base::fixed);
            13     
            14     double e = 0;
            15     for(int n = 0; n < 10; n++)
            16     {
            17         int i = 1;
            18         for(int k = 1; k <= n; k++)
            19             i *= k;
            20         e += 1.00 / i;
            21         cout << n << ' ';
            22         if(n < 2)
            23         {
            24             cout << int(e) << endl;;
            25             continue;
            26         }
            27         if(n == 2)
            28             cout.precision(1);
            29         if(n == 3)
            30             cout.precision(9);
            31         cout << e << endl;
            32     }
            33     
            34     return 0;
            35 }
            36 

            posted @ 2008-04-06 20:33 superman 閱讀(367) | 評(píng)論 (0)編輯 收藏

            Official Solution:

            Problem G: Phylogenetic Trees Inherited

            The first thing to observe is that the different positions in every sequence are independent of each other. This reduces the tree of sequences to a tree of amino acids. At the root of the tree, or for that matter of any sub-tree, there may be many possible amino acids leading to optimal costs. Suppose, you have calculated for two sub-trees Tl and Tr the sets of amino-acids leading to optimal costs Al and Ar. Adjacent sub-trees Tl and Tr have as their father the node T. Now you want to find the set of amino-acids A that you can mark T with, leading to optimal costs for T.

            There are two cases: if the intersection of Al with Ar is non-empty, define A as just this intersection, otherwise define A to be the union of Al and Ar. To see why this is true, observe the extra costs you get, when you assemble T from Tl and Tr. In the first case, you have 0 extra costs when you take an amino-acid from the intersection, but 1 or 2 extra costs when you do not. In the second case, you have 1 extra costs when you take an amino-acid from the union, but 2 extra-costs when you do not. Now, you may want to assemble T not from Tl and Tr but from some other sub-optimal trees. As you can easily verify, this leads to sub-optimal costs for T as well.

            This reasoning is carried over straightforwardly to an induction proof and leads to a dynamic programming solution. Since the amino-acids are upper-case letters, you can represent sets of amino-acids as ints. The set operations you need are then easily performed as bitwise and respectively or. Whenever you do a union operation, your costs increase by 1.

            Another, more straight-forward solution is to calculate for each node of the tree the optimal costs for every amino acid the node can be marked with. This is done by trying every possible combination of amino acids for the two sub-trees, assuming their optimal costs have already been calculated. Since this solution might turn out to be too inefficient, it can be improved upon by observing that a father node always can be marked with either the left or the right son's amino-acid - there is no need to take an amino acid that differs from both.

            Judges' test data was constructed from a test-case with a few long sequences, a test-case with many short sequences, a test-case where every possible pair of amino-acids occured, and 100 random-generated test-cases where length and number of sequences are geometrically distributed. The total number of test-cases is 110. Since there may be multiple correct answers for the test cases, a special verification program was written by slightly modifying the judges' solution.


             1 /* Accepted 1102 C++ 00:00.56 1040K */
             2 #include <string>
             3 #include <iostream>
             4 
             5 using namespace std;
             6 
             7 int main()
             8 {
             9     int n, l;
            10     while((cin >> n >> l) && n && l)
            11     {
            12         int heap[2048], cost = 0;
            13         string seq[1024];
            14         
            15         for(int i = 0; i < n; i++)
            16             cin >> seq[i];
            17         
            18         for(int i = 0; i < l; i++)
            19         {
            20             for(int k = 0; k < n; k++)
            21                 heap[n + k] = 1 << (seq[k][i] - 'A');
            22             for(int k = n - 1; k >= 1; k--)
            23                 if((heap[k] = heap[2 * k] & heap[2 * k + 1]) == 0)
            24                 {
            25                     cost++;
            26                     heap[k] = heap[2 * k] | heap[2 * k + 1];
            27                 }
            28             char c = 'A';
            29             while(heap[1>>= 1)
            30                 c++;
            31             cout << c;
            32         }
            33         cout << ' ' << cost << endl;
            34     }
            35     
            36     return 0;
            37 }
            38 

            posted @ 2008-04-06 11:13 superman 閱讀(432) | 評(píng)論 (0)編輯 收藏

             1 /* Accepted 1151 C++ 00:00.84 844K */
             2 #include <cstdio>
             3 #include <string>
             4 #include <iostream>
             5 
             6 using namespace std;
             7 
             8 int main()
             9 {
            10     int n, m;
            11     string word;
            12     
            13     cin >> n;
            14     while(n--)
            15     {
            16         cin >> m;
            17         
            18         while(m)
            19         {
            20             cin >> word;
            21             for(int i = word.size() - 1; i >= 0; i--)
            22                 cout << word[i];
            23             if(getchar() == '\n')
            24             {
            25                 m--;
            26                 cout << endl;
            27             }
            28             else
            29                 cout << ' ';
            30         }
            31         
            32         if(n)
            33             cout << endl;
            34     }
            35     
            36     return 0;
            37 }
            38 

            posted @ 2008-04-05 20:23 superman 閱讀(725) | 評(píng)論 (0)編輯 收藏

            僅列出標(biāo)題
            共19頁(yè): First 11 12 13 14 15 16 17 18 19 
            精品多毛少妇人妻AV免费久久| 国产一区二区久久久| av无码久久久久久不卡网站 | 国产精品美女久久福利网站| 久久精品综合网| 亚洲精品无码成人片久久| 久久国产精品久久久| 久久亚洲精品国产精品婷婷| 久久精品亚洲精品国产色婷| 欧美亚洲另类久久综合婷婷| 久久精品午夜一区二区福利| 一本色综合久久| 国产精品嫩草影院久久| 亚洲乱码中文字幕久久孕妇黑人| 国内精品欧美久久精品| 97热久久免费频精品99| 久久久无码精品亚洲日韩京东传媒 | 狠狠色丁香婷婷综合久久来来去| 无码精品久久久天天影视| 人妻无码精品久久亚瑟影视| 精品久久久久中文字幕日本| 久久久精品人妻一区二区三区蜜桃| 久久这里只精品国产99热| 久久久久亚洲AV无码网站| 人妻无码精品久久亚瑟影视| 久久无码人妻精品一区二区三区 | 免费精品99久久国产综合精品| 国产偷久久久精品专区| 久久综合鬼色88久久精品综合自在自线噜噜| 精品永久久福利一区二区| 亚洲色大成网站www久久九| 精品人妻久久久久久888| 精品久久久无码人妻中文字幕| 无码乱码观看精品久久| 久久影视国产亚洲| 热久久国产欧美一区二区精品| 久久高潮一级毛片免费| 免费一级欧美大片久久网| 青青热久久国产久精品 | 精品久久久久久无码中文字幕一区| 亚洲精品乱码久久久久久中文字幕 |