首页 > 其他分享 >Codeforces Round 876 (Div. 2) A-D

Codeforces Round 876 (Div. 2) A-D

时间:2023-06-07 18:35:56浏览次数:47  
标签:题意 876 个数 Codeforces int 序列 Div dp size

比赛地址

A.The Good Array

题意:定义一个数组是good的要求有:

从左往右所有的i,前i个数中至少有[i/k]个数是1

从右往左所有的i,前i个数中至少有[i/k]个数是1

问good数组对于n而言最少需要多少个1

Solution

先从左往右填1,直到满足第一个条件,然后从右往左填1,直到满足第二个条件

void solve()
{
	int n,k;cin>>n>>k;
	for(int i=1;i<=n;i++)a[i]=0;
	for(int i=1;i<=n;i++)
	{
		if(i%k==1)a[i]=1;
	}
	int s=0;
	for(int i=n;i>=1;i--)
	{
		int z=n-i+1;
		if(a[i]==1)s++;
		if((z+k-1)/k>s)
		{
			a[i]=1;
			s++;
		}
	}
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]==1)sum++;
	}
	cout<<sum<<"\n";
}

B.Lamps

题意:有一些灯,一开始都是关闭的,它们各有值a[i]和b[i],开启第i个灯会获得b[i]的分数,如果当前的有k个灯开着,则所有a[i]<=k的灯会立马毁掉,坏的灯无法开启,也不被视为开启,如何点灯会使得获得的点数最大

Solution

排两个优先队列,一个存剩下的灯,一个存开启的灯,剩下的灯里面把a[i]小的并且b[i]更大的放在前面,开启的灯把a[i]小的放在前面,每次点灯后判断一下即可

struct node
{
	int x,y;
	bool operator <(const node &t)const&{
		if(x!=t.x)return x > t.x;
		return y < t.y;
	}
};
 
 
void solve()
{
	int n;cin>>n;
	priority_queue<node>q;
	
	priority_queue<pii,vector<pii>,greater<pii> >p;
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		int a,b;cin>>a>>b;
		q.push({a,b});
	}
	int ans=0;
	while(q.size())
	{
		node t=q.top();
		q.pop();
		p.push({t.x,t.y});
		int z=p.size();
		ans+=t.y;
		while(p.size()&&p.size()>=p.top().first)p.pop();
		while(q.size()&&z>=q.top().x)q.pop();
	}
	cout<<ans<<"\n";
}

C.Insert Zero and Invert Prefix

题意:有一串01序列a,现在你有一个空的序列b,每次可以选一个位置加入0,这个位置左边的数会异或上1,右边不变,构造一系列操作使得a=b

Solution

我们可以发现,每一串1后面必须跟上一个0,不然就无法变为a,所以不成立的条件仅为a[n]为1的情况,其它情况必有解,那么我们可以每次在位置1加0,然后在这串0的右边加一个0,这样就会使得左边的0全变为1,而右边不变

void solve()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	if(a[n]!=0)
	{
		cout<<"NO\n";
		return;
	}
	int pos=n;
	int op=0;
	int cnt=0;
	while(pos>=0)
	{
		if(pos==0||a[pos]==0)
		{
			for(int i=1;i<=cnt;i++)
			{
				ans[++op]=0;
			}
			if(cnt!=0)ans[++op]=cnt;
			else if(pos!=n)ans[++op]=0;
			cnt=0;
		}else
		{
			cnt++;
		}
		pos--;
	}
	cout<<"YES\n";
	for(int i=1;i<=op;i++)
	{
		cout<<ans[i]<<" ";
	}
	cout<<"\n";
}

D.Ball Sorting

题意:给一个由[1...n]组成的序列,对于k=1,2,...,n,可以使用k个0,将其插入序列后,0的相邻数字可以调整到任意位置,这样的调整操作可以进行无数次,结束操作后所有0都会消失,问对于每一个k,最少需要多少次操作才能使得序列变为升序

Solution

这里是要找最大上升子序列,假设一条上升子序列可以把原序列分为k块,那么一个合法的答案就是n-len(子序列)

这里用dp处理出所有的情况

令dp[i][j]表示为以第i个数结尾,把前i个数分为j块的最长上升子序列的最大长度

转移方程为

dp[i][j]=dp[i-1][j]+1(当a[i]>a[i-1]时)

dp[i][j]=dp[k][j-1]+1(当a[i]>a[k]时)

void solve()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	memset(dp,-1,sizeof(dp));
	dp[0][0]=0;
	
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=(i+1)/2;j++)
		{
			if(a[i]>a[i-1]&&dp[i-1][j]!=-1)dp[i][j]=max(dp[i][j],dp[i-1][j]+1);
			if(j>0)
			{
				for(int k=0;k<i-1;k++)if(a[k]<a[i]&&dp[k][j-1]!=-1)dp[i][j]=max(dp[i][j],dp[k][j-1]+1);
			}
		}
	}
	
	
	int last=dp[n][0];
	for(int k=1;k<=n;k++)
	{
		int ans=0;
		for(int i=1;i<n;i++)
		{
			ans=max(ans,dp[i][k-1]);

		}
		ans=max(ans,dp[n][k]);
		ans=max(ans,last);
		last=ans;
		cout<<n-ans<<" ";
	}
	cout<<"\n";
}

