欧美色偷偷大香,亚洲欧美中日韩,国产欧美精品日韩

對于蝸牛來說，狂奔雖不代表極速，但展現的卻是一種拼盡全力的姿態........

pku 3252

2009年10月29日星期四

題目鏈接：PKU 3252 Round Numbers

分類：排列組合+區間計數

題目分析與算法原型
這道題目總的來說不是太難，但是實現起來細節比較多，所以WA了好多次，大致思路是，給你的兩個數，start和end ，分別求出1到start，以及1到end之間（包括start和end自身）的round number 的個數，然后兩個相減一下，就差不多是要求的數，當然了還需判斷一下start是不是也是round number是的話剛才減的結果還要加1。假設現在給你的數是a,那么求1到a之間的round number可以分兩步來進行，先求出a在二進制下的位數m，然后求出1到m-1位的二進制數的round number的和（這個不難，只是排列組合的計算），第二步就是要加上，二進制位數為m但《=a的所有二進制數中round number的個數。其實可以這樣考慮，設一個二進制數為101001100，那么從100000000到其之間的round number的數的個數可以這樣考慮，從第二位開始左往右掃描，碰到為1的時候將其變為0，然后此位后的位數任意組合的數都肯定小于原來的數，枚舉這個情況下（先記下當前0和1的個數，方便計算剩下的位數組合中round number的數目）的round number數目，然后繼續掃描一直到最后。
PS：此題代碼實現的有些繁瑣，有待改進..........

Code：

1

#include<stdio.h>
2

int x[35];
3

int cal(int m,int a)
4

{
5

int i,j=1,res=1;
6

for(i=m-1;i>=m-a;i--)
7

{
8

res*=i;
9

res/=j;
10

j++;
11

}
12

return res;
13

}
14

int num(int m)
15

{
16

int k,i,res=0;
17

if(m%2==0)k=m/2;
18

else k=m/2+1;
19

20

for(i=k;i<m;i++)res+=cal(m,i);
21

return res;
22

}
23

int check(int n)
24

{
25

int res=0,i,num=0,y[35];
26

int nn=n;
27

while(nn)
28

{
29

y[res++]=nn%2;
30

nn/=2;
31

}
32

for(i=0;i<res;i++)
33

if(y[i]==0)num++;
34

else num--;
35

36

if(num>=0)return 1;
37

else return 0;
38

}
39

int weishu(int n)
40

{
41

int res=0,y[35];
42

43

int nn=n;
44

while(nn)
45

{
46

y[res++]=nn%2;
47

nn/=2;
48

}
49

return res;
50

}
51

int jisuan(int n)
52

{
53

int k,i,j,y[35],num=0;
54

55

int nn=n;
56

while(nn)
57

{
58

y[num++]=nn%2;
59

nn/=2;
60

}
61

k=num/2-1;
62

for(i=0;i<=k;i++)
63

{
64

int t=y[i];
65

y[i]=y[num-1-i];
66

y[num-1-i]=t;
67

}
68

int num1=1,num0=0,ss,kk,res=0;
69

for(i=1;i<num;i++)
70

{
71

if(y[i]==1)
72

{
73

num0++;
74

ss=num-i-1;
75

76

if(ss+num1-num0<0)kk=0;
77

else
78

{
79

if((ss+num1-num0)%2==0)kk=(ss+num1-num0)/2;
80

else kk=(ss+num1-num0)/2+1;
81

}
82

if(kk<ss)
83

{
84

int mm,q,ii;
85

for(ii=kk;ii<=ss;ii++)
86

{
87

mm=1;
88

if(ii==0)res+=1;
89

else
90

{
91

q=1;
92

for(j=ss;j>ii;j--)
93

{
94

mm*=j;
95

mm/=q;
96

q++;
97

}
98

res+=mm;
99

}
100

}
101

}
102

else if(kk==ss)
103

{
104

res+=1;
105

}
106

107

num0--;
108

num1++;
109

}
110

else num0++;
111

112

if(i==num-1&&num0>=num1)res++;
113

}
114

return res;
115

}
116

int main()
117

{
118

int i,s,f;
119

x[1]=0;
120

for(i=2;i<=33;i++)x[i]=x[i-1]+num(i);
121

while(scanf("%d%d",&s,&f)!=EOF)
122

{
123

int a=weishu(s),b=weishu(f),ans=0,c,d;
124

c=jisuan(s);
125

c+=x[a-1];
126

d=jisuan(f);
127

d+=x[b-1];
128

ans=d-c;
129

if(check(s))ans++;
130

printf("%d\n",ans);
131

}
132

return 0;
133

}
134

posted on 2009-10-29 16:06 蝸牛也Coding 閱讀(343) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

<

2009年7月

>

日

一

二

三

四

五

六

28

29

30

1

2

3

4

5

6

7

8

9

10

11

14

16

20

22

27

28

29

30

31

1

2

3

4

5

6

7

8

統計

隨筆 - 78
文章 - 0
評論 - 96
引用 - 0

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

積分 - 95166
排名 - 261

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

pku 3252

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