Codeforces Round 914 (Div. 2)A~C

发布时间:2024年01月24日

A
反过来考虑,由皇后和国王的位置去寻找骑士的位置,当一个点既可以被皇后找到,也可以被国王找到时就说明这个点是满足条件的

#include <bits/stdc++.h> 
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 
#define x first
#define y second
using namespace std;

const int N=3e5+10;
int n,m;
int dx[]={0,1,1,-1,-1};
int dy[]={0,1,-1,1,-1};
void solve()
{
	map<PII,int>mp;
	int xk,yk,xq,yq,a,b;cin>>a>>b>>xk>>yk>>xq>>yq;
	rep(i,1,4)
	{
		mp[{xk+dx[i]*a,yk+dy[i]*b}]++;
		if(a!=b)	mp[{xk+dx[i]*b,yk+dy[i]*a}]++;
		mp[{xq+dx[i]*a,yq+dy[i]*b}]++;
		if(a!=b)	mp[{xq+dx[i]*b,yq+dy[i]*a}]++;
	}
	int ans=0;
	for(auto cnt:mp)	if(cnt.y>1)	ans++;
	cout<<ans<<endl;
}

int main()
{
	IOS	
//  	freopen("1.in", "r", stdin);
  	int t;
	cin>>t;
	while(t--)
	solve();
	return 0;
}

B
思路:排序+前缀和
先排序,对于 a [ i ] , 前面的数一定是小于它的一定可以被删除,需要找到后面最远能到达哪里 a[i],前面的数一定是小于它的一定可以被删除,需要找到后面最远能到达哪里 a[i],前面的数一定是小于它的一定可以被删除,需要找到后面最远能到达哪里
假设最远能到达 r ,那么 [ i , r ] 这一段区间中所有数的答案是一样的都是到 r ,如何判断哪里是最远? 假设最远能到达r,那么[i,r]这一段区间中所有数的答案是一样的都是到r,如何判断哪里是最远? 假设最远能到达r,那么[i,r]这一段区间中所有数的答案是一样的都是到r,如何判断哪里是最远?
当 s [ r ] < a [ r + 1 ] 时就说明此时 r 到达了最远 当s[r]<a[r+1]时就说明此时r到达了最远 s[r]<a[r+1]时就说明此时r到达了最远

#include <bits/stdc++.h> 
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 
#define x first
#define y second
using namespace std;

const int N=1e5+10;
ll n,m,a[N],s[N],ans[N];
struct node
{
	int val,pos;
}b[N];

bool cmp(node a, node b)
{
	return a.val<b.val;
}

void solve()
{
	cin>>n;
	rep(i,1,n)	cin>>a[i],b[i].val=a[i],b[i].pos=i;
	sort(b+1,b+1+n,cmp);
	rep(i,1,n)	s[i]=s[i-1]+b[i].val;
	int last=0;
	rep(i,1,n)
	{
		if(last<i)
		{
			last=i;
			while(s[last]>=b[last+1].val&&last+1<=n)	last++;
		}
		ans[b[i].pos]=last-1;
	}
	rep(i,1,n)	cout<<ans[i]<<' ';
	cout<<endl;
	rep(i,1,n)	s[i]=0,ans[i]=0;
}

int main()
{
	IOS	
//  	freopen("1.in", "r", stdin);
  	int t;
	cin>>t;
	while(t--)
	solve();
	return 0;
}

C
思路:
当 k = 1 时 当k=1时 k=1显然可以直接暴力求解, O ( n 2 ) 枚举 O(n^2)枚举 O(n2)枚举
当 k > = 3 时 当k>=3时 k>=3结果显然是0,前两次都选择一样的i、j,后面选择新产生的两个数直接相减为0
当 k = 2 时,对 n 2 个数每个数在排好序的 a 数组上面二分找到最接近的维护最小值就是答案 当k=2时,对n^2个数每个数在排好序的a数组上面二分找到最接近的维护最小值就是答案 k=2时,对n2个数每个数在排好序的a数组上面二分找到最接近的维护最小值就是答案
需要注意一定要和最开始的a取一下最小值,因为答案可能在最初的a中

#include <bits/stdc++.h> 
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 
#define x first
#define y second
using namespace std;

const int N=5e6+10;
ll n,k,a[N],b[N];


void solve()
{
	cin>>n>>k;
	ll ans=1e18;
	rep(i,1,n)	cin>>a[i],ans=min(ans,a[i]);
	if(k>=3)
	{
		cout<<0<<endl;
		return;
	}
	sort(a+1,a+1+n);
	rep(i,2,n)	ans=min(ans,a[i]-a[i-1]);
	if(k==1)
	{
		cout<<ans<<endl;
		return;
	}
	if(k==2)
	{
		rep(i,1,n)	rep(j,i+1,n)
		{
			ll xx=abs(a[j]-a[i]);
			int k=lower_bound(a+1,a+1+n,xx)-a;
			if(k<=n)	ans=min(ans,a[k]-xx);
			if(k>=2)	ans=min(ans,xx-a[k-1]);
		}
		cout<<ans<<endl;
	}
}

int main()
{
	IOS	
//  	freopen("1.in", "r", stdin);
  	int t;
	cin>>t;
	while(t--)
	solve();
	return 0;
}
文章来源:https://blog.csdn.net/weixin_61426225/article/details/135825379
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。