首页 > 其他分享 >Codeforces Round 868 (Div. 2) A-E题解

Codeforces Round 868 (Div. 2) A-E题解

时间:2023-04-28 19:34:02浏览次数:60  
标签:868 连通 题意 int 题解 合数 st Div find

比赛地址

这把真不在状态,麻了,看来还得再练

A. A-characteristic

题意:给出n和k,要求构造只含1和-1数组a,存在k对(i,j)(i≠j),有a[i]*a[j]=1

Solution

令构造的数组有x个1和y个-1,那么其对于答案的贡献有

\[x*(x-1)/2+y*(y-1)/2 \]

又因为有x+y=n,所以可以转化成关于x的一元二次方程

化简后有

\[2x^2-2nx+n^2-2k-n=0 \]

接下来根据求根公式写即可

void solve()
{
	int n,k;cin>>n>>k;
	//x*(x-1)/2+y*(y-1)/2==k
	//x+y=n;
	int t=4*n*n-8*(-n-2*k+n*n);
	if(t<0)
	{
		cout<<"NO\n";
		return;
	}
	int l=sqrt(t);
	if(l*l==t)
	{
		if((2*n-l)%4==0)
		{
			int oo=(2*n-l)/4;
			if(oo>n||oo<0)
			{
				cout<<"NO\n";
				return;
			}
			cout<<"YES\n";
			for(int i=1;i<=oo;i++)cout<<"1 ";
			for(int i=oo+1;i<=n;i++)cout<<"-1 ";
			cout<<"\n";
		}else if((2*n+l)%4==0)
		{
			int oo=(2*n+l)/4;
			if(oo>n||oo<0)
			{
				cout<<"NO\n";
				return;
			}
			cout<<"YES\n";
			for(int i=1;i<=oo;i++)cout<<"1 ";
			for(int i=oo+1;i<=n;i++)cout<<"-1 ";
			cout<<"\n";
		}else
		{
			cout<<"NO\n";
		}
	}else
	{
		cout<<"NO\n";
	}
}

B. Sort with Step

题意:给出长为n且由[1,2,...,n]组成的数组a和一个数c

可以进行无数次操作:选择i和j使得|i-j|=c,交换a[i]和a[j]

可以进行一次且只能进行一次操作:选择任意的i和j,交换a[i]和a[j]

问是否能使得交换后的数组按升序排列

Solution

显然在第i位上的数要满足a[i]%n==i%n,所以直接统计不符合的数的个数,看是否为2,有解的情况必定为2或者0

void solve()
{
	int n,k;cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	int res=0;
	for(int i=1;i<=n;i++)
	{
		if((a[i]%k)!=(i%k))
		{
			res++;
		}
	}
	if(res>2)
	{
		cout<<"-1\n";
	}else if(res==2)
	{
		cout<<"1\n";
		
	}else
	{
		cout<<"0\n";
	}
}

C. Strongly Composite

题意:定义一个合数,其约数中,素数的个数小于或等于合数的个数,这样的合数为强合数,现在给出一个数组a,要求构造出数组b,使得a中元素之积等于b中元素之积,并且b中元素均为强合数,求构造出的数组b的最大长度

Solution

通过找规律可以发现,至少有3个不同的素数或者2个相同的素数的合数是强合数,那么我们可以对a中的所有元素进行分解质因数,然后统计一下成对的素数对数以及不同的素数个数

先全部乘起来再分解质因数居然会t,不理解

void solve()
{
	int nn;cin>>nn;
	map<int,int>mp;
	map<int,int>::iterator it;
	for(int i=1;i<=nn;i++)
	{
		int x;
		cin>>x;
		for(int i=2;i*i<=x;i++)
		{
			if(x%i==0)
			{
				while(x%i==0)
				{
					mp[i]++;
					x/=i;
				}
			}
		
		}
		if(x>1)mp[x]++;
	}
	int ans=0;
	int res=0;
	for(it=mp.begin();it!=mp.end();it++)
	{
		ans+=it->second/2;
		res+=it->second%2;
	}
	cout<<ans+res/3<<"\n";
}

D. Unique Palindromes

题意:构造一个长为n的字符串,给出k个要求,其中第i个要求由s(1,x[i])(s从1开始)组成的字符串有c[i]个不同的回文子串

Solution

k给的比较小,在有要求的时候直接加入连续的下一个字母即可

