首页 > 代码库 > UVA计数方法练习[3]
UVA计数方法练习[3]
| UVA - 11538 Chess Queen |
题意：n*m放置两个互相攻击的后的方案数
分开讨论行 列 两条对角线
一个求和式
可以化简后计算
//// main.cpp// uva11538//// Created by Candy on 24/10/2016.// Copyright © 2016 Candy. All rights reserved.//#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;typedef long long ll;inline ll read(){ char c=getchar();ll x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}ll n,m;int main(int argc, const char * argv[]) { while((n=read())){ m=read(); if(n>m) swap(n,m); ll ans=m*(m+n-2)*n+2*n*(n-1)*(3*m-n-1)/3; printf("%lld\n",ans); } return 0;}
| UVA - 11401 Triangle Counting |
题意：1到n选三个不相同的数组成三角形的方案数
考虑以i为最大边的三角形，i-y<z<i
(i-1)*(i-2)/2 再减去剩下y==z的情况,i/2+1....i-1都可以相等
//// main.cpp// uva11401//// Created by Candy on 24/10/2016.// Copyright © 2016 Candy. All rights reserved.//#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const int N=1e6+5;typedef long long ll;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}ll f[N],n;void dp(){ f[3]=0; for(ll i=4;i<=1e6;i++) f[i]=f[i-1]+((i-1)*(i-2)/2-(i-1-i/2))/2;}int main(int argc, const char * argv[]) { dp(); while((n=read())>=3){ printf("%lld\n",f[n]); } return 0;}
| UVA - 11806 Cheerleaders |
题意：n*m放k个石子，第一行最后一行第一列最后一列都要有
没有的话很好求就是个组合数
二进制枚举集合，利用容斥原理的变式奇负偶正
//// main.cpp// uva11806//// Created by Candy on 24/10/2016.// Copyright © 2016 Candy. All rights reserved.//#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const int N=505,MOD=1000007;typedef long long ll;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int T,n,m,k,f[N][N];void init(){ f[0][0]=1; for(int i=1;i<=500;i++){ f[i][0]=f[i][i]=1; for(int j=1;j<i;j++) f[i][j]=(f[i-1][j]+f[i-1][j-1])%MOD; }}int main(int argc, const char * argv[]) { init(); T=read();int cas=0; while(T--){cas++; n=read();m=read();k=read(); int ans=0; for(int S=0;S<16;S++){ int b=0,r=n,c=m; if(S&1) r--,b++; if(S&2) r--,b++; if(S&4) c--,b++; if(S&8) c--,b++; if(b&1) ans=(ans-f[r*c][k]+MOD)%MOD; else ans=(ans+f[r*c][k])%MOD; } printf("Case %d: %d\n",cas,ans); } return 0;}
UVA计数方法练习[3]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。