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

            bon

              C++博客 :: 首頁 :: 聯系 :: 聚合  :: 管理
              46 Posts :: 0 Stories :: 12 Comments :: 0 Trackbacks

            常用鏈接

            留言簿(2)

            我參與的團隊

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            PKU 2941
            這道題需要動一下腦筋,屬于數學題。
            問題描述:給一個n×n的矩陣,如果從每行各拿出一個元素,且這些元素的列指標都不同,即



            其中的一個排列。
            如果任何這樣一個元素的和都相等,則稱這個矩陣是homogeneous的。

            題目要求任給一個n維矩陣,1<=n<=1000,判斷它是否是homogeneous的。

            如果直接做,即求出所有的然后求和,這樣的復雜度為n!,這是無法接受的。

            下面給出一個算法,能在時間內判斷出來。設n維矩陣A,現為A加上一行跟一列,使A變成n+1維的。



            Theorem 1 

            若n維矩陣A是homogeneous的,則劃去A的任一行與任一列,剩下的n-1維矩陣是homogeneous的。

            Proof
            設劃去的是第x行第y列,剩下的矩陣若不是homogeneous的,則存在,這兩個序列的和不等,那么都加上,可以得到矩陣A的兩個序列,這兩個序列的和不等,即A不是homogeneous的,與假設矛盾。

            Theorem 2
            若Homogeneous的A增廣后的矩陣B是Homogeneous的,則對于A中任意元素 ,必有

            Proof
            這個等式的意義是在A取元素,在新矩陣取,其余任取,這么一個序列的和必須等于在新矩陣中取,其余任取所得的序列的和。注意到任取那部分是在A劃去行i,列j后的子矩陣中取的。由于B是Homogeneous,任何合法序列的和都相等,若題設的等式不成立,則任取這一部分也不相等(這樣才可能使得所有B包含的序列的和都相等)。但A是Homogeneous的,任取這一部分不可能不等,矛盾。

            有了上面的定理2,算法就很簡單,看下面的代碼:

             1 #include <iostream>
             2 
             3 using namespace std;
             4 
             5 int a[1001][1001];
             6 
             7 int main()
             8 {
             9     int i,j,k,n;
            10     while(scanf("%d",&n) && n!=0){
            11         for(i=0;i<n;i++for(j=0;j<n;j++) scanf("%d",&a[i][j]);
            12         int flag=0;
            13         for(i=1;i<&& !flag;i++){
            14             for(j=0;j<&& !flag;j++){
            15                 for(k=0;k<&& !flag;k++){
            16                     if(a[i][i]+a[j][k] != a[i][k]+a[j][i]) flag=1;
            17                 }
            18             }
            19         }
            20         if(flag==1) printf("not homogeneous\n");
            21         else printf("homogeneous\n");
            22     }
            23     return 1;
            24 }
            posted on 2008-03-14 16:34 bon 閱讀(433) 評論(0)  編輯 收藏 引用 所屬分類: Programming Contest
            Google PageRank 
Checker - Page Rank Calculator
            久久人人爽人人爽人人爽| 亚洲国产精品成人久久蜜臀 | 久久99精品国产自在现线小黄鸭| 久久国产视屏| 国内精品久久久久影院亚洲| 中文字幕无码精品亚洲资源网久久| 新狼窝色AV性久久久久久| 国产成人综合久久综合| 久久这里只有精品视频99| 亚洲精品无码久久久久AV麻豆| 国产偷久久久精品专区| 久久被窝电影亚洲爽爽爽| 日韩久久久久中文字幕人妻| 中文字幕乱码久久午夜| 99久久综合狠狠综合久久| 久久人人爽人人爽人人片AV麻烦| 一本久久a久久精品综合夜夜 | 深夜久久AAAAA级毛片免费看| 久久久久久久精品成人热色戒| 精品久久久久久国产| 久久www免费人成看片| 久久精品女人天堂AV麻| 成人综合伊人五月婷久久| 久久99九九国产免费看小说| 久久免费高清视频| 久久精品中文字幕无码绿巨人| 一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区 | 国产69精品久久久久9999| 久久亚洲AV成人无码电影| 欧美亚洲另类久久综合婷婷| 狠狠干狠狠久久| 久久精品国产亚洲AV麻豆网站| 亚洲精品99久久久久中文字幕| 国产精品久久久久乳精品爆| 久久91亚洲人成电影网站| 国产精品99久久免费观看| 久久人人妻人人爽人人爽| 亚洲va中文字幕无码久久不卡| 久久精品无码一区二区WWW| 久久婷婷国产剧情内射白浆| 国产成人综合久久精品红|