2022.11.8每日刷题打卡

Dancing the Cheeky-Cheeky

原题链接：传送门

题意：

多组数据，每组给出一个循环小数的小数部分，要求其 最长 循环节。

输出循环节的后 8 位，后面加三个 "." 。

当一个部分重复在其尾部出现，则认为是循环部分，如果没有循环节就把整体当做循环节。

思路：kmp算循环节k，按照位置模拟输出8位

#include 
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while(t--) {
        string s;
        cin >> s;
        int n = s.size();
        vector<int> pi(n);
        for(int i = 1, j = 0; i < n; i++) {
            while(j && s[i] != s[j]) j = pi[j - 1];
            if(s[i] == s[j]) j ++;
            pi[i] = j; 
        }
        int l = n - pi[n - 1];
        int k = n % l;
        for(int i = 0; i < 8; i++){
            int j = (k + i + l) % l;
            cout << s[j];  
        }
        cout << "...\n";
    }
    return 0;
}

 

 

Secret Word

原题链接：传送门

题意：给出一个字符串S，求S的最长前缀，满足：其反转后的串是S的子串。

思路：很简单我们把s做匹配串把s的反转串做模式串，以此进行匹配找最大长度就可。

#include 
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while(t--) {
        string s, rs;
        cin >> s;
        rs = s, reverse(rs.begin(),rs.end());
        int n = s.size();
        vector<int> pi(n, 0);
        for(int i = 1, j = 0; i < n; i++) {
            while(j && s[i] != s[j]) j = pi[j - 1];
            if(s[i] == s[j]) j ++;
            pi[i] = j; 
        }
        int ans = 0;
        for(int i = 0, j = 0; i < n; i ++){
            while(j && rs[i] != s[j]) j = pi[j - 1];
            if(rs[i] == s[j]) j++;
            ans = max(ans, j);
            if(j == n) j = pi[j - 1];
        }
        string res = s.substr(0, ans);
        reverse(res.begin(), res.end());
        cout << res << "\n";
    }
    return 0;
}

MUH and Cube Walls

原题链接：传送门

题意：现有一个包含 n 个整数的序列 a1, a2, ..., an，和一个包含 m 个整数的序列 b1, b2, ..., bm。

问 a 序列中有多少个连续子序列，令每个数同时加上某个整数（可以为负数）后，与 b 序列相同？

思路：差分+KMP

#include 
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m), sa(n), sb(m);
    for(int &ai : a) cin >> ai;
    for(int &bi : b) cin >> bi;
    if(m == 1) cout << n << "\n";
    else{
        for(int i = 1; i < n; i++) sa[i] = a[i] - a[i - 1];
        for(int i = 1; i < m; i++) sb[i] = b[i] - b[i - 1];
        vector<int> pi(m);
        for(int i = 2, j = 0; i < m; i++){
            while(j && sb[i] != sb[j + 1]) j = pi[j];
            j+=(sb[i] == sb[j + 1]), pi[i] = j;
        }
        int ans = 0;
        for(int i = 1, j = 0; i < n ; i++){
            while(j && sa[i] != sb[j + 1]) j = pi[j];
            j += (sa[i] == sb[j + 1]);
            if(j + 1 == m) ans ++, j = pi[j];
        }
        cout << ans << "\n";
    }
    return 0;
}