• <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 1702簡單題,但思想很好。給定一些不同重量的砝碼,重為3^0, 3^1, ..., 3^19,要求用這些砝碼乘出物體的重量W,1 <= W <= (3^20-1)/2。
            形式化的描述為:
            給定W,以及砝碼重量,求出集合,使得

            移項得

            即系將W表示成一系列的3進制數的和或差。由于每個重量的砝碼只有一個,所以每個重量前面的系數只能是1,-1或0。首先將W表示為一般的3進制數,即系數允許為0,1,2,再將這個式子改寫為只含-1,0,1的式子,具體算法見下面的程序。
             1 #include <iostream>
             2 
             3 using namespace std;
             4 
             5 long a[20];
             6 int c[21];
             7 long w;
             8 void solve()
             9 {
            10     int i=19;
            11     memset(c,0,sizeof(c));
            12     while(w!=0)
            13     {
            14         c[i]=w/a[i];
            15         w%=a[i--];
            16     }
            17     for(i=0;i<=19;i++)
            18     {
            19         if(c[i]==2)
            20         {
            21             c[i]=-1;
            22             c[i+1]++;
            23         }
            24         else if(c[i]==3)
            25         {
            26             c[i]=0;
            27             c[i+1]++;
            28         }
            29     }
            30     
            31     //for(i=0;i<=19;i++) if(c[i]!=0) printf("%d ",c[i]*a[i]);
            32     //printf("\n");
            33     int flag=0;
            34     for(i=0;i<=19;i++)
            35     {
            36         if(c[i]==-1 && flag==0){printf("%d",a[i]);flag=1;}
            37         else if(c[i]==-1 && flag==1){printf(",%d",a[i]);}
            38     }
            39     if(flag==0) printf("empty");
            40     printf(" ");
            41     flag=0;
            42     for(i=0;i<=19;i++)
            43     {
            44         if(c[i]==1 && flag==0) {printf("%d",a[i]);flag=1;}
            45         else if(c[i]==1 && flag==1) printf(",%d",a[i]);
            46     }
            47     printf("\n");
            48     return;
            49 }
            50 
            51 int main()
            52 {
            53     int i,j,k;
            54     a[0]=1;
            55     for(i=1;i<=19;i++) a[i]=3*a[i-1];
            56     int t;
            57     scanf("%d",&t);
            58     while(t--)
            59     {
            60         scanf("%d",&w);
            61         solve();
            62     }
            63     return 1;
            64 }
            posted on 2008-02-12 12:43 bon 閱讀(203) 評論(0)  編輯 收藏 引用 所屬分類: Programming Contest
            Google PageRank 
Checker - Page Rank Calculator
            潮喷大喷水系列无码久久精品| 国产成人精品久久| 超级碰碰碰碰97久久久久| 国产A级毛片久久久精品毛片| 欧洲成人午夜精品无码区久久| 亚洲国产另类久久久精品黑人| 亚洲国产精品无码久久SM| 日本三级久久网| 少妇久久久久久被弄高潮| 久久青草国产精品一区| 日韩欧美亚洲国产精品字幕久久久| 97久久婷婷五月综合色d啪蜜芽| 狠狠88综合久久久久综合网| 婷婷久久综合九色综合绿巨人| 精品久久久久久国产潘金莲 | 青青青青久久精品国产| 婷婷久久精品国产| 精品久久人人做人人爽综合| 亚洲精品白浆高清久久久久久| 精品久久综合1区2区3区激情| 国产产无码乱码精品久久鸭| 久久天天躁狠狠躁夜夜不卡| 久久精品国产国产精品四凭 | 久久久久人妻一区精品| 久久99久久99精品免视看动漫| 久久久久久午夜精品| 久久久久亚洲AV成人网| 久久久综合九色合综国产| 午夜不卡久久精品无码免费| 亚洲国产视频久久| 久久精品视频一| 中文字幕无码av激情不卡久久| 久久久久噜噜噜亚洲熟女综合| 国产精品99久久久久久宅男 | 香蕉久久久久久狠狠色| 欧美一级久久久久久久大片| 久久精品国产99久久久香蕉| 久久久久国产日韩精品网站| 久久久久国产精品嫩草影院 | 久久精品aⅴ无码中文字字幕重口| 久久夜色精品国产噜噜亚洲a |