| UVA - 11538 |
题意：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=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';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-)*n+*n*(n-)*(*m-n-)/;
printf("%lld\n",ans);
} return ;
}
| UVA - 11401 |
题意：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+;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
ll f[N],n;
void dp(){
f[]=;
for(ll i=;i<=1e6;i++)
f[i]=f[i-]+((i-)*(i-)/-(i--i/))/;
}
int main(int argc, const char * argv[]) {
dp();
while((n=read())>=){
printf("%lld\n",f[n]);
}
return ;
}
| UVA - 11806 |
题意：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=,MOD=;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int T,n,m,k,f[N][N];
void init(){
f[][]=;
for(int i=;i<=;i++){
f[i][]=f[i][i]=;
for(int j=;j<i;j++) f[i][j]=(f[i-][j]+f[i-][j-])%MOD;
}
}
int main(int argc, const char * argv[]) {
init();
T=read();int cas=;
while(T--){cas++;
n=read();m=read();k=read();
int ans=;
for(int S=;S<;S++){
int b=,r=n,c=m;
if(S&) r--,b++;
if(S&) r--,b++;
if(S&) c--,b++;
if(S&) c--,b++;
if(b&) ans=(ans-f[r*c][k]+MOD)%MOD;
else ans=(ans+f[r*c][k])%MOD;
}
printf("Case %d: %d\n",cas,ans);
} return ;
}