首页 > 其他分享 >「杂题乱刷」P10678

「杂题乱刷」P10678

时间:2024-07-02 16:54:14浏览次数:22  
标签:度数 需连 ll long 200010 P10678 杂题 define

哎哎哎,原来的题解没怎么写证明被叉了 /yun

所以我来补下证明。

题目链接

P10678 『STA - R6』月

解题思路

时间复杂度优于官解的做法。

首先我们观察到一个性质就是 \(\sum a_i = 2 \times (n - 1)\),因为一个树有 \(n - 1\) 条边。

注意到一棵树必定有叶子结点。

于是我们每次给树连边只需要拿一个剩余需连的边数为 \(1\) 的点和剩余需连的边数大于 \(1\) 的点相连即可,注意,如果没有剩余需连的边数大于 \(1\) 的点,需要特判,让另一个度数为 \(1\) 的点与这个点相连。

正确性显然。

下面是证明:

你注意到,你可以把一次加边操作看为将两个点的剩余度数减去 \(1\) 的操作,并且加边操作有至少一个点剩余的度数为 \(1\),因此,一个点连接的所有点的数量减去一的点的数量都是因为该点的度数为 \(1\),而另外一个点则是因为该点度数为 \(1\) 因此连接下一个点。

也就是说,最后形成的树可以抽象的看成菊花状,并且只要能连点,那么当前剩余需连度数为 \(1\) 的点都被尽量连到了同一个点上,并且树的直径大小一定是两个度数为 \(1\) 的点的路径长度,因此这样的连边方式也就保证了最后的树的直径最小。

时间复杂度 \(O(\sum n)\)。

参考代码

点击查看代码
#include<bits/stdc++.h>
using namespace std;
//#define map unordered_map
#define forl(i,a,b) for(register long long i=a;i<=b;i++)
#define forr(i,a,b) for(register long long i=a;i>=b;i--)
#define forll(i,a,b,c) for(register long long i=a;i<=b;i+=c)
#define forrr(i,a,b,c) for(register long long i=a;i>=b;i-=c)
#define lc(x) x<<1
#define rc(x) x<<1|1
#define mid ((l+r)>>1)
#define cin(x) scanf("%lld",&x)
#define cout(x) printf("%lld",x)
#define lowbit(x) (x&-x)
#define pb push_back
#define pf push_front
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
#define ll long long
#define ull unsigned long long
#define lcm(x,y) x/__gcd(x,y)*y
#define Sum(x,y) 1ll*(x+y)*(y-x+1)/2
#define aty cout<<"Yes\n";
#define atn cout<<"No\n";
#define cfy cout<<"YES\n";
#define cfn cout<<"NO\n";
#define xxy cout<<"yes\n";
#define xxn cout<<"no\n";
#define printcf(x) x?cout<<"YES\n":cout<<"NO\n";
#define printat(x) x?cout<<"Yes\n":cout<<"No\n";
#define printxx(x) x?cout<<"yes\n":cout<<"no\n";
ll t;
ll n;
queue<ll>q[200010];
ll sz[200010];
ll a[200010];
ll b[200010];
map<ll,ll>mp;
void solve()
{
	cin>>n;
/*	forl(i,1,n)
	{
		b[i]=0;
		while(!q[i].empty())
			q[i].pop();
	}*/
	ll su=0,ma=0;
//	mp.clear();
	forl(i,1,n)
		cin>>a[i],ma=max(ma,a[i]),su+=++mp[a[i]]==1,b[a[i]]++,q[a[i]].push(i);
	ll S=0;
	while(S<n-1)
	{
		ll id1=q[1].front();
		q[1].pop();
		cout<<id1<<' ';
		ll pd=0;
		forl(j,2,ma)
		{
			if(!q[j].empty())
			{
				id1=q[j].front();
				cout<<id1<<endl;
				S++;
				q[j].pop();
				q[j-1].push(id1);
				ll L=j-1;
				while(L>=2)
				{
					id1=q[L].front();
					cout<<id1<<' ';
					cout<<q[1].front()<<endl;
					S++;
					q[1].pop();
					q[L].pop();
					q[--L].push(id1);	
				}
				pd=1;
				break;
			}
		}
		if(!pd)
		{
			if(!q[1].empty())
			{
				id1=q[1].front();
				cout<<id1<<endl;
				S++;
				q[1].pop();
			}
			else
				a[1145141919810]=0;
		}
	}		
	//	return ;
//	}
/*	forl(i,1,n)
		if(a[i]==n-1)
		{
			forl(j,1,n)
				if(j!=i)
					cout<<i<<' '<<j<<endl;
			return ;
		}*/
/*	if(b[1]==2 && b[2]==n-2)
	{
		ll id[n+5]={0},pd=0;
		forl(i,1,n)
			id[i]=i;
		forl(i,1,n)
		{
			if(a[i]==1)
			{
				pd++;
				if(pd==1)
					swap(id[i],id[1]);
				else
					swap(id[i],id[n]);
			}
		}
		forl(i,1,n-1)
			cout<<id[i]<<' '<<id[i+1]<<endl;
		return ;
	}*/
/*	forl(i,1,n-1)
	{
		ll id1=q[1].front();
		q[1].pop();
		cout<<id1<<' ';
		ll pd=0;
		forl(j,2,n)
		{
			if(!q[j].empty())
			{
				id1=q[j].front();
				cout<<id1<<endl;
				q[j].pop();
				q[j-1].push(id1);
				pd=1;
				break;
			}
		}
		if(!pd)
		{
			if(!q[1].empty())
			{
				id1=q[1].front();
				cout<<id1<<endl;
				q[1].pop();
			}
			else
				a[1145141919810]=0;
		}
	}*/
}
int main()
{
	IOS;
	t=1;
 	cin>>t;
	while(t--)
		solve();
	QwQ;
}