其他的要求没有回文子串的地方用abcabcabc....这样子填补

void solve()
{
	int n,k;cin>>n>>k;
	for(int i=1;i<=k;i++)cin>>x[i];
	for(int i=1;i<=k;i++)cin>>c[i];
	string s;
	int pos=3;
	int last=0;
	string tp;
	int len=0;
	while(len<n)
	{
		len+=3;
		tp+="abc";
	}
	for(int i=1;i<=k;i++)
	{
		if(i==1&&c[i]<=x[i])
		{
			s="ab";
            s+=string(c[i]-2,'c');
            int z=x[i]-c[i];
            s+=tp.substr(last,z);
            last+=z;
		}
		else if(c[i]>x[i]||c[i]-c[i-1]>x[i]-x[i-1])
		{
			cout<<"NO\n";
			return;
		}else
		{
			int p=x[i]-x[i-1];
			int z=c[i]-c[i-1];
			s+=tp.substr(last,p-z);
			last+=p-z;
			s+=string(z,(char)('a'+pos));
			pos++;
		}
		//cout<<s<<"\n";
	}
	cout<<"YES\n";
	cout<<s<<"\n";
}

E. Removing Graph

题意:给出一个无向图和一个区间[l,r],无重边和自环,其中所有的点度数均为2,Alice和Bob轮流进行以下操作:

选择一个有[l,r]个点连通子图,删去这些点和其所连的边

谁最后无法进行操作谁就输了

Solution

经典nim游戏,但是有坑,因为要选连通子图,把原图可以用并查集找到cnt个连通分量,因为所有点的度数均为2,那么每个连通分量都是一个环,在一次操作完后,原来是环的连通分量会变成一条链状连通分量,而链状连通分量在一次操作完后最多会变成两条链状连通分量

写出对应的sg函数后可以打表找出规律,发现对于i<l和i>l+r-1的sg函数都为0,其余的为i/l向下取整,后面的不用我多说了

debug一下午找不出为什么wa了,才发现要选连通子图.......

sg函数以及打表

int mex(set<int>&st)
{
	for(int i=0;;i++)
	{
		if(st.find(i)==st.end())return i;
	}
}

int sg(int x)
{
	if(x<l)return 0;
	if(dp[x]!=-1)return dp[x];
	set<int>st;
	for(int i=l;i<=r;i++)
	{
		for(int j=0;j<=x-i;j++)
		{
			st.insert(sg(j)^sg(x-i-j));
		}
	}
	dp[x]=mex(st);
	return dp[x];
}
void _table()
{
    for(int i=1;i<=n;i++)
    {
    	set<int>st;
    	for(int j=l;j<=min(i,r);j++)
    	{
    		st.insert(sg(i-j));
    	}
    	cout<<mex(st)<<"\n";
    }
}

AC代码

int t[N];
int p[N];
int find(int x)
{
	return t[x]==x?x:t[x]=find(t[x]);
}
int cnt=0;
int g[N];
int l,r,n;
int dp[N];
int mex(set<int>&st)
{
	for(int i=0;;i++)
	{
		if(st.find(i)==st.end())return i;
	}
}

int sg(int x)
{
	if(x<l)return 0;
	if(dp[x]!=-1)return dp[x];
	set<int>st;
	for(int i=l;i<=r;i++)
	{
		for(int j=0;j<=x-i;j++)
		{
			st.insert(sg(j)^sg(x-i-j));
		}
	}
	dp[x]=mex(st);
	return dp[x];
}

