CUGBACM 春季训练1部分题解

队员李玮宸

本人高中零基础，是从大学才开始系统学习算法的，目前进度覆盖不全，所以后面几题能力有限，只写我会的。

A题—因为开题之前几分钟队长发了题单了，所以我先把这个写了，成功拿下一血

E题—我先看的B题，没看懂，就先找另一个A题，这个挺简单，脑筋急转弯，中间隔一个就行，就是2*x-1,成功拿下一血

B题—最难的是读题，第一次看全英文题面，有些句子理解地不顺畅(英语不好，我已急哭)，不过其实看数字和样例可以大大加深理解程度，其实就是取一个最小值的问题，成功拿下一血

F题—另一个b题，哈希表存次数，然后为了防止麻烦的条件判断，可以新开一个字符串,成功拿下一血

string s1="";
for(int i=0;i<s.size();i++){
   if(mp[s[i]]!=maxn){
    s1+=s[i];
   }
}

截止到这里，都挺顺利的，看了看表，前四个题一共花了26分钟，稳居榜一，然后不出意外的话意外就要来了

G题

题目大意是：给你一个全是大写字母的字符串，每次你只能对它进行两种操作，要么从中加上一个A，要么从中删除一个A，再给你一个新字符串，问你能不能从原字符串变成新字符串，能的话输出最少几次可以变成。

这个对我来说看似不太简单，实则也确实有点难，事实上我一直是字符串模拟苦手，不过这个还好，比较考思维。这是第一个比较卡我的题，卡了大概半个小时

这个题的要点主要有两个，一个是判断能不能变成

对于这个来说，因为我们每次都可以对A进行操作，所以主要就是看A以外的字母。

首先，你不能有新的字母，必须是同一组字母，因为你只能对A操作

其次，非A字母出现的顺序也得一样，不然不可能变。

其实分析到这里，整个题目的流程已经可以想象出来了：

我们只需要把A当初分隔符，那么就是

S1：###B#####C##D##…

S2：#B##C######D#…

只有这样，才能在只对中间的分隔符操作的情况下变成另一个

在这里，我开了两个<int,char>哈希表，存S1和S2的非A字母和它的出现下标，如果把字母放在KEY位置，会重复，其实这里pair也可以，然后只需要比对mp1==mp2即可了

其二，也是这个题的核心逻辑：比对每个字母之间A的个数的差，多了就删，少了就加，反正想要变成新的字符串，只用把中间差的绝对值算出来就行。

开四个数字，分别存S1和S2的非A字母的下标，以及它每个字母之间的差值(差分数组，算一下差就行)

int pos1[N];
int pos2[N];
int pos3[N];
int pos4[N];

然后，由于一开始也有可能有A，所以我们把pos1和2的[0]设成1，后面相减的时候就可以直接算出第一个字母前面有几个A

int cnt=0;
pos1[0]=1;
pos2[0]=1;
for(int i=0;i<s.size();i++){
     t[s[i]-'A'+1]=1;
     if(s[i]!='A'){
         mp[++cnt]=s[i];
         pos1[cnt]=i+1;
         pos3[cnt]=pos1[cnt]-pos1[cnt-1]; //这个就是存每个之间有几个A
     }
}

注意，字母后面有可能有A，所以我们把cnt算出来之后，还需考虑最后有几个A

pos3[cnt+1]=s.size()-pos1[cnt];

然后再跑一遍S2

cnt=0;  //记得归零
string news;
cin>>news;
int flag=0;
for(int i=0;i<news.size();i++){
    if(t[news[i]-'A'+1]==0)flag=1; //这里我当时直接开桶数组判断了，但回过神来好像直接比较mp就可以，🍬完了
    if(news[i]!='A'){
        mp1[++cnt]=news[i];
        pos2[cnt]=i+1;
        pos4[cnt]=pos2[cnt]-pos2[cnt-1];
    }
}
pos4[cnt+1]=news.size()-pos2[cnt];

然后，把每个pos3pos4数组对应的求差就行了

if(flag==1)cout<<-1<<endl;
else if(mp!=mp1)cout<<-1<<endl;
else{
    int ans=0;
    for(int i=1;i<=cnt+1;i++){ //记得开到cnt+1
        ans+=abs(pos3[i]-pos4[i]);
    }
    cout<<ans<<endl;
}

这个其实理清逻辑也还好，稳健一点不难想，难的是各种边界，嗯，到这里之后成功拿下五个一血，回归榜一，感觉良好

然后，咚咚咚

C题和D题

C题我看了一遍题目，看完能理解，关键是我一看这不是动态区间查询吗？我也没学线段树啊，想套st表，不过忘干净了…然后就放弃了，对K<=5没有一点想法

D题重量级的来了，本来我在这里五个一血，时间是绝对优势的，到此时也才进行了一个小时出头，然后我就去刚D题了：

