继续存档
早上来补了一下昨天的题，不过肯定这两天的没法完全补起来
T1：
经典思路：关于位运算的题讨论每一位的贡献
#include<iostream> #include<cstdio> using namespace std; int t,mod=1e9+7;; long long l,r,all,cnt,ans; long long count(long long x,int k){ long long num=0; num+=x/(1ll<<(k+1)); x-=(1ll<<(k+1))*num; num*=(1ll<<k); num+=((x>=(1ll<<k))?(x+1-(1ll<<k)):0); return num; } int main() { scanf("%d",&t); while(t--){ scanf("%lld%lld",&l,&r); all=r-l+1; ans=0; for(int i=0;i<=31;i++){ cnt=count(r,i)-count(l-1,i); ans=(ans+cnt*(all-cnt)%mod*(1ll<<(i+1))%mod)%mod; } printf("%lld ",ans); } return 0; }
T2：
优化DP刷表可以卡过去，并不是完全的正解啦:P
（我才知道bool是1bit而int是4bits…一直以来bool都用int代替的…）
关键点：必败状态不能互相转移、打表+分析发现对于每个让二元组（x，y）必败的z，x、y所占用的数字不重复且x与y的差不重复。
题解里好像有点小锅，如果存在f(x,y)=k<i，则f(x+i-k,y)、f(x,y+i-k)、f(x+i-k,y+i-k)不可能等于i。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int t,x,y,z,maxn; bool f[301][301][301]; int main() { for(int i=0;i<=300;i++){ for(int j=0;j<=300;j++){ for(int k=0;k<=300;k++){ if(!f[i][j][k]){ for(int x=1;x<=7;x++){ maxn=300; if(x&1)maxn=min(maxn,300-i); if(x&2)maxn=min(maxn,300-j); if(x&4)maxn=min(maxn,300-k); for(int l=1;l<=maxn;l++)f[i+(x&1)*l][j+((x>>1)&1)*l][k+((x>>2)&1)*l]=1; } } } } } scanf("%d",&t); while(t--){ scanf("%d%d%d",&x,&y,&z); if(f[x][y][z])printf("Yes "); else printf("No "); } return 0; }
T3：
关键点在于转化题目。也是一个经典的思路：遇到绝对值的问题，可以考虑把绝对值拆成正负两种作差方法分开考虑。
于是对于一些si，它会被加两次或者减两次。对于另一些si，它会加一次减一次正好抵消。首位特殊讨论。
设计dp，首先可以想到+2、-2、0这三种。但是考虑2和-2的产生就会发现2和-2肯定是间隔的XD！所以还要考虑它们的间隔状态是否合法。
通过把0的状态拆成2->-2、-2->2两种来保证转移合法。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,k; int f[30010][210][4],a[30010]; int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++)scanf("%d",&a[i]); memset(f,-0x3f,sizeof(f)); for(int i=0;i<=n;i++){ for(int j=0;j<=3;j++){ f[i][0][j]=0; } } for(int i=1;i<=n;i++){ for(int j=1;j<=min(i,k);j++){ f[i][j][0]=max(f[i-1][j-1][3],f[i-1][j][0])+((j==1||j==k)?1:2)*a[i]; f[i][j][2]=max(f[i-1][j-1][1],f[i-1][j][2])-((j==1||j==k)?1:2)*a[i]; f[i][j][1]=max(f[i][j][0],f[i-1][j][1]); if(j!=1&&j!=k)f[i][j][1]=max(f[i][j][1],f[i-1][j-1][1]); f[i][j][3]=max(f[i][j][2],f[i-1][j][3]); if(j!=1&&j!=k)f[i][j][3]=max(f[i][j][3],f[i-1][j-1][3]); } } printf("%d ",max(f[n][k][1],f[n][k][3])); return 0; }
在尝试补这套题的时候发生了各种各样脑残的错误，例如“咦bool原来是1bit吗”之类的:D
脑子是个好东西 希望我有XDDDDDDDD