A http://acm.hust.edu.cn/vjudge/contest/view.action?cid=97654#problem/A
题意：输入12个数，输出平均值，但是不能有多余的后缀的零。直接。2f wa了一发。
解法：用sprintf 放到char【】里，然后去掉后面的0.
//#define debug
//#define txtout
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cctype>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
const double eps=1e-;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const int M=1e2+;
double a[M];
char buffer[M];
void solve(){
double sum=;
for(int i=;i<;i++){
sum+=a[i];
}
sprintf(buffer,"$%.2f",sum/);
int len=strlen(buffer);
if(buffer[len-]==''){
len--;
if(buffer[len-]==''){
len-=;
}
}
buffer[len]=;
}
int main(){
#ifdef txtout
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t;
while(~scanf("%d",&t)){
while(t--){
for(int i=;i<;i++){
scanf("%lf",&a[i]);
}
solve();
puts(buffer);
}
}
return ;
}
D http://acm.hust.edu.cn/vjudge/contest/view.action?cid=97654#problem/D
题意：给n点m边无向图，问按输入顺序依次删去第i条边后连通块的个数。
解法：倒着用并查集。
//#define debug
//#define txtout
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cctype>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
const double eps=1e-;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const int M=1e5+;
int n,m;
struct E {
int u,v;
} e[M];
int answer[M];
class UnionFindSet { ///并查集
static const int MV=1e4+; ///点的个数
int par[MV],num[MV];
void add(int son,int fa) {
par[fa]+=par[son];
par[son]=fa;
num[fa]+=num[son];
}
public:
void init(int n) {
for(int i=; i<=n; i++) {
num[i]=;
par[i]=-;
}
}
int getroot(int x) {
int i=x,j=x,temp;
while(par[i]>=) i=par[i];
while(j!=i) {
temp=par[j];
par[j]=i;
j=temp;
}
return i;
}
bool unite(int x,int y) {
int p=getroot(x);
int q=getroot(y);
if(p==q) return false;
if(par[p]>par[q]) {
add(p,q);
} else {
add(q,p);
}
return true;
}
int getnum(int id) { ///返回该点所在集合包含的点数
return num[getroot(id)];
}
} ufs;
void solve() {
int result=n;
ufs.init(n);
for(int i=m-;i>=;i--){
answer[i]=result;
if(ufs.unite(e[i].u,e[i].v)){
result--;
}
}
}
int main() {
#ifdef txtout
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
while(~scanf("%d%d",&n,&m)) {
for(int i=; i<m; i++) {
scanf("%d%d",&e[i].u,&e[i].v);
}
solve();
for(int i=; i<m; i++) {
printf("%d\n",answer[i]);
}
}
return ;
}
E http://acm.hust.edu.cn/vjudge/contest/view.action?cid=97654#problem/E
题意：求有多少个3元组abc满足 gcd（a,b,c）=G，lcm(a,b,c)=L
解法：质因数分解可以看出，gcd是3个数都有的质因子的次方的最小值，lcm是三个数的每一种质因子的次方最大值，那么lcm一定是gcd的倍数。所以不是倍数答案为0。当lcm==gcd时，只有一种，就是3个数相等。否则就是求lcm/gcd=value分配到abc的方法数。考虑value的一种质因子p，次方a，p^a，有两种情况，一种是只有一个有p，那么这个必须是p^a，这种情况有3个选择。第二种是有两个有p，那么至少一个次方是a，另一个可以1到a，所以一共有2*a种，但是两个都是a的会多算一次，所以一共2*a-1种，从3个中选出两个放p有C（3,2）种，所以最后是3+3*（2*a-1）种情况。
//#define debug
//#define txtout
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cctype>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
const double eps=1e-;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const int M=1e5+;
int G,L;
int solve(){
if(L%G) return ;
if(L==G) return ;
L/=G;
int result=;
for(int i=;i*i<=L;i++){
if(L%i) continue;
int a=;
while(L%i==){
L/=i;
a++;
}
result*=*a;
}
if(L>) result*=;
return result;
}
int main(){
#ifdef txtout
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t;
while(~scanf("%d",&t)){
while(t--){
scanf("%d%d",&G,&L);
printf("%d\n",solve());
}
}
return ;
}
G http://acm.hust.edu.cn/vjudge/contest/view.action?cid=97654#problem/G
题意：给n*m的棋盘，上面有q个点，其他位置可以放炮，就是象棋的规则，要保证最后放置的炮不能被吃，也就是不存在两个炮之间有点或者跑。
解法：dfs所有情况，每次放炮前先判一下行和列是否会被吃。
//#define debug
//#define txtout
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cctype>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
const double eps=1e-;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const int M=1e2+;
struct Q{
int x,y;
}p[M];
int n,m,q;
bool ispoint[M][M];
bool choose[M][M];
int result;
int dx[]={,,,-};
int dy[]={,-,,};
void init(){
for(int i=;i<n;i++){
for(int j=;j<m;j++){
ispoint[i][j]=false;
choose[i][j]=false;
}
}
for(int i=;i<q;i++){
ispoint[p[i].x][p[i].y]=true;
}
}
bool inside(int x,int y){
return x>=&&x<n&&y>=&&y<m;
}
bool eat(int x,int y,int d){
int tx=x+dx[d];
int ty=y+dy[d];
while(inside(tx,ty)&&!choose[tx][ty]&&!ispoint[tx][ty]){
tx+=dx[d];
ty+=dy[d];
}
if(!inside(tx,ty)) return false;
tx+=dx[d];
ty+=dy[d];
while(inside(tx,ty)&&!choose[tx][ty]&&!ispoint[tx][ty]){
tx+=dx[d];
ty+=dy[d];
}
if(!inside(tx,ty)) return false;
return choose[tx][ty];
}
bool judge(int x,int y){
for(int i=;i<;i++){
if(eat(x,y,i)) return false;
}
return true;
}
void dfs(int x,int y,int sum){
if(x==n){
result=max(result,sum);
return ;
}
if(y==m) return dfs(x+,,sum);
if(ispoint[x][y]) return dfs(x,y+,sum);
dfs(x,y+,sum);
if(judge(x,y)){
choose[x][y]=true;
dfs(x,y+,sum+);
choose[x][y]=false;
}
}
int solve(){
init();
result=;
dfs(,,);
return result;
}
int main(){
#ifdef txtout
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
while(~scanf("%d%d%d",&n,&m,&q)){
for(int i=;i<q;i++){
scanf("%d%d",&p[i].x,&p[i].y);
}
printf("%d\n",solve());
}
return ;
}
H http://acm.hust.edu.cn/vjudge/contest/view.action?cid=97654#problem/H
题意：给两堆牌，张数都为n，AB轮流拿，每次可以拿任意一堆的顶部或者底部，A先拿，AB都足够聪明，问最后A能得的最大分数。
解法：定义dp【x1】【y1】【x2】【y2】表示先手遇到 第一堆剩 x1到y1区间，第二堆剩 x2到y2区间时能得到的最大分数，答案就是dp[1][n][1][n].转移有4个，就是两堆的头尾都可以拿。比如拿a【x1】位置的牌 ，那么 就等于后手遇到了 dp【x1+1】【y1】【x2】【y2】的情况， 用后手的区间和减去后手的最大得分再加上a【x1】就是先手可能获得的得分。
//#define debug
//#define txtout
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cctype>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
const double eps=1e-;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const int M=;
int a[M];
int b[M];
int sa[M];
int sb[M];
int n;
int dp[M][M][M][M];
void init_sum(int sum[],int v[]){
sum[]=;
for(int i=;i<=n;i++){
sum[i]=sum[i-]+v[i];
}
}
void init_dp(){
for(int x1=;x1<=n;x1++){
for(int y1=;y1<=n;y1++){
for(int x2=;x2<=n;x2++){
for(int y2=;y2<=n;y2++){
dp[x1][y1][x2][y2]=-;
}
}
}
}
}
int get_sum(int x1,int y1,int x2,int y2){
int result=sa[y1]+sb[y2];
if(x1) result-=sa[x1-];
if(x2) result-=sb[x2-];
return result;
}
int dfs(int x1,int y1,int x2,int y2){
int& answer=dp[x1][y1][x2][y2];
if(answer!=-) return answer;
if(x1<y1){
answer=max(answer,a[x1]+get_sum(x1+,y1,x2,y2)-dfs(x1+,y1,x2,y2));
answer=max(answer,a[y1]+get_sum(x1,y1-,x2,y2)-dfs(x1,y1-,x2,y2));
}
if(x2<y2){
answer=max(answer,b[x2]+get_sum(x1,y1,x2+,y2)-dfs(x1,y1,x2+,y2));
answer=max(answer,b[y2]+get_sum(x1,y1,x2,y2-)-dfs(x1,y1,x2,y2-));
}
if(x1==y1&&x1){
answer=max(answer,a[x1]+get_sum(,,x2,y2)-dfs(,,x2,y2));
}
if(x2==y2&&x2){
answer=max(answer,b[x2]+get_sum(x1,y1,,)-dfs(x1,y1,,));
}
return answer;
}
int solve(){
init_sum(sa,a);
init_sum(sb,b);
init_dp();
dp[][][][]=;
for(int i=;i<=n;i++){
dp[i][i][][]=a[i];
dp[][][i][i]=b[i];
}
return dfs(,n,,n);
}
int main(){
#ifdef txtout
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t;
while(~scanf("%d",&t)){
while(t--){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=;i<=n;i++){
scanf("%d",&b[i]);
}
printf("%d\n",solve());
}
}
return ;
}
end