Chess Queen UVA - 11538 题意：给你n,m,然后问你在n*m棋盘中，两个皇后有多少种对抗位置（在同一行，同一列，同一对角线）。 这一题 wa了几发，因为其中的for循环中i要为longlong
Triangle Counting UVA - 11401 题意：给你n，然后问你从1到n种选3个数，能组成多少个不同的三角形（至少有一边不同）。
列了一个表 如果最小的边为1，那么不会有三角形 最小的边为2， 其次是3，就有一个三角形（4），比3大，比5小 其次是4，就有一个三角形（5），比4大，比6小 其次是5，就有一个三角形（6） ……. 最小的边为3， 其次是4，就有2个三角形 其次是5，就有2个三角形 ……. 最小的边为4 其次是5，就有3个三角形 其次是6，就有3个三角形 … 所以，我就可以枚举最小边，从2开始，到n-2。算出三角形的个数
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <vector> using namespace std; #define LL long long int main() { int n; while(scanf("%d",&n)!=EOF) { if(n<3) break; LL ans=0,t=0; for(LL i=2;i<=n-2;i++) { t+=i-2; int a=n-i-1-(i-1-1); LL temp; if(n-i-1<0) break;//这里不加的话会TLE if(a>=1) temp=a*(i-1)+t; else temp=(n-i-1)*(n-i)/2; ans+=temp; } printf("%lld\n",ans); } return 0; }卡时间过的。。
书上介绍了一种方法,c(x):以 x为最大边的三角形的数量。然后就可以打表将答案存起来用O（1）查询。
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <vector> using namespace std; #define LL long long const LL maxn = 1000010; LL f[maxn]; int main() { LL n; f[3]=0; for(LL i=4;i<=1000000;i++) f[i]=((i-1)*(i-2)/2-(i-1)/2)/2+f[i-1]; while(scanf("%lld",&n)!=EOF) { if(n<3) break; printf("%lld\n",f[n]); } return 0; }Cheerleaders UVA - 11806
题目有点难懂。其实就是有k个物品，然后第一行，最后一行，第一列，最后一列都要至少放一个物品。 用容斥原理+二进制枚举 设A为第一行不放物品，B为最后一行不放物品，C为第一列不放物品，D为最后一列不放物品。然后用容斥原理
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <vector> using namespace std; #define LL long long const LL maxn =505; #define MOD 1000007 LL C[maxn][maxn]; void init() { C[0][0]=1; for(int i=1;i<=400;i++) { C[i][0]=C[i][i]=1; for(int j=1;j<i;j++) { C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD; } } } int main() { int t; scanf("%d",&t); init(); int case1=1; while(t--) { int n,m,k; while(scanf("%d %d %d",&n,&m,&k)!=EOF) { printf("Case %d: ",case1++); if(k>m*n) printf("0\n"); else { LL sum=0; for(int i=0;i<16;i++)// { int b=0,r=n,c=m; for(int j=0;j<4;j++) { if(i&(1<<j)) { if(j%2) r--; else c--; b++; } } if(b%2) sum=(sum-C[r*c][k]+MOD)%MOD;// else sum=(sum+C[r*c][k])%MOD; } printf("%lld\n",sum); } } } return 0; }