首页 > 其他分享 >CF contest 1909 Pinely Round 3 (Div. 1 + Div. 2) 题解（Vanilla的掉分赛）

CF contest 1909 Pinely Round 3 (Div. 1 + Div. 2) 题解（Vanilla的掉分赛）

时间：2023-12-24 15:34:05浏览次数：51  
标签：contest int 题解 LL leq 端点 区间 Div

CF contest 1909 Pinely Round 3 (Div. 1 + Div. 2) Vanilla的掉分赛

绪言

Pinely Round 3 (Div. 1 + Div. 2) - Codeforces

\[\color{purple}\large\textbf{世界上只有一种真正的英雄主义，} \]

\[\color{red}\large\textbf{就是认清了生活的真相后还依然热爱它。} \]

\[\color{gray}\large\texttt{ ——罗曼·罗兰} \]

A Distinct Buttons

Problem

本来可以朝着上下左右移动，以依次（随便什么顺序）到达所有给定的坐标点。但是现在方向遥控器坏了，只能朝着三个方向移动了，请问现在是否还能到达所有给定的坐标点

Solution

只能朝着三个方向移动，也就是不能朝着某一个方向移动，并且这个方向是我们自选的。

假如不能往上走，那么还有整个第三第四象限可以走的（当然还包括x轴、y轴负半轴和坐标原点）；同理，如果所有点都出现在某个坐标轴的一侧的话，那么砍去一个方向依然还是能够全部走到的。

alt

Code


int t;
int n;
int point[2000][2];
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=0;i<n;i++)
		{
			cin>>point[i][0]>>point[i][1];
		}
		
		bool flag=1;
		for(int i=0;i<n;i++)
		{
			if(point[i][0]<0) flag=0; 
		}
		if(flag)
		{
			cout<<"YES"<<endl;
			continue;
		}
		
		flag=1;
		for(int i=0;i<n;i++)
		{
			if(point[i][1]<0) flag=0; 
		}
		if(flag)
		{
			cout<<"YES"<<endl;
			continue;
		}
		
		flag=1;
		for(int i=0;i<n;i++)
		{
			if(point[i][0]>0) flag=0; 
		}
		if(flag)
		{
			cout<<"YES"<<endl;
			continue;
		}
		
		flag=1;
		for(int i=0;i<n;i++)
		{
			if(point[i][1]>0) flag=0; 
		}
		if(flag)
		{
			cout<<"YES"<<endl;
			continue;
		}
		cout<<"NO"<<endl;
	}	
	return 0;
}

Attention

注意考虑坐标轴和原点，所以直接用大于小于号判断是否在禁区中即可。

B Make Almost Equal With Mod

Problem

给一个长度为n的数列a，任意找到一个k使得将a全部模上k之后的数列中只有两种数（正好两种）

  • 500组数据
  • \(n \leq 100,1 \leq a_i \leq {10}^{17},k \leq {10}^{18}\)

Solution

偏向于构造题一点？

可以试试当\(k=2\)的时候，显然a中只会有0或者1两种数字。但是也可能会出现只有一种数的情况，比如当a全为偶数时，取模之后就全是0了。

这里以\(k=2\)时\(a_i\%k=0\)为例，\(a_i\%4\)只会有两种可能性：0或者2，所以我们考虑把k放宽到4.

但是这样依然有可能只有一种数（比如恰好\(a_i\%4=0\)的情况）怎么办？那就继续扩大k，直到余数出现了两种为止。

时间复杂度\({O}(tn\mathrm{log}k)\).

Code

#define N 10010
int n,t;
LL a[N];
set<LL>s;
void work()
{
	
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	s.clear();
	for(LL k=2;k<=1000000000000000000ll;k*=2)
	{
		s.clear();
		for(int i=1;i<=n;i++) s.insert(a[i]%k);
		if(s.size()==2) 
		{
			cout<<k<<endl;
			return;
		}
	}
}

Attention

注意数据范围需要开LL

注意数据范围k的上限要开\(10^{18}\)

这里用了set来维护有点小暴力了，这里set最多存两个数，直接用数组就好了

