[数据结构与算法]2021/11/21 ICPC沈阳站个人题解BEFJ（附赛时记录）

E.Edward Gaming, the Champion

题目大意：给定一个全是小写字符的字符串，找出有几个为 edgnb 的字串。

题解：暴力模拟即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,ans;
void solve(){
    string s;
    cin>>s;
    string sr="edgnb";
    for(int i=0;i+5<=s.size();i++){
        int flag=1;
        for(int j=0;j<5;j++){
            if(s[i+j]!=sr[j]) flag=0;
        }
    	if(flag) ans++;
    }
    cout<<ans;
}
signed main()
{
    int t=1;
    //cin>>t;
    while(t--)
        solve();
    
}

F.Encoded Strings I

队友写的，先放个代码，等队友写题解

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

const int N=1e5+5;
string s;
int f[N];
set <char> se;
int vis[N];
void change(int len)
{
    se.clear();
    for(int i=len;i>=0;i--)
    {
        if(se.count(s[i])==0) f[s[i]-'a']=se.size(); 
        se.insert(s[i]);
    }
}
string sr[N];
char son[33]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};

signed main()
{
    int n;
    cin>>n;
    cin>>s;
    for(int i=1;i<=n;i++)
    {
        change(i-1);
        for(int j=0;j<i;j++)
        {
            sr[i]+=son[f[s[j]-'a']];
            //cout<<f[s[j]-'a']<<' '; 
        }
        //cout<<endl;
    }
    sort(sr+1,sr+1+n);
    cout<<sr[n]<<endl;
}

J.Luggage Lock

题目大意：有一个锁，起始状态是 $a_0$,$a_1$,$a_2$,$a_3$ ，每次只能将相邻的几个位进行顺时针旋转一次或逆时针旋转一次，请问移动到 $b_0$,$b_1$,$b_2$,$b_3$ 最少需要几步。

题解：

首先，容易观察到将 $a_0$,$a_1$,$a_2$,$a_3$ 转到 0，0，0，0，状态，并将 $b_0$,$b_1$,$b_2$,$b_3$ 进行与上相同操作后得到了$c_0$,$c_1$,$c_2$,$c_3$ 再将 $c_0$,$c_1$,$c_2$,$c_3$转至 0，0，0，0，所需要的步数即为答案。
发现所有的答案不超过10000种，对于每次输入的a与b，我们都可以计算出$c_0$,$c_1$,$c_2$,$c_3$ = $b_0$,$b_1$,$b_2$,$b_3$ - $a_0$,$a_1$,$a_2$,$a_3$并得到ans【$c_0$,$c_1$,$c_2$,$c_3$】
所以我们只需要预处理出至多10000组答案即可。

其次考虑预处理ans数组，容易分析得到任何时候可选择连续区间只有10种，且同一区间选择至多在同一方向旋转9次。于是便对每种区间选择考虑同方向旋转1-9次（旋转6，7，8，9次即可当作反向旋转4，3，2，1次）。

随后便可从0，0，0，0开始通过bfs处理所有ans。

代码实现：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,t;
int u,v,w;
int ans[10005];

struct node{
    int a,b,c,d;
    node operator +(node t){
        return {(a+t.a)%10,(b+t.b)%10,(c+t.c)%10,(d+t.d)%10};
    }
    node operator *(int t){
        return {t*a,t*b,t*c,t*d};
    }

    node operator - (node t){
        return {(a+10-t.a)%10,(b+10-t.b)%10,(c+10-t.c)%10,(d+10-t.d)%10};
    }

}a[10005];
node p1[20];
node f(int x){
    int a,b,c,d;
    d=x%10;x/=10;
    c=x%10;x/=10;
    b=x%10;a=x/10;
    return {a,b,c,d};
}
queue<int> q;
int f1(node t){return t.a*1000+t.b*100+t.c*10+t.d;}
int geti(int x,int y,int z){
    node t=f(x)+p1[y]*z;
    return f1(t);
}
void solve(){
    int l,r;
    cin>>l>>r;
    node ll=f(l),rr=f(r);
    cout<<ans[f1(rr-ll)]<<"\n";
}

signed main(){
    int p[20]={0,1,11,111,1111,10,110,1110,100,1100,1000};
    for(int i=1;i<=10;i++){
        p1[i]=f(p[i]);
    }
    for(int i=1;i<10000;i++){
        a[i]=f(i);
        ans[i]=10000;
    }
    q.push(0);
    while(!q.empty()){
        int i=q.front();
        q.pop();
        for(int j=1;j<=10;j++){
            for(int k=1;k<=9;k++){
                int v= geti(i,j,k);
                if(k<5){
                    if(ans[i]+k<ans[v]){
                        ans[v]=ans[i]+k;
                        q.push(v);
                    }
                }
                else{
                    if(ans[i]+10-k<ans[v]){
                        ans[v]=ans[i]+10-k;
                        q.push(v);
                    }
                }
            }
        }
    }
    cin>>t;
    while(t--){
        solve();
    }
}

Bitwise Exclusive-OR Sequence

题目大意：

给定n个点，m条边，每条边的边权为w，是其连边两点的异或和，求出满足题意的图的最小点权和，如果不存在这样的图则输出-1.

