菜鸡赛后补的题（本校有大佬拿了金牌%%%)

A - Krypton

暴力枚举所有组合(2^7)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
typedef long long ll;
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
int t, n, a[maxn], b[maxn];
char s[maxn];
int main() {
    n = read();
    int ans = 0;
    a[1] = 1; a[2] = 6; a[3] = 28; a[4] = 88; a[5] = 198; a[6] = 328; a[7] = 648;
    b[1] = 8; b[2] = 18; b[3] = 28; b[4] = 58; b[5] = 128; b[6] = 198; b[7] = 388;
    for (int i = 1; i < (1<<7); i++) {
        int tmp = 0, res = 0;
        for (int j = 0; j < 7; j++) {
            if((i>>j)&1) tmp += a[j + 1], res += b[j + 1];
        }
        if(tmp > n) continue;
        res += n * 10;
        ans = max(ans, res);
    }
    printf("%d\n", ans);
    return 0;
}

D - Meaningless Sequence

打表找规律，发现ai的值就是c的次方数(ai二进制1的个数)的值。然后比较裸的数位dp.

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

typedef long long ll;

const int mod=1e9+7;

ll dp[3005][2];
char d[3005];
int n,c;

ll dfs( ll now,bool limit )
{
    if( now==-1 ) return 1;
    if( dp[now][limit] ) return dp[now][limit];

    int up=limit ? d[now]-'0': 1;
    ll res=0;
    for( int i=0;i<=up;i++ )
    {
        res+=dfs( now-1,limit && i==up )*( i==1 ? c : 1 )%mod ;
        res%=mod;
    }
    return dp[now][limit]=res;
}

int main()
{

    scanf("%s%d",&d,&c);
    int n=strlen(d);
    reverse(d,d+n);
    printf("%lld\n",dfs(n-1,1));
}

F - Strange Memory

看题目的式子就往dsu想，枚举轻链然后找点对。由于求得贡献是下标的异或值，所以我们将点权作为数组下标，然后开20位空间，记录对应权值的下标二进制下各位的1的个数。（有个坑点，二进制拆解下标记得用for循环20次，不要用while(y) ）

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

const int maxn=1e5+10;
typedef unsigned long long ll;
int head[maxn],to[maxn<<1],nex[maxn<<1],tot,a[maxn];
int n,k;

void add( int x,int y )
{
    to[tot]=y;nex[tot]=head[x];
    head[x]=tot++;
}

int fa[maxn],siz[maxn],son[maxn],nowson,dep[maxn];
ll sum[maxn],ans[maxn],num[maxn];

void dfs( int x,int f )
{
    fa[x]=f;
    dep[x]=dep[f]+1;
    siz[x]=1;
    for( int i=head[x];~i;i=nex[i] )
    {
        int v=to[i];
        if( v==f ) continue;
        dfs(v,x);
        siz[x]+=siz[v];
        if( siz[v]>siz[son[x]] ) son[x]=v;
    }
}

ll sp[maxn*20][20][2];

void sol( int x,int y ,int p )
{
    int cnt=0;
    for( int i=0;i<20;i++ )
    {
        if( y>>i & 1 ) sp[x][i][1]+=p;
        else sp[x][i][0]+=p;
    }

}

void cal( int x,int p )
{
    sol(a[x],x,p);
    for( int i=head[x];~i;i=nex[i] )
    {
        int v=to[i];
        if( v==fa[x] || v==nowson ) continue;
        cal(v,p);
    }
}

void query( int x,int lca )
{
    int d=a[lca]^a[x];  // //计算贡献 改这里 
    for( int i=0;i<20;i++ )
    {
        if( x>>i & 1 ) ans[lca]+=(1ll<<i)*sp[d][i][0];
        else ans[lca]+=(1ll<<i)*sp[d][i][1];
    }

    for( int i=head[x];~i;i=nex[i] )
    {
        int v=to[i];
        if( v==fa[x] ) continue;
        query(v,lca);
    }
}


