A~D题解

前言：本人不是大佬，解法不一定是最优解，面向刚入门的朋友。若有错误，敬请指正！

A：小苯吃糖果

输出三个数里的最大值或者更小的那两个数的和，取他们的最大值即可

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX=1e9+7;

int t,n,m,s;
int a[5];
void solve(){
	for(int i=0;i<3;i++)
		cin>>a[i];
	sort(a,a+3);
	if(a[2]<a[1]+a[0])
		cout<<a[0]+a[1];
	else
		cout<<a[2];
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	t=1;
	//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

B：小苯的排列构造

构造题（constructive algorithms）

构造一个长度为 n 的排列 p，使得这个排列构成的数组 a 不是递增的，其中 ai = pi + p(pi)。也就是数组 a 的第 i 个数 = 排列 p 的第 i 个数 + 排列 p 的第 pi 个数，保证数组 a 不是递增的。我们用样例的排列来找找思路（把下标也写出来，从1开始），圈出每个 ai 对应的 pi、p(pi)，找了几个 ai 我们假设如果 ai 对应的两个数是从排列的一首一尾，从两边往中间缩，那有可能满足题意吗？相信数学小王子的你很快就会发现规律，既然 a 不是递增的就行，那构造所有 ai 都相等就可以了，所以答案可以是逆序的 n。

位于比赛前排的构造题一般不会很难，不要陷入了题目陷阱，思维开阔一点，这种诈骗题算是比较常见的，想要一眼得出答案，需要我们大量的练习。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX=1e9+7;

int t,n,m,s;
void solve(){
	cin>>n;
	for(int i=0;i<n;i++)
		cout<<n-i<<" ";
	cout<<endl;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	t=1;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

c：小苯的最小整数

相信大家都能理解题意，这种要对一个整数操作的题，我们一般都是把整数看成 string 类型，因为整形不好分割每一个数位；我们再看数据范围，1≤n≤10 ^ 10，n最多有10个0（看指数）也就是说 string 类型最多也才 11 位，测试用例 T 最大 10 ^ 5 乘于 10，最多也才 10 ^ 6，那我们就可以放心暴力了。

题目要求尽量小的 n，这可以转换成尽量小的字典序。

什么是字典序呢？就是字符按照ASCLL码表中对应的十进制数的大小的标准来规定字符的大小，从而得出一个字符串的字典序。例如 abb > aab 因为第二个位置 b > a（从左往右开始比较）；ab > a。

具体思路请看代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX=1e9+7;

int t,n,m,s;
void solve(){
	string s;
	cin>>s;
	string mi=s,a=s,b=s;
	n=s.size();
	for(int i=0;i<n-1;i++)
	{
		char ch=a[0];
		string temp=a.substr(1,n-1);//这个函数是获取字符串a中从下标1开始，长度为n-1的字符串
		temp+=ch;
		if(temp<mi)mi=temp;
		a=temp;
	}
	cout<<mi<<"\n";
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	t=1;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

D：小苯的蓄水池（easy）

不是并查集，不知道这题怎么用并查集，写的暴力

写题解好累，具体思路看代码吧，写了比较详细的注释（easy版本 n 才2000，完全可以暴力的）

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define int long long

int t,n,m;
int a[10004];
int sum[10004];//前缀和
int sign[10003][3];//用来存第i个水池能够连通的 最左边sign[i][0] 以及 最右边sign[i][1] 的水池位置
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];//前缀和
		sign[i][0]=sign[i][1]=i;//开始时每个水池都没有连通其他水池，计为 i
	}
	while(m--)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int l,r;
			cin>>l>>r;
			int lmin=l,rmax=r;//能连通的 最左端 以及 最右端
			for(int i=l;i<=r;i++)//找找这个区间有没有更大的范围
			{
				lmin=min(sign[i][0],lmin);//最左端取min
				rmax=max(sign[i][1],rmax);//最右端取max
			}
			for(int i=lmin;i<=rmax;i++)//lmin ~ rmax的区间的水池都要记录
				sign[i][0]=lmin,sign[i][1]=rmax;//记录它们能连通的左右两端的最大范围
		}
		else
		{
			int index;
			cin>>index;
			LL res=sum[sign[index][1]]-sum[sign[index][0]-1];//求区间和
			double len=sign[index][1]-sign[index][0]+1;//求长度
			printf("%.10f\n",1.0*res/len);
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	t=1;
	//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

E~G：嘎嘎嘎，不会啊┭┮﹏┭┮