526互联

CF996 Codeforces Round 492 (Div. 2) [Thanks, uDebug!]

发布时间 2023-09-27 22:19:22作者: Zhou_JK

CF996A Hit the Lottery

直接贪心尽可能的分配到 \(k_5\)，剩下的依次分配给 \(k_4,k_3,k_2,k_1\)。

#include<iostream>
#include<cstdio>
using namespace std;
int n;
int k[6];
int main()
{
	scanf("%d",&n);
	k[5]=n/100,n%=100;
	k[4]=n/20,n%=20;
	k[3]=n/10,n%=10;
	k[2]=n/5,n%=5;
	k[1]=n;
	int ans=0;
	for(int i=1;i<=5;i++)
		ans+=k[i];
	printf("%d",ans);
	return 0;
}

CF996B World Cup

算出每个位置会被经过的次数，最小值所在的位置即为答案。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005;
int n;
int a[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		a[i]=(a[i]-i+n)/n;
	int p=min_element(a+1,a+n+1)-a;
	printf("%d",p);
	return 0;
}

CF996C Tesla

贪心的能停到 \(1,4\) 就停，否则在 \(2,3\) 中转圈圈直到可以停为止。

#include<iostream>
#include<cstdio>
#include<tuple>
#include<vector>
using namespace std;
const int N=55;
int n,k;
int s[5][N];
vector<tuple<int,int,int>>res;
bool check()
{
	for(int i=1;i<=n;i++)
		if(s[2][i]||s[3][i]) return false;
	return true;
}
int m;
void moveupdown()
{
	for(int i=1;i<=n;i++)
	{
		if(s[2][i]&&s[2][i]==s[1][i]) res.emplace_back(s[2][i],1,i),m++,s[2][i]=0;
		if(s[3][i]&&s[3][i]==s[4][i]) res.emplace_back(s[3][i],4,i),m++,s[3][i]=0;
	}
	return;
}
void moveleftright()
{
	auto check=[=]()
	{
		for(int i=1;i<=n;i++)
			if(!s[2][i]||!s[3][i]) return false;
		return true;
	};
	if(check())
	{
		printf("-1");
		exit(0);
	}
	int flag=false;
	if(!s[2][1]&&s[3][1]) flag=true,s[2][1]=s[3][1],res.emplace_back(s[3][1],2,1),m++,s[3][1]=0;
	for(int i=2;i<=n;i++)
		if(!s[3][i-1]&&s[3][i]) s[3][i-1]=s[3][i],res.emplace_back(s[3][i],3,i-1),m++,s[3][i]=0;
	if(!s[3][n]&&s[2][n]) s[3][n]=s[2][n],res.emplace_back(s[2][n],3,n),m++,s[2][n]=0;
	for(int i=n-1;i>=2;i--)
		if(!s[2][i+1]&&s[2][i]) s[2][i+1]=s[2][i],res.emplace_back(s[2][i],2,i+1),m++,s[2][i]=0;
	if(!flag)
	{
		if(!s[2][2]&&s[2][1]) s[2][2]=s[2][1],res.emplace_back(s[2][1],2,2),m++,s[2][1]=0;
	}
	return;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=4;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&s[i][j]);
	while(!check())
	{
		moveupdown();
		if(m>20000)
		{
			printf("-1");
			return 0;
		}
		moveleftright();
	}
	printf("%d\n",m);
	for(auto [i,r,c]:res)
		printf("%d %d %d\n",i,r,c);
	return 0;
}

CF996D Suit and Tie

从前往后贪心，每次将所有的相同的位置换到这个位置。因为移到这个位置以后可以减少后面移动的次数。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=205;
int n;
int a[N];
int v[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n*2;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n*2;i++)
		v[i]=1;
	int ans=0;
	for(int i=1;i<=n*2;i++)
	{
		int cnt=0;
		for(int j=i+1;j<=n*2;j++)
			if(a[i]==a[j])
			{
				ans+=cnt;
				v[j]=0;
			}
			else cnt+=v[j];
	}
	printf("%d",ans);
	return 0;
}

CF996E Leaving the Bar

写了乱搞。。。

随机出答案序列，然后如果中间有位置 \(\sqrt{x^2+y^2}> 1.5\cdot 10^6\)，就撤销这次操作换成另一种。

#include<iostream>
#include<cstdio>
#include<random>
#include<ctime>
using namespace std;
const int N=100005;
const long long M=2250000000000;
int n;
pair<int,int>vec[N];
mt19937 myrand(time(NULL));
unsigned int rand(unsigned int l,unsigned int r)
{
	return myrand()%(r-l+1)+l;
}
int val[N];
bool check()
{
	long long x=0,y=0;
	for(int i=1;i<=n;i++)
	{
		x+=val[i]*vec[i].first,y+=val[i]*vec[i].second;
		if(x*x+y*y>M) x-=val[i]*vec[i].first*2,y-=val[i]*vec[i].second*2,val[i]=-val[i];
	}
	return x*x+y*y<=M;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		vec[i]={x,y};
	}
	while(true)
	{
		for(int i=1;i<=n;i++)
			val[i]=myrand()%2==0?-1:1;
		if(check())
		{
			for(int i=1;i<=n;i++)
				printf("%d ",val[i]);
			return 0;
		}
	}
	return 0;
}

CF996F Game

可以发现，每种情况的概率都是相等的。因为 \(A,B\) 是等概率随机的，所以对于一种情况如果 \(A\) 会尽可能到这种情况，则 \(B\) 肯定不会让他到这种情况，所以所有情况的概率都是一样的。然后就完了。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=(1<<18)+5;
int n,r;
int c[N];
int main()
{
	scanf("%d%d",&n,&r);
	for(int i=0;i<(1<<n);i++)
		scanf("%d",&c[i]);
	long long sum=0;
	for(int i=0;i<(1<<n);i++)
		sum+=c[i];
	printf("%.7lf\n",(double)sum/(1<<n));
	while(r--)
	{
		int z,g;
		scanf("%d%d",&z,&g);
		sum-=c[z];
		c[z]=g;
		sum+=c[z];
		printf("%.7lf\n",(double)sum/(1<<n));
	}
	return 0;
}