洛谷月赛 11.1题解

T1 P11242 碧树

原题链接

这道题虽然它给了是数论，但我觉得是个规律题，我们看一下是怎么找到规律的。

要求这棵树包含的最少节点，我们可以简单的画个图

对于我们要寻找的答案，可以抽象成如下想法：
我们将所有的节点都放在根节点的左子树，在小于最大深度时，如果某一个深度有叶子节点，那么它就会长成这样

那么我们就会发现，如果某个深度有叶子节点，那么它就会$+2$，否则$+1$，那么我们只需要找到最大的深度，用最大的深度加上叶子节点数-1即可。

$code$

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int n;
int maxn=0;
int ans;
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		maxn=max(maxn,a[i]);
	}
	ans=maxn+n-1;
	cout<<ans;
	return 0;
}

T2 P11243 繁花

原题链接

这道题走一遍双指针就行了。
我们用$ans$来记录答案，用$p$判断数对是否符合要求。分别判断三种符号的情况，最后记录答案即可。

#include <bits/stdc++.h>
#define int long long 
using namespace std;
int n,t,l,x,ans,p;
string s;
signed main(){
	scanf("%d",&t);
	while(t--){
		scanf("%lld",&n);
		cin>>s;
		s=" "+s;
		ans=0;
		l=1;
		x=1;
		p=0;
		for(int i=1;i<n;i++){
			x=1;
			l=i-1;
			while(s[i]=='='){
				ans+=p;
				if(i==n){
					break;
				}
				i++;
				x++;
			}
			if(i==n)break;
			if(s[i]!=s[l]){
				p=x;
			}
			else p+=x;
			ans+=p;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

T3 P11244 吻秋

原题链接

这道题还好，没有那么恶心人的东西。
首先我们需要知道一个结论，对于交换$a_x$和$a_y$的操作，如果满足$a_{x,n}\le a_{y,1}$,或者$a_{y,n}\le a_{x,1}$就称此操作为无效，else为有效的。

证明：

结论$A$：
交换$1$操作的$x，y$，只影响编号而不影响结果，因为元素相同，交换$x，y$与交换操作完之后的$x，y$等价。

结论$B$：
对$x，y$进行1操作后，$a_{x,n}\le{a_{y,1}}。

对于每次操作后，我们都会对$x，y$进行一次$1$操作。假设这些操作全部有效，也不会超过$m^3$次。注意到我们每个数组在第一次操作后可以保证完全有序，这样就能实现$O(n)$进行有效操作。

$code$

#include<bits/stdc++.h>
#define re register
#define il inline
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
using namespace std;
//快读快写
char buf[1 << 20], *p1, *p2;
il int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-')f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
	}
	return x * f;
}
il void write(int x) {
	if (x < 0)putchar('-'), x = -x;
	if (x > 9)write(x / 10);
	putchar(x % 10 + 48);
}
const int M = 25, INF = 0x3f3f3f3f;
int n, m, q;
vector<int> a[M], b;
bool used[M];
il void solve() {
	int opt = read(), x = read(), y = read();
	if (opt == 2) return write(a[x][y]), putchar('\n'), void();
	//这里简写了，等同于：
	/*
		if(opt==2)
		{
			write(a[x][y]),putchar('\n');
			return;
		}
	*/
	// step 1 排序
	if (!used[x]) sort(a[x].begin(), a[x].end()), used[x] = 1;
	if (!used[y]) sort(a[y].begin(), a[y].end()), used[y] = 1;
	// step 3 直接交换
	int minx = a[x][1], maxx = a[x][n];
	int miny = a[y][1], maxy = a[y][n];
	//判断 a_x 中所有元素是否都小于 a_y 中所有元素可以直接用 a_x 的最大值与 a_y 的最小值比较即可
	//因为已经排序，最大最小值在首尾取到即可
	if (maxx <= miny) return;
	if (maxy <= minx) return swap(a[x], a[y]), void();
	// step 2 归并
	int i = 1, j = 1, k = 0;
	while (i <= n && j <= n) {
		if (a[x][i] <= a[y][j]) b[++k] = a[x][i++];
		else b[++k] = a[y][j++];
	}
	while (i <= n) b[++k] = a[x][i++];
	while (j <= n) b[++k] = a[y][j++];
	for (re int i = 1; i <= n; i++) a[x][i] = b[i];
	for (re int i = n + 1; i <= n + n; i++) a[y][i - n] = b[i];
}
int main() {
	n = read(), m = read(), q = read();
	for (re int i = 1; i <= m; i++) a[i].resize(n + 1); //初始化 vector 大小
	for (re int i = 1; i <= m; i++)
		for (re int j = 1; j <= n; j++) a[i][j] = read(); //注意从下标 1 开始读入，方便后面的排序
	b.resize(n * 2 + 1);
	while (q--) solve();
	return 0;
}

T4 P11245 残雪

原题链接
思路先写上，代码就不贴了。

先计算$L=R$的情况，我们假设$n<m$，那么可以理解为要去找使$n$不会被吸收的合法解的对于$m$的要求。显然，如果我们$L$个$L$个去排波峰波谷是最能让他被吸收的排法。那么只需要把周期降低为$L-1$
，它就一定吸收不了了。那么对于$m$的限制，就是必须大于周期数乘上$L+1$。考虑$L<R$的情况。我们上边找对于$m$的限制，其实就是往$n$个波峰里面插入一定量的波谷。我们仍然按照$L-1$去排，然后每次使$L$变大去改我们的构造出来的序列，发现每$2L$个为一组，第一组为$L-1$
个波峰$L+1$个波谷，然后往后的每一组依次解体$R-L$个波峰 直到不存在连续的波峰。那么我们的构造方案就出来了。最后，我们假设的是$n<m$，不失一般性的，我们计算答案时只需要对于$n$算一遍$m$是否满足要求然后对$m$算一遍$n$是否满足要求即可。