Codeforces Round #267 (Div. 2)

题意：给出n对a,b,问有多少对a-b>=2

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath> 
 5 #include<stack>
 6 #include<vector>
 7 #include<map> 
 8 #include<queue> 
 9 #include<algorithm>  
10 #define mod=1e9+7;
11 using namespace std;
12 
13 typedef long long LL;
14 
15 int main(){
16     int n,a,b,ans=0;
17     scanf("%d",&n);
18     while(n--){
19         scanf("%d %d",&a,&b);
20         if((b-a)>=2) ans++;
21     }
22     
23     printf("%d
",ans);
24     return 0;
25 }

View Code

题意：给出m+1个数，给出k，求在前m个数里面与第m+1个数表示成二进制时，不相同的位数小于等于k的个数

翻的别人的代码，看怎么算二进制的位数不同的，发现一个函数 __builtin_popcount() 计算一个32位无符号整数共有多少个1 http://www.cnblogs.com/avema/p/3774294.html

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath> 
 5 #include<stack>
 6 #include<vector>
 7 #include<map> 
 8 #include<set>
 9 #include<queue> 
10 #include<algorithm>  
11 #define mod=1e9+7;
12 using namespace std;
13 
14 typedef long long LL;
15 const int maxn=1000+5;
16 int a[maxn];
17 
18 int main(){
19     int n,m,k,i,j,ans=0;
20     cin>>n>>m>>k;
21     for(i=0;i<=m;i++) {
22         cin>>a[i];
23     }
24     
25     for(i=0;i<m;i++){
26         ans+= __builtin_popcount(a[i]^a[m])<=k;
27     }
28     cout<<ans<<"
";
29     return 0;
30 }

View Code

题意：给出n个数，求将这n个数划分为k块，长度为m的区间的最大值

用dp[i][j]表示前i个数划分成j块的最大值

dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+sum[i]-sum[i-m])

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath> 
 5 #include<stack>
 6 #include<vector>
 7 #include<map> 
 8 #include<set>
 9 #include<queue> 
10 #include<algorithm>  
11 #define mod=1e9+7;
12 using namespace std;
13 
14 typedef long long LL;
15 const int maxn=5000+5;
16 LL num[maxn],dp[maxn][maxn];
17 
18 int main(){
19     int n,m,i,j,k;
20     cin>>n>>m>>k;
21     for(i=1;i<=n;i++){
22         cin>>num[i];
23         num[i]+=num[i-1];
24     }
25     
26     for(i=1;i<=n;i++){
27         for(j=1;j<=k;j++){
28             dp[i][j]=dp[i-1][j];
29             if(i>=m)
30             dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+num[i]-num[i-m]);
31             
32         //    printf("dp[%d][%d]=%d
",i,j,dp[i][j]);
33         }
34     }
35     printf("%I64d
",dp[n][k]);
36     return 0;    
37 }

View Code

B的二进制不懂写= = C搜了题解后，是背包= =

真是挫----爆----了 go---g0---go----