题目1:AcWing 3325.Kick_Start

Ksenia 非常喜欢读书，因此每天她都会从自己最喜欢的书中选取一段内容进行阅读，然后再开始她早晨的其他活动。

一段内容可以看作是整个文本中的一个子字符串。

Ksenia 有点迷信，她坚信如果阅读的这段内容是以字符串 KICK 开头，然后中间包含 0 个或更多个字符，最后以字符串 START 结尾，即使这段内容没什么意义，她的一天也会非常的幸运。

给定这本书的全部文本内容，请你数一数在这本书变得破旧不堪，Ksenia 不得不再买新书之前，共有多少个幸运片段可供她阅读。

只要两个片段的起始位置或结束位置不同，就认为这两个片段是不同的，即使它们包含的内容完全相同。

还需注意，不同片段之间可能会有重叠部分。

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
#include<iostream>
#include<string>
using namespace std;

int findLucky(string s)
{
    int kick = 0, ans = 0;
    for(int i=0;i<s.size()-4;i++)
    {
        //i的变化符合kmp思想
        if(s.substr(i, 4) == "KICK") kick ++, i += 2;
        else if (s.substr(i, 5) == "START") ans += kick, i += 4;
    }
   return ans; 
}


int main()
{
    int T;
    cin>>T;
    for(int t=1;t<=T;t++)
    {
        string s;
        cin>>s;
        int ans = findLucky(s);
        
        printf("Case #%d: %d\n",t,ans);
    }
    
    
    return 0;
}

题目2:AcWing 4114.垃圾桶

一条很长的街道上有 N 个房子。

第一个房子在位置 1，第二个房子在位置 2，以此类推。

任意一对房子 i 和 j 之间的距离为 |i−j|。

一些房子的位置处有垃圾桶。每个房子的主人都要倒垃圾。如果自己房子前面有垃圾桶，则无需移动，直接倒垃圾即可。

如果自己房子前面没有垃圾桶，则前往距离自己最近的垃圾桶处倒垃圾，如果这样的垃圾桶不唯一，则任意前往一个即可。

请计算，所有房子的主人倒垃圾需要行走的总距离之和。

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
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5e5 + 10;

char s[N];
int l[N], r[N];//分别表示该住户左侧和右侧最近的垃圾桶,若自带垃圾桶则为0

int main()
{
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++)
    {
        int n;
        scanf("%d%s", &n, s + 1);
        l[0] = -1e6, r[n + 1] = 1e6;

        for (int i = 1; i <= n; i++)
            l[i] = s[i] == '1' ? i : l[i - 1];
        for (int i = n; i > 0; i--)
            r[i] = s[i] == '1' ? i : r[i + 1];

        long long ans = 0;
        for (int i = 1; i <= n; i++)
            ans += min(i - l[i], r[i] - i);

        printf("Case #%d: %lld\n", t, ans);
    }


    return 0;
}