分差好大。。。但是从排名上看也许还可以接受？
不算太炸
但是这个还是算了吧。。。
其实状态不是很好。
T1不会，打的搜索，想到一个剪枝但是感觉没什么用，所以没打。
考后打上，85了。。。打上另一个就90了。。。
T3已经想到正解思路了，但是不完善
T2想到正解，但是没有证明它是树形，于是没有打。。。
又说不完，晚上又要考，改善状态。
T1：毛一琛
又是meet in miiddle。又没想到。
其实也就是双向搜索，然后hash_map查状态即可。
打的lower_bound，多了一个log。勉强过了。
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>X[],Y[];
int n,x[],ans,y[],r;
void sch1(int p,int w,int st){
if(p-==n>>){if(w>=)X[st].push_back(w);return;}
sch1(p+,w-x[p],st|<<p-);sch1(p+,w,st);sch1(p+,w+x[p],st|<<p-);
}
void sch2(int p,int w,int st){
if(p==n+){if(w>=)Y[st].push_back(w);return;}
sch2(p+,w+x[p],st|<<p-r);sch2(p+,w,st);sch2(p+,w-x[p],st|<<p-r);
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;++i)scanf("%d",&x[i]);r=(n>>)+;
sch1(,,);sch2(r,,);
for(int i=;i<<<(n>>);++i)sort(X[i].begin(),X[i].end());
for(int i=;i<<<n-(n>>);++i)sort(Y[i].begin(),Y[i].end());
for(int i=;i<<<(n>>);++i)for(int j=;j<<<n-(n>>);++j)
for(int v=;v<X[i].size();++v)
if(lower_bound(Y[j].begin(),Y[j].end(),X[i][v])!=Y[j].end())
if(*(lower_bound(Y[j].begin(),Y[j].end(),X[i][v]))==X[i][v])
y[i<<n-(n>>)|j]=;
for(int i=;i<<<n;++i)ans+=y[i];//,printf("%d\n",y[i]);
printf("%d\n",ans);
}
T2：毛二琛
首先这题puts("0")会爆零，所以所有情况都有解。
考虑每一个数移动的方向，那么其实就限制了q序列上某两个相差为1的值的相对位置。
这样的话就是SAO那道题简化到序列上了，dp[i][j]表示考虑到操作i，其相对位置是j，前缀和优化就完事了。
代码倒好说。想到就能写出来。
#include<cstdio>
#define mod 1000000007
inline int Mod(int p){return p>=mod?p-mod:p;}
int p[],np[],n,dir[],dp[][],sum[][];//dir=2先i后i-1
int main(){
scanf("%d",&n);
for(int i=;i<=n;++i)scanf("%d",&p[i]),p[i]++,np[p[i]]=i;
for(int i=;i<=n;++i)
if(np[i]>i){dir[i]=;for(int j=i+;j<p[i];++j)dir[j]=;}
else {dir[i]=;for(int j=i-;j>np[i];--j)dir[j]=;}
dp[][]=sum[][]=;
for(int i=;i<=n-;++i){
if(dir[i]==)for(int j=;j<=i;++j)dp[i][j]=Mod(mod+sum[i-][i-]-sum[i-][j-]);
else for(int j=;j<=i;++j)dp[i][j]=sum[i-][j-];
for(int j=;j<=i;++j)sum[i][j]=Mod(sum[i][j-]+dp[i][j]);
}printf("%d\n",sum[n-][n-]);
}
T3：毛三琛
二分答案，剪枝，及时跳出。
如果目前的x连目前最优答案都不到，continue。
#include<bits/stdc++.h>
using namespace std;
int n,k,p,a[],ans=;
int Mod(int x){return x>=p?x-p:x;}
int chk(int w,int xx){
int al=,f=;
for(int i=;i<=n&&al<=k;++i){int x=Mod(xx+a[i]);if(x>w)return ;if(f+x>w)al++,f=x;else f+=x;}
if(al<=k)return ;
return ;
}
int main(){
scanf("%d%d%d",&n,&p,&k);
for(int i=;i<=n;++i)scanf("%d",&a[i]);
for(int i=;i<p;++i){
if(!chk(ans,i))continue;
register int l=,r=ans;
while(l<r-)if(chk(l+r>>,i))r=l+r>>;else l=(l+r>>)+;
ans=min(ans,chk(l,i)?l:r);
}
printf("%d\n",ans);
}