首页 > 其他分享 > AtCoder Beginner Contest 278

AtCoder Beginner Contest 278

时间：2022-11-21 20:01:59浏览次数：51  
标签：AtCoder CI const Beginner int 278 include RI define

Preface

刚打完就来写题解，热乎的很

这周CF没Div2，Atcoder的ARC和微积分考试撞了打不了

所以和ztc一起打一下Div3和ABC，顺便锻炼一波解释题目的能力

做到G的时候还有30min的，然后码了个暴力找到了结论但是不知道怎么实践可交互的方案，遂跑路

话说ABC后面题目难度这么大的吗，那个Ex题是不是放AK的呀（笑）

A - Shift

SB题

#include<cstdio>
#define RI register int
#define CI const int&
using namespace std;
const int N=105;
int n,k,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%d",&n,&k),i=1;i<=n;++i) scanf("%d",&a[i]);
	if (k>=n)
	{
		for (i=1;i<=n;++i) printf("%d ",0);
	} else
	{
		for (i=k+1;i<=n;++i) printf("%d ",a[i]);
		for (i=1;i<=k;++i) printf("%d ",0);
	}
	return 0;
}

B - Misjudge the Time

刚开始题意看错+没考虑跑到第二天的情况WA了一发，还好Mechine提醒我不然可以又要被搞得心态爆炸了

直接大力往后枚举时间即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int H,M,A,B,C,D;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	scanf("%d%d",&H,&M); for (;;)
	{
		A=H/10; B=H%10; C=M/10; D=M%10; swap(B,C);
		int _H=A*10+B,_M=C*10+D;
		if (_H>=0&&_H<=23&&_M>=0&&_M<=59)
		{
			printf("%d %d\n",H,M); break;
		}
		if (++M>59) M=0,++H; if (H>23) H=0;
	}
	return 0;
}

C - FF

大力模拟题意即可，注意map的正确使用

#include<cstdio>
#include<map>
#define RI register int
#define CI const int&
using namespace std;
const int N=400005;
int n,q,opt,x,y,tot; map <int,int> id,rls[N];
inline int ID(CI x)
{
	if (!id.count(x)) id[x]=++tot; return id[x];
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%d",&n,&q),i=1;i<=q;++i)
	{
		scanf("%d%d%d",&opt,&x,&y); x=ID(x); y=ID(y);
		switch (opt)
		{
			case 1:
				rls[y][x]=1; break;
			case 2:
				rls[y][x]=2; break;
			case 3:
				puts(rls[x][y]==1&&rls[y][x]==1?"Yes":"No"); break;
		}
	}
	return 0;
}

D - All Assign Point Add

我们注意到修改只有全体赋值和单点加

不妨在每次全体赋值的时候用标记记下此时全局的值，然后对于每个点额外维护一个增量值

每次全体赋值的时候把增量数组清空即可，复杂度\(O(Q)\)

#include<cstdio>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,q,opt,x,y,a[N],cov,stk[N],top,dlt[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%lld",&n),i=1;i<=n;++i)
	scanf("%lld",&a[i]),stk[++top]=i,dlt[i]=a[i];
	for (scanf("%lld",&q),i=1;i<=q;++i)
	{
		scanf("%lld",&opt); switch (opt)
		{
			case 1:
				scanf("%lld",&cov); while (top) dlt[stk[top--]]=0; break;
			case 2:
				scanf("%lld%lld",&x,&y); dlt[x]+=y; stk[++top]=x; break;
			case 3:
				scanf("%lld",&x); printf("%lld\n",cov+dlt[x]); break;
		}
	}
	return 0;
}

E - Grid Filling

经典的数颜色，但是一些小细节挺搞的

考虑每次向右移动黑块时，变化的点数是\(O(h)\)级别的，因此可以直接暴力维护，总复杂度\(O(N^3)\)

#include<cstdio>
#define RI register int
#define CI const int&
using namespace std;
const int N=305;
int n,m,s,h,w,c[N],ret,a[N][N],ans[N][N];
inline void add(CI x)
{
	if (!c[x]) ++ret; ++c[x];
}
inline void del(CI x)
{
	if (c[x]==1) --ret; --c[x];
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k; for (scanf("%d%d%d%d%d",&n,&m,&s,&h,&w),i=1;i<=n;++i)
	for (j=1;j<=m;++j) scanf("%d",&a[i][j]);
	for (k=1;k<=n-h+1;++k) 
	{
		for (i=1;i<=s;++i) c[i]=0; ret=0;
		for (i=1;i<=n;++i) for (j=1;j<=m;++j) add(a[i][j]);
		for (i=0;i<h;++i) for (j=1;j<=w;++j) del(a[k+i][j]);
		for (ans[k][1]=ret,i=2;i<=m-w+1;++i)
		{
			for (j=0;j<h;++j) add(a[k+j][i-1]);
			for (j=0;j<h;++j) del(a[k+j][i+w-1]);
			ans[k][i]=ret;
		}
	}
	for (i=1;i<=n-h+1;++i) for (j=1;j<=m-w+1;++j)
	printf("%d%c",ans[i][j]," \n"[j==m-w+1]);
	return 0;
}

