2021/11/21 ICPC沈阳站个人题解B,E,F,J（附赛时记录）

E.Edward Gaming, the Champion

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

题解：暴力模拟即可。

#include #define int long longusing 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 #define int long longusing 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<        }        //cout<    }    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 #define int long longusing 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}
                 

                                                                                                                    
                         云服务器
                                             
                         GPU云服务器
                                                                                                                                                 
                                      
                     
                    
                                                                                               附解压密码
                                                                                                           二次浅封装实践【附源码】
                                                                                                           附在线计算工具
                                                                                                           附注册机