8.10第四周周六学习总结

hoshino- / 2024-08-10 / 原文

1 vj团队12补题

不错的一个题解
https://blog.fishze.com/archives/301

1)字符串变化（模拟+找规律）

题目：
给定一个字符串, 给定一个特定操作方式: 该字符串前半段 + 该字符串自己 + 该字符串后半段求next(每一个字符向后移动一个), 组成一个新字符串, 求经过10^100次这样的操作后, 新字符串的后m位是什么

点击查看代码

#include <iostream>

using namespace std;

const int MOD = 16;

string getNext(string s) {
    string res;
    for(auto ss : s) {
        res += ss == 'z' ? 'a' : (char)(ss + 1);
    }
    return res;
}
//一直变换直到后缀>=m,这样取m就不会在前面取了
//AB 
//A AB B1 
//AA AA,BB1 B1B2  变换几次使得一半的长度＞m，后面不断变化，因为是直接取后一半到最后，所以直接考虑这段取m的变化
//AAAA AAAA,BB1B1B2 B1B2B2B3
int main() {
    int n, m;
    string s;
    cin >> n >> m >> s;
    string ss = s.substr(s.length() / 2, s.length() / 2);//取的位置和取的长度
    int cnt = 0;
    while(1) {
        if(ss.length() >= m) {
            break;
        }
        cnt ++;//记录变化了几次
        ss = ss + getNext(ss);//字符串拼接  B-BB1-BB1B1B2
    }
    int xx = MOD - (cnt % 26);//还需变化几次，现在需要对s变化xx次
   /* (a + b) % m = ((a % m) + (b % m)) % m （加法的求余分配律）
      (a * b) % m = ((a % m) * (b % m)) % m （乘法的求余分配律）*/
    if(xx < 0) {
        xx += 26;
    }
    for(int i = ss.length() - m; i < ss.length(); i++){//取后m位
        int now = ss[i] + xx;
        if(now > 'z') {
            now -= 26;
        }
        cout << (char)now;
    }
    cout << endl;
    return 0;
}