首页 > 代码库 > 20140708总结
20140708总结
今天的题还是比较水的。。涨自信？
第一题。。显而易见的dp：dp[i][j][k][l][m]:表示i位，j个1，k是否顶上界，l个前导零，是否仍在前导零上。转移方程比较复杂，详见代码。
第二题比较复杂，大意就是把[ai，bi] 作为区间，落在[1，N]上，互不重叠，长度互不相等。然后dp[j][k]表示在i位，选了k个，其和为j。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 long long dp[50][50][2][50][2]; 6 long long work(long long x) 7 { 8 long long top[200]; 9 memset(dp,0,sizeof(dp));10 memset(top,0,sizeof(top));11 long long i=1;12 long long j=1;13 if(x==0) return 0;14 while(x/j)15 {16 i++;17 j*=2;18 }19 if(i)20 i--;21 long long n=i;22 while(x)23 {24 top[i]=x%2;25 x/=2;26 i--;27 }28 // for(int i=1;i<=n;i++)29 // cout<<top[i];30 // cout<<endl<<endl;31 dp[1][0][1][0][0]=1;32 // for(int i=1;i<=n;i++)33 // cout<<top[i];34 // cout<<endl;35 for(i=1;i<=n;i++)36 for(j=0;j<=n/2;j++)37 for(int k=0;k<=n;k++)38 {39 dp[i+1][j][0][k+1][0]+=dp[i][j][0][k][0];40 dp[i+1][j+1][0][k][1]+=dp[i][j][0][k][0];41 if(top[i]==0)42 dp[i+1][j][1][k+1][0]+=dp[i][j][1][k][0];43 else44 {45 dp[i+1][j][0][k+1][0]+=dp[i][j][1][k][0];46 dp[i+1][j+1][1][k][1]+=dp[i][j][1][k][0];47 }48 for(long long l=0;l<=1;l++)49 dp[i+1][j+l][0][k][1]+=dp[i][j][0][k][1];50 for(long long l=0;l<=top[i];l++)51 dp[i+1][j+l][l==top[i]][k][1]+=dp[i][j][1][k][1];52 // cout<<dp[i][j][up]<<endl;53 }54 long long ans=0;55 for(int k=0;k<=n;k++)56 for(int i=1;i<=(n-k)/2;i++)57 {58 ans+=dp[n+1][i][0][k][1]+dp[n+1][i][1][k][1];59 }60 61 // for(int j=1;j<=n+1;j++)62 // for(int k=0;k<=n;k++)63 // for(int i=1;i<=n;i++)64 // cout<<dp[j][i][0][k][1];65 return ans;66 }67 void work()68 {69 freopen("testA.in","r",stdin);70 freopen("testA.out","w",stdout);71 long long L,R;72 cin>>L>>R;73 if(L==1)74 cout<<work(R)<<endl;75 else76 cout<<work(R)-work(L-1)<<endl;77 // cout<<work(R)<<" "<<work(L-1)<<endl;78 }79 int main()80 {81 work();82 return 0;83 }
然后答案就是
，详见标程代码（我还没有写出来）。
1 #include <map> 2 #include <set> 3 #include <queue> 4 #include <stack> 5 #include <cctype> 6 #include <cstdio> 7 #include <string> 8 #include <vector> 9 #include <cstring>10 #include <iostream>11 #include <algorithm>12 using namespace std;13 14 typedef long long LL;15 typedef pair<int, int> PII;16 17 const int N = 1005;18 const int mod = 1000000007;19 int f[N][N];20 int c[N][N];21 LL fact[N];22 23 inline void add(int &x, int y) {24 x += y;25 if (x >= mod)26 x %= mod;27 }28 29 int main() {30 31 freopen("testB.in","r",stdin);32 freopen("testB.out","w",stdout);33 f[0][0] = f[0][1] = 1;34 for (int d = 1; d < N - 1; d++)35 for (int i = N - 1; i >= d; i--)36 for (int j = min(d + 1, 50); j > 0; j--)37 add(f[i][j], f[i - d][j - 1]);38 39 for (int i = 0; i < N; i++) {40 c[i][0] = c[i][i] = 1;41 for (int j = 1; j < i; j++) {42 c[i][j] = c[i - 1][j - 1] + c[i - 1][j];43 if (c[i][j] >= mod)44 c[i][j] -= mod;45 }46 }47 fact[0] = 1;48 for (int i = 1; i < N; i++)49 fact[i] = fact[i - 1] * i % mod;50 51 int T;52 scanf("%d", &T);53 while (T--) {54 int n, k;55 scanf("%d%d", &n, &k);56 if (n < k)57 puts("0");58 else {59 LL ans = 0;60 for (int x = 0; x <= n - k; x++) {61 LL s = (LL)c[n - x][k] * f[x][k] % mod;62 ans += s;63 if (ans >= mod)64 ans -= mod;65 }66 printf("%I64d\n", ans * fact[k] % mod);67 }68 }69 return 0;70 }
第三题比较水，我就不多说什么了，多特判就好了。。
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int main() 5 { 6 freopen("testC.in","r",stdin); 7 freopen("testC.out","w",stdout); 8 int n,m,x; 9 cin>>n>>m>>x;10 if(x<0)11 {12 cout<<0<<endl;13 return 0;14 }15 if(x==0)16 {17 cout<<n*m/2<<endl;18 return 0;19 }20 x-=1;21 n-=2*x;22 m-=2*x;23 if(n<=0||m<=0)24 cout<<0<<endl;25 else if(n==1||m==1)26 cout<<n*m-n*m/2<<endl;27 else28 cout<<(n+m)-2<<endl;29 return 0;30 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。