首页 > 其他分享 >solution - qoj8794

solution - qoj8794

时间:2024-07-25 18:55:39浏览次数:14  
标签:ch 点连边 int solution long qoj8794 id define

(Un)labeled graphs 题解

orz jiangly

通信题。不禁让人想到

对于这道题目,考虑要还原原来的点的编号,而题目条件里有一个 image

还是非常明显,发现我们可以搞出一排新的点让它们构成一条新的链。然后第 \(i\) 个点往原图中编号为 \(u\) 的点连边,满足 \(u \& 2^{i-1}\)。

现在我们需要解决的问题是如何辨认出这条链。发现还多了三个点可以供我们操作。设其为 A,B,C。

考虑怎么搞出一个特殊点让我们一开始就可以辨认出来。令其度数最大即可。于是我们让 A 与其他所有点连边。这样就可以把它一眼顶真出来。

发现好像只知道这一个点有点废。于是我们钦定 C 是唯一一个不与 A 连的点。然后我们又得到了一个可以被识别出来的全新点。

延续之前的思路,之前是向所有点连边,考虑让 C 只和一些点连边。比方说,让 C 与 B 连边,我们又得到了 B。

先考虑识别出链来,于是我们让 B 向原图中的所有点连边。这样不与 B 连边的点就是链上的点了。

发现无法确定链的方向。于是我们让 C 与链的端点连边。怎么区分链端点和 B ?看度数即可。

// Problem: C - (Un)labeled graphs
// URL: https://vjudge.net/contest/643391#problem/C
// Written by WRuperD

#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int mininf = 1e9 + 7;
#define int long long
#define pb emplace_back
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0');}
#define put() putchar(' ')
#define endl puts("")
const int MAX = 3e3 + 10;

bool edge[MAX][MAX];

void work2(int n, int m){
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			char ch = getchar();
			while(ch != '0' and ch != '1')	ch = getchar();
			edge[i][j] = ch - '0';
		}
	}
	for(int i = n + 1; i <= m - 3; i++){
		int now = i - n - 1;
		for(int j = 1; j <= n; j++){
			if(j & (1ll << now)){
				edge[j][i] = edge[i][j] = 1;
			}
		}
		if(i != m - 3){
			edge[i][i + 1] = edge[i + 1][i] = 1;
		}
	}
	int A = m - 2, B = m - 1, C = m;
	for(int i = 1; i < m; i++)	{
		if(i != A)	edge[i][A] = edge[A][i] = 1;
	}
	edge[B][C] = edge[C][B] = 1;
	edge[n + 1][C] = edge[C][n + 1] = 1;
	for(int i = 1; i <= n; i++){
	 	edge[B][i] = edge[i][B] = 1;
	}
	for(int i = 1; i <= m; i++){
		for(int j = 1; j <= m; j++){
			write(edge[i][j]);
		}endl;
	}
}

int id[MAX];
int deg[MAX];
int Ans[MAX][MAX];
bool isg[MAX];

void work(int x, int nowid, int m){
	for(int i = 1; i <= m; i++){
		if(edge[x][i] and isg[i]){
			id[i] |= nowid;
		}
	}
	id[x] = inf;
	isg[x] = 1;
	for(int i = 1; i <= m; i++)	if(edge[x][i] and !isg[i])	work(i, nowid * 2, m);
}

void work3(int m, int n){
	for(int i = 1; i <= m; i++){
		for(int j = 1; j <= m; j++){
			char ch = getchar();
			while(ch != '0' and ch != '1')	ch = getchar();
			edge[i][j] = ch - '0';
			deg[i] += edge[i][j], deg[j] += edge[i][j];
		}
	}
	int A = 0;
	for(int i = 1; i <= m; i++){
		if(deg[A] < deg[i])	A = i;
	}
	id[A] = n + 1;
	int C = 0;
	for(int i = 1; i <= m; i++)	if(i != A and edge[A][i] == 0) C = i;
	int B = 0;
	for(int i = 1; i <= m; i++)	if(edge[C][i] and deg[i] >= deg[B])	B = i;
	for(int i = 1; i <= m; i++)	if(edge[B][i] and i != A and i != C)	isg[i] = 1;
	id[A] = id[B] = id[C] = inf;
	isg[A] = isg[B] = isg[C] = 1;
	// write(A), put(), write(B), put(), write(C), endl;
	for(int i = 1; i <= m; i++)	if(edge[C][i] and i != B)	work(i, 1, m);
	// write(isg[2]), endl;
	for(int i = 1; i <= m; i++)	if(!id[i])	id[i] = n;
	// for(int i = 1; i <= m; i++)	write(is[])
	for(int i = 1; i <= m; i++){
		for(int j = 1; j <= m; j++){
			if(!id[i] or !id[j] or id[i] > n or id[j] > n or i == A or i == B or i == C or j == A or j == B or j == C)	continue;
			Ans[id[i]][id[j]] = edge[i][j];
			Ans[id[j]][id[i]] = edge[i][j];
		}
	}
	// for(int i = 1; i <= m; i++)	if()
	// write(A), put(), write(B), put(), write(C), endl;
	// for(int i = 1; i <= m; i++)	write(id[i]), put();
	// endl;
	// write(n), endl;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			write(Ans[i][j]);
		}endl;
	}
}