void dsu( int x,int T )
{
    for( int i=head[x];~i;i=nex[i] )
    {
        int v=to[i];
        if( v!=fa[x] && v!=son[x] ) dsu(v,0);
    }
    if( son[x] ) dsu(son[x],1),nowson=son[x];

    for( int i=head[x];~i;i=nex[i] )
    {
        int v=to[i];
        if( v==fa[x] || v==nowson ) continue;
        query(v,x);  //  //改这里  
        cal(v,1);    // //改这里 
    }
    sol(a[x],x,1);
    nowson=0;
    if( !T ) cal(x,-1);
}

int main()
{
    memset(head,-1,sizeof(head));
    scanf("%d",&n);
    for( int i=1;i<=n;i++ ) scanf("%d",&a[i]);
    for( int i=1;i<n;i++ )
    {
        int x,y;scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs(1,0);
    dsu(1,1);
    ll res=0;
    for( int i=1;i<=n;i++ ) res+=ans[i];
    printf("%lld\n",res);
}

K - Ragdoll

看题没思路的话，对着式子打表。你会发现满足gcd(i,j)==(i^j)的点对，一定满足i-j=gcd(i,j)。然后就是枚举因子打表了。
然后三种操作就是并查集的按秩合并，用unordered_map维护一下集合每种权值的个数（注意map会T）.

#include<bits/stdc++.h>

using namespace std;

const int maxn=3e5+10;
typedef long long ll;
vector<ll> dd[maxn];
int a[maxn],fa[maxn];
int siz[maxn];
ll ans=0;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar() ;
    }
    return x * f;
}

unordered_map<ll,ll> mp[maxn];

int get_fa( int x ) { return x==fa[x] ? x:fa[x]=get_fa(fa[x]); }

void solve( int fx,int fy )
{
    for( pair<ll,ll> g:mp[fy] )
    {
        for( int l=0;l<dd[g.first].size();l++ )
        {
            int tmp=dd[g.first][l];
            if( mp[fx].count(tmp) )
            {
                ans+=mp[fx][tmp]*g.second;
            }
        }
    }
    for( pair<ll,ll> g:mp[fy] ) 
    {
        mp[fx][g.first]+=g.second;
    }
    mp[fy].clear();
    fa[fy]=fx;
    siz[fx]+=siz[fy]; 
}


int main()
{
    for( int i=1;i<=2e5;i++ )
    {
        for( int j=1;j*j<=i && j<i;j++ )
        {
            if( i%j==0 )
            {
                int tmp=i-j;
                if( (tmp^i)==j )
                {
                    dd[i].push_back(tmp);
                    dd[tmp].push_back(i);
                }
                if( j*j!=i )
                {
                    int cc=i/j;
                    int tmp=i-cc;
                    if( (tmp^i)==cc )
                    {
                        dd[i].push_back(tmp);
                        dd[tmp].push_back(i);
                    }
                }
            }
        }
        sort(dd[i].begin(),dd[i].end());
        dd[i].erase(unique(dd[i].begin(),dd[i].end()),dd[i].end());
    }

    int n,m;
    n=read(),m=read();


    for( int i=1;i<=n;i++ )    a[i]=read(),fa[i]=i,siz[i]=1,mp[i][a[i]]++;


    while( m-- )
    {
        int t,x,y;
        t=read(),x=read(),y=read();
        if( t==1 )
        {
            a[x]=y;
            fa[x]=x;
            mp[x][y]++;
            siz[x]=1;
        }
        else if( t==2 )
        {
            int fx=get_fa(x),fy=get_fa(y);
            if( fx!=fy )
            {
                if( siz[fx]>siz[fy] )    solve(fx,fy);
                else solve(fy,fx);
            }
        }
        else if( t==3 )
        {
            if( y!=a[x] ) 
            {
                int fx=get_fa(x);
                for( int i=0;i<dd[a[x]].size();i++ )
                {
                    int tmp=dd[a[x]][i];
                    if( mp[fx].count(tmp) )    ans-=mp[fx][tmp];
                }
                mp[fx][a[x]]--;
                a[x]=y;
                mp[fx][y]++;
                for( int i=0;i<dd[y].size();i++ )
                {
                    int tmp=dd[y][i];
                    if( mp[fx].count(tmp) ) ans+=mp[fx][tmp];
                }
            }
        } 
        printf("%lld\n",ans);
    }


}

2020ccpc长春站

A - Krypton

D - Meaningless Sequence

F - Strange Memory

K - Ragdoll