void solve()
{
	memset(dp,-1,sizeof(dp));
	cin>>n>>l>>r;
	for(int i=1;i<=n;i++)
	{
		t[i]=i;
		p[i]=1;
	}
	for(int i=1;i<=n;i++)
	{
		int x,y;cin>>x>>y;
		int a=find(x),b=find(y);
		if(a!=b)
		{
			t[a]=b;
			p[b]+=p[a];
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(t[i]==i)g[++cnt]=p[i];
	}
	int ans=0;
	for(int i=1;i<=cnt;i++)
	{
		int x=g[i]/l;
		if(g[i]<l||g[i]>l+r-1)x=0;
		ans^=x;
	}
	

	if(ans)cout<<"Alice\n";
	else cout<<"Bob\n";
	
    /*for(int i=1;i<=n;i++)
    {
    	set<int>st;
    	for(int j=l;j<=min(i,r);j++)
    	{
    		st.insert(sg(i-j));
    	}
    	cout<<mex(st)<<"\n";
    }*/
}

标签:868,连通,题意,int,题解,合数,st,Div,find
From: https://www.cnblogs.com/HikariFears/p/17362991.html

相关文章

  • COMPSCI 589 问题解答
    COMPSCI589Homework4-Spring2023DueMay6,2023,11:55pmEasternTime1InstructionsThishomeworkassignmentconsistsofaprogrammingportion.Whileyoumaydiscussproblemswithyourpeers,youmustanswerthequestionsonyourownandimplementall......
  • P4681 [THUSC2015]平方运算 题解
    题面链接简要题意给定一个序列,区间.map([](intx){x=x*x%p;});,区间求和。p给定,为小质数。\(N,M\le10^5\)。题解而把一个数看作一个点,向其平方取模连一条边,则最终必然构成一个基环森林,注意到\(P\)很小,每个数经过\(11\)次迭代之后就会进入环中。对于一个区间,如......
  • “makefile:425: *** 遗漏分隔符 。 停止。”问题解决
    在终端下输入make时出现“makefile:2:***遗漏分隔符。停止。”问题,原因是在编写makefile文件时:3:3.c        gcc-o33.cgcc前的是tab分隔符,不能用空格,否则会出现“makefile:2:***遗漏分隔符。停止。”提示。。。make中规定每一Shell命令之前的开头必须使用<t......
  • cf-div.2-868-D
    题目链接:https://codeforces.com/contest/1823/problem/D比赛的时候关键性质已经想到,但没想到怎么正确构造。性质:每次新加一个字母,回文子串的数量最多增加1(因为题目需要不相同的回文子串)。证明:可以用反证法,易证。构造方法:由于k的值很小(只有20),所以对于不再增加(回文子串)的......
  • Codeforces Round 867 (Div. 3)(A~D)
    目录A.TubeTubeFeed题意思路代码B.KarinaandArray题意思路代码C.BunLover题意思路代码D.Super-Permutation题意思路代码A.TubeTubeFeed题意给定时间\(t\),每个视频有一个价值\(b_i\),观看一个视频需要\(a_i\)秒,跳过一个视频需要花费\(1s\),求能观看完的价值最大......
  • 题解(开始学知识点
    D.FrogTraveler1900dpgq!https://codeforces.com/contest/1602/problem/D题解:我们可以通过类似bfs的过程找到每个点的能到达的所需步数最小的点,完成更新,但每个点能被哪些点到达很难判断,故我们反过来考虑,如果我们能得到从n->0的最短跳跃次数,亦得解,而每个点下一步能到达的点容......
  • P1345 [USACO5.4]奶牛的电信Telecowmunication 题解
    一、题目描述:n个点,m条边,给定起点s和终点t,求最少删去几个点后,s和t不连通。注意,s和t不能删掉。1<=n<=100,1<=m<=600; 二、解题思路:刚刚学了最大费用流,知道最大流等于最小割。但此题割的不是边,是点。我们需要将将割点转化为割边。把一个点切成两半......
  • 【题解】P3185 [HNOI2007]分裂游戏
    P3185[HNOI2007]分裂游戏题目描述聪聪和睿睿最近迷上了一款叫做分裂的游戏。该游戏的规则是:共有\(n\)个瓶子,标号为\(0,1,\ldots,n-1\),第\(i\)个瓶子中装有\(p_i\)颗巧克力豆,两个人轮流取豆子,每一轮每人选择\(3\)个瓶子,标号为\(i,j,k\),并要保证\(i\ltj,j......
  • Codeforces Round 867 (Div. 3)
    CodeforcesRound867(Div.3)A-TubeTubeFeed#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>PII;typedefpair<string,int>PSI;constintN=50+5,INF=0x3f3f3f3f,Mod=1e6;constdoubleeps=1e-6;typedeflonglongll;......
  • 【题解】P4363 [九省联考 2018] 一双木棋 chess
    原题链接题目描述菲菲和牛牛在一块\(n\)行\(m\)列的棋盘上下棋,菲菲执黑棋先手,牛牛执白棋后手。棋局开始时,棋盘上没有任何棋子,两人轮流在格子上落子,直到填满棋盘时结束。落子的规则是:一个格子可以落子当且仅当这个格子内没有棋子且这个格子的左侧及上方的所有格子内都有棋......