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

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;
}