首页 > 其他分享 >Codeforces 871 div4(重拳出击)

Codeforces 871 div4(重拳出击)

时间:2023-05-07 10:11:37浏览次数:49  
标签:tmp cnt int void Codeforces dfs 871 flag div4

Codeforces 871 div4

ABC

简单题

D

题意

每次操作可以将当前的数分成两份,一份是\(\frac{1}{3}\),一份是\(\frac{2}{3}\),问当前数n可否进行若干次操作,最终出现一份大小为m的片。递归一下就好了,数据最大才\(10^7\)

代码

void dfs(int x) 
{	
	if(x==m) {flag=1;return;}
	if(flag) return;//找到了就不用再递归了
	if(x%3) return;
	dfs(x/3*2);
	dfs(x/3);
}

void solve()
{	
	flag=0;
	cin>>n>>m;
	if(n<m) {cout<<"NO\n";return;}
	if(n==m){cout<<"YES\n";return;}
	if(n%3) {cout<<"NO\n";return;}
	flag=0;
	dfs(n);
	if(flag) {cout<<"YES\n";}
	else cout<<"NO\n";
}

E (FloodFill)

题意

经典dfs了

代码

int n,m,k;
int ans,tmp;
int a[1100][1100];
bool vis[1100][1100];
int flag=0;

int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int sum=0;//能遍历到的点的总和
void dfs(int x,int y) 
{
	for(int i=0;i<4;i++) 
	{
		int nx=x+dx[i],ny=y+dy[i];
		if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]&&!vis[nx][ny]) 
		{
			vis[nx][ny]=1;
			sum+=a[nx][ny];
			dfs(nx,ny);
		}
	}
}

void solve()
{	
	cin>>n>>m;
	ans=0;
	for(int i=1;i<=n;i++) 
	{
		for(int j=1;j<=m;j++) cin>>a[i][j],vis[i][j]=0;
	}
	for(int i=1;i<=n;i++) 
	{
		for(int j=1;j<=m;j++) 
		{
			if(!vis[i][j]&&a[i][j]) 
			{	
				vis[i][j]=1;
				sum=a[i][j];
				dfs(i,j);
				ans=max(ans,sum);
			}
		}
	}
	cout<<ans<<endl;
}

F

题意

题目给出一个雪花图,从根节点延伸出x个子节点,每个子节点又延伸出y个子节点

思路

先扫一遍树统计一下每个点的子节点个数,然后再扫一遍遍历就ok了。注意x和y都大于1

代码

int n,m,k;
int ans,tmp;
int h[N],e[N*2],ne[N*2],idx;
int cnt[N],cnt1[N];
int x=-1,y=-1;
void add(int a,int b) 
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}

void dfs(int u,int fa) 
{
	cnt[u]=1;
	for(int i=h[u];i!=-1;i=ne[i]) 
	{
		int j=e[i];
		if(j==fa) continue;
		dfs(j,u);
		cnt[u]+=cnt[j];
	}
}

void dfs1(int u,int fa) 
{		
	if(x>1) return;//找到直接返回
	int tmp=-1,flag=1;
	if(u==1) //特判根节点,因为它没有父节点,不用考虑父亲的那棵树的情况
	{
		for(int i=h[u];i!=-1;i=ne[i]) 
		{
			int j=e[i];
			if(j==fa) continue;
			if(tmp==-1) tmp=cnt[j];
			if(tmp!=cnt[j]) {flag=0;break;}
		}
	}
	else 
	{	
		tmp=n-cnt[u];//父亲那颗树的大小
		for(int i=h[u];i!=-1;i=ne[i]) 
		{
			int j=e[i];
			if(j==fa) continue;
			if(tmp!=cnt[j]) {flag=0;break;}
		}
	}

	if(flag==1) 
	{
		int c1=0;
		for(int i=h[u];i!=-1;i=ne[i]) 
		{
			c1++;
		}
		if(c1>1) x=c1,y=(n-c1-1)/x;
	}
	for(int i=h[u];i!=-1;i=ne[i]) 
	{
		int j=e[i];
		if(j==fa) continue;
		dfs1(j,u);
	}

}

void solve() 
{
	memset(h,-1,sizeof(h));
	idx=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cnt[i]=0,cnt1[i]=0;
	for(int i=1;i<=m;i++) 
	{
		int a,b;
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	if(n==2) {cout<<1<<" "<<0<<endl;return;}
	dfs(1,-1);
	x=-1,y=-1;
	dfs1(1,-1);
	cout<<x<<" "<<y<<endl;
}

G

题意

一个金字塔,然后把某个块搞垮,与它上表面接触的块也会搞垮,依次类推,问搞垮某个块,垮掉的块的总贡献是多少。块n的贡献为\(n^2\)

思路

一开始想的很复杂,又分左右情况去讨论,记忆化搜索好像又不可行。后来想着暴力,过啦。
暴力思路:用个f数组记录每个数的位置。

代码

int f[2010][2010],g[2010][2010];
void init() 
{	
	int x=1;
	for(int i=1;i<=2000;i++) 
	{
		for(int j=1;j<=i;j++) 
		{
			f[i][j]=x*x;
			x++;
		}
	}
}

int x,y;

void get(int n) 
{
	x=1;
	while(n>x) n-=x,x++;
	y=n;
}

void solve() 
{
	cin>>n;
	get(n);//获取n的位置
	int ans=0;
	int k=1;
	while(x) 
	{	
		for(int i=max(0ll,y-k+1);i<=y;i++) ans+=f[x][i];
		x--,k++;
	}
	cout<<ans<<endl;
}

H(补)

题意

给了一个长度为n的数组,问有多少个不为空的子数组,它们的与的结果是只有k个1.

思路

dp。设状态\(f[i][j]\)为前i个数能构成结果j的方案。
转移方程:
\(f(i,j\&a[i])=f(i-1,j\&a[i])+f[j]+(j==a[i])\)

代码

int n,m,k;
int ans,tmp;
int a[N],f[64];

void solve() 
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) 
	{
		cin>>a[i];
	}
	for(int i=0;i<64;i++) f[i]=0;
	for(int i=1;i<=n;i++)
	{	
		for(int j=0;j<=63;j++) //j&a[i]<=j,正着来
		{	
			f[j&a[i]] = (f[j&a[i]]+f[j]%mod)%mod;
			if(j==a[i]) f[j]=(f[j]+1)%mod;
		}
	}
	int ans=0;
	for(int i=0;i<64;i++) 
	{
		int cnt=0;
		for(int j=0;j<=6;j++) if((i>>j)&1) cnt++;
		if(cnt==m) ans=(ans+f[i])%mod;
	}
	cout<<ans<<endl;
}

