2025牛客寒假算法基础集训营2

时间：2025-01-26 21:18:05

H 一起画很大的圆！

        看起来像是一道计算几何的题，实际上通过分析和猜想，是有O1复杂度的结论的。具体证明略，结论是三点越接近共线，得出的半径越大。

        

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e6+7;
const int mod = 998244353;
int n, m, k;
// int a[N];


void sovle()
{
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    if(b-a>d-c){
        cout<<a<<' '<<d<<endl;
        cout<<a+1<<' '<<d<<endl;
        cout<<b<<" "<<d-1<<endl;
    }else{
        cout<<b<<' '<<d<<endl;
        cout<<b<<' '<<d-1<<endl;
        cout<<b-1<<' '<<c<<endl;
    }
}


signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int ING = 1;
    cin>>ING;
    while (ING--)
    {
        sovle();
    }
    
    return 0;
}

C 字符串外串

        首先我们找k的下界，通过D题我们可以知道，k与两个相同字母之间的间隔距离有关，那么想要最小化相隔距离，我们就要尽量地填充不一样的字母，但是每26个字母之后必定会出现相同的字母，那么不难推出来下界就是max(0,n-26)，上界很容易知道是n-1。

        想要构造出特定可爱值的字符串，就类似与构造出一个特殊的回文串。我的代码太屎了，移步官方题解吧。。。。原本我是想着b到z循环m-1次，然后放两个aa，构造出m可爱值的前缀串，后面再接n-m-1个不同的字符就好了。后面发现n-m-1可能会大于m-1导致可爱值变大。于是我发现了n-m>m时构造会不一样，这种情况的具体构造可以变成回文串，前n-m个和后n-m个对称，中间n-2m个相等的就好了。实现起来乱七八糟额

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e6+7;
const int mod = 998244353;
int n, m, k;
// int a[N];


void sovle()
{
    // string x="abcdefghijklmnopqrstuvwxzzzzxwvutsrqponmlkjihgfedcba";cout<<x.size()<<endl;
    cin>>n>>m;
    if(n==m||n-26>m){
        cout<<"NO"<<endl;
        return;
    }
    cout<<"YES"<<endl;
    string s;
    if(n-m>m){
        char ch='b';
        for(int i=0;i<m-1;i++) s.push_back(ch),ch++;
        s.push_back('a');
        for(int i=m;i<n-m;i++) s.push_back(ch),ch++;
        if(n>1&&m!=0) s.push_back('a');
        ch='b'+m-2;
        for(int i=n-m+1;i<n;i++) s.push_back(ch),ch--;
        // if(n>1&&m!=0) s.push_back('a');
        cout<<s<<endl;
        return;
    }
    char ch='a';
    for(int i=0;i<n-m-1;i++) s.push_back(ch),ch++;
    for(int i=n-m-1;i<=m;i++) s.push_back('z');
    ch='a'+n-m-2;
    for(int i=m+1;i<n;i++) s.push_back(ch),ch--;
    cout<<s<<endl;
}


signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int ING = 1;
    cin>>ING;
    while (ING--)
    {
        sovle();
    }
    
    return 0;
}

相关文章