首页 > 代码库 > Topcoder SRM 639 (Div.2)
Topcoder SRM 639 (Div.2)
A.ElectronicPetEasy
【题意】一个数st1开始，每次加p1，一共加t1次，另外一个数st2开始，每次加p2，一共加t2次，输入的数均小于1000，问这两个数有没有可能相等，有可能输出“Easy”，否则输出“Difficult”
【解释】显然列出两个循环即可，1000*1000也不会超时
const string dif="Difficult";const string eas="Easy";class ElectronicPetEasy{ public: string isDifficult(int st1, int p1, int t1, int st2, int p2, int t2) { int i,j,k; int m1=st1+p1*(t1-1); int m2=st2+p2*(t2-1); for (i=st1;i<=m1;i+=p1) { for (j=st2;j<=m2;j+=p2) { if (i==j) return dif; } } return eas; }};B.AliceGameEasy
【题意】从1到n，爱丽丝取出几个数累加为x，桐人取出几个数累加为y，给出x和y，问爱丽丝做少取了多少个数（不可能时输出-1）。
【解释】贪心算法
先判断x+y=n*(n+1)/2，能否求出整数n，不能求出来 或者 求出的n不是整数 那么输出-1就好喽
既然求出n了，就让爱丽丝从最大的数开始取，n,n-1,n-2...直到存在k ，使得刚好n+(n-1)+(n-1)+...+(n-k+1)>=x（"刚好"的意思是n+(n-1)+(n-1)+...+(n-k)<x），答案就是k。
class AliceGameEasy{ public: long long findMinimumValue(long long x, long long y) { LL i,j,k; LL dt=(x+y)*8+1; LL sqr_dt=(LL)(sqrt(dt)); if (sqr_dt*sqr_dt!=dt) return -1; sqr_dt--; if (sqr_dt%2) return -1; LL n=sqr_dt/2; LL ans=0; while (x>0) { x-=n; n--; ans++; } return ans; }};C.BoardFoldingDiv2
【题意】给出一个01矩阵（最多50*50）（就是题目说的纸），现在要折叠这个矩阵，折叠要满足：
1.平行于某条边折叠
2.要沿相邻两列数字之间折叠
3.折叠后下方的数字与上方的数字相等
现在问有多少种折叠方法，（其中折叠后如果是同一块矩阵区间则算同一种方法）
【解释】显然是可以将行与列分开求，求只按行折叠的方法数ansr，和只按列折叠的方法数ansc，最后ansr*ansc就是答案。
由于按行和按列求的方法相同，下面以按列举例。
出题人相当良心，只给了50*50的规模，而且最重要的是只有0和1，那么将每列的01串视为一个二进制数，用long long存完全能存下，我们存到c[]数组中。
大致思路：枚举右界，如果右界可行的话（需要预处理），再枚举左界，如果左界也可行的话，就算是一个解。
这是预处理：设right[i]=1表示从右开始折叠，能折叠到i，即折叠后第i+1~n-1个数（数的编号是0到n-1）全都消失掉了。当然right[i]=0时表示不能折叠到第i个数。
然后枚举左界，right[k]=1时，枚举左界i，用left[i]表示从左开始折叠，能折叠到i（与right[]是相同的思路，只是变了一下方向）。
算法是O(n3)的
typedef long long LL;int n,m;LL r[55],c[55];int ansr,ansc,lef[55],rig[55];class BoardFoldingDiv2{ public: int howMany(vector <string> paper) { int i,j,k; memset(r,0,sizeof(r)); memset(c,0,sizeof(c)); ansr=ansc=0; n=paper.size(); m=paper[0].size(); for (i=0;i<n;i++) { for (j=0;j<m;j++) { r[i]=r[i]*2+paper[i][j]-‘0‘; c[j]=c[j]*2+paper[i][j]-‘0‘; } } /*对每一横行操作*/ memset(rig,0,sizeof(rig)); rig[n-1]=1; for (i=n-2;i>=0;i--) { for (j=1;i+j<n&&i-j+1>=0;j++) { if (r[i+j]==r[i-j+1]) { if (rig[i+j]) { rig[i]=1; break; } } else break; } } for (k=n-1;k>=0;k--)//枚举右界 { if (rig[k]==0) continue;//如果右界不可达，continue memset(lef,0,sizeof(lef)); lef[0]=1; ansr++; for (i=1;i<=k;i++)//枚举左界 { for (j=1;i+j-1<=k&&i-j>=0;j++)//判断左界是否可达 { if (r[i+j-1]==r[i-j]) { if (lef[i-j])//如果left[i-j]可达 并且 正好能沿数i与数i-1间折叠 { lef[i]=1;//设为可达后跳出 break; } } else break; } if (lef[i]!=0) ansr++; } } /*对每一列操作*/ memset(rig,0,sizeof(rig)); rig[m-1]=1; for (i=m-2;i>=0;i--) { for (j=1;i+j<m&&i-j+1>=0;j++) { if (c[i+j]==c[i-j+1]) { if (rig[i+j]) { rig[i]=1; break; } } else break; } } for (k=m-1;k>=0;k--) { if (rig[k]==0) continue; memset(lef,0,sizeof(lef)); lef[0]=1; ansc+=min(1,lef[0]*rig[k]); for (i=1;i<=k;i++) { for (j=1;i+j-1<=k&&i-j>=0;j++) { if (c[i+j-1]==c[i-j]) { if (lef[i-j]) { lef[i]=1; break; } } else break; } if (lef[i]!=0) ansc++; } } return ansr*ansc; }};
Topcoder SRM 639 (Div.2)