还是构造大佬

· · 题解

闲话

随机跳题刷到的，一看是黑题，AC率竟有 0\%，但是这个图灵机的形式让我觉得很有意思。

于是开始想，想到了正解大概思路，然后写出来，随便调了几下就过了。

其实这道题不算很难，但是好像 GCJ 赛时没有人通过？（雾

题意

为了方便，在此简化亿下题意，先解释什么是图灵机：

有一个无限长的纸带，初始上面都写着 0。

有一个机器，初始所在位置为 0，分为控制器和表头两个部分，表头有一个状态。

控制器接受一些规则，形如“若表头状态为 a 且所在格子写着 b，则将格子中的数改为 c，状态改为 d，然后左/右（题目中为 W 和 E）移动一个单位长度”。

每一次根据所在位置和状态对应的规则执行一步操作，直到当表头状态为 Halt（题目中为 R）时停止运行图灵机。

题目要求的就是：构造不超过 30 条规则，使得图灵机在 X 步内恰好在 N 这个位置停机。

小数据集：0 \leq N \leq 500，X = 250,000，时限 30 秒。

大数据集：0 \leq N \leq 5000，X = 150,000，时限 60 秒。

思路

分析

首先拿到这种构造题，先写一个可视化工具或 SPJ （代码在后面）方便观察调试。

考虑一个暴力：将状态设为已经走过的步数，每走一次加 1，当状态为 n 时停机。

虽然它花费步数最少，从不回头，但这显然浪费了纸带的存储功能，需要用 O(n) 条规则。

为了利用纸带，不妨将剩下的步数写在纸带上。每次遍历一遍存在纸带上的数，将纸带上数的减一。

当纸带上的数归零时，就完成了计数，直接停机即可。

但是 X=150000=5000\times30，也就是说平均每个规则只能被调用 O(n) 次，卡得比较紧。

所以我们不能来回太多次，应该带着纸带一起走，边移动边把纸带往前面也移动一格。

考虑如何在纸带上存数字，不妨选定一个进制 k，因为这是 OI 题目，这里选定二进制（后面会解释原因）。

特别地，由于纸带上所有数默认为零，我们将二进制中每个数位上的数 +1 以便和 0 区分开：

例如：5=(101)_2，在这里记为 (2,1,2)。

综上，图灵机的运行大概分为四个阶段：

Step I. 初始化，将题目中的 N 按位从高到低存在纸带上。（从左到右遍历）

Step II. 将纸带上的数减一，若数字已经为 0 则跳转 Step III，否则跳转 Step IV。（从右到左遍历）

Step III. 复制纸带上的数到下一位，跳转 Step II。（从左到右遍历）

Step IV. 停机。

可以发现，这样的安排总是左右横跳，没有出现无意义的遍历，可以在 O(n\log n) 步内停机。

然后按步构造规则就可以了。

Tips：

Step I 初始阶段

首先，Step I 的实现是 naive 的，状态为 S_i（初始 i=0,S_0=0）时就填充从高到低第 i 位上的数，然后向右移动，状态切换为 S_{i+1}。于是表头从左边移动到了右边。

初始转移：

S0 0 -> E S1 t0
S1 0 -> E S2 t1
...  -> ...
Sn-1 0 -> E Sn tn-1

Step II 减法阶段

现在我们在数字的右侧，此时从高到低存储的好处就体现出来了。

此时定义状态 M_1，表示未完成减法，需要借位（更高位继续 -1）。

此时定义状态 M_2，表示减法已经完成，不需要借位（更高位不变）。

当状态为 S_n 时，往回走并改为 M_1 状态。

过渡转移：

Sn 0 -> W M1 0

减法转移：

//重要的事情说三遍：记录的二进制数位上的数会 +1
M1 1 -> W M1 2 //这一位是 0，减了 1 之后为 1，后面仍需继续借位
M1 2 -> W M2 1 //这一位是 1，减了 1 之后为 0，后面不需要借位了    
M2 1 -> W M2 1 //不需要借位，保持原样
M2 2 -> W M2 2 //不需要借位，保持原样

