A http://acm.hust.edu.cn/vjudge/contest/view.action?cid=97654#problem/A
题意：输入12个数，输出平均值，但是不能有多余的后缀的零。直接。2f wa了一发。
解法：用sprintf 放到char【】里，然后去掉后面的0.
1 //#define debug 2 //#define txtout 3 #include<cstdio> 4 #include<cstdlib> 5 #include<cstring> 6 #include<cmath> 7 #include<cctype> 8 #include<ctime> 9 #include<iostream> 10 #include<algorithm> 11 #include<vector> 12 #include<queue> 13 #include<stack> 14 #include<map> 15 #include<set> 16 #define mt(a,b) memset(a,b,sizeof(a)) 17 using namespace std; 18 typedef long long LL; 19 const double eps=1e-8; 20 const double pi=acos(-1.0); 21 const int inf=0x3f3f3f3f; 22 const int M=1e2+10; 23 double a[M]; 24 char buffer[M]; 25 void solve(){ 26 double sum=0; 27 for(int i=0;i<12;i++){ 28 sum+=a[i]; 29 } 30 sprintf(buffer,"$%.2f",sum/12); 31 int len=strlen(buffer); 32 if(buffer[len-1]=='0'){ 33 len--; 34 if(buffer[len-1]=='0'){ 35 len-=2; 36 } 37 } 38 buffer[len]=0; 39 } 40 int main(){ 41 #ifdef txtout 42 freopen("in.txt","r",stdin); 43 freopen("out.txt","w",stdout); 44 #endif 45 int t; 46 while(~scanf("%d",&t)){ 47 while(t--){ 48 for(int i=0;i<12;i++){ 49 scanf("%lf",&a[i]); 50 } 51 solve(); 52 puts(buffer); 53 } 54 } 55 return 0; 56 }
D http://acm.hust.edu.cn/vjudge/contest/view.action?cid=97654#problem/D
题意：给n点m边无向图，问按输入顺序依次删去第i条边后连通块的个数。
解法：倒着用并查集。
1 //#define debug 2 //#define txtout 3 #include<cstdio> 4 #include<cstdlib> 5 #include<cstring> 6 #include<cmath> 7 #include<cctype> 8 #include<ctime> 9 #include<iostream> 10 #include<algorithm> 11 #include<vector> 12 #include<queue> 13 #include<stack> 14 #include<map> 15 #include<set> 16 #define mt(a,b) memset(a,b,sizeof(a)) 17 using namespace std; 18 typedef long long LL; 19 const double eps=1e-8; 20 const double pi=acos(-1.0); 21 const int inf=0x3f3f3f3f; 22 const int M=1e5+10; 23 int n,m; 24 struct E { 25 int u,v; 26 } e[M]; 27 int answer[M]; 28 class UnionFindSet { ///并查集 29 static const int MV=1e4+10; ///点的个数 30 int par[MV],num[MV]; 31 void add(int son,int fa) { 32 par[fa]+=par[son]; 33 par[son]=fa; 34 num[fa]+=num[son]; 35 } 36 public: 37 void init(int n) { 38 for(int i=0; i<=n; i++) { 39 num[i]=1; 40 par[i]=-1; 41 } 42 } 43 int getroot(int x) { 44 int i=x,j=x,temp; 45 while(par[i]>=0) i=par[i]; 46 while(j!=i) { 47 temp=par[j]; 48 par[j]=i; 49 j=temp; 50 } 51 return i; 52 } 53 bool unite(int x,int y) { 54 int p=getroot(x); 55 int q=getroot(y); 56 if(p==q) return false; 57 if(par[p]>par[q]) { 58 add(p,q); 59 } else { 60 add(q,p); 61 } 62 return true; 63 } 64 int getnum(int id) { ///返回该点所在集合包含的点数 65 return num[getroot(id)]; 66 } 67 } ufs; 68 void solve() { 69 int result=n; 70 ufs.init(n); 71 for(int i=m-1;i>=0;i--){ 72 answer[i]=result; 73 if(ufs.unite(e[i].u,e[i].v)){ 74 result--; 75 } 76 } 77 } 78 int main() { 79 #ifdef txtout 80 freopen("in.txt","r",stdin); 81 freopen("out.txt","w",stdout); 82 #endif 83 while(~scanf("%d%d",&n,&m)) { 84 for(int i=0; i<m; i++) { 85 scanf("%d%d",&e[i].u,&e[i].v); 86 } 87 solve(); 88 for(int i=0; i<m; i++) { 89 printf("%d ",answer[i]); 90 } 91 } 92 return 0; 93 }
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）种情况。
1 //#define debug 2 //#define txtout 3 #include<cstdio> 4 #include<cstdlib> 5 #include<cstring> 6 #include<cmath> 7 #include<cctype> 8 #include<ctime> 9 #include<iostream> 10 #include<algorithm> 11 #include<vector> 12 #include<queue> 13 #include<stack> 14 #include<map> 15 #include<set> 16 #define mt(a,b) memset(a,b,sizeof(a)) 17 using namespace std; 18 typedef long long LL; 19 const double eps=1e-8; 20 const double pi=acos(-1.0); 21 const int inf=0x3f3f3f3f; 22 const int M=1e5+10; 23 int G,L; 24 int solve(){ 25 if(L%G) return 0; 26 if(L==G) return 1; 27 L/=G; 28 int result=1; 29 for(int i=2;i*i<=L;i++){ 30 if(L%i) continue; 31 int a=0; 32 while(L%i==0){ 33 L/=i; 34 a++; 35 } 36 result*=6*a; 37 } 38 if(L>1) result*=6; 39 return result; 40 } 41 int main(){ 42 #ifdef txtout 43 freopen("in.txt","r",stdin); 44 freopen("out.txt","w",stdout); 45 #endif 46 int t; 47 while(~scanf("%d",&t)){ 48 while(t--){ 49 scanf("%d%d",&G,&L); 50 printf("%d ",solve()); 51 } 52 } 53 return 0; 54 }
G http://acm.hust.edu.cn/vjudge/contest/view.action?cid=97654#problem/G
题意：给n*m的棋盘，上面有q个点，其他位置可以放炮，就是象棋的规则，要保证最后放置的炮不能被吃，也就是不存在两个炮之间有点或者跑。
解法：dfs所有情况，每次放炮前先判一下行和列是否会被吃。
1 //#define debug 2 //#define txtout 3 #include<cstdio> 4 #include<cstdlib> 5 #include<cstring> 6 #include<cmath> 7 #include<cctype> 8 #include<ctime> 9 #include<iostream> 10 #include<algorithm> 11 #include<vector> 12 #include<queue> 13 #include<stack> 14 #include<map> 15 #include<set> 16 #define mt(a,b) memset(a,b,sizeof(a)) 17 using namespace std; 18 typedef long long LL; 19 const double eps=1e-8; 20 const double pi=acos(-1.0); 21 const int inf=0x3f3f3f3f; 22 const int M=1e2+10; 23 struct Q{ 24 int x,y; 25 }p[M]; 26 int n,m,q; 27 bool ispoint[M][M]; 28 bool choose[M][M]; 29 int result; 30 int dx[]={0,0,1,-1}; 31 int dy[]={1,-1,0,0}; 32 void init(){ 33 for(int i=0;i<n;i++){ 34 for(int j=0;j<m;j++){ 35 ispoint[i][j]=false; 36 choose[i][j]=false; 37 } 38 } 39 for(int i=0;i<q;i++){ 40 ispoint[p[i].x][p[i].y]=true; 41 } 42 } 43 bool inside(int x,int y){ 44 return x>=0&&x<n&&y>=0&&y<m; 45 } 46 bool eat(int x,int y,int d){ 47 int tx=x+dx[d]; 48 int ty=y+dy[d]; 49 while(inside(tx,ty)&&!choose[tx][ty]&&!ispoint[tx][ty]){ 50 tx+=dx[d]; 51 ty+=dy[d]; 52 } 53 if(!inside(tx,ty)) return false; 54 tx+=dx[d]; 55 ty+=dy[d]; 56 while(inside(tx,ty)&&!choose[tx][ty]&&!ispoint[tx][ty]){ 57 tx+=dx[d]; 58 ty+=dy[d]; 59 } 60 if(!inside(tx,ty)) return false; 61 return choose[tx][ty]; 62 } 63 bool judge(int x,int y){ 64 for(int i=0;i<4;i++){ 65 if(eat(x,y,i)) return false; 66 } 67 return true; 68 } 69 void dfs(int x,int y,int sum){ 70 if(x==n){ 71 result=max(result,sum); 72 return ; 73 } 74 if(y==m) return dfs(x+1,0,sum); 75 if(ispoint[x][y]) return dfs(x,y+1,sum); 76 dfs(x,y+1,sum); 77 if(judge(x,y)){ 78 choose[x][y]=true; 79 dfs(x,y+1,sum+1); 80 choose[x][y]=false; 81 } 82 } 83 int solve(){ 84 init(); 85 result=0; 86 dfs(0,0,0); 87 return result; 88 } 89 int main(){ 90 #ifdef txtout 91 freopen("in.txt","r",stdin); 92 freopen("out.txt","w",stdout); 93 #endif 94 while(~scanf("%d%d%d",&n,&m,&q)){ 95 for(int i=0;i<q;i++){ 96 scanf("%d%d",&p[i].x,&p[i].y); 97 } 98 printf("%d ",solve()); 99 } 100 return 0; 101 }
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】就是先手可能获得的得分。
1 //#define debug 2 //#define txtout 3 #include<cstdio> 4 #include<cstdlib> 5 #include<cstring> 6 #include<cmath> 7 #include<cctype> 8 #include<ctime> 9 #include<iostream> 10 #include<algorithm> 11 #include<vector> 12 #include<queue> 13 #include<stack> 14 #include<map> 15 #include<set> 16 #define mt(a,b) memset(a,b,sizeof(a)) 17 using namespace std; 18 typedef long long LL; 19 const double eps=1e-8; 20 const double pi=acos(-1.0); 21 const int inf=0x3f3f3f3f; 22 const int M=25; 23 int a[M]; 24 int b[M]; 25 int sa[M]; 26 int sb[M]; 27 int n; 28 int dp[M][M][M][M]; 29 void init_sum(int sum[],int v[]){ 30 sum[0]=0; 31 for(int i=1;i<=n;i++){ 32 sum[i]=sum[i-1]+v[i]; 33 } 34 } 35 void init_dp(){ 36 for(int x1=0;x1<=n;x1++){ 37 for(int y1=0;y1<=n;y1++){ 38 for(int x2=0;x2<=n;x2++){ 39 for(int y2=0;y2<=n;y2++){ 40 dp[x1][y1][x2][y2]=-1; 41 } 42 } 43 } 44 } 45 } 46 int get_sum(int x1,int y1,int x2,int y2){ 47 int result=sa[y1]+sb[y2]; 48 if(x1) result-=sa[x1-1]; 49 if(x2) result-=sb[x2-1]; 50 return result; 51 } 52 int dfs(int x1,int y1,int x2,int y2){ 53 int& answer=dp[x1][y1][x2][y2]; 54 if(answer!=-1) return answer; 55 if(x1<y1){ 56 answer=max(answer,a[x1]+get_sum(x1+1,y1,x2,y2)-dfs(x1+1,y1,x2,y2)); 57 answer=max(answer,a[y1]+get_sum(x1,y1-1,x2,y2)-dfs(x1,y1-1,x2,y2)); 58 } 59 if(x2<y2){ 60 answer=max(answer,b[x2]+get_sum(x1,y1,x2+1,y2)-dfs(x1,y1,x2+1,y2)); 61 answer=max(answer,b[y2]+get_sum(x1,y1,x2,y2-1)-dfs(x1,y1,x2,y2-1)); 62 } 63 if(x1==y1&&x1){ 64 answer=max(answer,a[x1]+get_sum(0,0,x2,y2)-dfs(0,0,x2,y2)); 65 } 66 if(x2==y2&&x2){ 67 answer=max(answer,b[x2]+get_sum(x1,y1,0,0)-dfs(x1,y1,0,0)); 68 } 69 return answer; 70 } 71 int solve(){ 72 init_sum(sa,a); 73 init_sum(sb,b); 74 init_dp(); 75 dp[0][0][0][0]=0; 76 for(int i=1;i<=n;i++){ 77 dp[i][i][0][0]=a[i]; 78 dp[0][0][i][i]=b[i]; 79 } 80 return dfs(1,n,1,n); 81 } 82 int main(){ 83 #ifdef txtout 84 freopen("in.txt","r",stdin); 85 freopen("out.txt","w",stdout); 86 #endif 87 int t; 88 while(~scanf("%d",&t)){ 89 while(t--){ 90 scanf("%d",&n); 91 for(int i=1;i<=n;i++){ 92 scanf("%d",&a[i]); 93 } 94 for(int i=1;i<=n;i++){ 95 scanf("%d",&b[i]); 96 } 97 printf("%d ",solve()); 98 } 99 } 100 return 0; 101 }
end