网站增加用户体验,彭州建设网站,软件工程包括什么专业,英文网站怎么做seo传送门
题意#xff1a;给一棵nnn个结点的树#xff0c;构造一个nnn阶排列ppp#xff0c;使得所有距离为333的点对(i,j)(i,j)(i,j)满足pipjp_ip_jpipj和pipjp_ip_jpipj至少一个为333的倍数。
分析一下#xff0c;这个条件等价于所有距离333的点对点权对三取模后不…传送门
题意给一棵nnn个结点的树构造一个nnn阶排列ppp使得所有距离为333的点对(i,j)(i,j)(i,j)满足pipjp_ip_jpipj和pipjp_ip_jpipj至少一个为333的倍数。
分析一下这个条件等价于所有距离333的点对点权对三取模后不都为111且不都为222
换句话说所有余数为111的点中不存在距离为333的222一样。
因为要求距离为333可以二分图染色把余数相同的放在同一个颜色中。
问题转换成了把⌊n23⌋\lfloor\frac{n2}3\rfloor⌊3n2⌋个111和⌊n13⌋\lfloor\frac{n1}3\rfloor⌊3n1⌋个222放入两个集合要求相同的数只能放在同一个集合。且这两个集合最多分别只能放x,yx,yx,y个其中xynxynxyn
如果x,yx,yx,y中一个很大就把两个都放进去否则分开放。
根据意识流一定可以放下瞎搞一波即可。
最后剩下的放333
#include iostream
#include cstdio
#include cstring
#include cctype
#define MAXN 200005
#define MAXM 400005
using namespace std;
struct edge{int u,v;}e[MAXM];
int head[MAXN],nxt[MAXM],cnt;
void addnode(int u,int v)
{e[cnt](edge){u,v};nxt[cnt]head[u];head[u]cnt;
}
int col[MAXN],tot[2],p[MAXN],n;
void dfs(int u)
{tot[col[u]];for (int ihead[u];i;inxt[i])if (col[e[i].v]-1)col[e[i].v]col[u]^1,dfs(e[i].v);
}
inline void putp(int r,int c)//freedomly put r3k into color c
{int curr;for (int i1;in;i)if (col[i]c!p[i]){p[i]cur,cur3;if (curn) return;}
}
int main()
{scanf(%d,n);for (int i1;in;i){int u,v;scanf(%d%d,u,v);addnode(u,v),addnode(v,u);}memset(col,-1,sizeof(col));for (int i1;in;i) if (col[i]-1) col[i]0,dfs(i);int k(n1)/3;if (kmin(tot[0],tot[1])) putp(2,tot[1]tot[0]);else putp(2,tot[1]tot[0]);putp(1,tot[1]tot[0]);int cur3;for (int i1;in;i)if (!p[i])p[i]cur,cur3;for (int i1;in;i) printf(%d%c,p[i], \n[in]);return 0;
}