完成后表头从右边移动到了左边。

Step III 移动阶段

当表头在左侧时若状态为 M_2，则说明减法成功，需要将数字移动到下一位。

现在我们在数字的左侧，设 C_i 表示上一位为 i，初始 i=0。

若这一位是 j，则将这一位改为 i，状态改为 C_j，向右移动进入下一位。

特别地，此时需要考虑 0，因为左边的位置需要归零保证复杂度，而且占用新的位置也需要考虑 0。

特别地，当状态为 C_0 且纸带上的数为 0 时，即到达最右边，需要结束移动阶段，进入新一轮减法阶段。

移动转移：

//Ci j -> E Cj i
C0 0 -> W M1 0 //完成循环
C0 1 -> E C1 0
C0 2 -> E C2 0
C1 0 -> E C0 1
C1 1 -> E C1 1
C1 2 -> E C2 1
C2 0 -> E C0 2
C2 1 -> E C1 2
C2 2 -> E C2 2

Step IV 结束阶段

当表头在左侧时若状态为 M_1，则说明减法失败，即当前数字已经为 0。

显然，数字的二进制位最左边就是位置 n ，但是我们在最左边的下一个，也就是位置 n-1。

很好，我们的图灵机输入 n 能到达位置 n-1，不妨将输入的 n 先 +1。

那么我们的图灵机输入 n+1 能到达位置 n，直接停机，完成任务。

复盘

简单复盘一下，若用 k 进制，不考虑状态数和纸带上的数的大小限制（10^6 想必用不完）。

需要 \log_kN+1+2k+1+(k+1)^2+1=k^2+4k+5+\log_kN 个转移。

丢进画图工具里你会发现只有 k=2 这个整数始终在 N\le5000 时满足条件，所以只能选二进制。

只要理解了思路，代码超级好写。实现时对于 S,M,C 函数随便取不同的值就可以了（特别地，满足S_0=0）。

代码

哈哈哈，居然是首A。

不是一分钟的时间限制我就跑了 4 毫秒？

建议降低时限以免被别有用心之人利用。

::::info[code.cpp]

#include<bits/stdc++.h>
using namespace std;
vector<int>b;
int S(int x){return x;}
int C(int x){return 100+x;}
const int M1=-1,M2=-2;
struct rules{
    int bs;int bm;
    char mv;
    int es;int em;
};vector<rules>r;
void solve(int c){
    int n;cin>>n;n++;//记得要先+1
    b.clear();r.clear();
    //初始阶段
    for(int i=n;i;i>>=1)
        b.push_back((i&1)+1);
    reverse(b.begin(),b.end());
    int m=b.size();
    for(int i=0;i<m;i++)
        r.push_back({S(i),0,'E',S(i+1),b[i]});
    //初始->减法
    r.push_back({S(m),0,'W',M1,0});
    //减法阶段
    r.push_back({M1,1,'W',M1,2});
    r.push_back({M1,2,'W',M2,1});       
    r.push_back({M2,1,'W',M2,1});
    r.push_back({M2,2,'W',M2,2});
    //减法成功，进入复制阶段
    r.push_back({M2,0,'E',C(0),0});
    //移动阶段
    for(int i=0;i<=2;i++){
        for(int j=0;j<=2;j++){
            if(!i&&!j)r.push_back({C(0),0,'W',M1,0});
            else r.push_back({C(i),j,'E',C(j),i});
        }
    }
    //减法失败，停机
    r.push_back({M1,0,'R',114514,1919810});
    //输出
    cout<<"Case #"<<c<<": "<<r.size()<<'\n';
    for(auto [bs,bm,mv,es,em]:r){
        if(mv=='R')cout<<bs<<' '<<bm<<" -> "<<mv<<'\n';
        else cout<<bs<<' '<<bm<<" -> "<<mv<<' '<<es<<' '<<em<<'\n';
    }
}
int main(){
    int t;cin>>t;
    for(int i=1;i<=t;i++)solve(i);
    return 0;
}
/*
当时的思路：
------------------
S0 0 -> E S1 t
S1 0 -> E S2 t    ->  logn<=13
...  -> ...
Sn-1 0 -> E Sn t
------------------
Sn 0 -> W M1 0
------------------
M1 1 -> W M1 2
M1 2 -> W M2 1        
M2 1 -> W M2 1
M2 2 -> W M2 2
------------------
M2 0 -> E C0 0  ||  M1 0 -> r
------------------
//Ci j -> E Cj i
C0 0 -> W M1 0
C0 1 -> E C1 0
C0 2 -> E C2 0
C1 0 -> E C0 1
C1 1 -> E C1 1
C1 2 -> E C2 1
C2 0 -> E C0 2
C2 1 -> E C1 2
C2 2 -> E C2 2
------------------
*/

