NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2011國中組初賽
 E、守塔新武器

作者 主題: E、守塔新武器  (閱讀 2248 次)

joe59491

  • 初級會員
  • **
  • 文章數: 30
  • qazwsxedcrfvtg14
    • 檢視個人資料
E、守塔新武器
« 於: 十一月 26, 2011, 08:19:34 pm »

這題勒...就先用1+2+4+8...加到超過,再從最大的值加回來,加到剛好時就跳出(注意long long int)。

程式碼:
代碼: [選擇]
#include <iostream>
#include <stdio.h>
#include <string>
#include <stdlib.h>
using namespace std;
int map[200000];
int main(){
    int a,b,c,d,e,f,g,h,i,j,k;
    long long lld,ld;
    string s,ss;
    scanf("%d",&a);
    for(c=0;c<a;c++){
    scanf("%I64d",&lld);
    //scanf("%lld",&lld);    //這是zerojudge上用的
    long long int l;
    ld=0;i=0;
for(l=1;l<99999999999LL;l*=2){i++;
    ld+=l;
if(ld>lld){i--;ld-=l;break;}
}
    for(;l>=1LL;l/=2){
for(k=0;k<10000;k++){
ld+=l;i++;
if(ld>lld){i--;ld-=l;break;}
}
}
printf("%d\n",i);
}
   return 0;
}
« 上次編輯: 十二月 05, 2011, 11:12:29 pm 由 joe59491 »
記錄
(\ (\
(^_^) --by joe59491

lfs92002

  • 新手
  • *
  • 文章數: 4
    • 檢視個人資料
Re: E、守塔新武器
« 回覆 #1 於: 十二月 09, 2011, 01:16:48 pm »

這題除了硬爆以外還有其他想法
ex.101
101=1*101
     =1*1+2*50
     =1*1+2*2+4*24
     =1*1+2*2+4*2+8*11
     =1*1+2*2+4*2+8*1+16*5
     =1*1+2*2+4*2+8*1+16*1+32*2
     ∴1+2+2+1+1+2=9次
這樣用到了"兩兩合併"的思維
用數學式表達
H=20*n0+21*n1......+2x*nx
(1≦nx≦2 ,nx為正整數)
求S(n) min
附上程式碼以供參考
代碼: [選擇]
#include<iostream>
using namespace std;
long long int pow2[35]={1,2};
short T,p;
long int H,s;
int main()
{
for(int x=1;x<35;x++)
pow2[x]=pow2[x-1]*2;
cin>>T;
while(T--)
{
cin>>H;
p=s=0;
while(H!=0)
{
H-=pow2[p];
s++;
if(H%pow2[p+1]!=0)
{
H-=pow2[p];
s++;
}
p++;
}
cout<<s<<endl;
}
return 0;
}
記錄

skipper

  • 初級會員
  • **
  • 文章數: 28
    • 檢視個人資料
Re: E、守塔新武器
« 回覆 #2 於: 十一月 05, 2012, 11:41:15 am »

n = a[0] * 2^0 + a[1] * 2 ^1 +a[2] * 2 ^2 + ....
a:{1,2}=>a:{0,1}
n 先減掉跟他最靠近比她小的的 2^m -1
p = n - (2^m -1) = n- 2^(log(n)+1
再計算p的2進位表示法有幾個1即可

1(1): 1             1
2(2): 1+1          1...1
3(2): 1+2         11...0
4(3): 1+1+2         11...1
5(3): 1+2+2         11...10
6(4): 1+1+2+2      11...11
7(3): 1+2+4         111...0
8(4): 1+1+2+4      111...1
9(4): 1+2+2+4      111...10

2*1 = 1*2, 10=02
  10 =>   02   =>#2
 100 =>  012   =>#3
1000 => 0112   =>#4
5:    101 =>   021
9:   1001 =>  0121
17: 10001 => 01121
   10101 => 10021 => 1221
29:   11101 => 11021 => 10221 => 02221
987651432: 111010110111100101110101101000

111010110111100101110101101000
111010110111100101110101100112
111010110111100101110101012112
111010110111100101110100212112
111010110111100101110012212112
111010110111100101101212212112
111010110111100101021212212112
111010110111100100221212212112
111010110111100012221212212112
111010110111011212221212212112
111010110110211212221212212112
111010110102211212221212212112
111010110022211212221212212112
111010101222211212221212212112
111010021222211212221212212112
111001221222211212221212212112
110121221222211212221212212112
102121221222211212221212212112
022121221222211212221212212112

11: 1
18: 2
11 + 36 = 47
代碼: [選擇]
#include <iostream>
#include <cmath>
using namespace std;
int f(int x){

long long y,z;
int b[90];
int l=0,r=0;
z=x;
while(z>0){
b[l]= z%2;
z/=2;
l++;
}
y = (long long int)pow((double)2,(l-1))-1;
if(x-y==0){

}
else{
x=x-y;
while(x>0){
r+= x%2;
x/=2;
}
}
return r+(l-1);
}
int main(){
int cases, x;
cin >> cases;
for(int i = 0;i < cases;i++){
cin >> x ;
cout << f(x) << endl;
}
return 0;
}
記錄

silithus

  • 新手
  • *
  • 文章數: 11
    • 檢視個人資料
    • 希利蘇斯的XOI筆記
Re: E、守塔新武器
« 回覆 #3 於: 八月 25, 2013, 11:08:06 pm »

我的解法:

題目大意是把一個數字分解成一串1,2,4,..2^n之和,要求每個數字至少出現一次,且數字總數最少。

分析:
把一個數字表示成二進制,若沒有0,1的數目便是答案
如:7 = 111B = (4+2+1),答案為3
  15 = 1111B = (8+4+2+1),答案為4

如果有0的話,要靠分解高位的1來覆蓋低位的0,即把2^n分解成兩個2^(n-1)
如:2 = 10B = 02(1+1),答案是2
  11 = 1011B = 0211(4+4+2+1),答案為4

當一個1被分解後,該位便變為0,因此需靠分解更高一位的1來填補
如:13 = 1101B = 1021 = 0221(4+4+2+2+1),答案為5

若有一串0,需靠把高位的1分解再分解來填補
如:8 = 1000B = 0200 = 0120 = 0112(4+2+1+1),答案為4
  75 = 1001011B = 1000211 = 0200211 = 0120211 = 0112211(32+16+8+8+4+4+2+1),答案為8

從上述的分析,可得出結論:
1. 若最低位為1,計數+1
2. 若最低位為0,且高一位為1,計數+2,高一位變為0
3. 若最低位為0,且高一位不為0,則這串序列的計數等於0的數目+1,如1000B = 3+1 = 4

把這個規律再簡化的話,可得出:
1. 若數值H的最低兩位為10,計數+2,最低兩位變為00;否則計數+1(不論最低一位是0還是1)
2. 把數值H位運算右移一位
3. 若數值H不為零,跳至step 1,否則結束

這個解法能AC全部官方測資,請多多指教!

代碼: [選擇]
#include <stdio.h>

int main(void)
{
    int T,H,cnt;

    while(scanf("%d", &T) != EOF)
    {
        while(T--) {
            scanf("%d", &H);
            cnt = 0;
            while(H) {
                if((H&0x3) == 0x2) {
                    H &= ~0x3;
                    cnt+=2;
                }
                else
                    cnt++;
                H >>= 1;
            }
            printf("%d\n", cnt);
        }
    }

    return 0;
}
« 上次編輯: 八月 25, 2013, 11:38:17 pm 由 silithus »
記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2011國中組初賽
 E、守塔新武器