\(\color{white}{\mathbb{缀以无尽之群星点点，饰以常青之巨木郁郁，可细斟木纹叶脉，独无可极苍穹之览，名之以：密林}}\)

---

看完题后感觉整套题都没什么思路，而且基本上整场考试确实是这样

倒序开题，发现 \(t3\) 的做法没有优化空间了，\(t2\) 发现了一些规律，但是卡在求拓扑序上，最后乱搞 \(t1\)，本来复杂度及其不正确，但是测的在随机数据下还是很可观的

事实上最后分数比预期高多了

---

A. 毛一琛

考完 cyh 说才发现是曾经随机跳题跳到的USACO的题，但不幸的是当时直接跳了……

如果直接枚举的话有三种状态：分到第一组，分到第二组，不要，这样是 \(3^n\)

对于这种范围刚刚超的，而且还是枚举集合的题，常常可以使用折半搜索

对于前半段共 \(\frac{n}{2}\) 个元素暴搜一下，消耗 \(3^{\frac{n}{2}}\)，并且把每种状态记录在其和的 \(vector\) 里面

右边再重复上述操作，设求出的和为 \(sum\)，那么在左边寻找 \(-sum\) 的集合，并且更新和起来的答案即可

代码实现

#include<bits/stdc++.h>
using namespace std;
const int maxn=55,maxm=1e6+1e5+5;
int n,a[maxn],half,tot,ans;
bool vis[maxm];
map<int,int>mp;
vector<pair<int,int> >num[maxm];
void dfs1(int pos,int sum,int S1,int S2){
    if(pos==half+1){
        if(mp.find(sum)==mp.end())mp[sum]=++tot;
        num[mp[sum]].push_back(make_pair(S1,S2));
        return ;
    }
    dfs1(pos+1,sum,S1<<1,S2<<1);
    dfs1(pos+1,sum+a[pos],S1<<1|1,S2<<1);
    dfs1(pos+1,sum-a[pos],S1<<1,S2<<1|1);
    return ;
}
void dfs2(int pos,int sum,int S1,int S2){
    if(pos==n+1){
        if(mp.find(-sum)==mp.end())return ;
        int id=mp[-sum];
        for(int i=0;i<num[id].size();i++){
//            cout<<"hhh";
            vis[S1|S2|((num[id][i].first|num[id][i].second)<<(n-half))]=true;
        }
        return ;
    }
    dfs2(pos+1,sum,S1<<1,S2<<1);
    dfs2(pos+1,sum+a[pos],S1<<1|1,S2<<1);
    dfs2(pos+1,sum-a[pos],S1<<1,S2<<1|1);
    return ;
}
int main(){
    cin>>n;
    half=n/2;
//    if(n>=10)half+=3;
    for(int i=1;i<=n;i++)cin>>a[i];
    dfs1(1,0,0,0);
    dfs2(half+1,0,0,0);
    for(int i=1;i<=(1<<n)-1;i++)if(vis[i])ans++;
    cout<<ans;
    return 0;
} 

---

B. 毛二琛

考场上想到可以根据先后顺序建边，相当于求有向图的拓扑序个数

然后想到以前有到叫 \(SAO\) 的题，然而当时咕咕咕了……

正解是用 \(dp\) 来做

设 \(f[i][j]\) 表示第 \(i\) 个数在前 \(i\) 个数形成的图中拓扑序为 \(j\) 的方案数

考虑从 \(f[i-1][k]\) 转移

如果 \(i-1\) 向 \(i\) 连边，相当于如果 \(i\) 的拓扑序为 \(j\)，那么 \(k\) 的范围为 \([1,j-1]\)

如果 \(i\) 向 \(i-1\) 连边，\(k\) 的范围为 \([j,i]\) (可以取到 \(j\) 是因为加入 \(i\) 这个数相当于把值域往后平移一位，那么原来的 \(j\) 现在相当于 \(j+1\)，是满足条件的)

然后发现 \(k\) 的值域是连续的，可以前缀和优化一下

代码实现

#include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=x*10+ch-48;
        ch=getchar();
    }
    return x*f;
}
const int maxn=5005;
const int mod=1e9+7;
int n,a[maxn],f[2][maxn],g[2][maxn],ans;
bool le[maxn];//rk[i]<rk[i+1]
int main(){
    n=read();
    for(int i=0;i<n;i++)a[i]=read();
    for(int i=0;i<n;i++){
        if(a[i]<i){//往左走
            for(int j=a[i];j<=i-2;j++)le[j]=true;
        }
        else{
            if(i>0)le[i-1]=true;
            le[a[i]-1]=true;
        }
    }
    f[0][1]=g[0][1]=1;
    for(int i=1;i<=n-2;i++){
        for(int j=1;j<=i+1;j++){
            if(le[i-1])f[i&1][j]=(g[(i-1)&1][i]-g[(i-1)&1][j-1]+mod)%mod;
            else f[i&1][j]=g[(i-1)&1][j-1];
        }
        for(int j=1;j<=i+1;j++){
            g[i&1][j]=(g[i&1][j-1]+f[i&1][j])%mod;
        }
    }
    for(int i=1;i<=n;i++)ans=(ans+f[(n-2)&1][i])%mod;
    cout<<ans;
    return 0;
} 

---

B. 毛三琛

玄学题

首先应该乖乖地按照题目上说的确定 \(x\)（考场上因为加了个小优化所以不得不先二分再定 \(x\))

当 \(x\) 随机打乱后，最优解的更新序列长度期望是 \(logP\) 的

那么只需要每次开始二分前，\(O(n)\) 判断一下当前 \(x\) 是否比当前答案优即可

代码实现

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,p,k,a[maxn],ans,b[maxn],x;
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=x*10+ch-48;
        ch=getchar();
    }
    return x*f;
}
bool check(int limit,int x){
    int cnt=1,sum=0;
    for(int i=1;i<=n;i++){
        int val=(a[i]+x)%p;
        if(val>limit) return false;
        if(sum+val<=limit)sum+=val;
        else sum=val,cnt++;
        if(cnt>k)break;
    }
    if(cnt<=k)return true;
    return false;
}
int main(){
    srand(time(0));
    n=read();
    p=read();
    k=read();
    for(int i=1;i<=n;i++)a[i]=read(),ans+=a[i];
    for(int i=0;i<p;i++)b[i]=i;
    random_shuffle(b,b+p);
    for(int i=0;i<p;i++){
        x=b[i];
        if(check(ans,x)){
            int l=0,r=ans+1;
            while(l<r){
                int mid=l+r>>1;
                if(check(mid,x))r=mid;
                else l=mid+1;
            }
            ans=l;
        }
    }
    cout<<ans;
    return 0;
} 

\(\color{white}{\mathbb{溯洄从之，道阻且长}}\)