#define N 10010
int n,t;
LL a[N];
vector<LL>s;
void work()
{
	
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	s.clear();
	for(LL k=2;k<=1000000000000000000ll;k*=2)
	{
		s.clear();

		for(int i=1;i<=n;i++) 
		{
			bool flag=1;
			for(unsigned int j=0;j<s.size();j++)
			if(s[j]==a[i]%k)
			{
				flag=0;
				break;
			}
			if(flag)
			{
				s.push_back(a[i]%k);
				if(s.size()>2) continue;
			}
			
		}
		if(s.size()==2) 
		{
			cout<<k<<endl;
			return;
		}
	}
}

C Heavy Intervals

Problem

给定n个区间左端点\(l_i\)和区间右端点\(r_i\)，你可以自由组合左右端点形成区间，但是要保证每个区间都是合法的（\(l_i<r_i\)）

再给n个权重\(c_i\)，可以与n个区间自由组合，这个区间的价值就是\(c_i \times (r_i-l_i)\)

总价值为

\[\sum_{i=1}^n c_i \times (r_i-l_i)\ \]

请重新组合\(l_i,r_i,c_i\)以最小化总价值

  • 10000组数据
  • \(n \leq 10^5,1 \leq l_i,r_i \leq 2\cdot{10}^{5},1\leq c \leq {10}^{7}\)

Solution

首先看乘法部分。由逆序<乱序<顺序可以知道我们要让最小的c乘以最长的区间，最大的c乘以最短的区间。

接下来分配左右端点。对于两对左右端点，有两种情况：

l=1  4
r=  3  6

这种情况由于要保证区间合法（\(l_i<r_i\)），只能1-3+4-6组合

l=1 3
r=   4 6

这种情况既可以1-4+3-6组合，也可以1-6+3-4组合

注意到两端区间长度之和相等，都是\(4-1+6-3=6-1+4-3=6\)，但是分配给两个区间的不一样了。第一种相交式的组合让两个长度更加平均，而第二种包含式的组合让两个区间长度差别更大。

当两段区间长度\(len_1,len_2(len_1<len_2)\)在乘以不同的权重\(c_1,c_2(c_1<c_2)\)时，可以发现：

\[len_1\times c_1+len_2\times c_2<\frac{len_1+len_2}2c_1+\frac{len_1+len_2}2c_2<len_2\times c_1+len_1\times c_2 \]

即让两端区间的长度差别更大，并且与权重c形成逆序，可以得到更小的总价值

于是得出一个选择策略：

从最后一个左端点开始，寻找在其右侧的最靠左的右端点，与之匹配成区间

通过从后往前为左端点匹配，保证在不会抢占其右侧的左端点匹配右端点，同时使得最近的右端点与之匹配

这里使用map记录所有右端点的坐标，使用upper_bound为每个左端点查找最合适的右端点，并且匹配后将被匹配的右端点从map中移除

最后乘以倒序的c再求和，即为最小总价值。

时间复杂度\(O(tn\log n)\).

Code

#define N 1000010
int t;
int n;
LL l[N],r[N],c[N];
bool cmp(LL a,LL b)
{
	return a>b;
}
map<int,int>m;
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=0;i<n;i++) cin>>l[i];
		for(int i=0;i<n;i++) cin>>r[i],m[r[i]]++;
		for(int i=0;i<n;i++) cin>>c[i];
		sort(l,l+n);
		
		sort(c,c+n,cmp);
		
		for(int i=n-1;i>=0;i--)
		{
			if(m.upper_bound(l[i])!=m.end())
			{
				int rr=(*m.upper_bound(l[i])).first;
				m[rr]--;
				if(m[rr]==0) m.erase(rr);
				r[i]=rr-l[i];//这里借用r来存r[i]-l[i]
			}
			
		}
		sort(r,r+n);
		
		
		LL ans=0;
		for(int i=0;i<n;i++)
		{
			ans+=c[i]*(r[i]);
		}
		cout<<ans<<endl;
	}
	return 0;
}

Tips

