喵喵思维题

算法

L.Palm Island

2023哈尔滨ccpc

有一个字符串，可以把第一个字符移动到最后一个，也可以把最后一个字符移动到最后一个。前者为1操作，后者为2操作。假设字符串长度为n，你需要输出一个由12组成的序列（长度不超过n方），

带有模拟思想的构造。

这种题目往往你需要想出一种易于模拟的想法，然后用代码实现。如果你面对一个序列，要变成目标序列，只能这两个操作，你会怎么办？

**注意到你有n方的操作机会。**也就意味着，你可以双重循环暴力。所以你根本不用考虑最优解法，非常暴力的模拟即可。

我们现在重新来看这两个操作，表面上只能操作序号1，2的字符，但是我们可以通过不断循环，让3，4也变成1，2。那么就有了一个初步的思路。

把你的目标牌通过1操作移到牌顶，然后不断进行2操作就可以修改目标牌后对应的数字，直到目标牌的后一位对应自己应该对应的数字。执行完之后，再直接两个操作一，进行下一对数字的匹配。

对于目标牌，由于我们不需要考虑时间复杂度，所以不需要想先选择哪个作为目标牌。直接按照目标牌的遍历。如果顶部的牌不是目标牌，进行操作一，当成为目标牌后，然后不断操作二，把操控第二位数字。然后1，2就正确了。

但是聪明的你有没有发现一个问题。如果目标牌固定好后，我把应该在他后面的数字放到第二位然后继续循环会发生什么

  1. 逻辑混乱：我们试图同时控制”当前目标牌”和”它的后继”，但操作2实际上影响的是底部牌
  2. 破坏已固定的关系：当我们调整第二位时，实际上在改变整个序列的后面部分，破坏了之前建立的关系
  3. 缺乏稳定性：没有固定的”锚点”来保持已匹配部分的位置。

这样说也许有点抽象。

假设：

  • 初始序列：[1, 2, 3, 4]
  • 目标序列：[3, 1, 4, 2]
  • image-20251121102336069

可以看到这样会打乱我们已经匹配好的。所以我们需要避免这个问题。

我们每次把目标牌移到顶部，然后不断操作二，其实可以看作是在调整底部牌，为什么要调整底部牌呢？

因为我们要固定已经匹配好的牌

想象一下，我们每次匹配好一对牌后，希望这对牌的位置关系不再改变。通过把已经匹配好的牌放到底部，它们就不会被后续的操作影响到底部以上的部分。

再深入思考一下：操作1是整体旋转，操作2是跳过第一张牌调整后面的顺序。这两个操作结合起来，就能让我们像**“冒泡排序**”（划重点）一样，逐步把正确的牌放到正确的位置。

具体执行过程：

  1. 我们按顺序处理目标序列的第2到第n张牌
  2. 对于每个目标位置i，我们先把b[i]牌转到顶部（操作1）
  3. 然后调整底部，让b[i-1]牌到底部（操作2）（这样相对位置就对了，只需要后期1操作循环即可）
  4. 这样b[i-1]和b[i]的相对位置就固定了

直观理解一下。

image-20251121103040791

1
2
3
4
5
6
7
8
9
10
for(int i = 2; i <= n; i++){
    // 步骤1：旋转直到顶部是目标第i张牌
    while(顶部牌 != b[i]) 执行操作1;
    
    // 步骤2：调整直到底部是目标第i-1张牌  
    while(底部牌 != b[i-1]) 执行操作2;
}

// 最后调整：旋转直到顶部是目标第一张牌
while(顶部牌 != b[1]) 执行操作1;

附上AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
int a[N], b[N], n;

void op1() {
    int t = a[1];
    for(int i = 2; i <= n; i++) a[i-1] = a[i];
    a[n] = t;
}

void op2() {
    int t = a[2];
    for(int i = 2; i < n; i++) a[i] = a[i+1];
    a[n] = t;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while(t--) {
        cin >> n;
        vector<int> ans;
        for(int i = 1; i <= n; i++) cin >> a[i];
        for(int i = 1; i <= n; i++) cin >> b[i];
        
        for(int i = 2; i <= n; i++) {
            while(a[1] != b[i]) {
                op1();
                ans.push_back(1);
            }
            while(a[n] != b[i-1]) {
                op2();
                ans.push_back(2);
            }
        }
        
        while(a[1] != b[1]) {
            op1();
            ans.push_back(1);
        }
        
        for(auto x : ans) cout << x;
        cout << endl;
    }
    return 0;
}

B.Memory

2023哈尔滨ccpc

image-20251121130940238

给一串数字，求Mood。

一眼暴力的话，其实很简单写。你可能会注意到小数的精度问题。（心存侥幸的话你会这么写）

1
2
3
4
5
6
7
8
9
for (int i = n;i >= 1;i--){
    result = a[i] * pow(2,zz);
    zz--;
    sum += result;
}
b[n] = sum;
for(int i = n;i >= 1;i--){
    b[i-1]=(b[i]-a[i])*2.0;
}

（注意到其实是有递归关系的，mood[i]-a[i]再×2就可以得到mood[i-1]。这是一个递归关系。虽然你喜提wa3，但是你得到了一个很重要的递归关系。

又注意到mood×上一个正整数不改变符号，那我×2的n方不就没小数了。而且这样还很便捷的可以×上幂部分。但是你大概估算就知道显然也会整数溢出。恭喜wa3。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
string result = "";
   long long sum = 0;
   long long power = 2; // 2^1
   
   for (int i = 1; i <= n; i++) {
       sum += a[i] * power;
       
       if (sum < 0) {
           result += '-';
       } else if (sum > 0) {
           result += '+';
       } else {
           result += '0';
       }
       
       if (i < n) power *= 2;
   }

从这两次失败我们可以看出，算出每个mood再判断符号肯定不行，我们需要有一个巧妙的办法。

整数数字太大会移除，浮点数的精度不够，小数点可能有很多位。

那么两者结合一下，如果浮点数是整数，不就不用考虑精度，而且不用担心数字太大了？

简单来说就是把1.00000001变成1，这样并不会改变符号。

也就是整数截断，然后用

但是你可能有问题，忽略小数点后的数字最后累积起来不会影响最后正负吗？

我想告诉你的是，如果采用递归，每次加上新的整数，误差都会被重置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    int val = 0;    // 当前 Mood 的整数部分
    int sig = 0;    // 小数部分的符号趋势
    
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        
        // 如果是奇数，记录小数部分符号
        if (val % 2 != 0) {
            sig = (val > 0) ? 1 : -1;
        }
        
        // 递推计算
        val = val / 2 + x;
        
        // 判断符号
        if (val == 0 && sig == 0) {
            cout << '0';        // 精确为0
        } else if (val >= 1 || (val == 0 && sig == 1)) {
            cout << '+';        // 正数
        } else {
            cout << '-';        // 负数
        }
    }
    
    return 0;
}