F - Shiritori

刚开始以为是某个经典的图上博弈问题，后来看到数据范围才发现直接暴力就好了

设\(f_{s,lst}\)表示状压后用过的串的集合为\(s\)，上一个用的串是\(lst\)时，该局面是必胜态还是必败态

转移的话就是枚举所有后继状态，若存在一个必败态则该点为必胜态，否则为必败态

#include<cstdio>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=16;
int n,len[N],f[1<<N][N]; char s[N][15]; bool g[N][N];
inline int DP(CI st,CI lst)
{
	if (~f[st][lst]) return f[st][lst];
	for (RI i=0;i<n;++i) if (!((st>>i)&1)&&g[lst][i])
	if (!DP(st|(1<<i),i)) return f[st][lst]=1;
	return f[st][lst]=0;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d",&n),i=0;i<n;++i)
	scanf("%s",s[i]+1),len[i]=strlen(s[i]+1);
	for (i=0;i<n;++i) for (j=0;j<n;++j) if (i!=j) g[i][j]=s[i][len[i]]==s[j][1];
	for (memset(f,-1,sizeof(f)),i=0;i<n;++i)
	if (!DP(1<<i,i)) return puts("First"),0;
	return puts("Second"),0;
}

G - Generalized Subtraction Game

很有颠覆性的一道交互题，属于是让我惊呼：woc，博弈论还能这么出！

首先经过之前的多次CF和AT的经验，我知道凭我的脑子是想不出什么策略的，因此先上来码个暴力找找规律：

#include<cstdio>
#include<cstring>
#include<windows.h>
#define RI register int
#define CI const int&
using namespace std;
const int N=10;
int n,l,r; bool a[N];
inline bool DFS(void)
{
	for (RI i=1,j,k;i<=n-l+1;++i)
	{
		bool flag=1; for (j=0;j<l&&flag;++j) if (!a[i+j]) flag=0;
		if (!flag) continue; for (j=0;j<l;++j) a[i+j]=0;
		if (!DFS())
		{
			for (j=0;j<l;++j) a[i+j]=1; return 1;
		}
		for (j=l;j<r&&i+j<=n&&flag;++j)
		if (!a[i+j])
		{
			for (k=0;k<j;++k) a[i+k]=1; flag=0;
		}
		else
		{
			a[i+j]=0; if (!DFS())
			{
				for (k=0;k<=j;++k) a[i+k]=1; return 1;
			}
		}
		if (flag) for (j=0;j<r;++j) a[i+j]=1;
	}
	return 0;
}
int main()
{
	scanf("%d%d%d",&n,&l,&r); for (RI i=1;i<=n;++i) a[i]=1;
	puts(DFS()?"First":"Second"); return Sleep(1000),0;
}

（妈的这个暴力还有点难写，浪费我20min没时间写正解了）

大致跑了一下发现绝大部分情况都是先手胜，仅有的后手胜的都是\(l=r\)的情况

然后和ztc扯皮着就结束了，今天早上顺着区间长度不为\(1\)先手必胜这个结论一想就豁然开朗了

首先在博弈论中一种很重要的构造必胜策略的方法就是利用镜像法则，即把初始局面变成某种对称情况，然后模仿对手的操作

这样若对方能操作则自己必定能操作，可以立于不败之地

因此这里我们就很容易想出，把\([1,n]\)这个大区间中间挖走一块，使得剩下两个区间的长度相等

这样我们只要模仿对面的操作即可，不难发现当\(l<r\or 2|(n-l)\)时我们都可以这样构造

那么仅考虑剩余的一种\(l=r\and 2\nmid (n-l)\)的情形即可，不难发现由于此时每个人每次能取的数量唯一，因此可以用SG函数

考虑对于每个长度求出SG函数，则一个局面的SG函数就是其每一段的SG函数的异或和

这样若初始状态SG函数不为\(0\)，则我们选择先手，然后枚举在哪个位置执行操作可以使得SG函数为\(0\)

否则我们选择后手，在对方操作后把SG函数变回\(0\)即可

重复上述操作即可得胜