标签:tmp,cnt,int,void,Codeforces,dfs,871,flag,div4
From: https://www.cnblogs.com/LIang2003/p/17378933.html

相关文章

  • Codeforces Round 870 (Div. 2)
    CodeforcesRound870(Div.2)A-TrustNobody思路:枚举每一种说谎人数x,若a[i]大于x则说谎人数加一,判断最后说谎总人数是否为x,若是则输出x,结束枚举;若没有满足的x则-1#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>PII;typedefpair<string,int>PSI;......
  • Codeforces 1817F - Entangled Substrings(SA)
    为什么赛时不开串串题?为什么赛时不开串串题?为什么赛时不开串串题?为什么赛时不开串串题?为什么赛时不开串串题?一种SA做法,本质上和SAM做法等价,但是说来也丢人,一般要用到SAM的题我都是拿SA过的/wul考虑将\(ac\)看作一个整体。记\(\text{occ}(S)\)为\(S\)出现位置的集......
  • Codeforces Round 848 (Div. 2)C
    B.TheForbiddenPermutation一定要注意题目中说的是对于alli满足才算不好的,我们做的时候只要破坏一个i这个a就不算好的了,被这一点坑了,没注意到all。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;constintN=2e5+10;intp[N],a[N];vo......
  • Codeforces Round 856 (Div. 2)C
    C.ScoringSubsequences思路:我们想要找到满足的最大值的长度最长的的区间,因为单调不减,所以更大的数一定在最大值的里面包含,所以我们用两个指针维护这样一个满足当前i的最大值区间,当新来一个数,这时我们答案里面一定要包含这个数,我们看能否保持这个长度,能不能保持需要看j指针所指......
  • Codeforces——870
    A.TrustNobody题目大意给你一个长度为\(n\)的数组\(a\),\(a\)中每个元素\(a_i\)表示当前人认为\(n\)个人中至少有\(a_i\)个人说谎,让你找出说谎的人的个数。思路:枚举说谎人数\(x\),遍历\(a\)数组,对于当前\(a_i\),如果有\(a_i\geqx\),那么显然第\(i\)个人在说谎,记录人数看是否等......
  • [CodeForces-143A]题解(C++)
    PartIPreface原题目(Luogu)原题目(CodeForces)PartIISketch设有一个\(2\times2\)的棋盘,上面可以填入\(1-9\)的数字。给出\(6\)个数字,为每行每列以及每个对角线上的数字之和,求相应的摆放方式,无解输出\(-1\)。PartIIIAnalysis观察此题数据规模,不难发现数据......
  • [CodeForces-1104A]题解(C++)
    PartIPreface原题目(Luogu)原题目(CodeForces)PartIISketch给定一个整数\(n\)。将\(n\)拆分成一个数列\(a_1,a_2,a_3,\dots,a_m\)。使得\(\sum\limits_{k=1}^{m}a_k=n\),每个\(a_i\in[0,9]\)且数列中不相同的数的数量尽量少。PartIIIAnalysis我们很容易......
  • [CodeForces-545A]题解(C++)
    PartIPreface原题目(Luogu)原题目(CodeForces)PartIISketch给定一个正整数\(n\),表示汽车数量。给定一个\(n\timesn\)阶矩阵\(A\),第\(i\)行\(j\)列上的数字表示\(i\)车与\(j\)车的对撞情况。\(\begin{aligned}\begin{cases}A_{i,j}=-1&i,j\text{车没......
  • [CodeForces-545A]题解(C++)
    PartIPreface原题目(Luogu)原题目(CodeForces)PartIISketch给定一个正整数\(n\),表示汽车数量。给定一个\(n\timesn\)阶矩阵\(A\),第\(i\)行\(j\)列上的数字表示\(i\)车与\(j\)车的对撞情况。\(\begin{aligned}\begin{cases}A_{i,j}=-1&i,j\text{车没......
  • Educational Codeforces Round 147 (Rated for Div. 2) (贪心)
    原题链接:https://codeforces.com/contest/1821/problem/D*题意:从1开始走,走的给定区间的值要k次。且shift按了要松开,代表走了一个区间除了往右的次数,还要多两次按shift的次数,求最小次数。*思路:1.先把不可能的情况列出来,就是给出的区间大小小于k时直接输出-12.我的思路是暴......