• <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
            国产综合久久久久| 91精品婷婷国产综合久久| 精品国产日韩久久亚洲| 人妻无码αv中文字幕久久琪琪布| 国内精品综合久久久40p| 人妻精品久久久久中文字幕一冢本| 久久国产精品无码HDAV| 久久中文精品无码中文字幕| 亚洲精品蜜桃久久久久久| 久久久青草久久久青草| 久久笫一福利免费导航| 91精品婷婷国产综合久久| 色8久久人人97超碰香蕉987| 99久久精品无码一区二区毛片 | WWW婷婷AV久久久影片| 国产精品日韩欧美久久综合| 亚洲国产精品无码久久久不卡| 国产精品亚洲美女久久久| 囯产精品久久久久久久久蜜桃| 久久久久久A亚洲欧洲AV冫| 久久偷看各类wc女厕嘘嘘| 97香蕉久久夜色精品国产| 国产伊人久久| 久久免费视频观看| 色婷婷综合久久久久中文| 亚洲日本久久久午夜精品| 久久婷婷色综合一区二区| 国产精品久久久久久久午夜片| 精品久久久久久久久午夜福利| 少妇无套内谢久久久久| 亚洲人成无码久久电影网站| 久久99精品久久久久久水蜜桃| 国产午夜精品理论片久久影视| 人妻久久久一区二区三区| 婷婷综合久久中文字幕蜜桃三电影| 欧美精品丝袜久久久中文字幕| 久久久久香蕉视频| 亚洲国产成人精品女人久久久| 香蕉久久久久久狠狠色| 久久久久国产精品嫩草影院| 老男人久久青草av高清|