Codeforces Round 628 (Div. 2)

Codeforces Round #628 (Div. 2)
久违的(?)更新
实习offer疑似要因为实习时间太短告吹了，只能打打cf维持生活这样子

---

A. EhAb AnD gCd

给一个数x，找到满足$GCD(a,b)+LCM(a,b)=x$的数对a,b

很显然是1+(x-1)嘛

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
int main()
{
	int t;
	scanf("%d", &t);
	while(t --)
	{
		int x;
		scanf("%d", &x);
		printf("%d %d\n", 1, x - 1);
	}
	return 0;
}

---

B. CopyCopyCopyCopyCopy

把长度为n的序列复制n次，问它的最长上升子序列长度。

第i组有效的是第i个大的数，所以答案是序列里不同数字的个数。

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
const int maxn = 1e5 + 10;
int a[maxn];
 
int main()
{
	int t;
	scanf("%d", &t);
	while(t --)
	{
		int n;
		scanf("%d", &n);
		for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
		set<int> st;
		for(int i = 1; i <= n; i ++) st.insert(a[i]);
		printf("%d\n",(int)st.size());
	}
	return 0;
}

---

C. Ehab and Path-etic MEXs

给树上每条边一个0~n-2的不重复权值，怎么使树上所有路径的MEX最大值最小。

我的思路是把最小值赋给叶子的父边，这样在叶子个数超过3（也就是不是链的情况）时，MEX的最大值不会超过2。

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
const int maxn = 1e5 + 10;
int de[maxn], pos[maxn];
pair<int, int> edge[maxn];
int res[maxn];
 
int main()
{
	int n;
	scanf("%d", &n);
	for(int i = 1; i < n; i ++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		edge[i] = make_pair(u, v);
		de[u] ++, de[v] ++;
		pos[u] = i, pos[v] = i;
	}
	int mex = 0;
	memset(res, 0xff, sizeof res);
	for(int i = 1; i <= n; i ++)
	{
		if(de[i] == 1)
		{
			if(res[pos[i]] == -1) res[pos[i]] = mex ++;
		}
	}
	for(int i = 1; i < n; i ++)
	{
		if(res[i] == -1) printf("%d\n", mex ++);
		else printf("%d\n", res[i]);
	}
	return 0;
}

---

D. Ehab the Xorcist

给定两个非负整数$u$,$v$，求一个元素个数最少的数组，满足它们的异或和为$u$,和为$v$.

题解

先特判u=0或者u=v的情况。当v>u或者(v-u)%2==1时无解。

对于(v-u)%2==0的情况，如果u&((v-u)>>1)==0，答案就是u^((v-u)>>1),(v-u)>>1)，否则就是u,(v-u)>>1,(v-u)>>1，因为前者将a[0]和a[1]合并之后不影响它们的和。

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
int main()
{
	ll u, v;
	scanf("%lld%lld", &u, &v);
	if(u > v) return 0 * puts("-1");
	if(u == 0)
	{
		if(v == 0) return 0 * puts("0");
		else if(v % 2 == 0)
		{
			printf("%d\n%lld %lld\n", 2, v / 2, v / 2);
			return 0;
		}
		else return 0 * puts("-1");
	}
	if(u == v) return 0 * printf("%d\n%lld\n", 1, u);
	if((v - u) % 2 == 0)
	{
		ll tmp = v - u;
		tmp /= 2;
		if((u & tmp) == 0)
		{
			printf("%d\n", 2);
			ll res1 = u, res2 = 0;
			for(ll i = 0; i < 64; i ++) if((tmp >> i) & 1) 
			{
				(res1 ^= (1ll << i));
				(res2 ^= (1ll << i));
			}
			printf("%lld %lld\n", res1, res2);
			return 0;
		}
		else 
		{
			printf("3\n%lld %lld %lld\n", u, tmp, tmp);
			return 0;
		}
	}
	puts("-1");
	return 0;
}

---

E. Ehab’s REAL Number Theory Problem

给定一个长度为$n(1 \le n \le 10^5)$的数组，元素大小满足$(1 \le a_i \le 10^6)$且元素的因数个数不超过7.找出最小的子集大小，满足子集中元素的积是一个完全平方数。

题解

