Good Bye 2020

---

前言

​ 虽然小号上分了，但我很伤心，因为……..

​ 我放假能不能上紫呢！？

---

题解

---

A. Bovine Dilemma

​ 暴力枚举水题。

B. Last minute enhancements

​ 贪心水题。

C. Canine poetry

​ 考虑长度为2，3的回文串，然后用一个数组维护字符是否被修改过。

        scanf("%s",s+1);int n=strlen(s+1),ans=0;
        mst(vis,0);for(int i=1;i<=n;i++){
            int f=0;
            if(s[i]==s[i-1]&&!vis[i-1]) f=1;
            if(i>=2&&s[i]==s[i-2]&&!vis[i-2]) f=1;
            ans+=(vis[i]=f);
        }printf("%d\n",ans); 

D. 13th Labour of Heracles

​ 贪心，用优先队列维护度数大于1的，权越大在前面，权相同按度数排。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int n;
ll a[N],ans[N];
int deg[N];
struct node{
    ll x,y;
    bool operator<(const node&no)const{
        return x==no.x?y<no.y:x<no.x;
    }
}; 
int main(){
    int t;scanf("%d",&t);
    while(t--){
        scanf("%d",&n);mst(deg,0);
        priority_queue<node>q;
        ll s=0;for(int  i=1;i<=n;i++) scanf("%lld",&a[i]),s+=a[i];
        for(int  i=1;i<n;i++){
            int u,v;scanf("%d%d",&u,&v);
            deg[u]++,deg[v]++;
        }
        for(int i=1;i<=n;i++){
            if(deg[i]>1) q.push({a[i],(ll)deg[i]});
        }
        int cnt=n-2;printf("%lld",s);
        while(cnt--){
            node u=q.top();
            s+=u.x;
            printf(" %lld",s);
            if(u.y==2){
                q.pop();
            }
            else {
                q.pop();
                q.push({u.x,u.y-1});
            } 
        }printf("\n");
    }
    return 0;
}

E. Apollo versus Pan

​ 按位计算贡献，题解说的很明白了。

---

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5,M=60,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int t,n;
ll a[N],w[65]; 
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=0;i<60;i++) w[i]=0;
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            for(int j=0;j<M;j++) w[j]+=a[i]>>j&1;
        }
        ll ans=0;
        for(int i=1;i<=n;i++){
            ll Xor=0,And=0;
            for(int j=0;j<M;j++){
                if(a[i]>>j&1){
                    And+=(1LL<<j)%mod*w[j];
                    Xor+=(1LL<<j)%mod*n;
                    And%=mod,Xor%=mod; 
                }else Xor+=(1LL<<j)%mod*w[j],Xor%=mod;
            }
            ans=(ans+Xor*And%mod)%mod;
        }printf("%lld\n",ans);
    }
    return 0;
}

F. Euclid’s nightmare

题意：给定$n$个$m$维向量，每个向量最多两维是$1$，其他都是0，问最多能生成多少个不同的$m$维向量，和最小生成这么多个向量的子集。

思路：并查集，每个向量看成一条边，然后连通分量的大小就是第二个答案，然后最大生成的向量个数就是$2^{size}$个，从小到大加入子集就满足字典序了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int n,m,s[N];
int find(int x){
    return x==s[x]?x:s[x]=find(s[x]);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m+1;i++) s[i]=i;vector<int>ans;
    for(int i=1;i<=n;i++){
        int k;scanf("%d",&k);
        int u,v=m+1;
        scanf("%d",&u);
        if(k==2) scanf("%d",&v);
        u=find(u),v=find(v);
        if(u!=v){
            s[u]=v;
            ans.pb(i);
        }
    }
    ll t=1,sz=(int)ans.size();
    for(int i=0;i<sz;i++) t=(t<<1)%mod;
    printf("%lld %d\n",t,sz);
    for(int i:ans) printf("%d ",i);printf("\n");
    return 0;
}