标签:度数,需连,ll,long,200010,P10678,杂题,define
From: https://www.cnblogs.com/wangmarui/p/18280162

相关文章

  • 杂题乱刷1
    杂题乱刷目录杂题乱刷P7231COCI2015-2016#3]DOMINOCF888GXor-MSTCF1886E题目大意solutionCF1209G2IntoBlocks(hardversion)题目大意solutionCSP-S2019Emiya家今天的饭题目大意preface正解WhatIhavegotP4151[WC2011]最大XOR和路径[CF510D]FoxAndJumping题目大意so......
  • 杂题乱刷2
    杂题乱刷目录杂题乱刷P10141[USACO24JAN]MergingCellsP题目大意solutionP4770[NOI2018]你的名字题目大意CF1037HSecurity[ABC215G]ColorfulCandies2题目描述solution[USACO24FEB]LazyCowP题目描述solutionP1410子序列&P4728[HNOI2009]双递增序列题目大意solution......
  • 「杂题乱刷」AT_abc358_g
    代码恢复训练2024.6.15(补)链接(luogu)链接(atcoder)abc最水的G了吧。你发现,你最后肯定全在在同一个点上不动,而且你一定可以在\(n\timesm\)回合内走到这个点,因此我们直接\(dp_{i,x,y}\)表示走\(i\)步到\((x,y)\)这个格子所能得到的最大值即可。时间复杂度\(O(......
  • 2024年6月杂题乱写
    6.5P3214[HNOI2011]卡农设\(f_i\)表示选了\(m\)个集合的答案,简单观察发现,只要确定了\(m-1\)个集合,最后一个集合就是确定的,不是偶数次数的出现,偶数次数的不出现,选\(m\)个集合有\(C_{2^n-1}^{m-1}\)种方案,考虑下面两种不合法的情况。这\(m-1\)个集合已经合法,最后......
  • 「杂题乱刷」AT_abc161_d
    代码恢复训练2024.6.14.bfs板子题。链接(luogu)链接(atcoder)代码:点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出来,是不是该考虑换题?打cf不要用umap!!!记住,rating是身外之物。该冲正解时冲正解!Problem:算法:思......
  • 「杂题乱刷」CF1985F
    代码恢复训练2024.6.13.题目链接CF1985F(CF)CF1985F(luogu)解题思路由于一个回合可以用所有无冷却的技能,因此我们对于技能肯定是能用就用的。进而推出答案具有单调性。直接二分答案即可,注意二分边界问题,这里我开了__int128来避免这个问题。参考代码点击查看代码#i......
  • 杂题选讲 #1:二分图边着色
    Vizing定理定义考虑如下的问题:对一个无向图的边进行着色,要求相邻的边染不同种颜色。问需要的最少的颜色数是多少。解决上述问题需要借助Vizing定理(又称维金定理)。在开始之前,我们先进行一些符号的规定。\(\Delta(G)\):无向图\(G=(V,E)\)的最大度数,即\(\Delta(G)=\max_......
  • 「杂题乱刷」AT_abc154_e
    代码恢复训练2024.6.10.(补)链接(luogu)链接(atcoder)数位dp板子题。dfs(last,sum,_1)剩下未搜的数位数,当前非零数位数,目前是否取满。这里采用记搜的写法。点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出来,是不是该考虑换......
  • 「杂题乱刷」AT_abc132_e
    代码恢复训练2024.6.11.链接(luogu)链接(atcoder)分层图板子。结束。代码:点击查看代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出来,是不是该考虑换题?打cf不要用umap!!!记住,rating是身外之物。该冲正解时冲正解!Problem:算......
  • 「杂题乱刷」AT_abc357_f
    代码恢复训练2024.6.8.题目链接链接(atcoder)链接(luogu)解题思路数据结构板子题。设\(ans_i=a_i\timesb_i\)(\(a_i\)和\(b_i\)是此时的\(a_i,b_i\))。设\(f1(i,j)\)表示\(a_i+a_{i+1}+a_{i+2}+\dots+a_j\)的值。设\(f2(i,j)\)表示\(b_i+b_{i+......