Codeforces Round #749 (Div. 1 + Div. 2)

A.思维

题意:给你 n n n个正整数,让你选一些数,使得选出来的数的和不是一个素数

问你最多能选多少数?

首先我们可以将所有的偶数凑在一起,因为他们一定会被 2 2 2整除

其次我们还可以加上奇数个奇数,这样最终还是能够被 2 2 2整除

因此,最终答案要不是 n n n,要不是 n − 1 n-1 n−1

n n n的情况即所有的数,只需我们计算所有数的和再验证是否为素数即可

#include<bits/stdc++.h>
using namespace std;
int a[200];
int n;
bool check(int num)
{
	for (int i=2;i*i<=num;++i)if (num%i==0)return true;
	return false;
}
vector<int> ans,res;
int main()
{
	ios::sync_with_stdio(0);
	int T;cin>>T;
	while (T--)
	{
		res.clear();ans.clear();
		cin>>n;
		for (int i=1;i<=n;++i)cin>>a[i];
		int sum = 0;
		for (int i=1;i<=n;++i)
		{
			if (a[i]%2==0)
			{
				ans.push_back(i);
			}else res.push_back(i);
			sum+=a[i];
		}
		if (res.size()%2==0||check(sum))
		{
			cout<<n<<"\n";
			for (int i=1;i<=n;++i)cout<<i<<" ";
		}
		else
		{
			res.pop_back();
			cout<<ans.size()+res.size()<<"\n";
			for (int num:ans)cout<<num<<" ";
			for (int num:res)cout<<num<<" ";
		}cout<<endl;
	}
}

B.构造

题意:要求构造一个 n n n个点的树,给 m m m个限制条件。每个限制条件 a , b , c a,b,c a,b,c,要求点 a a a到点 c c c的路径上不存在 b b b

注意到 1 ≤ m < n 1\le m < n 1≤m<n

则限制条件 a   b   c a\ b\ c a b c中不能经过的 b b b最多只有 n − 1 n-1 n−1个

我们可以找到未被选为 b b b的点作为根,连成一个菊花图。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+100;
bool vis[maxn];
int n,m;
int main()
{
	ios::sync_with_stdio(0);
	int T;cin>>T;
	while (T--)
	{
		cin>>n>>m;
		for (int i=1;i<=n;++i)vis[i]=0;
		for (int i=1,u,v,c;i<=m;++i)
		{
			cin>>u>>v>>c;
			vis[v]=1;
		}
		int root = 1;
		for (int i=1;i<=n;++i)if (vis[i]==0)
		{
			root=i;
			break;
		}
		for (int i=1;i<=n;++i)if (i!=root)
		{
			cout<<i<<" "<<root<<"\n";
		}
	}
}

C.思维

题意:给定一个二维字符矩阵, ′ X ′ 'X' ′X′代表堵截了的点, ′ . ′ '.' ′.′代表空闲的点

一个点可以只能向左、向上走,可以走出矩阵边界的话我们称其可以逃脱 ( ′ X ′ 'X' ′X′的点必然无法逃脱)

每一次查询我们选取连续的列组成新的图形,问当前的堵截方式是否唯一

唯一的定义为:对于当前的堵截方式( ′ X ′ 'X' ′X′的分布),有没有另一种 ′ X ′ 'X' ′X′的的分布,使得每个点能否逃脱的状态不变

题意比较难懂,具体可以参考样例进行理解

其实就是要求我们寻找是否有这样的图形

即,对于一点,其上边的点为 ′ X ′ 'X' ′X′,左边的点也为 ′ X ′ 'X' ′X′。

那么,无论当前点是 ′ X ′ 'X' ′X′还是 ′ . ′ '.' ′.′都是不可能逃脱的

这样的点我们记为 1 1 1

每一次查询 l , r l,r l,r,其实就是询问 [ l + 1 , r ] [l+1,r] [l+1,r]中是否存在 1 1 1

这里我们利用前缀和即可

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+100;
vector<int> G[maxn];
int n,m;
int pre[maxn];
int main()
{
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for (int i=1;i<=n;++i)G[i].resize(m+10);
	for (int i=1;i<=n;++i)for (int j=1;j<=m;++j)
	{
		char ch;cin>>ch;
		if (ch=='X')G[i][j]=1;
		else G[i][j]=0;
	}
	for (int i=2;i<=n;++i)
		for (int j=2;j<=m;++j)
			if (G[i-1][j]==1&&G[i][j-1]==1)pre[j]++;
	for (int i=1;i<=m;++i)pre[i]+=pre[i-1];
	int q;cin>>q;
	while (q--)
	{
		int l,r;cin>>l>>r;
		if (l==r)cout<<"Yes\n";
		else if (pre[r]-pre[l]==0)cout<<"Yes\n";
		else cout<<"No\n";
	}
}

D.构造

现在存在一个长为 n n n的排列 p p p,我们的目标是通过至多 2 n 2n 2n次操作得知 p p p

每次操作如下:构造一个长为 n n n的数列 a a a,保证 1 ≤ a [ i ] ≤ n 1\le a[i]\le n 1≤a[i]≤n

