2023.11.7

A

给出 \(n\)，构造最大的 \(m\) 和 \(\{(a,b,c)_m\}\)，值域为 \([0,n]\) 且无偏序关系。

\(n\le 600\)。

显然构造所有的 \(\displaystyle a+b+c=\lfloor\frac{3n}{2}\rfloor\) 即可。

#include<bits/stdc++.h>
#define N 605
using namespace std;
int read(){
	int x=0,w=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*w;
}
int n,x;
struct dat{
	int a,b,c;
};
vector<dat>ans;
int main(){
	n=read();
	x=3*n/2;
	for(int a=0;a<=x;a++)
		for(int b=0;a+b<=x;b++)
			if(a<=n&&b<=n&&x-a-b<=n)
				ans.push_back((dat){a,b,x-a-b});
	printf("%d\n",(int)ans.size());
	for(dat j:ans)printf("%d %d %d\n",j.a,j.b,j.c);
	
	return 0;
}

B

\(n\) 次操作，往初始为空的序列的右端加入 \(l_i\) 个 \(p_i\)。

在序列中找出和在 \([L,R]\) 间的一个区间，最大化平均值。

\(n\le 3\times 10^5\)，\(1\le l_i,p_i\le 10^6\)，\(1\le L\le R\le \sum l_i\cdot p_i\)，精度要求 \(10^{-6}\).

把题目所给的 \(n\) 个连续段称整块，那么最终答案不可能两端均为散块。可以得到 \(O(n^2)\) 的做法。

然后使用单调队列优化。在出题人造的数据下接近 \(O(n\log n)\).

C

一棵树 \(T_0\)，\(k\) 次砍断一条边并选取两个连通块其一，记为 \(T_i\)。

问多少种切树方案 \(\{T_0,\dots,T_k\}\) 满足 \(i\in[1,k]\)，\(|T_i|=a_i\)。

\(n\le 5000\)。

D

最小树形图。不好评价。