周赛77

B

注意力

注意到我们要求每个长度为9的子数组都出现1-9，那么实际上构造方式只能是选择一个1-9的排列然后一直循环，最后剩下的不到9个也可以利用前面的组成长度为9的排列。

但是注意到这样是不行的，也就是只有剩余不到9个的数里没有重复的才行。这个条件也可以转化为，所有数字中最大出现次数-最小出现次数不能超过1

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int cnt[10]={0};
    for(int i=0;i<n;i++){
        int t;
        cin>>t;
        cnt[t]++;
    }
    int mn=1e9,mx=0;
    for(int i=1;i<=9;i++){
        mn=min(mn,cnt[i]);
        mx=max(mx,cnt[i]);
    }
    if(mx-mn<=1){
        cout<<"YES\n";
    }
    else{
        cout<<"NO\n"; 
    }
}

C

数论

给你两个数ab，问他们的线性组合能不能等于某个特定的数k？实际上他们的线性组合，最后能得到的数一定是的倍数，所以我们看k是不是的倍数就行了，这是裴蜀定理的一个重要结论

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll gcd(ll x,ll y){
    return y?gcd(y,x%y):x;
}
int main(){
    int x,y,a,b,c,d;
    int t;
    cin>>t;
    while(t--){
        cin>>x>>y>>a>>b>>c>>d;
        int g1=gcd(a,b);
        int g2=gcd(c,d);
        
        if(y%g1==0&&x%g2==0){
            cout<<"YES\n";
        }
        else{
            cout<<"NO\n";
        }
    }
}

D

位运算+并查集

两个数字按位与不为0就有连边，问最后最大的连通块的大小？

按位与不为0的意思就是存在某一位，两个数在这一位都为1。那么我们可以把元素放进位对应地桶里，然后对于每个数字，把它为1的位都连接起来，合并对应的桶，最后去重一下看最大集合就行

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        set<int>s[70];
        int n;
        cin>>n;
        int vis[70][70]={0};

        for(int k=0;k<n;k++){
            long long x;
            cin>>x;
            for(int i=0;i<=60;i++){
                if(x>>i&1){
                    s[i].insert(k);
                    for(int j=i+1;j<=60;j++){
                        if(x>>j&1){
                            vis[i][j]=1;
                        }
                    }
                }
            }
        }
        int f[70];
        for(int i=0;i<=60;i++)f[i]=i;
        auto &&find=[&](auto &&find,int x)->int{
            if(f[x]==x)return x;
            return find(find,f[x]);
        };
        for(int i=0;i<=60;i++){
            for(int j=i+1;j<=60;j++){
                if(vis[i][j]){
                    int fx=find(find,i),fy=find(find,j);
                    if(fx!=fy){
                        f[fx]=fy;
                        for(int x:s[fx]){
                            s[fy].insert(x);
                        }
                    }
                }
            }
        }
        int ans=0;
        for(int i=0;i<=60;i++){
            ans=max(ans,(int)s[i].size());
        }
        cout<<ans<<'\n';
    }
}

E

巧妙的前缀和+维护出现下标

给一个01串，问一个区间里所有子数组的按位或之和。实际上就是问区间内至少含一个1的的子数组的数量。正难则反，可以算区间内全零子数组的数量。然后这个东西可以前缀和维护。但问题是可能可能正好在某个0区间的内部，答案并不完整，所以我们需要找到内部一个完整的地方，也就是a[l]=a[r]=1的，这个区间内的答案都是完整的，具体来说我们可以维护一个位置两侧的第一个1的位置，然后l1就是l后面第一个1的位置，r1就是r前面第一个1的位置。然后我们还要处理这两段的答案，这两段其实都是全0，和前面一样的处理

#include<bits/stdc++.h>
using namespace std;
#define int long long
int sum[202020],pre[202020],nxt[202020];
int cal(int x){
    return x*(x+1)/2;
}
signed main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    s=' '+s;
    int len=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='0'){
            len++;
            sum[i]=sum[i-1];
        }
        else{
            sum[i]=sum[i-1]+cal(len);
            len=0;
        }
    }
    for(int i=1;i<=n;i++){
        if(s[i]=='1'){
            pre[i]=i;
        }
        else{
            pre[i]=pre[i-1];
        }
    }
    nxt[n+1]=n+1;
    for(int i=n;i>=1;i--){
        if(s[i]=='1'){
            nxt[i]=i;
        }
        else{
            nxt[i]=nxt[i+1];
        }
    }
    
    int q;
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        int l1=nxt[l];
        int r1=pre[r];
        int ans=cal(r-l+1);
        if(l1>r1){
            ans=0;
        }
        else{
            ans-=sum[r1]-sum[l1];
            ans-=cal(r-r1);
            ans-=cal(l1-l);
        }
        cout<<ans<<'\n';
    }
}

F

树形dp

一棵树上选出一些点，从这个集合里随机选两个点uv，可以相同，问所有选法中，每个点作为出现了多少次。

一个点i能作为uv的lca，其实就是要么u在i的一个子树，v在另一个子树，要么是u就是i，v在一个子树里，要么是u=v=i。这三种情况分开讨论就行了

第一种情况，我们可以统计每个点为根的子树中，集合中的点的个数，然后对于一个子树i，对答案的贡献就是，其中是所有子树的之和，虽然uv可以交换位置，应该乘二，但是这个计算方式已经计算了交换位置的情况了，不用乘

第二种情况，只有在当前节点i在集合里时才有贡献，贡献就是，含义同上，这里没有考虑交换位置的情况，但是也可以交换，所以应该乘二

第三种情况，只有在i在集合里才有贡献，贡献就是1，因为，交换了也是一样的，这个组合只会出现一次

#include<bits/stdc++.h>
using namespace std;
vector<int>a[101010];
long long cnt[101010],sz[101010],vis[101010];
void dfs(int u,int f){
    for(int v:a[u]){
        if(v==f)continue;
        dfs(v,u);
        sz[u]+=sz[v];
    }
    long long sum=0,tot=0;
    for(int v:a[u]){
        if(v==f)continue;
        tot+=sz[v];
    }
    for(int v:a[u]){
        if(v==f)continue;
        sum+=(tot-sz[v])*sz[v];
    }
    cnt[u]+=sum;
    if(vis[u])cnt[u]+=tot*2;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    int k;
    cin>>k;
    for(int i=0;i<k;i++){
        int t;
        cin>>t;
        sz[t]=1;
        cnt[t]=1;
        vis[t]=1;
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)cout<<cnt[i]<<' ';
}