P6703 题解

· · 题解

P6703 KOLO

分析与解

一道经典的模拟

分析

注意事项：

  1. 首先 轮中没有字母重复出现；

  2. 然后 轮沿顺时针方向旋转；说明

  3. 最后 从最后一次旋转结束时的尖头字母开始，然后顺时针方向输出；

综上所述，我们总结出如下几点：

  1. 如果有同一个字母在不同位置出现即不成立

  2. 如果同一位置有不同字母出现即不成立

  3. 指针沿逆时针转动，而需要顺时针输出

解

步骤一：读入+不成立判断

没有必要详解，附代码：


    cin>>n>>k; 
    for(i=1;i<=k;i++)
    {
        cin>>s>>c;
        x=(x+s)%n;//指针更新
        if(ans[x]!=0&&int(c)!=ans[x]||f[c]&&ans[x]!=int(c))
            /*不成立条件：
                    1.该位置有不同字母
                    2.该字母已出现且不在当前位置
                */
        {
            cout<<'!';return 0;//判断不成立，结束
        }
        ans[x]=int(c);//设置
        f[c]=1;//已使用
    }

步骤二：输出

由题意可得：由指针x开始反序输出， 所以说，要分两段输出

如果ans[i] 没有值（没有赋值）那么输出?

附代码：

    for(i=x;i>=0;i--)
    if(ans[i]!=0)cout<<char(ans[i]);//第一段
    else cout<<'?';
    for(i=n-1;i>=x+1;i--)
    if(ans[i]!=0)cout<<char(ans[i]);//第二段
    else cout<<'?';

完整代码

快看！

#include<bits/stdc++.h>
using namespace std;
char c;
int f[128],ans[26],s/*改变次数*/,k/*转向次数*/,i,j,n/*转子数*/,x/*指针*/; 
int main()
{
    cin>>n>>k; 
    for(i=1;i<=k;i++)
    {
        cin>>s>>c;
        x=(x+s)%n;
        if(ans[x]!=0&&int(c)!=ans[x]||f[c]&&ans[x]!=int(c))
        {
            cout<<'!';return 0;
        }
        ans[x]=int(c);
        f[c]=1;
    }
    for(i=x;i>=0;i--)
    if(ans[i]!=0)cout<<char(ans[i]);
    else cout<<'?';
    for(i=n-1;i>=x+1;i--)
    if(ans[i]!=0)cout<<char(ans[i]);
    else cout<<'?';
    return 0;
}