foreword

ummm... 开始前几个小时被朋友拉来打了这一场，总体海星，题目体验极佳，很符合口味，稍微有点点简单了不知道是不是因为是 New Year Round，很快就打到了 D，但是题目阅读难度有点点大，Alice 和 Bob 永远离不开的博弈论，呼应去年的博弈论。

少有的评测机出锅（也有可能是我打的少），一片 In queue 了大概 40 分钟，加时了以为会继续 Rated，结果又加时又 Unrated 可还行。太久不打有点不熟悉规则，手有点滑，A 题打成了 ... map[i+xd[k]][j+xd[k]] ...，调了十分钟。。还好 pretest 比较给力没有让我 fst。。另外就是 CF 上面的 printf 64 位整数输出用法的提示，%I64d 和 %l64d 傻傻分不清楚，结果 wa on test 1，又因为评测机锅了，过了一个多小时才看到。

总体来说，题目体验很好，这次的平台体验稍差。题目很经典，能学到很多。

A

没啥好说的，\(n^2\) 判一下相邻几个点的值就行了。。

#include<cstdio>

const int MAXN=500+5;

int xd[5]={0,-1,-1,1,1},yd[5]={0,-1,1,-1,1};

int n,cnt;char c[MAXN][MAXN];

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

		scanf("%s",c[i]+1);

	for(int i=1;i<=n;i++)

		for(int j=1;j<=n;j++)

		{

			for(int k=0;k<5;k++)

				if(c[i+xd[k]][j+yd[k]]!='X') goto exit;

			cnt++;

			exit:;

		}

	printf("%d\n",cnt);

	return 0;

}

B

一个硬模拟，均摊 \(O(n)\)。

#include<cstdio>

#include<algorithm>

const int MAXN=100000+5;

typedef long long ll;

struct data{ll price,id;};

int n,m,ptr;data d[MAXN];long long cost,cnt[MAXN],price[MAXN],x,y,tot;

bool comp(data a,data b){return a.price==b.price?a.id<b.id:a.price<b.price;}

int main()

{

	scanf("%d %d",&n,&m);

	for(int i=1;i<=n;i++)

	{

		scanf("%I64d",&cnt[i]);

	}

	for(int i=1;i<=n;i++)

		scanf("%I64d",&price[i]);

	for(int i=1;i<=n;i++)

	{

		d[i].id=i;

		d[i].price=price[i];

		tot+=cnt[i];

	}

	std::sort(d+1,d+n+1,comp);

	ptr=1;long long q;

	for(int i=1;i<=m;i++)

	{

		scanf("%I64d %I64d",&x,&y);

		cost=0;

		if(cnt[x])

		{

			q=std::min(y,cnt[x]);

			y-=q;

			cnt[x]-=q;

			cost=q*price[x];

		}

		while(y&&ptr<=n)

		{

			q=std::min(y,cnt[d[ptr].id]);

			y-=q;

			cnt[d[ptr].id]-=q;

			cost+=q*price[d[ptr].id];

			if(!cnt[d[ptr].id])ptr++;

		}

		if(!y) printf("%I64d\n",cost); else printf("0\n");

	}

	return 0;

}

C

可以说是数学题了，最大配最小总答案最小。

#include<cstdio>

#include<algorithm>

const int MAXN=300000+5;

int n;long long ans,num[MAXN];//org:dp[MAXN][MAXN] len is i, start from j

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

		scanf("%I64d",&num[i]);

	std::sort(num+1,num+n+1);

	for(int i=1,j=n;i<=n/2;i++,j--)

		ans+=(num[i]+num[j])*(num[i]+num[j]);

	printf("%I64d\n",ans);

	return 0;

}

D

因为可以走回去，每次从所有已访问的点中选一个未访问的且能拓展出去的点，且点序号最小的，可以保证字典序最小。

# include<cstdio>

# include<cstring>

# include<algorithm>

# include<queue>

using namespace std;

const int N = 1e5 + 5;

priority_queue <int> q;

int st[N],to[N << 1],nx[N << 1],vis[N];

int n,m,tot;

inline void add(int u,int v)

{

	to[++tot] = v,nx[tot] = st[u],st[u] = tot;

	to[++tot] = u,nx[tot] = st[v],st[v] = tot;

}

int main()

{

	scanf("%d%d",&n,&m);

	for (int i = 1 ; i <= m ; ++i)

	{

		int u,v; scanf("%d%d",&u,&v);

		add(u,v);

	} q.push(-1),vis[1] = 1;

	while (!q.empty())

	{

		int x = -q.top(); q.pop(); printf("%d ",x);

		for (int i = st[x] ; i ; i = nx[i])

		if (!vis[to[i]]) vis[to[i]] = 1,q.push(-to[i]);

	}

	return 0;

}

巴特西

Codeforces #536 A..D 题解

foreword

A

B

C

D

最新文章

热门文章