void solve(){
	int n = read(), m = read();
	if(n < m)	work2(n, m);
	else work3(n, m);
}

signed main(){
	int t = 1;
	while(t--)	solve();
	return 0;

标签:ch,点连边,int,solution,long,qoj8794,id,define
From: https://www.cnblogs.com/WRuperD/p/18323944

相关文章

  • AT_abc363_e [ABC363E] Sinking Land Solution
    题目大意:有一座矩形岛屿,被分为\(H\timesW\)的网格,四周与海水接触,给定时间\(Y\)年,最初海平面位于高度\(0\\text{m}\),每年海水上升\(1\\text{m}\),请求出每年未被海水淹没的格子数(高度小于等于海水高度即为淹没)。显然有点类似于广搜的想法,用一个队列存储与海水接触的方......
  • Solution - Atcoder Xmas2019E Sum of f(n)
    考虑\(F(n)=\sum\limits_{i=1}^nf_i=\sum\limits_{i=1}^n\sum\limits_{p\in\mathbb{P},k\ge1}[p^k|i]=\sum\limits_{p\in\mathbb{P},k\ge1}\lfloor\frac{n}{p^k}\rfloor\)。对于这个\(\lfloor\frac{n}{x}\rfloor\),一个比较经典的想法就是考虑对其......
  • Solution - Atcoder Xmas2019D Sum of (-1)^f(n).md
    对于\(f(i)=(-1)^{\sum\limits_jc_j}(i=\prod\limits_jp_j^{c_j}(p_j\in\mathbb{P}))\),一个比较特殊的值就是在\(i\in\mathbb{P}\)时有\(f(i)=-1\)。于是考虑PowerfulNumber筛,构造积性函数\(g\)使得对于\(i\in\mathbb{P}\)有\(g(p)=f(p)\)且\(g\)易......
  • Solution Set - 容斥原理/二项式反演
    https://www.becoder.com.cn/contest/5400「BZOJ2863」愤怒的元首题目就是求\(n\)个点DAG的数量。设\(dp_i\)表示\(i\)个点的DAG数量。首先DAG一定存在出度为\(0\)的点,其次删去出度为\(0\)的点,仍构成一个DAG。所以我们可以枚举删去的数量,从而划分子问题。......
  • Solution Set - NOI真题
    NOI2024RP++!NOI2021Day1T1Link&Submission.对整棵树做轻重链剖分。每一次修改,找到轻标记边集合中涉及到该路径的边删掉。然后,拿出重链上的所有轻边和重链。,把重链上除了底部的点全部标记为“到重儿子的边是标记边”,把所有轻边加入轻标记边集合。每一次查询,查询重链上有多少个......
  • CF1988C Increasing Sequence with Fixed OR Solution
    题意简述如下:给定一个正整数\(n\),请构造一个正整数序列使其满足以下条件并尽可能长:这个序列中每个数都大于等于\(1\)且小于等于\(n\);这个序列是单调递增的;这个序列中任意两个相邻的数按位或的结果都为\(n\)。通过手玩或者写个最长上升子序列可以发现,我们记这个数在二进制......
  • Solution - Atcoder AGC022D Shopping
    考虑到不管怎么走,都是\(0\)最后又绕回\(0\),于是答案肯定是\(2L\)的倍数。那么考虑\(\frac{\operatorname{ans}}{2L}\)即可。那么对于\(t_i\),可以先让答案加上\(\lfloor\frac{t_i}{2L}\rfloor\),同时令\(t_i\leftarrowt_i\bmod2L\)。原因就是考虑到这被去除掉的\(2......
  • Solution - Codeforces 1311E Construct the Binary Tree
    先去考虑找一下无解条件。首先就是有\(d\)关于\(n\)的下界\(L\),就是弄成一颗完全二叉树的答案。其次有\(d\)关于\(n\)的上界\(R\),就是成一条链的样子。首先当\(d<L\)或\(R<d\)时显然无解。对于\(L\led\leR\)又如何去判定。能发现没有一个比较好的判定......
  • Solution - Atcoder AGC021D Reversed LCS
    考虑到\(\operatorname{LCS}(T,T')\)这个形式实在是不太优美,考虑转化一下形式。感受一下,能够知道\(T\)的最长回文子序列\(|\operatorname{LPS}(T)|=|\operatorname{LCS}(T,T')|\)。具体证明可以见zhihu,本人暂时还没看懂。那么接下来对于单个串的\(\operatorname{LPS......
  • Solution - Atcoder ARC127E Priority Queue
    考虑转化一下,每个最后留下来的集合都相对的对应着一个被删除的集合。于是考虑去对被删除的数去计数。然后贪心的,去让每一次\(2\)操作删除的数都是前面加入中还剩下的最后加入的数(因为有的可能被前面的\(2\)操作删了)。对于证明,考虑到如果不是剩下的最后加入的,那么中间可能会......