A.CCA的词典

没啥好讲的，map记录下出没出现过，然后每次查询枚举下可能的来源，叠加贡献即可。注意特判aa这种情况

map<string,int>cnt;
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;++i){
        string t;
        cin>>t;
        cnt[t]++;
    }
    int q;
    read(q);
    while(q--){
        string s;
        cin>>s;
        int ans=cnt[s];
        if(s.size()==2&&s[0]!=s[1]){
            swap(s[0],s[1]);
            ans+=cnt[s];
        }
        cout<<ans<<endl;
    }
    return 0;
}

B.CCA的搬运

差点死在这题。。
想到了最优的顺序是按照要拿的顺序堆在一起，但是没注意到一个东西可以拿几次。。
按照第一次出现的顺序堆起来，之后模拟即可。

const int maxn=2e3+10;
struct node{
    int val,id;
}st[maxn];
int top;
int w[maxn];
int vis[maxn];
int pi[maxn];
int n,m;

int main(){
    //freopen("in.txt","r",stdin);
    read(n),read(m);
    for(int i=1;i<=n;++i)read(w[i]);
    for(int i=1;i<=m;++i){
        int x;
        read(x);
        pi[i]=x;
        if(!vis[x]){
            st[++top]={w[x],x};
        }
        vis[x]=1;
    }
    int ans=0;
    for(int i=1;i<=m;++i){
        for(int j=1;j<=top;++j){
            if(st[j].id==pi[i]){
                node tmp=st[j];
                for(int k=j;k>=2;--k){
                    st[k]=st[k-1];
                }
                st[1]=tmp;
                break;
            }
            else{
                ans+=st[j].val;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

C.CCA的子树

还是比较好想的树形dp。
题目要求选择的两个子树根节点不能有祖孙关系，其实也就是说，他们得是一个节点下，任意两个儿子所在子树的子树（有点绕），也就是说，他们的lca不能是他们其中的一个。若分别取枚举两个子树的根节点则需要 $n^2$ 的时间，所以考虑在他们的lca处合并。对于一个lca，我们向下找要求的子树即可（qaq真的不知道怎么表达）。具体看代码：

#define int ll
const int maxn=2e5+10;
struct Edge{
    int to,next;
}e[maxn<<1];
int head[maxn],cnt;
void add(int x,int y){
    e[cnt].to=y;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
int w[maxn];
int sum_of_son[maxn];
int mx_of_son[maxn];
int n;
void dfs(int u,int fa){
    sum_of_son[u]=w[u];
    for(int i=head[u];~i;i=e[i].next){
        int v=e[i].to;
        if(v==fa)continue;
        dfs(v,u);
        sum_of_son[u]+=sum_of_son[v];
    }
}
int ans=-inf;
void solve(int u,int fa){
    vector<int>tmp;
    for(int i=head[u];~i;i=e[i].next){
        int v=e[i].to;
        if(v==fa)continue;
        solve(v,u);
        tmp.push_back(mx_of_son[v]);
    }
    sort(tmp.begin(),tmp.end(),greater<int>());
    mx_of_son[u]=sum_of_son[u];
    if(tmp.size()<1)return ;
    mx_of_son[u]=max(mx_of_son[u],tmp[0]);
    if(tmp.size()<2)return ;
    ans=max(ans,tmp[0]+tmp[1]);
}

signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    //clock_t c1 = clock();
    //===========================================================
    read(n);
    memset(mx_of_son,-inf,sizeof(mx_of_son));
    memset(head,-1,sizeof(head));
    rep(i,1,n)read(w[i]);
    rep(i,2,n){
        int u,v;
        read(u),read(v);
        add(u,v);add(v,u);
    }
    dfs(1,-1);
    solve(1,-1);
    //cout<<endl;
    if(ans==-inf){
        puts("Error");
    }
    else{
        cout<<ans<<endl;
    }
    //===========================================================
    //std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
    return 0;
}

D.CCA的小球

这题本质解法是容斥原理。但个人感觉细节还是蛮多的Orz。
首先，正面算的话想不出来，所以考虑下容斥。
那么，正难则反，考虑n个球任意排列，方案数为n!.
题目要求不能有相邻球颜色相同，所以，我们需要减去不合理方案。根据容斥公式：
设至少有i组相邻颜色相同小球的方案数为f(i)
则，答案为

$ans=n!+\sum_{i=1}^{num2}(-1)^iC_{num2}^if(i)$

考虑 $f(i)$ ：假设现在要求至少i组相邻小球颜色相同，则，考虑捆绑法，将这i组小球分别捆绑，则，原来n个小球就变成了n-i个小球全排列。同时，考虑我们上面的总情况没有去除两个相同颜色小球颠倒位置的情况，所以需要乘上 $2^i$ ，综上 $f(i)=2^i(n-i)!$
最后，我们还是要去掉两个颜色相同小球颠倒的情况，所以，乘个 $2^{num2}$ 的逆元即可。
另外，对于上面的式子，我们也可以用二项式反演处理：
设g(i)为恰好有i组相邻小球颜色相同，则：

$f(k)=\sum_{i=k}^{num2}C_{num2}^ig(i)$
（为什么要乘上组合数：每次可以选择不同颜色相邻）
根据反演公式：

$g(k)=\sum_{i=k}^{num2}(-1)^{(i-k)}f(i)$
以此代替容斥原理（不过感觉难点不在这吧，而是在如何求出 $f(k)$ ）

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(int i = a; i <= n; ++ i)
#define per(i, a, n) for(int i = n; i >= a; -- i)
//#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}

template<typename T> void read(T &x)
{
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}

int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int lcm(int a,int b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){
    ll ans=1;
    while(n){
        if(n&1) ans=(ans*a)%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans%mod;
}
//==============================================================
const int maxn=1e6+10;
#define int ll
int n;
int a[maxn];
int f[maxn];
int pow2[maxn];
int finv[maxn];
int inv2[maxn];
unordered_map<int,int>cnt;
void init(){
    f[0]=1;
    rep(i,1,maxn-1)f[i]=f[i-1]*i%mod;
    finv[maxn-1]=ksm(f[maxn-1],mod-2);
    for(int i=maxn-2;i>=0;--i){
        finv[i]=1ll*finv[i+1]*(i+1)%mod;
    }
    pow2[0]=1;
    for(int i=1;i<maxn;++i){
        pow2[i]=1ll*pow2[i-1]*2%mod;
    }
    inv2[0]=1;
    ll inv22=ksm(2,mod-2);
    for(int i=1;i<maxn;++i){
        inv2[i]=inv2[i-1]*inv22%mod;
    }
}

ll C(ll n,ll m){
    if(m>n||m<0)return 0;
    //cerr<<n<<" "<<m<<endl;
    //cerr<<f[n]<<" "<<finv[n-m]<<" "<<finv[m]<<endl;
    return 1ll*f[n]*finv[n-m]%mod*finv[m]%mod;
}

int sig(int x){
    return (x&1)?-1:1;
}

signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    //clock_t c1 = clock();
    //===========================================================
    init();
    read(n);
    ll res=f[n];
    for(int i=1;i<=n;++i){
        read(a[i]);
        cnt[a[i]]++;
    }
    int cnt2=0;
    for(auto x:cnt)cnt2+=(x.second==2);
    for(int i=1;i<=cnt2;++i){
        res=(res+sig(i)*C(cnt2,i)*f[n-i]%mod*pow2[i]%mod)%mod;
        res=(res%mod+mod)%mod;
    }
    cout<<res*inv2[cnt2]%mod<<endl;
    //===========================================================
    //std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
    return 0;
}

牛客练习赛78（AB.思维C.树形dp（树中两个子树最大贡献和）D容斥原理E枚举

A.CCA的词典

B.CCA的搬运

C.CCA的子树

D.CCA的小球