D. 字符串里串

题目简介：

给定一个字符串，找出长度为 的连续子串 ，和长度为 的不连续子串 ，满足 ，求 的最大值，其中定义 为一个字符串的可爱度。

连续子串：从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。

不连续子串：至少由两段不相邻的非空子串构成。

思路：

由贪心思想得出：要使 最大，就要使子串 和子串 重复的片段越多。

若已选择子串 ，那么 的最优构造方案为以下两个中的其中一个：

• 第一段仅包含一个字符，即 的第一个字母，需要去位置 前寻找；第二段包含 的剩余部分，可以共用这部分；
• 第二段仅包含一个字符，即 的最后一个字母，需要去位置 后寻找；第一段包含 的剩余部分，可以共用这部分；

代码如下

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    string s;
    cin>>n>>s;
    s="#"+s;		//字符串下标从1开始，方便处理
    int ans=0;
    for(int ch=0;ch<26;ch++)		//从'a'遍历到'z'
	{
        int pre=0,net=0;		//标记当前查找的字母是否已经找到，pre往前寻找第一个字母，net往后寻找最后一个字母
        for(int i=1;i<=n;i++)
		{
            if(s[i]-'a'!=ch) continue;		//如果当前s[i]==ch
            if(pre!=0)		//如果s中已经找到过ch
                ans=max(ans,n-i+1);		//更新答案为当前位置到字符串结尾
            pre=i;		//更新pre
        }
        for(int i=n;i>=1;i--)		//从后往前查找
		{
            if(s[i]-'a'!=ch) continue;
            if(net!=0)
                ans=max(ans,i);
            net=i;
        }
    }
    cout<<(ans==1?0:ans);
}

H. 一起画很大的圆！

题目简介：

给定一个矩形，在举行的边上选取三个点，使得经过这三个点画出的圆半径最大

思路：

由正弦定理 得，当最长的边对的角度越大时，圆的半径越大 如图，当其中两点位于矩形的长边(A,B)，一点位于矩形的短边(C),且点A，B尽可能的远离短边，点C尽可能的靠近长边时，画出的圆半径最大。

代码如下

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
	{
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        if(b-a<d-c)		//判断长边与短边
		{
            cout<<a<<" "<<c<<endl;
            cout<<a<<" "<<c+1<<endl;
            cout<<a+1<<" "<<d<<endl;
        }
		else
		{
            cout<<a<<" "<<d<<endl;
            cout<<a+1<<" "<<d<<endl;
            cout<<b<<" "<<d-1<<endl;
        }
    }
    return 0;
}

C. 字符串外串

题目简介：

给定 和 ，构造长度为 的字符串，满足字符串的可爱度为

思路：

要满足题意，我们只需要在字符串的开头填充一个字母 ，在字符串的结尾 个字母处填充长度为 ，且以 开头的字符串，中间的部分用其他字母填充

由于不连续子序列定义为至少由两段不相邻的非空子串构成，且26个字母有限，因此我们不难发现两种无解条件：

代码如下：

#include <bits/stdc++.h>
using namespace std;
int t,n,m;
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        if(n==m||n-m>26) cout<<"NO"<<endl;
        else
        {
            cout<<"YES"<<endl;
            for(int i=0;i<n;i++)
                cout<<(char)('a'+i%(n-m));
            cout<<endl;
        }
    }
    return 0;
}

完结撒花