这是一道树上DFS，大意是给了一颗树，每个节点有它的权值，问你每个节点，从1到这个节点的路径(不走回头路，一气呵成),如果路径上的节点有重复值，输出Yes，否则No

DFS我熟啊，然后直接上手了，然后就懵了，看来还是不能纸上谈兵，一上实战就露出马脚了

一开始，我甚至是开vis数组防止回头的，丝毫没想多传入一个fa就行了，然后又想的是怎么开哈希表标记权值，具体的我已经忘了，只记得逻辑一团乱麻，甚至还想每一次都跑一遍DFS

事实上，DFS核心的在哪return，在哪标记，在哪回溯我其实没有掌握好

最后几分钟甚至已经祭出AI了，还是没怎么明白

接下来我以我的视角讲一下这个题我最后的正确解法

int n;
int wei[N];
vector<int> adj[N];
bool flag[N]; //这个数组用来记录从1到i的路径是不是有重复

然后，就是最核心的DFS

void dfs(int x,int fa){ //传入的一个是节点，一个是父节点，用来防止往回走
    mp[wei[x]]++; //在这里把节点权值入哈希表
    if(mp[wei[x]]>1||flag[fa])flag[x]=1; //最抽象的一点：首先必须这个点的次数要大于1才能有重复，其次，如果前面以及有点是重复的了，就可以直接大大方方标记
    else flag[x]=0; 
    for(auto i:adj[x]){
        if(i==fa)continue;
        dfs(i,x);
    }
    mp[wei[x]]--; //回溯状态，需要跟标记对称，所以放到for循环外面
    return;
}

为什么我没想开，一个是我在标记和回溯的位置上卡住了，一个是flag数组的判断卡住了

经过和AI的深入交流，我现在对DFS的标记有了更深的理解：

DFS里，可以把整个函数体想象成一个房间，把for循环想象成房间里的几个分支，在我们进行树上DFS的时候，每次访问的都是一个节点，也就是一个独立的房间，所以可以放在for循环外面。为什么说可以呢？因为放在里面也不是不行，但是需要特殊判断，不然就把起点略过了，而且不够直观。

当我们传入dfs的时候，实际上传入了一个节点，这个节点是有具体物理意义的实体，是一个实例化对象，我们在循环外面标记，在循环外面回溯，是没有任何问题的，因为操作的是这个对象本身具有的属性。

而如果dfs传入的是一种抽象的，不具有实际意义的状态，那么就不能在for循环外面操作

例如：

void dfs(int step){
    if(step>n){
        for(int i=1;i<=n;i++){
            cout<<path[i]<<" ";
        }
        cout<<endl;
        return;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            path[step]=i;
            vis[i]=1;
            dfs(step+1);
            vis[i]=0;
        }
    }
}

这是一段全排列的代码，我们可以看到它传入的是step，意味着这是当前第几步了，给一个dfs传入step的时候，你能对它的属性访问吗？不能，比如vis数组，vis[step]是没有意义的，vis存的是当前下标的元素是否访问了，而vis数组的操作，很明显是只有在for循环里面，当我们遍历每个节点i的时候才能进行的。

想清楚这个之后，接下来就通关了

H题—H题是第二天补的，也是想了很久，没有想出来，其实只有一步之遥了，后来才知道这个是典型的贪心求特定子序列

最开始我的想法是：

开一个哈希表<char,int>;

遇到A了，mpa++,遇到B了，如果mpa存在，就让mpb++,遇到c了，如果mpb存在，就让mpc++

这样可以保证先后顺序，然后判断一下如果mpa,b,c都有，就cnt++,各种–就行了

关键的是：

例如：ABBBBACCCCA

A存进去，B存到4，A存到2，C存到1，走掉，这时候A变成1，B变成3，C又可以存进去了，又可以走了，发现没有，是存在A在B后面的情况的。

这道题的正统写法应该是：

开一个数组numa记录A，遇到A就++，再开一个数组numab记录AB，然后遇到B，如果A已经存在，就让numab++,把numa–，然后遇到C以此类推，把最后ABC的++，AB的–

为什么可以这么做呢？可以想象一个篮子，装A，如果有B了，就把A拿出来一个撞到B里面，组合成AB，那么A的篮子自然少一个，如果遇到C了，就把AB里面拿出来一个AB，组成ABC，AB篮子自然少了一个，这相当于是模拟了三个栈，一个A栈，一个AB栈，一个ABC栈。

那么我的写法自然也可以很简单的改正，只需要在mpb++时mpa–,mpc++时mpb–就行了

string s;
int cnt;
int na,nab;
int main(){
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(s[i]=='A')na++;
        else if(na>0&&s[i]=='B'){
            na--;
            nab++;
        }
        else if(nab>0&&s[i]=='C'){
            nab--;
            cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}