A.时间表查询

寒假营比完了两场，所以当 输出 YES，否则输出 NO。

时间复杂度:

void solve(){
    int x;
    cin>>x;
    if(x==1||x==2){
        cout<<"YES";
    }else{
        cout<<"NO";
    }
}

B.一起做很甜的梦！

ps:本来是给寒假营2的，有点原了，所以给周赛签到了。

考虑区间长度为 的都不能构成排列，那么这些排列所组成的数都包含 两个数字，所以只需要令 ，其他的由 任意填入即可。

时间复杂度:

void solve(){
    int n;
    cin>>n;
    cout<<1<<" ";
    for(int i=n;i>=2;i--){
        cout<<i<<" ";
    }
}

C.翻之

我们考虑每列组成的字符串为 ，一行的翻转必然会影响其他列，所以只有当两列的字符串完全相同时，才会同步变，所以就考虑列组成的字符串中出现次数最多的。

时间复杂度:

void solve(){
    int n,m;
    cin>>n>>m;
    vector<string>s(n+1);
    for(int i=1;i<=n;i++) cin>>s[i],assert(s[i].size()==m),s[i]=" "+s[i];
    map<string,int>cnt;
    for(int j=1;j<=m;j++){
        string t="";
        for(int i=1;i<=n;i++){
            t+=s[i][j];
        }
        cnt[t]++;
    }
    int res=0;
    for(auto [s,g]:cnt){
        res=max(res,g);
    }
    cout<<res;
}

D.乘之

update:2025/1/25 22:10 ps:写得过于抽象了，所以换个讲题人的证明吧。

先确定操作一个区间是 ，先证明两个人操作的区间一定是包含关系或者是连续的关系，因为如果不连续那么两个区间中间的区间和要么>=0让第一个人可以选，要么是<0让第二个人选，所以一定是连续的更优，所以相当于两个人操作一个区间，接下来证明这个区间是整个区间，考虑选了个区间 ，对于左侧如果区间和>=0那么第一个人会选，如果<0那么第二个人会选，右侧情况相同，所以一定是操作整个区间

时间复杂度:

void solve(){
    int n,k;
    cin>>n>>k;
    i64 ans=0;
    for(int i=1;i<=n;i++){
        i64 x;
        cin>>x;
        ans+=(k*x);
    }
    cout<<ans<<"\n";
}

E.在树上游玩

本质上就是一些关键点需要引出一条边到非关键点，由于 ，就只需要对每个关键点联通块引出一点红色边即可，所以最小染色代价就是连通块的个数。

而染色方案就是每个关键点连通块中所接的白边条数之积。

时间复杂度:

const int mod=1e9+7;
void solve(){
    int n,k;
    cin>>n>>k;
    vector<int>vis(n+1,0);
    vector<int>p(n+1);
    for(int i=1;i<=k;i++){
        int x;
        cin>>x;
        vis[x]=1;
    }
    iota(p.begin(),p.end(),0);
    auto find=[&](auto &&self,int x)->int {
        if(p[x]==x) return x;
        p[x]=self(self,p[x]);
        return p[x];
    };
    vector<int>cnt(n+1);
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        if(vis[u]==1&&vis[v]==0){
            cnt[find(find,u)]++;
        }else if(vis[u]==0&&vis[v]==1){
            cnt[find(find,v)]++;
        }else if(vis[u]==1&&vis[v]==1){
            int fu=find(find,u);
            int fv=find(find,v);
            cnt[fv]+=cnt[fu];
            p[fu]=fv;
        }
    }
    i64 res1=0,res2=1;
    for(int i=1;i<=n;i++){
        if(find(find,i)==i&&vis[i]){
            res1++;
            res2=res2*cnt[i]%mod;
        }
    }
    cout<<res1<<" "<<res2; 
}

F.小红的01子序列计数(hard)

我们考虑以每个位置 开始的子串包含01子序列的个数。

首先答案由以下部分组成： 1. 这部分只需要加上自身区间的答案，即该区间中的每个 到 的区间长度乘上 到该位置 的个数 。 然后这段还可以贡献的长度还有 ，此部分的答案就是该区间的 子序列个数乘以 。

2. 的部分就是用每个 所在位置到 的长度乘上字符串头部到该位置 的个数，然后再减去 中 子序列乘以 多贡献的这部分。

3. 中的 和 中的 相互搭配的贡献: 即 中 的个数乘以 （ 中每个 '1' 的位置到 的距离和）。 然后需要减掉这段搭配区间的 子序列个数乘以 的贡献。

时间复杂度:

这样就大功告成！ 之所以要每个位置扣掉，是因为预处理方便。 如果代码看不懂，可以先把 mod 全部删掉后，会清晰一点。

const int mod=1e9+7;
void solve(){
    int n;
    string s;
    cin>>n>>s;
    s=" "+s;
    vector<i64>num0(n+2),num1(n+2),num01(n+2);
    vector<i64>pre_gx1(n+2);
    for(int i=1;i<=n;i++){
        num0[i]=num0[i-1]+(s[i]=='0');
        num1[i]=num1[i-1]+(s[i]=='1');
        num01[i]=num01[i-1]+(s[i]=='1')*num0[i]%mod;
        num01[i]%=mod;
        pre_gx1[i]=pre_gx1[i-1]+(s[i]=='1')*(n-i+1)%mod;
        pre_gx1[i]%=mod;
    }
    vector<i64>gx(n+2);
    for(int i=1;i<=n;i++){
        gx[i]=gx[i-1]+(s[i]=='1')*num0[i]*(n-i+1)%mod;
        gx[i]%=mod;
    }
    // 以 i 为起点
    i64 ans=0;
    for(int i=1;i<=n;i++){
        // 先选 [i,n] 这部分自己的答案
        i64 part1=(gx[n]-gx[i-1])-(pre_gx1[n]-pre_gx1[i-1]+mod)*(num0[i-1])%mod;
        part1%=mod;
        
        //算 [i,n] 这部分 01 还可以贡献的区间长度
        i64 part2= part1+(num01[n]-num01[i-1]+mod-num0[i-1]*(num1[n]-num1[i-1]+mod)%mod)*(i-1)%mod;   //是最后的答案的部分
        part2%=mod;
        // 算 [1,i-1] 这部分自己的答案
        i64 part3=gx[i-1];
        //算 [1,i-1] 这部分需要扣掉的贡献长度
        i64 part4=part3-num01[i-1]*(n-i+1)%mod;
        part4=(part4+mod)%mod;
        //算 [i,n] 这部分的 0 和 [1,i-1] 这部分的 1 的贡献
        i64 part5= (num0[n]-num0[i-1]+mod)%mod*(pre_gx1[i-1])%mod;
        // 扣掉多贡献的部分
        part5=part5-(num0[n]-num0[i-1]+mod)%mod*(n-i+1)%mod*(num1[i-1])%mod;
        ans+=part2+part4+part5;
        ans%=mod;
    }
    cout<<ans;
}