YL 模拟赛总结 6

Problem

T1

为了方便处理，我们令男生为 \(1\)，女生为 \(-1\)。

求一遍前缀和 \(sum\)，若存在两个下标 \(l,r\) 使得 \(sum_l=sum_r\)，则说明区间 \([l+1,r]\) 的和为 \(0\)，即男女人数相等。在这样的区间中取长度最大的即可。

需要特殊处理 \(sum_0\)。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,ans=-1e9;
int a[100031],s[100031];
map<int,bool> vis;
map<int,int> first;

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(!a[i]) a[i]=-1;
        s[i]=s[i-1]+a[i];
        //cout<<s[i]<<' ';
    }
    //cout<<'\n';
    vis[s[0]]=1; //特殊处理sum_0
    for(int i=1;i<=n;i++){
        if(!vis[s[i]]) vis[s[i]]=1,first[s[i]]=i;
        else{
            if(ans<i-first[s[i]]){
                ans=i-first[s[i]];
                //cout<<last[s[i]]+1<<' '<<i<<'\n';
            }
        }
    }
    cout<<(ans==-1e9?0:ans);
    return 0;
}

T2

将字符串 \(A\) 按照下标 \(\bmod \gcd(|A|,|B|)\) 的值进行分类，统计 \(A\) 中每一类中的每一个字符在字符串 \(B\) 中出现的次数，将这些次数相加即为每一类字符的匹配次数，乘以 \(\dfrac{n}{\operatorname{lcm}(|A|,|B|)}\)（即以 \(\operatorname{lcm}(|A|,|B|)\) 为循环节的循环次数）即为答案。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,m,ans,x;
string s,t;
int cnt[31][1000031];

signed main(){
    cin>>n>>m>>s>>t;
    x=__gcd(s.size(),t.size());
    for(int i=0;i<t.size();i++)
        cnt[i%x][t[i]-'a'+1]++;
    for(int i=0;i<s.size();i++)
        ans+=cnt[i%x][s[i]-'a'+1];
    cout<<ans*(n/(s.size()/x*t.size()/s.size()));
    return 0;
}

T3

我们令节点 \(x\) 需要染黑的点的总数为 \(all\)。

首先题目中所说的 \(B\) 限制其实可以转化为“至少要将节点 \(x\) 的子树内至少要有 \(all-y\) 个点被染黑。

同时 \(A\) 限制中若多次出现同一个 \(x\)，则仅需保留最大值。

然后就进行一遍树形 dp，求出树上每个节点的子树大小，并将节点 \(x\) 子树中所有需要染黑的点都算到 \(x\) 下面。

接着我们发现经过转化后的 \(B\) 限制中需要染黑的节点数其实已经包括了子树内需要染黑的节点数，也就是说 \(B\) 限制中需要染黑的节点数一定 \(\ge A\) 限制中需要染黑的节点数。

于是我们又发现，因为子树大小不变，所以 \(all\) 越大就越可能满足上述条件。

因此我们考虑二分 \(all\) 的值，检验其是否满足条件即可。

#include<bits/stdc++.h>
using namespace std;

int n,a,b;
vector<int> e[100031];
int ax[100031],bx[100031];
int ain[100031],fin[100031];
int sz[100031];

void dfs(int u,int fa){
    int sum=0;
    sz[u]=1;
    for(auto i:e[u])
        if(i!=fa) dfs(i,u),sz[u]+=sz[i],sum+=ain[i];
    ain[u]=max(ain[u],sum);
}
bool judge(int u,int fa){
    int sum=1;
    for(auto i:e[u]){
        if(i!=fa){
            if(!judge(i,u)) return 0;
            sum+=fin[i];
        }
    }
    fin[u]=min(fin[u],sum);
    return fin[u]>=ain[u];
}
bool check(int x){
    for(int i=1;i<=n;i++) fin[i]=sz[i];
    for(int i=1;i<=b;i++) fin[ax[i]]=min(fin[ax[i]],x-bx[i]);
    return judge(1,0)&&fin[1]>=x;
}

int main(){
    cin>>n;
    for(int i=1,u,v;i<n;i++) cin>>u>>v,e[u].push_back(v),e[v].push_back(u);
    cin>>a;
    for(int i=1,x,y;i<=a;i++) cin>>x>>y,ain[x]=max(ain[x],y);
    cin>>b;
    for(int i=1;i<=b;i++) cin>>ax[i]>>bx[i];
    dfs(1,0);
    int l=ain[1]-1,r=n+1;
    while(l+1<r){
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid;
    }
    cout<<(r>n?-1:r);
    return 0;
}

T4

因为 std 有误，所以咕了。