专栏文章

P13786 题解

DDaiRuiChen007
P13786题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimz3c5o
此快照首次捕获于
2025/12/01 17:54
3 个月前
此快照最后确认于
2025/12/01 17:54
3 个月前
查看原文
Problem Link
首先假设 p=[1,…,n]p=[1,\dots,n]，则 a=LIS(q),b=LIS(r)a=\mathrm{LIS}(q),b=\mathrm{LIS}(r)。
通过 a=1,c=na=1,c=n 的部分分可以猜测合法条件为 abc≥n,a+b≤c+nabc\ge n,a+b\le c+n 及其轮换形式。
首先 a+b≤c+na+b\le c+n 较显然，因为长度为 a,ba,b 的 LIS\mathrm{LIS} 至少有长为 a+b−na+b-n 的 LCS\mathrm{LCS}。
然后考虑 abc<nabc<n 时的情况，首先 LDS(q)≥na≥bc+1\mathrm{LDS}(q)\ge \dfrac na\ge bc+1，考虑 LDS(q)\mathrm{LDS}(q) 中元素在 rr 中出现的顺序 tt， LIS(t)≤LCS(q,r)=c\mathrm{LIS}(t)\le \mathrm{LCS}(q,r)=c，其次 LDS(t)≤LIS(r)=b\mathrm{LDS}(t)\le \mathrm{LIS}(r)=b，那么 LIS(t)×LDS(t)<∣t∣\mathrm{LIS}(t)\times\mathrm{LDS }(t)< |t|，这显然是不可能的。
考虑 n=abcn=abc 时的构造，考虑在 LIS,LDS\mathrm{LIS},\mathrm{LDS} 一定时 nn 尽可能大的经典构造：若干值域递减的上升序列和若干值域递增的下降序列。
那么直接运用之，qq 为 bcbc 个长度为 aa 的上升序列，rr 为 bb 个长度为 acac 的下降序列，则 r∘q−1r\circ q^{-1} 为 cc 个值域递增的长度为 bb 的下降序列值域递减地重复 aa 次，此时 LCS(q,r)=a\mathrm{LCS}(q,r)=a 合法。
注意到我们只要取出三个排列中值为 [1,2,…,a],[1,ac+1,2ac+1,…,(b−1)ac+1],[1,a+1,2a+1,…,(c−1)a+1][1,2,\dots,a],[1,ac+1,2ac+1,\dots,(b-1)ac+1],[1,a+1,2a+1,\dots,(c-1)a+1] 的元素构成的子序列（即 p,q,rp,q,r 之间的 LCS\mathrm{LCS} 中元素），此时得到 a+b+c−1a+b+c-1 个元素的排列，如果 n>a+b+c−1n>a+b+c-1，随便选一些剩下的元素放进去即可。
那么只要考虑 n≤a+b+c−2n\le a+b+c-2 的情况，如果 (a−1)(b−1)(c−1)≥n−1(a-1)(b-1)(c-1)\ge n-1，则求 (n−1,a−1,b−1,c−1)(n-1,a-1,b-1,c-1) 的解然后在末尾插入 nn 即可。
否则 (a−1)(b−1)(c−1)<n−1(a-1)(b-1)(c-1)<n-1，容易发现此时必有 a−1=b−1=1a-1=b-1=1，即 a=b=2,c=n−1a=b=2,c=n-1，在 q,r=[n,n−1,…,1]q,r=[n,n-1,\dots,1] 的基础上交换 (q1,q2),(r1,r3)(q_1,q_2),(r_1,r_3) 即可。
那么我们就给出了所有 (n,a,b,c)(n,a,b,c) 的构造方法。
时间复杂度 O(nlog⁡n)\mathcal O(n\log n)。
代码：
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
void solve() {
	ll n,a,b,c,ty,m;
	cin>>n>>a>>b>>c>>ty,m=n;
	if(a*b*c<n||a+b>c+n||a+c>b+n||b+c>a+n) return cout<<"No\n",void();
	cout<<"Yes\n";
	if(!ty) return ;
	int k=0;
	for(;n&&(a-1)*(b-1)*(c-1)>=n-1;++k,--a,--b,--c,--n);
	basic_string <int> B,C;
	if(!n);
	else if(a+b+c-2>n) {
		for(int i=n-1;~i;--i) B+=i,C+=i;
		swap(B[0],B[1]),swap(C[1],C[2]);
	} else {
		map <ll,int> X;
		vector <array<ll,2>> Y,Z;
		auto ins=[&](ll x) { X[x]=0,Y.push_back({-(x/a),x}),Z.push_back({x/a/c,-x}); };
		ins(0);
		for(int i=1;i<a;++i) ins(i);
		for(int i=1;i<b;++i) ins(a*c*i);
		for(int i=1;i<c;++i) ins(a*i);
		for(int i=0;i<n&&(int)X.size()<n;++i) if(!X.count(i)) ins(i);
		sort(Y.begin(),Y.end()),sort(Z.begin(),Z.end());
		int t=0;
		for(auto &o:X) o.second=t++;
		for(auto o:Y) B+=X[o[1]];
		for(auto o:Z) C+=X[-o[1]];
	}
	for(int i=n;i<m;++i) B+=i,C+=i;
	for(int i=0;i<m;++i) cout<<i+1<<" \n"[i==m-1];
	for(int i=0;i<m;++i) cout<<B[i]+1<<" \n"[i==m-1];
	for(int i=0;i<m;++i) cout<<C[i]+1<<" \n"[i==m-1];
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _; cin>>_;
	while(_--) solve();
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...