A题：
给出一个8*8的棋盘，棋盘上是一些字符，大写字母代表white的分数，小写代表black的分数，问最后谁的分数多，直接扫一遍就好了。
1 #include<cstdio> 2 int update(char str) 3 { 4 if(str=='.') 5 return 0; 6 else if(str=='Q') 7 return 9; 8 else if(str=='q') 9 return -9; 10 else if(str=='R') 11 return 5; 12 else if(str=='r') 13 return -5; 14 else if(str=='B'||str=='N') 15 return 3; 16 else if(str=='b'||str=='n') 17 return -3; 18 else if(str=='P') 19 return 1; 20 else if(str=='p') 21 return -1; 22 return 0; 23 } 24 int main() 25 { 26 char s[10]; 27 while(scanf("%s",&s)!=EOF){ 28 int sum=0; 29 for(int i=0;i<8;i++) 30 sum+=update(s[i]); 31 for(int i=1;i<8;i++){ 32 scanf("%s",&s); 33 for(int j=0;j<8;j++) 34 sum+=update(s[j]); 35 } 36 if(sum>0) 37 printf("White "); 38 else if(sum<0) 39 printf("Black "); 40 else 41 printf("Draw "); 42 } 43 return 0; 44 }
B题：
给出3段由数字组成的序列，第二段少第一段一个数，第三段少第二段一个数，则相当于第一段少了2个数，问少了哪2个数。
分别把3段的数字加起来，相减就知道少了哪个数了。
1 #include<cstdio> 2 int main() 3 { 4 int n; 5 while(scanf("%d",&n)!=EOF){ 6 long long sum[3]; 7 sum[0]=sum[1]=sum[2]=0; 8 int w; 9 for(int i=0;i<n;i++){ 10 scanf("%d",&w); 11 sum[0]+=w; 12 } 13 for(int i=0;i<n-1;i++){ 14 scanf("%d",&w); 15 sum[1]+=w; 16 } 17 for(int i=0;i<n-2;i++){ 18 scanf("%d",&w); 19 sum[2]+=w; 20 } 21 printf("%I64d ",sum[0]-sum[1]); 22 printf("%I64d ",sum[1]-sum[2]); 23 } 24 return 0; 25 }
C题：
n个有经验的acmer，m个新手，现在要组队，要求：2个有经验的+1个新手 or 1个有经验的加2个新手。
问最多能组成多少只队伍。
刚开始看到题目的时候，看到了那些tags，没有什么信心做下去了，其实很水。
1,1,时特殊情况。
当一个为另一个的2倍以上时，直接得出结果了。
当一个为a，另一个为a到2*a时，大的取2个，小的取一个。
31ms
1 #include<cstdio> 2 int main() 3 { 4 int n,m; 5 while(scanf("%d%d",&n,&m)!=EOF){ 6 if(n>m){ 7 int t=n; 8 n=m; 9 m=t; 10 } 11 if(n==1&&m==1) 12 printf("0 "); 13 else if(m>=n*2) 14 printf("%d ",n); 15 else{ 16 int ans=0; 17 while(n>0&&m>1){ 18 m-=2; 19 n-=1; 20 ans++; 21 if(m<n){ 22 int t=n; 23 n=m; 24 m=t; 25 } 26 } 27 printf("%d ",ans); 28 } 29 } 30 return 0; 31 }
E题：
给出n个房间，有n-1条走廊，刚好构成一个树。
每条走廊的长度都是1.
现在每次询问给出a,b，问：有多少个房间到a房间，b房间的距离是相同的。
思路：把无根树化为有根树。
先dfs预处理一个siz，dep，p[][]
其中siz[i]表示以i为根的子树有多少个节点
dep[i] i的深度
p[][],倍增法求lca
每次询问，求出其LCA，再分情况讨论：
4种情况(先保证dep[a]>=dep[b])
1.a=b=lca(a,b) （特判）
2.dep[a]==dep[b]，且a!=lca(a,b)
3.dep[a]!=dep[b],且lca(a,b)=b;
4.dep[a]!=dep[b],且lca(a,b)!=b
然后，若一个点到达a,b的距离一样，则这个点的儿子节点到达a,b的距离也一样(去掉a,b所在的子树)
所以，先要找出这个点，这个点就是a,b路径的中点mid
mid==lca当且仅当情况2时。
情况3,4时，mid！=lca。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 5 using namespace std; 6 7 const int maxn=100000+5; 8 9 int siz[maxn]; 10 int dep[maxn]; 11 int p[maxn][20]; 12 13 struct Edge 14 { 15 int to,next; 16 }edge[maxn<<1]; 17 18 int head[maxn]; 19 int tot; 20 21 void init(int n) 22 { 23 memset(head,-1,sizeof(head)); 24 tot=0; 25 memset(dep,0,sizeof(dep)); 26 27 for(int i=1;i<=n;i++) 28 for(int j=0;j<20;j++) 29 p[i][j]=-1; 30 } 31 32 void addedge(int u,int v) 33 { 34 edge[tot].to=v; 35 edge[tot].next=head[u]; 36 head[u]=tot++; 37 } 38 39 void dfs(int n,int rt) 40 { 41 siz[rt]=1; 42 for(int i=head[rt];~i;i=edge[i].next) 43 { 44 int v=edge[i].to; 45 if(!dep[v]) 46 { 47 dep[v]=dep[rt]+1; 48 p[v][0]=rt; 49 dfs(n,v); 50 siz[rt]+=siz[v]; 51 } 52 } 53 } 54 55 void init_lca(int n) 56 { 57 for(int j=1;(1<<j)<=n;j++) 58 { 59 for(int i=1;i<=n;i++) 60 { 61 if(p[i][j-1]!=-1) 62 { 63 p[i][j]=p[p[i][j-1]][j-1]; 64 } 65 } 66 } 67 } 68 69 int solve(int n,int a,int b) 70 { 71 if(a==b) 72 return n; 73 74 if(dep[a]<dep[b]) 75 swap(a,b); 76 77 int cnt; 78 for(cnt=0;(1<<cnt)<=dep[a];cnt++) 79 ; 80 cnt--; 81 82 //printf("cnt=%d ",cnt); 83 84 int init_a=a; 85 86 for(int j=cnt;j>=0;j--) 87 { 88 if(dep[a]-(1<<j)>=dep[b]) 89 a=p[a][j]; 90 } 91 92 //printf("a=%d ",a); 93 94 if(init_a==a) 95 { 96 for(int j=cnt;j>=0;j--) 97 { 98 if(p[a][j]!=-1&&p[a][j]!=p[b][j]) 99 { 100 a=p[a][j]; 101 b=p[b][j]; 102 } 103 } 104 return (n-siz[a]-siz[b]); 105 } 106 else if(a==b) 107 { 108 if((dep[init_a]-dep[a])%2) 109 return 0; 110 111 int mid=init_a; 112 int temp=(dep[init_a]-dep[a])/2; 113 temp=dep[init_a]-temp+1; 114 for(int j=cnt;j>=0;j--) 115 if(dep[mid]-(1<<j)>=temp) 116 mid=p[mid][j]; 117 int ans=siz[p[mid][0]]-siz[mid]; 118 return ans; 119 } 120 else 121 { 122 int init_b=b; 123 for(int j=cnt;j>=0;j--) 124 { 125 if(p[a][j]!=-1&&p[a][j]!=p[b][j]) 126 { 127 a=p[a][j]; 128 b=p[b][j]; 129 } 130 } 131 int lca=p[a][0]; 132 int cur=dep[init_a]+dep[init_b]-2*dep[lca]; 133 if(cur%2) 134 return 0; 135 int mid=init_a; 136 cur/=2; 137 cur=dep[init_a]-cur+1; 138 for(int j=cnt;j>=0;j--) 139 if(dep[mid]-(1<<j)>=cur) 140 mid=p[mid][j]; 141 int ans=siz[p[mid][0]]-siz[mid]; 142 return ans; 143 } 144 } 145 146 int main() 147 { 148 int n; 149 150 while(scanf("%d",&n)!=EOF) 151 { 152 init(n); 153 154 for(int i=1;i<n;i++) 155 { 156 int a,b; 157 scanf("%d%d",&a,&b); 158 addedge(a,b); 159 addedge(b,a); 160 } 161 dep[1]=1; 162 dfs(n,1); 163 164 init_lca(n); 165 166 int m; 167 scanf("%d",&m); 168 169 /* 170 for(int i=1;i<=n;i++) 171 printf("%d ",dep[i]); 172 */ 173 174 for(int i=1;i<=m;i++) 175 { 176 int a,b; 177 scanf("%d%d",&a,&b); 178 printf("%d ",solve(n,a,b)); 179 } 180 181 182 } 183 184 return 0; 185 }