题解：根据题意建图，考虑一块连通区域，若合法，则只需对任意一点的点权确定，则能确定连通块中所有的点都有唯一确定点权，并且任选一点为该连通块基点，能确定该连通块内任何一点与基点的异或和。
根据上述结论，我们可以从1开始对所有为经过的点dfs，dfs过程中，存在某点无法拥有唯一确认点权则没有满足题目要求的图，输出-1。否则便在dfs过程中建立以本次dfs基点为中心的菊花图，边权为基点与目标点连边的异或和。

对每个建的新连通块，对每一位都可以对基点枚举1与0两种情况，取更小值，最终累加到答案即可

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

const int N=1e5+5;
vector <pair<int,int> > g[N];
vector <int> ans[N];
int fn[N];
int vis[N],pr[N];
int st,flag=1;
void dfs(int u,int res){
    int len=g[u].size();
    for(int i=0;i<len;i++){
        int v=g[u][i].first;
        if(vis[v]){
            if(fn[v]!=(res^g[u][i].second)){
                //cout<<v<<' '<<fn[v]<<' '<<(res^g[u][i].second) <<endl;
                flag=0;
            }
        }
        else{
            vis[v]=1;
            fn[v]=res^g[u][i].second;
            ans[st].push_back(v);
            dfs(v,fn[v]);
        }
    }
}
int cnt[55];
int add(int st)
{
    memset(cnt,0,sizeof(cnt));
    int len=ans[st].size();
    int x=0;
    for(int j=0;j<30;j++)
    {
        for(int v : ans[st])
        {
            int t=fn[v];
            if((t>>j)&1) cnt[j]++;
        }
        if(cnt[j]>len/2) x+=(1<<j);
    }
    int ans1=x;
    for(int v : ans[st])
    {
        ans1+=fn[v]^x;
    }
    return ans1;
}
signed main()
{
    ios_base::sync_with_stdio(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    int ans1=0;
    for(int i=1;i<=n;i++)
    {
        if(flag && !vis[i])
        {
            st=i;
            vis[i]=1;
            dfs(i,0);
            int t=add(st);
            ans1+=t;
            //cout<<t<<endl;
        }
    }
    if(flag){
        cout<<ans1<<endl;
    }
    else {
        cout<<-1;
    }
}

小作文：
rk167，手速四题cu。

我队分配大致是
我：数学（数论部分）+各种签到+模拟
队友Y：数据结构，树，图
队友Z：dp+图+数学（多项式部分）
非常显然我队的学过的知识点非常少，大部分知识点还没学就去比赛了。

开赛前和队友信誓旦旦的说A题必是签到，结果精确开中一道光头题。好在队友运气好，开局看了E告诉我题意，5min码完，旁边学长的队伍和我队响亮的过题声几乎同时响起。此时rk约为150左右，感觉速度还算可以，遂准备去找另一道签到题。此时我去看M，两个队友去开B，过了10min想出一个后缀数组维护的较复杂的做法，由于队内三人都不是很会字符串，便记录了一下做法想着中期去写。看榜发现出现第二个签到题F，队友Y前去读题，此时我跟另一个开B的队友了解了一下题意，得知大体题意如何但是脑中根本没有任何思路。

随后队友Y快速读出题意，变准备去写F，但是仍然没有任何思路，此时全队气氛很不对劲感觉读了很多题但是仍然没有可写的题目，紧急换题，队友Y去想B，Z去想F，好在队友Z秒出F正解直接上机开码，另一个队友继续看B。对这两题都没什么想法，又不想看M的我只能前去找新题。便去看榜上过的第四多的题J，发现是个暴力的模拟非常兴奋地写了模拟过程便等队友写完F下机开写。

50min+队友写完F此时rk300+但是榜上3题队伍不是很多上去开始速码J，但是可能是个人处理的有问题中间花费了好多时间修改自己的代码写了快30min，第一遍预处理写的是for循环，对于大部分样例好像都已经过了但是交上去转了许久最后报了一发WA，当时觉得自己中间可能有过程写挂了心态有点小崩，队友也看不懂的模拟过程导致只能自己去调bug。同时两个队友的B也毫无进展。

此时看榜发现B过的人显著多于L而且认识的队伍基本都把B过了，只能强行继续写BJ

静坐了约20min感觉可能答案需要bfs更新而不是for循环更新便把更新改成了bfs，但是肉眼比对两个表仍然无法得出结论，队友拍了一下两个表发现确实有部分答案不一样，且bfs更新的都小于for循环，确认了是这一点出问题后交了，此时2h约200名铜尾，感觉再速写1题稳了。

好在队友Z得到了一个结论，经过三人沟通总算把B的解法给憋了出来，然后写出代码1。此时3h，rk142感觉cu还是不稳（但是事实证明绝大多数4题队已经写不出5题了），便想继续开一道新题。此时翻出开场口胡的字符串题，队友不能理解。无可奈何之下三人同时去看榜上此时过的差不多的HIL三题。

H题意没有理解，L题毫无思路，I题手推了一个高斯消元出解的式子，交上去wa了队友也不能帮忙写开始绝望罚坐。

最后30min终于读了一个H的假题意模过了所有样例，两个队友上机光速码，但是终究结束前没有码完。感觉cu很悬，但是解榜后发现只掉了一100+rank还是稳住了cu。

7月沈阳首战打铁，决定努力学习数学（但是啥都没学会）。11月二战沈阳拿到了acm生涯的第一个区域赛牌子，虽然只是cu，但是也是证明这一年的学习没有白费吧。虽然队伍三人会的知识点还不是很全面，但是接下来一年就应该下一个小目标就是争取尽可能多的学更多的常见知识点，向着下一个牌牌努力吧。