首页 > 其他分享 >CF 158 (Rated for Div

CF 158 (Rated for Div

时间:2023-11-26 15:01:06浏览次数:45  
标签:Rated cout int 158 ll cin ans Div 题意

CF-158

这次比赛较上次也是有进步,成功地多AC了一道题。但第4题也是很遗憾只差一点了。

A. Line Trip

题意:车在数轴上从$0$点到达$x$点又返回$0$点,有$k$点的油,可以走$k$个单位,在数轴上$a_1,a_2,a_3...a_n$处可以加油到$k$点,$0$点处和$x$点处无法加油,问$k$的最小值。

思路:那么根据题意我们可以很好地考虑出$k$的最小值,即两个加油点之间的距离的最大值,所以$k=max(a_1-0,a_2-a_1,...,a_n-a_{n-1}))$,同时我们还要记得考虑从$a_n$点到$x$点又返回$a_n$点的距离$2*(x-a_n)$。

代码如下:

#include<bits/stdc++.h>
using namespace std;
const int N=1e2+2;
int t;
int n,x;
int a[N];
int ans;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--)
	{
		ans=0;
		cin>>n>>x;
		for(int i=1;i<=n;i++) cin>>a[i],ans=max(ans,a[i]-a[i-1]);
		ans=max(2*(x-a[n]),ans);
		cout<<ans<<endl;
	}
	return 0;
}

B. Chip and Ribbon

题意:芯片从$1$点到$n$点,有两种移动方式:

  • 从$i$点到$(i+1)$点
  • 随意到$1$至$n$的任意一点且耗费$1$次转移次数

芯片每到一点该点的标量加$1$,求使得$1$至$n$点的值变成$a_1,a_2...a_n$的最小转移次数为多少?

思路:我们可以容易得到在一段单调递减的数列中最小的转移次数是第一个值减去$1$。那么在连续的两段单调递减的数列中第一段的答案仍一样,而第二段的答案则为其第一个值减去前一个值,两者相加得到答案。如果碰到$0$则将加上记录的值。

那么我们可以推出答案为每段单调递减的数列的答案之和。

得到代码:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
typedef long long ll;
int t;
int n,c[N];
ll ans;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--)
	{
		ans=0;
		cin>>n;
		for(int i=1;i<=n;i++) cin>>c[i];
		c[n+1]=0;//记录答案
		ll s=0;
		for(int i=1;i<=n+1;i++)
		{
			if(!c[i]) ans+=s,s=0;
			else if(c[i]>c[i-1])
				s+=c[i]-c[i-1];
		}
		cout<<ans-1<<endl;
	}
	return 0;
}

C. Add, Divide and Floor

题意:给定一个数列$a_1,a_2...a_n$,对每一个数进行一次操作:将$a_i$改为$\lfloor \frac{a_i+x}{2}\rfloor$($0 \le x \le 10^{18}$)。求最少次数$k$使得数列的每一个数都相等,且若$k \le n$,则输出$x$的数列。

思路:由于除以$2$,所以$x$只与就相关,也就只考虑$1$与$0$即可。再考虑$a_i$的奇偶性:

  • 若$a_i$为奇数,$x$为$1$时,$a_i$变为$\lfloor \frac{a_i}{2} \rfloor+1 $, $x$为$0$时,$a_i$变为$\lfloor \frac{a_i}{2} \rfloor$。
  • 若$a_i$为偶数,不管$x$为$1$还是$0$,$a_i$都变为$\frac{a_i}{2}$。

    而对于整个数列我们只需考虑最大值$MX$和最小值$MN$达成一致。那$MX$为奇数则$x=0$,否则再看$MN$,若为奇数则$x=1$,反之则无所谓,假设为$x=0$。由于得到不断除以$2$直到$0$,绝对保证相等,时间复杂度为$O(log(MX))$。

    代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int t,n;
int a[N];
int ans[N];
int mn,mx;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--)
	{
		cin>>n;
		mn=INT_MAX,mx=0;
		for(int i=1;i<=n;i++) cin>>a[i],mn=min(a[i],mn),mx=max(a[i],mx);
		if(mn==mx)
		{
			cout<<0<<endl;//若值都相等,那么直接输出0
			continue;
		}
		int k=0;
		while(mn!=mx)
		{
			if(mx%2)
			{
				ans[++k]=0;
				mx/=2,mn/=2;
			} 
			else if(mn%2)
			{
				ans[++k]=1;
				mx/=2,mn=mn/2+1;
			}
			else
			{
				ans[++k]=0;
				mx/=2,mn/=2;
			}
		}
		cout<<k<<endl;
		if(k<=n)
		{
			for(int i=1;i<=k;i++) cout<<ans[i]<<" ";
			cout<<endl;	
		}
	}
	return 0;
}

D. Yet Another Monster Fight

题意:魔法师瓦夏要击败$n$个怪兽,生命值分别为$a_1,a_2...a_n$,他会挑选一个怪兽攻击,伤害为$k$,若$k>=a_i$,则该怪物被击败,同时会随机攻击已经攻击的怪兽旁边的怪兽,一共攻击$n$次,伤害会递减。瓦夏希望凸显自己的强大,要求伤害最小值能击败所有怪兽。

思路:明显伤害越高,则击败所有怪物的可能性越高,具有单调性,可以考虑二分(到这一步赛上都想到了,可惜接下来的check函数思路错了)。