标签:题意,876,个数,Codeforces,int,序列,Div,dp,size
From: https://www.cnblogs.com/HikariFears/p/17464217.html

相关文章

  • div元素自适应屏幕大小
    简单介绍一下实现方式(结尾处有代码)1.首先创建一个根元素,将这个跟元素宽高设置为100%,当然,用100vw、100vh也可以,并且将根元素设置为相对定位。2.再创建我们要实现自适应大小的元素,自适应元素我们要给固定的宽高。可以按照常见的屏幕分辨率赋值,1920*1080或者2560*1440。(注:至于为什......
  • ACM-CodeForces-#685(Div.2)
    A.SubtractorDivide#include<iostream>usingnamespacestd;intmain(){ intT,n; cin>>T; while(T--) { cin>>n; if(n<=3) n--; else n=2+(n&1); cout<<n<<endl; } return0;}B.Non-SubstringSubsequence#in......
  • Codeforces 1566G - Four Vertices(线段树分治)
    交了整整2页,本来想用随机化卡过去的,后来发现我的实现跑得太慢就写正常做法了。首先发现最优答案对应的四个点只可能有以下两种可能:\(a,b\)间有边,\(c,d\)间有边,此时答案是\(a,b\)边权值加\(c,d\)边权值。\(a\)与\(b,c,d\)三个点间都有边,此时答案是三条边权值之和。......
  • Codeforces 1801D The way home
    看到shortestpaths来做的。首先有一个贪心的策略,对于当前点\(u\)若不能直接往后走则肯定是选择经过的点中\(w_i\)最大的加。很好理解,证明就不需要了。所以可以定义状态\(f_{u,mx}\)为\(u\)点最大能加的值为\(h_{mx}\)的最优状态,\(h\)是\(w\)离散化后的数组。......
  • Codeforces 1588F - Jumping Through the Array
    显然无法用polylog的数据结构维护,序列分块也不行,考虑询问分块。每\(B\)个询问处理一次。将这个询问中\(2,3\)操作涉及到的点设为“关键点”,那么容易发现,环上每一段以关键点结尾的链在这块操作的过程中始终保持不变,也就是说我们可以把它们缩在一起。先预处理出每个块的增量......
  • Codeforces 1495F - Squares
    不知道怎么放到div1F的,感觉没啥亮点。首先对于一条\(1\)到\(n+1\)的路径而言,它经过的点的编号一定是递增的,也就是说,如果我们将关键点大小排个序,那么答案就是相邻两点间最短路的和。删/加点造成的变化是\(O(1)\)的,所以问题等价于,多次询问这张图中\(x,y\)之间最短路的......
  • Codeforces Round 876 (Div. 2)
    PrefaceDP腐乳闪总出列!(本来以为大掉分的一把,但这个号因为挺新的所以竟然还能上挺多分的,压线完成了5场上紫)早知道去做E题了,感觉CF真得要看题目相性,有些题目就是一眼感觉不适合自己的说A.TheGoodArray一个要动点脑子的签到题,因为\(a_1,a_n\)必须等于\(1\),然后中间的\(n-1\)......
  • Codeforces Round 876 (Div. 2)题解
    CodeforcesRound876(Div.2)A.TheGoodArray标签greedymath题意对于任意\(i\in\{1,2,\dots,n\}\),要求数列\(a\)满足前\(i\)个元素中至少有\(\lceil\frac{i}{k}\rceil\)个元素为\(1\),后\(i\)个元素中至少有\(\lceil\frac{i}{k}\rceil\)个元素为\(1\)。思......
  • 2023.5 codeforces 杂题选做
    2023.5codeforces杂题选做E.Location\(n\le5\times10^4\)的范围,并且区间赋值、区间维护最值,可以考虑分块。然后对于散块的修改可以直接暴力,对于整块,由于\(b_i\)值不变,\(a_i\)值只有一个,思考如何快速求。由于\(\dfrac{\operatorname{lcm}(a_i,b_i)}{\gcd(a_i,b_i)}=\d......
  • 【LGR-141-Div.2】洛谷 6 月月赛 I (前两题)
    T1:金盏花传送门直接暴力枚举前6位的值即可,记得开longlong#include<bits/stdc++.h>usingnamespacestd;#defineintlonglonginty,z,ans=1e18;signedmain(){ scanf("%lld%lld",&y,&z); for(inti=100000;i<=999999;i++){ intx=i*1000000+y; ans=min......