2024.4.2

2024.4.2 【总有一阵风会吹过我再吹过你，总有一个瞬间我们之前的距离是零。】

Tuesday 二月二十三

qyrh:帮我写测试吧 (*5)

2018沈阳集训day1(我也不知道教练为什么找这个题，可能是喜欢马克吧)

A. 马克的字符串

【问题描述】
定义一个字符串满足'MK'性质当且仅当它修改其中不超过k个字符后是回文串。给你一个字符串，问它有多少非空子串满足'MK'性质。

【输入格式】
从文件​string.in中输入数据。

输入的第一行包含一个字符串s

输入的第二行包含一个整数k

【输出格式】
输出到文件​string.out中。

输出的第一行包含一个整数，为满足'MK'性质的字串数量。

【样例输入】

Aab
1

【样例输出】

6

【样例说明】
每一个字串都是回文串或修改一个字母后是回文串
【数据规模与约定】
对于30%的数据：k=0

对于100% 的数据：字符串长度 1<=l<=100，0<=k<=50

//2024.4.2
//by white_ice
#include<bits/stdc++.h>
using namespace std;
#define itn int

char st[202];
int k; 

bool check(int i, int j){
    int cnt = 0;
    while(i<=j){
        if(st[i]!=st[j])
            cnt++;
        if(cnt>k)
            return 0;
        i++;
        j--;
    }
    return 1;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin >> st;
    cin >> k;

    int ans = 0;
    int len = strlen(st);

    for(int i=0;i<len;i++)
        for(int j=i;j<len;j++)
            if (check(i,j))
                ans ++;

    cout << ans;

    return 0;
}

B. 马克家的书

【问题描述】
马克家收藏了一套书，这套书叫《OIER故事集》，这套书有n本，每本书有一个编号，从1号到n号。

马克把这些书按照编号从小到大，从上往下摞成一摞。马克对这套书很珍视，不允许其他人动。

有一天一格到马克家玩，马克因为和妹子约会，就让一格自己呆在家里。一格因为对这套书非常好奇，偷偷的看了一下，结果发现书中竟然有ljs和commonc的故事。一格看的入了迷，结果把一摞书的顺序弄乱了。

眼看着马克就要回来了，一格需要把书恢复到原状，由于每本书都比较重，所以一格能做的操作是把一本书从书堆中抽出来，然后把这本书放到书堆的顶部。

给你打乱的书的顺序，你能帮一格算算最少需要几次上述操作，才能恢复书的顺序。

【输入格式】
从文件​book​.in中输入数据。

输入包含多组数据。

第一行包含一格正整数T(T<=10)，表示数据组数。

对于每组数据，第一行为一格整数n。

接下来的一行有n个用空格分开的正整数，表示一格打乱后的书的顺序，从上到下。

【输出格式】
输出到文件​book.out中。

对于每组数据，输出一行一个整数，表示一格最少经过几次操作才能恢复书的顺序。

【样例输入】

2
4
4 1 2 3
5
1 2 3 4 5

【样例输出】

3
0

【样例说明】
样对于第一组数据，我们先把3号书放在最上面，接着操作2号书，最后操作1号书，（4，1，2，3）—（3，4，1，2）—（2，3，4，1）—（1，2，3，4）这样就有序了。

对于第二组数据，已经有序就不需要挪了。

【数据规模与约定】
对于 50% 的数据满足 n<=10

对于 80%的数据满足 n<=1000

对于 100% 的数据满足 n<=100000

//2024.4.2
//by white_ice
#include<bits/stdc++.h>
using namespace std;
#define itn int
const int oo = 1000005;

int st[oo];
int t,n;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    freopen("book.in","r",stdin);
    freopen("book.out","w",stdout);

    cin >> t;
    while(t--){
        cin >> n;
        for(int i=1;i<=n;i++)
            cin >> st[i];
        int p = n,cnt = 0;

        for(int i=n;i>=1;i--)
            if(st[i] == p){
                p--;
                cnt++;
            }

        int out = n - cnt;
        cout << out << endl;
    }

    return 0;
}

剩下两个下次发。。。