【题解】牛客小白月赛107

A.Cidoai的吃饭

按照题意输出即可。

int ans=0;
ans+=n/a;n%=a;
ans+=n/b;n%=b;
ans+=n/c;n%=c;
write(ans);

B.Cidoai的听歌

注意我们只需要关心最小值和最大值的操作次数。同时注意题面中的从操作 1 开始与循环操作，我们可以得到最终要么两种操作操作次数相等，要么操作 1 的次数比操作 2 多一次。因此输出最大值减去最小值以及两者平均数上取整即可。

int n=read();
int mn=0,mx=0;
for(int i=1,x;i<=n;++i){
  x=read();
  if(!mn) mn=mx=x;
  else mn=min(mn,x),mx=max(mx,x);
}
printf("%d %d\n",mx-mn,(mn+mx-1)/2+1);

C.Cidoai的植物

完全按照题意模拟是不可行的。我们考虑每次只会删除一个位置上的数，且每次种植物只会往空位上种，因此使用一个数组记下每一列的空位标号即可。

unsigned seed;
unsigned rnd(){
    unsigned ret=seed;
    seed^=seed<<13;
    seed^=seed>>17;
    seed^=seed<<5;
    return ret;
}
int main() {
    ll n,m,k;
    cin>>n>>m>>k>>seed;
    ll mp[n+1][m+1];
    memset(mp,0,sizeof(mp));
    vector<ll> st[m+1];
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++)st[i].push_back(j);
    }
    for(int i=1;i<=k;i++){
        ll op=(rnd()%2)+1;
        if(op==1){
            ll ii=(rnd()%m)+1;
            ll x=(rnd()%(n*m))+1;
            if(st[ii].empty())continue;
            for(const auto& i:st[ii]){
                mp[i][ii]=x;
            }
            st[ii].clear();
        }else{
            ll a=(rnd()%n)+1;
            ll b=(rnd()%m)+1;
            mp[a][b]=0;
            st[b].push_back(a);
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            ans^=mp[i][j]*((i-1)*m+j);
        }
    }
    cout<<ans;
}

D.Cidoai的猫猫

读题后我们可以发现，题目要求的其实是：定义 为将字符串 中所有连续相同字符长度超过 的子串压缩为长为 的子串后的字符串串长。求出所有 。

有关转化题意证明：考虑 ，当 时，并无法减短 ，只有当 时才能减短 ，而此时需满足 。由此便可得到转化后的题意。

字符串 中一个长为 的连续相同字符构成的子串会对 的长度贡献 ，因此将所有连续相同字符构成的子串长度记录在数组中，倒着逐个计算 即可。

int n=read();
scanf("%s",s+1);
int len=1;
for(int i=2;i<=n;++i){
  if(s[i]==s[i-1]) ++len;
  else{
    if(len>1) cnt[len]++;
    len=1;
  }
}
for(int i=1;i<=n;++i) ans[i]=n;
int nowsum=0;
for(int i=n,now=0;i>=1;--i){
  ans[i]-=nowsum-now*i;
  now+=cnt[i];
  nowsum+=cnt[i]*i;
}
ll sum=0;
for(int i=1;i<=n;++i) sum^=(ll)i*ans[i];
write(sum);

E.Cidoai的可乐

由于边数肯定是 ，我们希望能够让更小的权值在边上出现更多次。考虑按照点权从小到大排序后，从前往后安排边。我们可以证明顶着度数限制只取最前面的点权得到的答案是最优的。因此排序后计算即可。考虑证明：假设选了 个点，满足 ，且 是最小的满足该条件的值。我们选定的点间顺序连边，花费 条边，每个点花费掉一个度数限制，而剩下的 个点顺序连到这 个点上，当第 个点的度数限制被用完后再连第 个点，这样就能达到最小值了。

int n;
struct node{int a,d;}e[N];
inline bool cmp(node x,node y){return x.a<y.a;}
inline void solve(){
    n=read();
    for(int i=1;i<=n;++i) e[i].a=read();
    for(int i=1;i<=n;++i) e[i].d=read();
    sort(e+1,e+n+1,cmp);
    ll ans=0;
    int rst=n-1;
    for(int i=1;i<=n;++i){
        if(e[i].d<rst) ans+=(ll)e[i].d*e[i].a,rst-=e[i].d;
        else{
            ans+=(ll)rst*e[i].a;
            break;
        }
    }
    write(ans);
}

F.Cidoai的自恋

考虑要使无效询问最多，则要使有效询问最少。有效询问的贡献由两部分构成：上界为 的最长上升子序列且满足子序列中任意两个数在原序列之间不存在比它们更大的数，下界为 的最长下降子序列且满足子序列中任意两个数在原序列之间不存在比它们更小的数。我们的目的是使这两者的长度之和最小。

我们有一个显然的思路是，枚举每一个可能的 ，并且使用 的时间复杂度去询问这两者的长度之和。

但是显然我们需要一个时间复杂度为线性的做法。

我们转变思路，将所有数的第一次出现位置记录下来，可以得到一个数组 ，如果一个数 没有出现过，则 。

为了计算有上界 的最长递增子序列，我们从前往后枚举 到 。若存在两个数满足 ，则 是一个无效询问。我们可以维护一个单调栈，每次加入 都要将栈顶 的数弹出。因此一个数 对应的有上界 最长递增子序列长度即为枚举到它时栈的大小。求最长递减子序列类似，枚举 到 即可。时间复杂度 。

const int N=5e6+5;
ll n,k;
int vis[N],pre[N],suf[N];
int stk[N],top;
unsigned seed;
unsigned rnd(){
    unsigned ret=seed;
    seed^=seed<<13;
    seed^=seed>>17;
    seed^=seed<<5;
    return ret;
}
void solve(){
    cin>>n>>k>>seed;
    for(int i=1,x;i<=k;++i){
        x=rnd()%n+1;
        if(!vis[x]) vis[x]=i;
    }
    top=0;
    for(int i=1;i<=n;++i){
        if(vis[i]){
            int x=vis[i];
            while(top&&x<stk[top]) --top;
            stk[++top]=x;
        }
        else
            pre[i]=top;
    }
    top=0;
    for(int i=n;i>=1;--i){
        if(vis[i]){
            int x=vis[i];
            while(top&&x<stk[top]) --top;
            stk[++top]=x;
        }
        else
            suf[i]=top;
    }
    int mn=-1;
    for(int i=1;i<=n;++i){
        if(vis[i]) continue;
        if(mn==-1) mn=i;
        else if(pre[mn]+suf[mn]>pre[i]+suf[i]) mn=i;
    }
    cout<<mn<<'\n';
}