题目1:小红的环形字符串

小红拿到了一个环形字符串s。所谓环形字符串，指首尾相接的字符串。
小红想顺时针截取其中一段连续子串正好等于t，一共有多少种截法？

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
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;

char s[2*N],s1[N];


int main()
{
    cin>>s>>s1;
    int len=strlen(s);
    int ans=0;
    //直接倍增构造一个伪环形串
    for(int i=len;i<2*len;i++) s[i]=s[i-len];
    for(int i=0;i<len;i++)
    {
        bool flag=true;
        for(int j=0;j<strlen(s1);j++)
        {
            if(s[i+j]!=s1[j])
            {
                flag=false;
                break;
            }
        }
        if(flag) ans++;
    }
    
    cout<<ans<<endl;
    
    return 0;
}

题目2:相邻不同数字的标记

小红拿到了一个数组，每个数字被染成了红色或蓝色。

小红有很多次操作，每次操作可以选择两个相邻的不同颜色的数字标记，并获得它们数字之和的得分。已经被标记的数字无法再次标记。
小红想知道，自己最多能获得多少分。

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

//dp[i]表示就计算到i时的最大得分
long long dp[N]={0};
int a[N];
string s;


int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    cin>>s;
    char c=s[0];
    int t=1;
    for(;t<n;t++)
        if(c!=s[t])
        {
            dp[t]=a[t]+a[t-1];
            c=s[t];
            break;
        }
    t++;
    for(;t<n;t++)
    {
        if(c==s[t]) dp[t]=dp[t-1];
        else{
            c=s[t];
            dp[t]=max(dp[t-1],dp[t-2]+a[t]+a[t-1]);
        }
    }
    cout<<dp[n-1]<<endl;
    
    return 0;
}