构造

参考资料

构造 - OI Wiki

例题

洛谷 CF743C Vladik and fractions

构造一组 $x,y,z$ ，使得对于给定的 $n$ ，满足：

\frac{1}{x}+\frac{1}{y}+\frac{1}{z}=\frac{2}{n}

Code (1)

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	if(n==1)
	{
		cout<<"-1"<<'\n';
		return 0;
	}
	cout<<n<<' '<<n+1<<' '<<n*(n+1)<<'\n';
	return 0;
}

洛谷 CF1899F Alex's whims

树中两个顶点 $u$ 和 $v$ 之间的距离是指顶点 $u$ 到顶点 $v$ 必须经过的最小边数。

亚历克斯的生日快到了，蒂莫菲想送他一棵有 $n$ 个顶点的树。然而，亚历克斯是个喜怒无常的孩子。在 $q$ 天里，他每天都会选择一个整数，第 $i$ 天选择的整数用 $d_i$ 表示。如果在第 $i$ 天，树上没有两片距离正好为 $d_i$ 的叶子节点，亚历克斯就会很失望。

蒂莫菲决定送给亚历克斯一个设计器，这样他就可以随心所欲地改变他的树了。蒂莫菲知道亚历克斯也很懒惰，所以每天一开始，他可以进行仅仅一次以下类型的操作：

选择顶点 $u$ 、 $v_1$ 和 $v_2$ ，需要满足 $u$ 和 $v_1$ 之间有一条边， $u$ 和 $v_2$ 之间没有边。然后删除 $u$ 和 $v_1$ 之间的边，并在 $u$ 和 $v_2$ 之间添加一条边。如果操作后图形不再是树，则不能执行此操作。

不知怎的，蒂莫菲设法找出了所有的 $d_i$ 。之后，他又想出了一个绝妙的主意——以防万一，为这组集合 $d_i$ 制作一本说明书，这样亚历克斯就不会失望了。

Solution

原题链接

洛谷 CF1899F Alex's whims

解题思路

如图，用 $n-1$ 个节点构造一条链，根节点为 $n$ ，叶节点为 $1$ 。（此处 $n=8$ ）

让动点 $n$ 与编号为 $k\in[2,n-1]$ 的点相连。

不难发现，节点 $n$ 也是叶节点。

节点 $1$ 到节点 $k$ 的距离为 $k-1$ ，节点 $k$ 到节点 $n$ 的距离为 $1$ ，所以节点 $1$ 到节点 $n$ 的距离为 $k$ 。

通过调整 $k\in[2,n-1]$ 的编号，即可得到距离为 $d\in[2,n-1]$ 的两个叶节点。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int inf=0x3f3f3f3f;
const int N=505;
int d[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		int n,q;
		cin>>n>>q;
		for(int i=1;i<=q;i++)
		{
			cin>>d[i];
		}
		for(int i=1;i<=n-2;i++)
		{
			cout<<i<<' '<<i+1<<'\n';
		}
		cout<<n<<' '<<2<<'\n';
		int now=2;
		for(int i=1;i<=q;i++)
		{
			if(d[i]==now)
			{
				cout<<"-1"<<' '<<"-1"<<' '<<"-1"<<'\n';
			}
			else
			{
				cout<<n<<' '<<now<<' '<<d[i]<<'\n';
				now=d[i];
			}
		}
	}
    return 0;
}

参考资料​

例题​

洛谷 CF743C Vladik and fractions​

洛谷 CF1899F Alex's whims​

原题链接​

解题思路​

参考代码​