打了20分钟的时候突然被叫去干活了。。心急火燎的交了A题。然后在8.50的时候坐下来想B题，最后在回寝室的床上打完了。。

赛后补了C题。

这里只放了前三题的题解，第四题开始不会了。。

  • A CCA的词典

    可以证明，对两个单词进行排序，如果排序以后相同，那么就可以认为两个原单词是一样的。
    注意到单词长度<=2。所以我们直接比较两个位置的字母排序，然后哈希就可以了。

代码：

#include<bits/stdc++.h>
using namespace std;
int t[100000];
int main()
{
    int n;
    string s;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s;
        int tmp=0;
        int a,b;
        a=s[0]-'a'+1;
        if(s.size()==1)b=0;
        else b=s[1]-'a'+1;
        if(a>b)swap(a,b);
        tmp=a*100+b;
        t[tmp]++;
    }
    int q;

    cin>>q;
    string c;
    while(q--){
        cin>>c;
        int tmp=0;
        int a,b;
        a=c[0]-'a'+1;
        if(c.size()==1)b=0;
        else  b=c[1]-'a'+1;
        if(a>b)swap(a,b);
        tmp=a*100+b;
        cout<<t[tmp]<<endl;
    }
    return 0;
}

  • B CCA的搬运

    这题想了挺久的，然后写的时候由于心急一直写错。。
    首先题目告诉我们，每次取一个球然后会把他放到最上面。
    我们考虑一种比较特殊的情况，每个球都会被取一次。此时我们考虑最后一个球，当他被取的时候，他肯定在最下方。同理，上一个球被取肯定在倒数第二个位置。
    那么位置就被固定了。要让消耗最小，我们其实只能按照小球被叫的顺序从上往下放。

那我们其实只要模拟这个过程就好了。由于小球可能会被重复取，我们其实需要知道当前被取小球的上面有哪些小球。发现n,m<=2000。因此我们开个数组每次都暴力的去维护小球的位置。
复杂度就是O(n*m)

代码：

#include<bits/stdc++.h>
using namespace std;
int vis[2003],c[200003];
int main()
{
    int n,m;
    long long sum=0;
    cin>>n>>m;
    int a[3000],b[3000];
    for(int i=1;i<=n;i++)cin>>a[i];
    long long ans=0;
    long long tot=0;
    for(int i=1;i<=m;i++){
        cin>>b[i];
    }
    for(int i=1;i<=m;i++){
        if(!vis[b[i]]){
            vis[b[i]]=1;
             ans+=sum;
            c[++tot]=b[i];
            sum+=a[b[i]];
        }
       else {
           int tmp=0,k=tot;
           for(int j=tot;j>=1;j--){
               if(c[j]==b[i]){
                   ans+=tmp;
                   k=j;
                   break;
               }
               else tmp+=a[c[j]];
           }
           for(int j=k;j<=tot-1;j++)c[j]=c[j+1];
            c[tot]=b[i];
       }

    }
    cout<<ans<<endl;
}

  • C CCA的子树

    这题应该是比较容易想到的。简单的树形dp。
    首先Error的情况就是只有一条链的时候。
    令dp[i][1/2]表示以点i为根节点的选1/2个子树的最大点权和。
    考虑某个结点x，我们可以在dfs中枚举x连出去的边，得到另一个端点y。根据题意我们可以得到转移方程：
    dp[x][1]=max(dp[y][1],sum[x])。其中sum[x]为选x点的点权和
    dp[x][2]=max(dp[y][2],m1+m2)。其中m1,m2为dp[y][1]中的最大值和次大值。这个m1m2我们可以在计算dp[y][1]的时候进行维护。

代码：

#include<bits/stdc++.h>
using namespace std;
const int inf=1e16;
int n,a[200040],d[200400];
int tot,head[200030];
struct node{
    int to,next;
}e[400050];
long long f[200400][3];
void init(){
    tot=0;
    memset(head,-1,sizeof(head));
    for(int i=0;i<200005;i++)f[i][1]=f[i][2]=-inf;
}
void add(int a,int b){
    tot++;
    e[tot].to=b;
    e[tot].next=head[a];
    head[a]=tot;
}
long long dfs(int x){
    long long m1,m2;
    m1=m2=-inf;
    long long sum=a[x];
    int ff=0;
    for(int i=head[x];~i;i=e[i].next){
        int y=e[i].to;
        ff=1;
        sum+=dfs(y);
        if(m1<f[y][1])m2=m1,m1=f[y][1];
        else if(m2<f[y][1])m2=f[y][1];
        f[x][1]=max(f[x][1],m1);
        f[x][2]=max(f[x][2],f[y][2]);
        f[x][2]=max(f[x][2],m1+m2);
    }
    f[x][1]=max(f[x][1],sum);
    return sum;
}
int main()
{
    init();
    cin>>n;
    int maxi=0;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        add(u,v);
        d[u]++;
        maxi=max(maxi,d[u]);
    }
    dfs(1);
    if(maxi==1)cout<<"Error"<<endl;
    else
    cout<<f[1][2]<<endl;
    return 0;
}