首先对元素做预处理，只留下满足cnt%2==1的质数（因为平方数不影响答案）。

特判预处理后存在元素为1或者两个元素相等的情况。

考虑元素的因数个数不超过7这个条件，说明元素本身只有最多2个质因数（如果质因数为3，因数个数等于8）。

对于元素的质因数p,q（如果小于2，令其它为1）建图，连边p-q，边表示某个元素。对于图上的路径s-t，除了起点s和终点t，其它质数都出现了两次。所以答案就是这张图上的最小环，枚举起点，用BFS树求解即可。

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
const int maxn = 1e5 + 10;
const int maxm = 1e6 + 10;
const int inf = 0x3f3f3f3f;
 
int a[maxn], dis[maxm];
bool vis[maxm];
vector<int> edge[maxm];
 
int main()
{
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++) 
	{
		scanf("%d", &a[i]);
		for(int j = 2; j * j <= a[i]; j ++) while(a[i] % (j * j) == 0) a[i] /= j * j;
	}
	sort(a + 1, a + 1 + n);
	if(a[1] == 1) return 0 * puts("1");
	for(int i = 1; i < n; i ++)
		if(a[i] == a[i + 1]) return 0 * puts("2");
	set<int> val;
	for(int i = 1; i <= n; i ++)
	{
		vector<int> tmp;
		for(int j = 2; j * j <= a[i]; j ++) if(a[i] % j == 0)
		{
			tmp.push_back(j);
			while(a[i] % j == 0) a[i] /= j; 
		}
		if(a[i] > 1) tmp.push_back(a[i]); 
		while(tmp.size() < 2) tmp.push_back(1);
		int u = tmp[0], v = tmp[1];
		edge[u].push_back(v);
		edge[v].push_back(u);
		val.insert(u);
		val.insert(v);
	}
	int res = inf;
	for(int i = 1; i <= 1000; i ++)
	{
		if(!edge[i].size()) continue;
		for(auto v : val) vis[v] = false, dis[v] = inf;
		queue<int> que;
		que.push(i); 
		vis[i] = true, dis[i] = 0;
		while(!que.empty())
		{
			int u = que.front(); 
			que.pop();
			vis[u] = false;
			for(auto v : edge[u])
			{
				if(dis[v] > dis[u] + 1)
				{
					dis[v] = dis[u] + 1;
					vis[v] = true;
					que.push(v);
				}
				else if(vis[v])
					res = min(res, dis[u] + dis[v] + 1);
			}
		}
	}
	printf("%d\n", res == inf ? -1 : res);
	return 0;
}

---

F. Ehab’s Last Theorem

给定一张n个点的图，保证至少存在以下一种情况:

• 存在一个恰好有$\lceil\sqrt{n}\rceil$个点的独立集

• 存在一个至少有$\lceil\sqrt{n}\rceil$个点的环

找到上述其中一种的任意一个合法解并输出。

题解

对于情况2，只需要dfs树找到图的最大环。如果不满足条件，对dfs树上的节点01染色，保证取一个点就不取连向它的所有点来求独立集。

赛中没调出来还越写越丑，码力属实不大行。

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
const int maxn = 1e5 + 10;
 
vector<int> edge[maxn];
int dep[maxn], pre[maxn], lim;
bool mark[maxn];
 
void dfs(int u)
{
	dep[u] = dep[pre[u]] + 1;
	for(auto v:edge[u])
	{
		if(v == pre[u]) continue;
		if(!dep[v]) pre[v] = u, dfs(v);
		else 
		{
			if(dep[u] - dep[v] + 1 >= lim)
			{
				printf("2\n%d\n%d ", dep[u] - dep[v] + 1, u);
				int now = u;
				do {
					now = pre[now];
					printf("%d ", now);
				}while(now != v);
				exit(0);
			}
		}
	}
	if(!mark[u]) for(auto v : edge[u]) mark[v] = 1;
}
 
int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	lim = sqrt(n);
	while(lim * lim < n) lim ++;
	while(m --)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	pre[1] = 0;
	dfs(1);
	printf("1\n");
	for(int i = 1; lim; i ++)
	{
		if(!mark[i]) 
		{
			printf("%d ", i);
			lim --;
		}
	}
	return 0;
}