#include<cstdio>
#include<set>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
int n,l,r;
namespace Mirror
{
	inline void solve(void)
	{
		int len=l+((n&1)!=(l&1)),pos=(n-len)/2+1;
		printf("First\n%d %d\n",pos,len); fflush(stdout);
		for (;;)
		{
			int x,y; scanf("%d%d",&x,&y); if (x==0||x==-1) break;
			if (x<pos) printf("%d %d\n",x+len+pos-1,y);
			else printf("%d %d\n",x-len-pos+1,y); fflush(stdout); 
		}
	}
};
namespace SG
{
	#define mp make_pair
	const int N=2005;
	typedef pair <int,int> pi;
	int sg[N],cur; bool vis[N]; set <pi> s;
	inline int findpos(void)
	{
		for (auto it:s)
		{
			int L=it.first,R=it.second; for (RI i=L;i+l-1<=R;++i)
			if (!(cur^sg[R-L+1]^sg[i-L]^sg[R-(i+l-1)])) return i;
		}
		return 0;
	}
	inline void remove(CI pos,CI len)
	{
		for (auto it:s)
		{
			int L=it.first,R=it.second;	if (L<=pos&&pos+len-1<=R)
			{
				cur^=sg[R-L+1]^sg[pos-L]^sg[R-(pos+len-1)];
				if (L<=pos-1) s.insert(mp(L,pos-1));
				if (pos+len<=R) s.insert(mp(pos+len,R));
				s.erase(it); break;
			}
		}
	}
	inline void solve(void)
	{
		RI i,j; for (i=1;i<=n;++i)
		{
			for (memset(vis,0,sizeof(vis)),j=1;j+l-1<=i;++j)
			vis[sg[j-1]^sg[i-(j+l-1)]]=1;
			int mex=0; while (vis[mex]) ++mex; sg[i]=mex;
		}
		s.insert(mp(1,n)); cur=sg[n];
		if (!cur) printf("Second\n"),fflush(stdout); else
		{
			int pos=findpos(); printf("First\n%d %d\n",pos,l);
			fflush(stdout); remove(pos,l);
		}
		for (;;)
		{
			int x,y; scanf("%d%d",&x,&y); if (x==0||x==-1) break;
			remove(x,y); int pos=findpos();
			printf("%d %d\n",pos,l); fflush(stdout); remove(pos,l);
		}
	}
};
int main()
{
	scanf("%d%d%d",&n,&l,&r);
	if (r>l||(n&1)==(l&1)) Mirror::solve(); else SG::solve();
	return 0;
}

Postscript

Ex看起来很仙的样子直接跑路

话说今天写博客的时候发现昨天的ARC我报了名然而去考微积分了，点都没点进去给我扣了好多分，这场直接白打

呃就很离谱，我收回我比赛时对Atcoder的无限赞誉（夸奖它样例给的多，基本交上去不会挂）

标签：AtCoder,CI,const,Beginner,int,278,include,RI,define
From： https://www.cnblogs.com/cjjsb/p/16912999.html

相关文章

  • AtCoder Regular Contest 152 (A-D)
    根本不知道有ARC。然后unratedregister。然后一直在聊天，只写了A。难蚌。按照pog的说法，这场应该不看题直接写代码！！1这样才能写的飞快。摆了一上午。我好像一直在贺题，所以......
  • AtCoder Beginner Contest 278-F
    F-Shiritori题解：n最大16，所以可以状态压缩，相当于n个点的带权有向图。dp[i][j]表示当前状态为i，j结尾的情况，其中dp[i][j]=1表示First赢,0为second赢，如果一个字符串s[i]，第......
  • ABC278 整合题解
    AA题，送分题。link。思路数据范围很小，其实直接模拟也是可以通过的。不过我们很容易想到\(O(n)\)的算法。对于前\(k\)个数，不输出，其他数正常输出。然后再在末尾......
  • ABC278F 题解
    前言题目传送门！或许更好的阅读体验？博弈论，状压，记忆化搜索。思路看到很小的\(n\)，容易联想到状压、搜索。本题就是状压加搜索。设状态\(x\)的每一位表示：如果第\(i\)......
  • ABC278D 题解
    前言题目传送门！更好的阅读体验？难度加强版：P1253。思路很容易想到线段树。维护\(cov_i\)表示覆盖的懒标记。单点加与单点查都非常简单。全局覆盖只需要给每一层都打......
  • AtCoder Beignner Contest 278
    D给定一个长度为\(n\)的序列，有如下三种操作：把所有的数全部修改为\(x\)把第\(i\)个数加\(x\)输出第\(i\)个数的值不难发现，每次一操作会覆盖之前的所有操作，所......
  • 「NOIP赛前冲刺」ABC278F
    Solution简单状态压缩，考虑设\(f_{S,i}\)表示状态为\(S\)并且当前要求一个开头为\(s_i\)的结尾字符的单词，\(\text{First}\)如果能赢为\(0\)，否则为\(1\)。那么很......
  • AtCoder Beginner Contest 278
    A-Shift原题链接题意给定一个有\(n\)个整数的数组\(a\)，要求进行以下\(k\)次操作，输出操作后的数组。操作为：将第一个数去掉，在队尾加上一个\(0\)。分析依题意模......
  • AtCoder Beginner Contest 278
    A-Shift(abc278a)题目大意给定一个有\(n\)个整数的数组\(a\)，要求进行以下\(k\)次操作，输出操作后的数组。操作为：将第一个数去掉，在队尾加上一个\(0\)。解题思路模......
  • AtCoder Regular Contest 150补题
    AtCoderRegularContest150A.Continuous1知识点：简单题复杂度：\(O(n)\)当一个区间合法，那么必定区间长度为k，并且区间内无0，并且1的个数等于所有的1的总和这个使用个......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99