系统会返回一个最小的 i i i,存在 j > i , a [ i ] + p [ i ] = a [ j ] + p [ j ] j>i,a[i]+p[i]=a[j]+p[j] j>i,a[i]+p[i]=a[j]+p[j]

如果不存在 a [ i ] + p [ i ] = a [ j ] + p [ j ] a[i]+p[i]=a[j]+p[j] a[i]+p[i]=a[j]+p[j],那么系统返回 0 0 0

我们的排列 p : 1 , 2 , 3 , 4 , 5 p:1,2,3,4,5 p:1,2,3,4,5

假设我们现在已经知道了 p [ 3 ] = 3 p[3]=3 p[3]=3

那么,我们可以通过 a : 5 , 5 , 3 , 5 , 5 a:5,5,3,5,5 a:5,5,3,5,5

求出 p [ 1 ] = 1 p[1]=1 p[1]=1

同理,我们可以通过 a : 4 , 4 , 3 , 4 , 4 a:4,4,3,4,4 a:4,4,3,4,4

求出 p [ 2 ] = 2 p[2]=2 p[2]=2

但是,我们不能通过 2 , 2 , 3 , 2 , 2 2,2,3,2,2 2,2,3,2,2

求出 p [ 4 ] = 4 p[4]=4 p[4]=4

问题在于 p [ 4 ] p[4] p[4]的索引大于我们事先知道的 p [ 3 ] p[3] p[3]

因此,如果我们事先知道的不是 p [ 3 ] p[3] p[3]而是 p [ 5 ] p[5] p[5],那么就可以通过 n − 1 n-1 n−1次查询明白所有的数字

好了现在关键是如何知道 p [ n ] p[n] p[n]的数字

注意到操作:如果不存在相等的两位,则返回 0 0 0

假设我们的排列 p : 3 , 1 , 2 p:3,1,2 p:3,1,2

第一次我们给出 a : 1 , 1 , 2 a:1,1,2 a:1,1,2,返回 1 1 1

第二次我们给出 a : 1 , 1 , 3 a:1,1,3 a:1,1,3,返回 0 0 0

那么我们就可以肯定 p [ n ] = 2 p[n]=2 p[n]=2

即,我们以 n + 2 n+2 n+2为目标, a [ 1 ] = a [ 2 ] = ⋯ = a [ n − 1 ] = 1 a[1]=a[2]=\dots=a[n-1]=1 a[1]=a[2]=⋯=a[n−1]=1, a [ n ] = n + 2 − p [ n ] a[n]=n+2-p[n] a[n]=n+2−p[n]

这种情况下回复一定是 0 0 0的

因此,我们可以将 a [ n ] a[n] a[n]从 2 2 2一直枚举到 n n n,对应的分别为 n n n到 2 2 2

如果,最终都没有出现 0 0 0的话,那么就是 1 1 1

#include<bits/stdc++.h>
using namespace std;
int a[110];
int n;
int main()
{
	ios::sync_with_stdio(0);
	cin>>n;
	for (int i=1;i<n;++i)
	{
		cout<<"?";
		for (int j=1;j<n;++j)cout<<" 1";
		cout<<" "<<i+1<<endl;
		int id;cin>>id;
		if (id==0)
		{
			a[n] = n+1-i;
			break;
		}
	}if (a[n]==0)a[n]=1;
	for (int i=1;i<=n;++i)if (i!=a[n])
	{
		cout<<"?";
		for (int j=1;j<n;++j)cout<<" "<<n+1-i;
		cout<<" "<<n+1-a[n]<<endl;
		int id;cin>>id;
		a[id]=i;
	}
	cout<<"!";
	for (int i=1;i<=n;++i)cout<<" "<<a[i];
	cout<<endl;
}

E.思维+结论

给一张大小为 n n n的无向联通图,以及 q q q次询问

每次询问 a , b a,b a,b 要求你从 a a a走到 b b b。

不要求走最短路,但是要求不走重复的节点,所经过的边边权都要加一

要求你判断,是否可能 q q q次询问后,所有的边权都为偶数

如果可能,还要求你输出每一次询问走的路径

不可能的话,要求你输出至少还需要多少次询问

首先一个小结论

如果存在一点 u u u,其在所有的询问中出现的次数为奇数

那么一定输出 N O NO NO

证明很简单,对于 u u u来说,每一条路径都必然会经过一条连接 u u u的临近边

如果总路径数为奇数个,那么我们一定无法保证分配给每条临近边一个偶数

而这个结论是充要的

换而言之,只要我们保证每个点在所有询问中出现的次数为偶数次即可

输出方案:首先求出这个图的生成树,然后每一次询问都走生成树的路径

这样可以保证每一条边的权值都为偶数

简单的证明:

我们假设每一个点在查询中出现的次数都为偶数次,然后现在树中有一条边的权值为 1 1 1

经过这条边的路径端点为 ( a , b ) (a,b) (a,b)

那么,我们断开这条边, a , b a,b a,b就被分开了

如果想让每一个点在查询中出现的次数都为偶数次

那么在 a a a所在的集合中,除了 a a a,所有人在查询中应该出现的次数仍然为偶数次

