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;
}