::::

::::info[spj.cpp]

#include "testlib.h"
#include <bits/stdc++.h>
using namespace std;

const int MAX_STATEMENTS = 30;
const int MAX_STEPS = 1e6;
const int MIN_VAL = -1000000;
const int MAX_VAL = 1000000;

struct Rule {
    int state, mark;
    string action;
    char dir;
    int next_state, new_mark;
    bool drop;
};

struct Transition {
    int state, mark;
    Rule rule;
};

map<pair<int, int>, Rule> rules;

int main(int argc, char* argv[]) {
    registerTestlibCmd(argc, argv);

    int T = inf.readInt(1, 15, "T"), total = 0;
    for (int testCase = 1; testCase <= T; ++testCase) {
        int N = inf.readInt(0, 5000, "N");
        string caseHeader = ouf.readToken();
        ensuref(caseHeader == "Case", "Expected 'Case' at line start.");
        string caseNumStr = ouf.readToken();
        ensuref(caseNumStr == "#" + to_string(testCase) + ":", "Expected '#<testCase>:'.");
        int ruleCount = ouf.readInt(1, MAX_STATEMENTS, "number of rules.");

        rules.clear();

        for (int i = 0; i < ruleCount; ++i) {
            int S = ouf.readInt(MIN_VAL, MAX_VAL, "state");
            int M = ouf.readInt(MIN_VAL, MAX_VAL, "mark");
            string arrow = ouf.readToken();
            ensuref(arrow == "->", "Expected '->'");

            string token = ouf.readToken();

            Rule rule;
            rule.state = S;
            rule.mark = M;
            rule.drop = false;

            if (token == "R") {
                rule.drop = true;
            } else {
                ensuref(token == "E" || token == "W", "Invalid direction (must be E/W).");
                rule.dir = token[0];
                rule.next_state = ouf.readInt(MIN_VAL, MAX_VAL, "next state");
                rule.new_mark = ouf.readInt(MIN_VAL, MAX_VAL, "new mark");
            }

            pair<int, int> key = {S, M};
            ensuref(!rules.count(key), "Duplicate rule for (state=%d, mark=%d).", S, M);
            rules[key] = rule;
        }

        map<int, int> tape;
        int pos = 0;
        int state = 0;
        int steps = 0;

        while (true) {
            ++steps;
            if (steps > MAX_STEPS) {
                quitf(_wa, "Exceeded step limit (%d).", MAX_STEPS);
            }

            int mark = tape.count(pos) ? tape[pos] : 0;
            auto it = rules.find({state, mark});
            if (it == rules.end()) {
                quitf(_wa, "No rule for state=%d and mark=%d (robot got confused).", state, mark);
            }

            Rule r = it->second;

            if (r.drop) {
                if (pos == N) {
                    break;
                } else {
                    quitf(_wa, "Dropped cake at wrong position: %d (expected %d).", pos, N);
                }
            } else {
                tape[pos] = r.new_mark;
                state = r.next_state;
                pos += (r.dir == 'E') ? 1 : -1;
            }
        }
        total += steps;
    }
    quitf(_ok, "All cases passed in %d steps.",total);
}

::::