8月11日 集训测试

B

题目链接

http://acm.hust.edu.cn/vjudge/problem/24840

题意

给出一个天枰的文字描述，问最少修改多少次可以使天枰的所有支点都是平衡的。

题解

找一个基准（depth*weigh），把其他所有的重量的基准都修改为这个值，那么只要这个基准的出现次数最多，那么修改的次数也就越少。sum-基准次数。

代码

#include<iostream> #include<queue> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<string> #include<cctype> #include<algorithm> #include<vector> #include<map> using namespace std; int main() { int t; scanf("%d",&t); while(t--) { string st; cin>>st; int n=st.size(); int cnt1=0,cnt2=0; map<long long,int>num; int cnt3=0; for(int i=0;i<n;i++) { if(st[i]=='['){cnt1++;cnt2++;} //出现一个'['深度就+1 else if(isdigit(st[i])) //只要是数字就开始“基准”处理 { long long numm=st[i]-'0'; i++; while(isdigit(st[i])){ numm=numm*10+st[i]-'0'; i++; if(i>=n){break;} } i--; long long aa=1; for(int j=0;j<cnt1;j++)aa*=2; numm*=aa; num[numm]++; cnt3++; } else if(st[i]==']')cnt1--; //出现一个']'深度-1 } map<long long,int>::iterator it=num.begin();//用一个map映射基准出现的次数，最后找到出现次数最多的基准。 int ans=-1; for(;it!=num.end();it++) { ans=max(ans,it->second); } if(cnt2==0)printf("0\n"); else printf("%d\n",cnt3-ans); } return 0; }

C

题目链接

http://acm.hust.edu.cn/vjudge/problem/22883

题意

切披萨，问n刀下去，披萨可以被切成几块。

题解

ans=1+（（n+1）*n）/2；

D

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=4334

题意

给出5个数的集合，问能否从每个集合中选出一个数，使5个数之后等于0。

题解

先把前两个集合的数的和依次求出来，得到新集合n1，然后同样处理第三第四个集合得到新集合n2，遍历第五个集合中的每个元素x，n=n1+x，二分查找在n2集合中是否存在n的相反数。

代码

#include<iostream> #include<queue> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<string> #include<cctype> #include<algorithm> #include<vector> using namespace std; long long a[7][300]; int main() { int t; scanf("%d",&t); while(t--) { for(int i=0;i<7;i++) for(int j=0;j<300;j++)a[i][j]=0; int n; scanf("%d",&n); for(int i=0;i<5;i++) for(int j=0;j<n;j++)scanf("%lld",&a[i][j]); vector<long long>s1; vector<long long>s2; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { long long t=a[0][i]+a[1][j];s1.push_back(t); } } //处理第一第二个集合 for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { long long t=a[3][i]+a[4][j];s2.push_back(t); } } //处理第三第四个集合 sort(s1.begin(),s1.end()); //排序后二分查找 sort(s2.begin(),s2.end()); int ok=0; for(int i=0;i<n;i++) { for(int j=0;j<s1.size();j++) { long long t=a[2][i]+s1[j]; int op=lower_bound(s2.begin(),s2.end(),-t)-s2.begin();//二分查找 if(s2[op]+t==0){ok=1;break;} } if(ok==1)break; } if(ok==1)printf("Yes\n"); else printf("No\n"); } return 0; }

F

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=4346

题意

只要存在i位置为R，j位置也为R，并且（i+j）/2位置为G，那么这条路就是美丽的，问最多可以构造出多少条美丽的路。

题解

正面构造感觉特别难，不能把所有情况按某种思路一次找出来。所有就反着来了，美丽的串=总的串数-不美丽的串。而不美丽的串，首先满足条件，相邻的两个R之间的距离为奇数，易得。其次，所有的R之间的距离应该是相同的。反正法，假如R1，R2，R3，R1与R2之间的距离不等于R2与R3之间的距离，因为奇数+奇数=偶数，那么R1与R3之间距离是偶数，存在（R1+R3）/2点，但这个点不是R2，是G，所有事美丽串，与条件矛盾。简而言之就是R1与R3中间的判断点一个要是个R。 然后就好了，遍历R的起点，遍历所有奇数距离，判定是否所有的R都满足不美丽串条件，最后total-unbea。

代码

#include<iostream> #include<queue> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<string> #include<cctype> #include<algorithm> #include<vector> using namespace std; const long long mod=1e9+7; int main() { std::ios::sync_with_stdio(false); int t; cin>>t; while(t--) { string st; cin>>st; int unknow=0,r_num=0; for(int i=0;i<st.size();i++) { if(st[i]=='R')r_num++; if(st[i]=='?')unknow++; } int n=st.size(); long long unbea=0; if(r_num==0)unbea++; //R为0时，一种不美丽串特判 for(int i=0;i<n;i++) { if(st[i]=='R'||st[i]=='?') {int zz=0; if(st[i]=='R')zz=1; //判断初始的一个R是否满足 if(zz==r_num){unbea=(unbea+1)%mod;} for(int j=1;j+i<n;j+=2) { int z=zz; for(int k=i+j;k<n;k+=j) { if(st[k]=='R')z++; if(st[k]=='G')break; if(z==r_num){unbea=(unbea+1)%mod;} //满足一次就+1 } } } } long long cc=1; for(int i=0;i<unknow;i++){cc=(cc*2)%mod;} //这开始的时候写傻逼了 居然写成了cc*=2%mod; 这分明就没有Mod嘛。。。 long long ans=cc-unbea; cout<<ans<<endl; } return 0; }

G

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=4371

题意

一个博弈问题，一个人x开始写0=s1，然后另外一个人y任选一个数加上去得到s2，然后x可以有两个选择，一个在n的基础上可以任意加一个数得到s3，s3不能大于n，或者任意减一个数得到s3，但减的时候s3>s1，即s3必须大于前前个数。当一个人无法操作时，即认输。

题解

一个贪心的博弈，首先我们排除选大的数的情况- -，因为你选大数，别人就选小的数求差，那么你就只能一直选大的数，直到最后输。这个游戏是由最小的数和上限来决定输赢的，上限/最小的数=奇数，则Alice赢，偶数则Bob赢。上面已经分析了，选大数一点赢的希望都没有，那就只有选最小的数，两个人都一直选最小的数，知道最后一个人没办法选了，决出胜负。

代码

#include<iostream> #include<queue> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<string> #include<cctype> #include<algorithm> #include<vector> using namespace std; int main() { int t; scanf("%d",&t); for(int i=1;i<=t;i++) { int n,m; scanf("%d%d",&n,&m); int minx=1e9+9; for(int j=0;j<m;j++) { int z; scanf("%d",&z); minx=min(minx,z); } int t=n/minx; if(t%2==1)printf("Case #%d: Bob\n",i); else printf("Case #%d: Alice\n",i); } return 0; }