噢，刚刚写数据范围的时候发现l和r都比较小（\(2\cdot10^5\)）也就是说可以直接开值域数组记录r，可以把map换成别的算法了

求区间最小位置且动态修改——线段树？怎么反而变复杂了呢……我越想越麻烦啊……

看了一眼Tutorial，这不就是括号匹配嘛，直接上堆栈啊！

复习一下：首先将\(l_n\)右侧的\(r_i\)依次放入栈中，栈顶就是最接近\(l_n\)的\(r_i\)了

取出栈顶与\(l_n\)匹配，并出栈

现在为\(l_{n-1}\)匹配：先将\(l_{n-1}\)右侧的\(r_i\)继续入栈，然后取出栈顶与之匹配出栈

继续匹配到\(l_1\)

D Split Plus K

Problem

给定k，将一个长度为n的数列a进行以下操作，用最小的步数使其元素全部相同，若不能则输出-1

  1. 在a中选择一个元素x
  2. 构造一对数\((y,z)\)，满足\(y+z=x+k\)
  3. 用\(y,z\)代替数列a中原本的x

Solution

参考了Tutorial

首先将等式\(x+k=y+z\)变形为\((x-k)=(y-k)+(z-k)\)

这意味着，本来对一个数\(x\)进行操作时，会使得数列a的和发生变化；而如果我们事先将数列a中所有的元素\(x\)都换成\(x'=x-k\)，那么对于\(x'\)操作时，就只需直接将\(x'\)分裂成两个数\(y',z'\)即可.

现在问题简化为：

对于数列\(a'\)，每次选择一个数裂成两个数，用最小的步数使其元素全部相同。

假如将\(a'\)最终分成了p个元素，每个元素都是m，那么也就是说最后一步完成之后，数列\(a'\)会变成p个m

这时候从最后一步往前反推一步，也就是两个m合并为一个2m……继续合并，会发现无论怎么合并，合并出来的数字都是m的倍数，且正负性永远与m相同

这意味着

  • m是所有\(a'_i\)的因子
  • 所有\(a'_i\)同号

所以结论

  • 为了使得步数最少，答案即为最小公倍数\(|m|=\mathrm{gcd}(|a'_i|)\)

  • 若\(a'_i\)不同号或者不皆为0，则无解

  • 若\(a'_i\)皆为0，则m=0，

最小操作次数\(T=p-n=\frac{\sum a'_i}{m}-n\)

时间复杂度\(O(n+\mathrm{log}(\max a_i))\).

Code

#define N 200010
int t;
int n;
LL k;
LL a[N],ans,sum;
bool zheng,fu,zero;


LL gcd(LL x,LL y)
{
	if(y==0) return x;
	return gcd(y,x%y);
}

int main()
{
	t=read();
	while(t--)
	{
		n=read();k=read();zheng=fu=zero=1;sum=0;
		//cout<<"gcd="<<gcd(n,k)<<endl;
		for(int i=0;i<n;i++) a[i]=read()-k,sum+=a[i];
		for(int i=0;i<n;i++)
		{
			if(a[i]>0) fu=zero=0;
			if(a[i]==0) fu=zheng=0;
			if(a[i]<0) zheng=zero=0;
		}
		
		if(zero)
		{
			cout<<"0"<<endl;
		}
		else if(zheng)
		{
			ans=a[0];
			for(int i=1;i<n;i++) ans=gcd(ans,a[i]);
			cout<<sum/ans-n<<endl;
		}
		else if(fu)
		{
			ans=-a[0];sum=-sum;
			for(int i=1;i<n;i++) ans=gcd(ans,-a[i]);
			cout<<sum/ans-n<<endl;
		}
		else cout<<"-1"<<endl;
		
	}
	return 0;
}

标签：contest,int,题解,LL,leq,端点,区间,Div
From： https://www.cnblogs.com/Vanilla-chan/p/17924426.html

相关文章

  • AtCoder Beginner Contest 334题解
    ⭐AtCoderBeginnerContest334前言:比赛题目链接--按照惯例只写了主要部分的代码--特别说明：Rust有一个竞赛用的输入库，并且写ABC是可以用的，但是平时写洛谷是用不了的，所以我自己写了一个cin(),凑活能用，代码见下：读输入函数fncin()->String{letmutinput=String......
  • 【题解】洛谷P1496 火烧赤壁 （离散化）
    P1496火烧赤壁-洛谷|计算机科学教育新生态(luogu.com.cn)我们首先先看数据，n<=20000，数据不多，但是范围大（-10^9<=Ai,Bi<=10^9），这时，就可以用离散化了。但是在这里我们会遇到区间重合的问题（也可以使用区间合并），如下图本题的题意是让我们求出燃烧位置的长度之和。区间重合时只......
  • [ABC265F] Manhattan Cafe 题解
    [ABC265F]ManhattanCafe题解思路解析很有思维难度的一道题。思路是dp，\(f[i][j][k]\)表示已经计算了\(i\)维，距离点\(p\)的距离为\(j\)，距离点\(q\)的距离为\(k\)时的整点\(r\)个数，由此可见我们的每一维都可以从上一维推出来，也即\(f[i][j][k]\)可以由\(f[i-1][j......
  • ABC334 全套题解
    A-ChristmasPresent简单题。voidslv(){ inta=Read<int>(),b=Read<int>(); if(a>b)Puts("Bat"); elsePuts("Glove"); return;}B-ChristmasTrees也是简单题。constexpri128INF=-1e18;i128a,m,l,r;voidslv(......
  • Pinely Round 3 (Div. 1 + Div. 2)
    A构造题，分两种情况考虑上下都行，左右选一个左右都行，上下选一个voidsolve(){ intn; cin>>n; vector<pair<int,int>>a(n); for(auto&t:a)cin>>t.x>>t.y; sort(a.begin(),a.end()); boolokx=a[0].x*a.back().x>=0; for(auto&am......
  • AtCoder Beginner Contest 334 G Christmas Color Grid 2
    洛谷传送门AtCoder传送门考虑相当于把每个标记点的边全部断掉，然后求连通块个数。考虑一条边\((u,v)\)（设\(u<v\)）的出现时间，不难发现是\([1,u-1]\cup[u+1,v-1]\cup[v+1,n]\)。于是考虑直接套线段树分治和可撤销并查集。时空复杂度均为\(O(n^2\logn)\)......
  • 题解 ABC334G【Christmas Color Grid 2】
    先求出初始时绿连通块数量。将一个绿色格子染成红色，会改变绿连通块数量，当且仅当这个绿色格子是孤点或割点。如果是孤点，会使得绿连通块数量减少一；如果是割点，会使得绿连通块数量增加它所在的点双数量减一。根据上述规则可以求出每个绿色格子染红后的绿连通块数量，求平均值即可。时......
  • 题解 ABC334F【Christmas Present 2】
    设\(f_i\)表示假设只有编号为\(1\simi\)的点，此时的答案。\(f_n\)即为所求。显然有：\[f_i=\min\limits_{i-k\lej<i}\{f_j+dis(s\toj+1\toj+2\to\cdots\toi)\}+dis(i\tos)\]当\(i\toi+1\)时，大括号内部全局增加\(dis(i\toi+1)\)，可以全局打标记后单调队列维护。......
  • 题解 ABC334E【Christmas Color Grid 1】
    先求出初始时绿连通块数量。枚举每个红色格子，将其染成绿色本应增加一个绿连通块，但是它每与一个绿连通块相邻，就又会减少一个绿连通块。根据上述规则可以求出每个红色格子染绿后的绿连通块数量，求平均值即可。时间复杂度\(O(nm)\)。//Problem:E-ChristmasColorGrid1//Co......
  • 检查Windows更新问题解决
    在任务栏搜索框输入cmd，点击右侧的“以管理员身份运行”，打开后输入：（建议复制粘贴，防止输入有误出现错误提示等请忽略*）SCconfigwuauservstart=auto回车（Enter按键）SCconfigbitsstart=auto回车（Enter按键）SCconfigcryptsvcstart=auto回车（Enter按键）SCconfigtrustedin......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99