果然还是太菜了

T1想了很久，结果竟然是以前CYY讲的Meet in middle？？？

结果自己现在写的HASH又长又丑(还不如以前写的爆搜)

正解就是左右各分10个状态

暴力处理出左右的状态

最后再把左右状态合并

#include
    
     using namespace std;int n,a[30],tot1,tot2,ans,tail=1,head=1;bool vis[1100000];struct ss{int s,now;}x[1100000],y[1100000];bool cmp1(ss x,ss y){return x.s
     
      y.s;}void dfs(int l,int r,int s,int now){    if(l>r)    {        if(r==n/2)x[++tot1].s=s,x[tot1].now=now;        else y[++tot2].s=s,y[tot2].now=now;        return;    }dfs(l+1,r,s,now);    dfs(l+1,r,s-a[l],now+(1<<(l-1)));    dfs(l+1,r,s+a[l],now+(1<<(l-1)));}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)scanf("%d",&a[i]);    dfs(1,n/2,0,0);dfs(n/2+1,n,0,0);    sort(x,x+tot1+1,cmp1);sort(y,y+tot2+1,cmp2);    while(head<=tot1&&tail<=tot2)    {        while(y[tail].s>-x[head].s&&tail<=tot2)tail++;        int pps=tail;        while(tail<=tot2&&y[tail].s==-x[head].s)        {            if(!vis[x[head].now|y[tail].now])                vis[x[head].now|y[tail].now]=1,ans++;            tail++;        }        if(x[head].s==x[head+1].s&&head
     
    

T2是一个大dp

f[i][j]表示前i个数，第i个数在前i个数中是第j小的

两种情况，q中i在i+1之前或是之后

即\(\sum_{i=1}^{n} \sum_{j=1}^{n}f[i][j]=g[i-1][j-1]\)

或\(\sum_{i=1}^{n} \sum_{j=1}^{n}f[i][j]=g[i-1][i]-g[i-1][j-1]\)

(g数组为前缀和优化)

#include
    
     using namespace std;int f[5010][5010],g[5010][5010],n,ok[5010],ans,mo=1e9+7;vector
     
       p;int work(){    n=p.size();memset(ok,-1,sizeof(ok));    for(int i=0;i<=n-1;i++)    {        if (p[i]>i)        {            if (i-1>=0){if (ok[i-1]==0) return 0;ok[i-1]=1;}            for(int j=i;i<=p[i]-2;j++){if (ok[j]==1) return 0;ok[j]=0;}            if (p[i]-1<=n-3){if (ok[p[i]-1]==0) return 0;ok[p[i]-1]=1;}        }        else if (p[i]
      
       =0){if (ok[p[i]-1]==1) return 0;ok[p[i]-1]=0;}            for(int j=p[i];j<=i-2;j++){if (ok[j]==0) return 0;ok[j]=1;}            if (i-1<=n-3){if (ok[i-1]==1) return 0;ok[i-1]=0;}        }else return 0;    }f[0][1]=1;g[0][1]=1;    for(int i=1;i<=n-2;i++)        for(int j=1;j<=i+1;j++)        {            if (ok[i-1]!=1){(f[i][j]+=g[i-1][j-1])%=mo;}            if (ok[i-1]!=0){(f[i][j]+=(g[i-1][i]-g[i-1][j-1])%mo)%=mo;}            g[i][j]=(g[i][j-1]+f[i][j])%mo;        }ans=0;for(int i=1;i<=n-1;i++)(ans+=f[n-2][i])%=mo;    ans=(ans%mo+mo)%mo;return ans;}int main(){scanf("%d",&n);for(int i=1;i<=n;i++){int x;scanf("%d",&x);p.push_back(x);}printf("%d",work());}
      
     
    

T3智商检测题

就是在暴力的基础上，加上随机化

随机出+x的顺序，之后二分验证

若比之前二分结果更优，则check答案

#include
    
     using namespace std;int n,p,K,a[10010],b[10010],w[10010],T[10010],ans;long long sum;bool ok[10010];bool cmp(int x,int y){return x>y;}bool check(int x){    int res=0,pps=1;    for(int i=1;i<=n;i++)    {if(x
     
      x)pps++,res=b[i];}    return pps<=K;}int main(){    srand('A'+'K'+'M'+'e'+'r');    scanf("%d%d%d",&n,&p,&K);for(int i=1;i<=n;i++)scanf("%d",&a[i]),sum+=a[i];ans=1e9;    for(int i=0;i