首页 > 代码库 > SRM 09
SRM 09
A
这道题就是要求删掉最右边若干本数之后，使得最终撕掉的书页最少。
先按照P值从小到大排个序，然后先建立一个数组s[i]，表示执行第i页的指令最远能撕到第几页（排序好之后的），由于P[i]是有序的，因此可以用二分查找。再用ans[i]表示若将i页之后的书页全部删去，最终会撕掉几页书，很显然ans[i]=ans[s[i]-1]+i-s[i]，然后就不停地更新答案就行了。
代码：
#include<cmath>#include<cstring>#include<algorithm>#include<cstdio>#include<iostream>using namespace std;int p[1000],a[1000],s[1000],i,j,n,ans[1000],Ans=0x7fffffff;void qs(int l,int r){ int i=l,j=r,m=p[(l+r)>>1],t; while (i<=j) { while (p[i]<m) i++; while (p[j]>m) j--; if (i<=j) { t=p[i];p[i]=p[j];p[j]=t; t=a[i];a[i]=a[j];a[j]=t; i++;j--; } } if (i<r) qs(i,r);if (l<j) qs(l,j);}int Search(int k){ int m,l=1,r=n; while (l<=r) { m=(l+r)>>1; if (p[m]<k) l=m+1; else r=m-1; } return l;}main(){ scanf("%d",&n); for (i=1; i<=n; i++) scanf("%d%d",&p[i],&a[i]); qs(1,n); for (i=1; i<=n; i++) { s[i]=Search(p[i]-a[i]); ans[i]=ans[s[i]-1]+i-s[i]; Ans=min(Ans,n-i+ans[i]); } printf("%d\n",Ans);}
题目
B
给出两个数，一个是两数之和a，一个是两数异或之后的值b。
由于异或是将两个数进行不进位的加法，因此设c=a-b为两数因为没有进位而造成的差，由于进位不可能在第一位，因此先将c右移一格。
接着将b与c逐位转化为二进制，将每一位进行比较。若b[i]==1,c[i]==0，则表示这一位没有进位并且和为1，这样在这一位的情况有{1+0}{0+1}，答案就*2；若b[i]==0,c[i]==1，则表示这一位有进位，所以在这一位只有{1+1}1种情况；若b[i]==0,c[i]==0则表示没有进位且和为0，只有{0+0}1种情况；若b[i]==1,c[i]==1，则不存在这样的情况，答案*0。
最后特判一下若一开始a==b则ans-=2，因为题目要求是正整数，而这种情况下存在0+x和x+0的情况。
代码：
#include<cmath>#include<cstring>#include<cstdio>#include<iostream>#include<algorithm>#define INF 0x7fffffff#define ll long longusing namespace std;ll i,a,b,z[42],x[42],y[42],c,ans=1,l,r;main(){ scanf("%lld%lld",&a,&b); c=(a-b)>>1;l=a;r=b; for (i=1; i<=41; i++) x[i]=c&1,c>>=1; for (i=1; i<=41; i++) y[i]=b&1,b>>=1; for (i=1; i<=41; i++) { if (x[i]==0 && y[i]==1) z[i]=2; if (x[i]==1 && y[i]==0) z[i]=1; if (x[i]==1 && y[i]==1) z[i]=0; if (x[i]==0 && y[i]==0) z[i]=1; ans*=z[i]; } if (l==r) ans-=2; printf("%lld\n",ans); return 0;}
题目
C
其实C的DP并不难写，考试的时候智障根本没想DP。
设f[i][j]为撕掉[i,j]范围内的书最少要几步。于是先预处理，撕掉单一页的书只需要一步，因为单个字符就是一个回文串。然后就可以DP了。
第一重枚举左端点i，第二重枚举右端点j，若a[i]==a[j]那当前的最小方案数就是f[i+1][j-1](这里要注意，当i+1==j时，f[i][j]=1；否则=f[i+1][j-1])；若不相同则赋值INF。接着不管f[i][j]是f[i+1][j-1]还是INF都交给下一重循环解决。设k由i枚举到j-1，在这个过程中不断更新f[i][j]的答案：f[i][j]=min(f[i][j],f[i][k]+f[k+1][j])。最终答案为f[1][n]。
代码：
#include<cmath>#include<cstring>#include<cstdio>#include<iostream>#include<algorithm>#define INF 0x7fffffffusing namespace std;int f[1000][1000],a[1000],i,j,k,n;main(){ scanf("%d",&n); for (i=1; i<=n; i++) scanf("%d",&a[i]); for (i=1; i<=n; i++) f[i][i]=1; for (j=2; j<=n; j++) { for (i=j-1; i; i--) { if (a[i]==a[j]) { if (i+1==j) f[i][j]=1; else f[i][j]=f[i+1][j-1]; } else f[i][j]=INF; for (k=i; k<j; k++) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]); } } printf("%d\n",f[1][n]); return 0;}
题目
SRM 09