check()函数可以枚举每一个点作为初始点$i$,再判断是否可行。
由题意知:

  • 若$j<i$,那么最坏情况下$[j+1,n]$的点都要被打倒,那么此时伤害已经递减为$k-n+j$,那么可以被击倒的话则有$a_j \le k-n+j$,即$a_j-j \le k-n$
  • 若$j>i$,那么最坏情况下$[j-1,n]$的点都要被打倒,那么此时伤害已经递减为$k-n+j$,那么可以被击倒的话则有$a_j \le k-j+1$,即$a_j+j \le k+1$

    那么我们可以用数组预处理出$i$点前的$a_j-j$的最大值和$i$点后的$a_j+j$的最大值。

    那么得到代码
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
typedef long long ll;
int n;
ll a[N];
ll pre[N],aft[N];

bool check(ll k)
{
	for(int i=1;i<=n;i++)
	{
		if(a[i]<=k&&pre[i-1]<=(k-n)&&aft[i+1]<=(k+1))
		return true;
	}
	return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
	pre[i]=max(pre[i-1],a[i]-i);
	for(int i=n;i>=1;i--)
	aft[i]=max(aft[i+1],a[i]+i);
	ll l=0,r=1e18;
	ll ans=0;
	while(l<=r)
	{
		ll mid=(l+r)>>1;
		if(check(mid)) r=mid-1,ans=mid;
		else l=mid+1;
	}
	if(check(r))
	ans=min(r,ans);
	cout<<ans;
	return 0;
}

标签:Rated,cout,int,158,ll,cin,ans,Div,题意
From: https://www.cnblogs.com/ljh-hh/p/17857254.html

相关文章

  • How Can South Asia Adapt Integrated River Basin Management to Its Soil Erosion
    Duetotheinstabilityofthemonsoon,floodsanddroughtsarefrequentinSouthAsia,resultinginseveresoilerosion.Everyyear,SouthAsiasuffershugelossesduetosoilerosion,includingpropertydamage,humancasualties,andenvironmentaldamage.......
  • CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
    CodeTONRound7(Div.1+Div.2,Rated,Prizes!)基本情况A题花了快半小时,做出来了但是不如正解。B题又是老毛病,一条路走到黑,爆搜打出来超时就死命想剪枝和记忆化,没想过换方法(觉得贪心不可行)。A-JaggedSwaps我的解法没啥好说的,纯模拟。看到\(n\leq10\)知道能过。......
  • Educational Codeforces Round 158 (Rated for Div. 2)
    EducationalCodeforcesRound158(RatedforDiv.2)基本情况A题很水,几分钟秒了。B题想到一个解,被自己hack掉之后没有重新想,一直想在自己一开始的基础上改好,结果最后B都没拿下。B.ChipandRibbon我的思路其实也是找规律,根本没严谨地证明正确性。不应该一条路走到黑的......
  • HTML <div> 和<span>
    HTML <div>和<span>HTML可以通过<div>和<span>将元素组合起来。HTML区块元素大多数HTML元素被定义为块级元素或内联元素。块级元素在浏览器显示时,通常会以新行来开始(和结束)。实例:<h1>,<p>,<ul>,<table>HTML内联元素内联元素在显示时通常不会以新行开始。......
  • Educational Codeforces Round 158 补题(A~D)
    A.思路找出最大耗油的路程即可ac代码#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;consti64inf=8e18;typedefpair<int,int>pii;voidsolve(){intn,x;cin>>n>>x;std::vector<int>v(n);f......
  • Educational Codeforces Round 158 (Rated for Div. 2)
    A.LineTrip题意是:有n个加油点,人要来回两趟,问你最少要多少油?usingnamespacestd;inta[100];voidsolve(){ intn,m; cin>>n>>m; for(inti=1;i<=n;i++)cin>>a[i]; intans=a[1]; for(inti=2;i<=n;i++){ ans=max(ans,a[i]-a[i-1]); } ans=max(ans,2*(m-......
  • Educational Codeforces Round 158 (Rated for Div. 2) A-C
    A大致题意:有一条长度为x的直线公路,最开始你位于0号点并且此时你的油箱装满了油,公路有n个加油站,当你经过加油站的时候你可以在加油站加满油,每走一个单位需要花费1升油量,起始位置和终点没有加油站,请问你的油箱容量至少为多少升才可以够你跑一个来回。解题思路:我们的路径大致是......
  • Codeforces Round 905 (Div. 3)
    CodeforcesRound905(Div.3)A.Morning题意:操作:显示,向前走都为一次操作;目标:显示这四个数思路:0->10,然后依次作差就行#include<bits/stdc++.h>usingnamespacestd;voidsolve(){chara[4];intmi=100,sum=4,b[4];for(inti=0;i<4;i++){cin>>a[i]......
  • Codeforces Round 903 (Div. 3)
    CodeforcesRound903(Div.3)A.Don'tTrytoCount大概题意给你两个字符串a,b。a串可进行的操作为将整个a串复制到之前的a串后面(直接用a+a即可),然后看操作多少次可以让b串变为a串的子串如果不能就输出-1。#include<iostream>usingnamespacestd;stringa,b;voidsolve()......
  • Codeforces Round 910 (Div. 2)
    CodeforcesRound910(Div.2)A.MilicaandString解题思路:统计给定字符串\(s\)中的\(B\)的数量,记录为\(cnt\)。如果\(cnt==k\):输出0;如果\(cnt<k\):从左往右数,将第\(cnt-k\)个\(A\)的位置前的数全部变成\(B\).如果\(cnt>k\):从左往右数,将第\(k-cnt\)个\(B\)的......