526互联

Codeforces Round 886 (Div. 4)补题

发布时间 2023-07-22 15:09:47作者: 橘赴亦梦人ω

Codeforces Round 886 (Div. 4)

//A:
bool solve(){
	cin>>a[1]>>a[2]>>a[3];
	sort(a+1,a+4);
	return a[2]+a[3]>=10 ? 1:0;
}
//B:
void solve(){
	int n;
	cin>>n;
	int maxa=0;
	int num=0;
	int x,y;
	for(int i=1;i<=n;i++){cin>>x>>y;
		if(x>10) continue;
		else{
			if(y>maxa){ maxa=y;
			num=i;}
		}
	}
	cout<<num<<endl;
}
//C:
void solve(){
	char ch;
	string s;
	s.clear();
	int n=8;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=8;j++){
			cin>>ch;
			if(ch!='.') s+=ch;
		}
	}
	cout<<s<<"\n";
}
//D:
struct node{
	int len,qua;
	int id;
}e[N];
bool cmp(node k,node kk){
	if(k.len!=kk.len) return k.len>kk.len;
	else return k.qua>kk.qua;
}
int a[N];
void solve(){
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	a[n+1]=a[n]+k+2;
	int maxa=1;
	int now=1;
	for(int i=1;i<=n;i++){
		if(a[i+1]-a[i]<=k) {
			now++;
		}
		else{
			 maxa=max(maxa,now);
			 now=1;
		}
	}
	maxa=max(maxa,now);
	cout<<(n-maxa)<<endl;
}

E:

题意：
有n块正方形，已知每一个边长，每一个都会往上下左右方向延申w的长度，最后n个正方形面积刚好为c。
保证w存在，输出w。
思路：
二分w即可。
注意精度的范围。
二分函数：
对于现在的w明显大于c就返回yes,这样一旦爆了最大范围，直接return 1就好。
很好的避免了范围的有关问题。
很多有关的精度方面的问题都可以用这种方式避免。

#define int long long 
const int N=2e5+6;
int n,c;
int a[N];
const int inf=1e18;
int mul(int x,int y){
	if(inf/x<y) return -1;
	else return x*y;
}
bool check(int w){
	int tot=0;
	for(int i=1;i<=n;i++){
		if(a[i]+2*w>1e9) return 1;
		int ans=mul(a[i]+2*w,a[i]+2*w);
		if(ans==-1) return 1;
		if(c-ans<=tot) return 1;//这一句还是很需要的。
		tot+=ans;
	}
	if(tot>=c) return 1;
	return 0;
}
void solve(){
	cin>>n>>c;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int l=0;
	int r=1e9;
	while(l<r){
		int mid=(l+r)>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	cout<<l<<endl;
}

F:

题意：
有n只青蛙有一个自己的跳跃间隔，都从0开始跳跃。
问我们设置一个笼子的前提下，最多捕捉到几只青蛙。
思路：
n只有2e5。
可以对于每一个位置，枚举这个位置所有的因数，看看因数的对应位置一共有几只青蛙即可。
枚举因数用vector桶排就可以

void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		vis[i]=0;
	}
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]<=n) vis[a[i]]++;
	}
	int maxa=0;
	int num=0;
	for(int i=1;i<=n;i++){
		int ans=0;
		for(auto v:p[i]){
			ans+=vis[v];
		}
		if(ans>maxa) {
			maxa=ans;
			num=i;
		}
    }
	cout<<maxa<<endl;
}
signed main()
{	
	for(int i=1;i<=2e5;i++){
		for(int j=i;j<=2e5;j+=i){
			p[j].push_back(i);
		}
	}
	int T;cin>>T;
	while(T--)solve();
	return 0;
}

G:

题意：
一个指南针可以有八个方向：上下左右，上左上右，下左下右。
给出n个坐标，问能够右多少对组合，这两个组合可以判断出上面的某一种方向。
思路：
n是2e5，坐标范围是1e9。

  • 对于上下的情况，直接记录所有的横坐标，有重复的就加到答案里面。
  • 左右同理。
  • \(y=x+b\)的情况：发现如果在一条线上，那么\(y-x\)一定是一个定值，所以记录\(y-x\)的值就可以。
  • \(y=-x+b\)的情况：对y轴做一个对称就是\(y=x+b\)的情况，所以记录\(y+x\)即可。
void solve(){
	mp1.clear();
	mp2.clear();
	mp3.clear();
	mp4.clear();
	int ans=0;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y;
		ans+=2*mp1[x];
		mp1[x]++;
		ans+=2*mp2[y];
		mp2[y]++;
		ans+=2*mp3[x+y];
		mp3[x+y]++;
		ans+=2*mp4[y-x];
		mp4[y-x]++;
	}
	cout<<ans<<endl;
}

H.The Third Letter

题目：
对于n个士兵，给定m种要求，类似于\(loc_{士兵1}-loc_{士兵2}==d\)的情况，问最后可不可以构造出来一种排列。
思路：

  • 可以把所有的m当边建立起来，规定士兵1在0位置，之后跑一边图把每一个士兵的位置找出来，没有冲突就是YES
  • 考虑带权并查集：\(loc_{士兵1}-loc_{士兵2}==d\)把士兵2合并到士兵1的树里面，并用距离更新权值即可。

注意应该在所有的数据都处理完、都输入完毕之后再返回结果，不能在输入的时候发现no就直接结束。(要不然当时1小时就下班了。。。)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int N=2e5+6;
int n,c;
int a[N];
int fa[N],value[N];
int find(int x)
{
	if (x != fa[x])
	{
		int t = fa[x];
		fa[x] = find(fa[x]);
		value[x] += value[t];
	}
	return fa[x];
}
void merge(int x,int y,int s){
    int fx=find(x);
    int fy=find(y);
    fa[fy]=fx;
    value[fy]=(-value[y]+value[x]+s);
}
bool solve(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		fa[i]=i;
		value[i]=0;
	}
	bool ok=1;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		if(z<0) {
			z=abs(z);
			swap(x,y);
		}
		if(find(x)==find(y)){
			if(value[y]-value[x]!=z)  ok=0;
		}
		else {
			merge(x,y,z);
		}
	}
	return ok==0?0:1;
}
signed main()
{	
	int T;
	cin>>T;
	while(T--){
		if(solve()) cout<<"YES\n";
		else cout<<"NO\n";
	}
	return 0;
}