但是, a a a一个人应当出现的次数为奇数次

这是绝对不可能的!

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5+100;
vector<int> G[maxn];
int n,m;
int par[maxn];
int find(int x)
{
	return x==par[x]?x:par[x]=find(par[x]);
}
void merge(int x,int y)
{
	x = find(x);y = find(y);
	par[x]=y;
}
int us[maxn],vs[maxn];
int fa[maxn],dep[maxn];
void dfs(int u,int p)
{
	fa[u]=p;dep[u]=dep[p]+1;
	for (int v:G[u])if (v!=p)dfs(v,u);
}
int du[maxn];
int a[maxn],b[maxn];
int main()
{
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for (int i=1;i<=m;++i)cin>>us[i]>>vs[i];
	int q;cin>>q;
	for (int i=1;i<=q;++i)
	{
		cin>>a[i]>>b[i];
		du[a[i]]++;du[b[i]]++;
	}
	int cnt = 0;
	for (int i=1;i<=n;++i)if (du[i]&1)++cnt;
	if (cnt!=0)
	{
		cout<<"NO\n";
		cout<<cnt/2<<endl;
		return 0;
	}
	for (int i=1;i<=n;++i)par[i]=i;
	for (int i=1;i<=m;++i)
	{
		if (find(us[i])==find(vs[i]))continue;
		merge(us[i],vs[i]);
		G[us[i]].push_back(vs[i]);
		G[vs[i]].push_back(us[i]);
	}
	dfs(1,0);
	cout<<"YES\n";
	for (int i=1;i<=q;++i)
	{
		int u = a[i], v = b[i];
		if (dep[u] < dep[v])swap(u, v);
		vector<int> lf,rg;
		while (dep[u]>dep[v])
		{
			lf.push_back(u);
			u = fa[u];
		}
		while (u!=v)
		{
			lf.push_back(u);
			rg.push_back(v);
			u=fa[u];v=fa[v];
		}lf.push_back(u);
		cout<<lf.size()+rg.size()<<endl;
		if (lf[0]==a[i])
		{
			reverse(rg.begin(),rg.end());
			for (int num:lf)cout<<num<<" ";
			for (int num:rg)cout<<num<<" ";
		}
		else 
		{
			reverse(lf.begin(),lf.end());
			for (int num:rg)cout<<num<<" ";
			for (int num:lf)cout<<num<<" ";
		}cout<<endl;
	}
}

F.思维+分治+构造

给一个长为 n n n的图,点编号从 1 1 1到 n n n

对于任意不同两点 u < v u<v u<v,存在边 u → v u\rightarrow v u→v

对每一条边染色,要求任意一条长度 ≥ k \ge k ≥k的路径,保证边的颜色不唯一

要求使用的颜色数最少

我们要将每一种颜色利用到极致

把 n n n 个点分为 k k k 个连续段

每一段大小为 ⌊ n k ⌋ \lfloor\frac{n}{k}\rfloor ⌊kn​⌋ 或 ⌊ n k ⌋ + 1 \lfloor\frac{n}{k}\rfloor+1 ⌊kn​⌋+1。

然后对于在两个不同段的点,把他们之间的边设为第一种颜色。

这样从任意点开始,最多只能走 k − 1 k-1 k−1 条长度为 1 1 1 的路。

好了,接下来的染色就都不用第一种颜色了

而对于每一个段,都是原问题的一个子问题。

并且我们发现子问题所代表区间之间的点,已经不可能只是一种颜色了(第一种颜色已经不使用了)

每一个子问题彼此之间独立,因此应当尽量平分他们的规模。这样才能保证使用的颜色数最少

直接递归处理,这样最后使用的颜色数是 ⌈ log ⁡ k n ⌉ \lceil\log_k n\rceil ⌈logk​n⌉ 的。

#include<bits/stdc++.h>
using namespace std;
int n,k;
int gra[1100][1100];
void solve(int l,int r,int col)
{
	if (r-l+1<=k)
	{
		for (int i=l;i<=r;++i)for (int j=i+1;j<=r;++j)gra[i][j]=col;
		return;
	}
	int len = (r-l+1)/k;
	int ex = (r-l+1)%k;
	for (int i=l;i<=r;)
	{
		int ql = i;
		int qr = i+len;
		if (ex==0)--qr;
		else --ex;
		solve(ql,qr,col+1);
		for (int j=ql;j<=qr;++j)
			for (int k = qr+1;k<=r;++k)gra[j][k]=col;
		i = qr+1;
	}return;
}
int main()
{
	ios::sync_with_stdio(0);
	cin>>n>>k;
	solve(1,n,1);
	int ans = 0;
	for (int i=1;i<=n;++i)
		for (int j=i+1;j<=n;++j)
			ans = max(ans,gra[i][j]);
	cout<<ans<<endl;
	for (int i=1;i<=n;++i)
		for (int j=i+1;j<=n;++j)
			cout<<gra[i][j]<<" ";
	cout<<endl;
}
上一篇:Codeforces Round #751 (Div. 2) A. Two Subsequences


下一篇:codeforces 282C