基于.net平台网站内容管理系统研究与实现,企业网站建设需要多少钱,wordpress首页加音乐,广西建设厅网站行业网AGC011D - Half Reflector
Solution
先考虑改变一次。 我们令LLL表示往左走的球#xff0c;RRR表示往右走的球#xff0c;xxx表示任意种类的球#xff0c;(−x)(-x)(−x)表示与xxx相反种类的球。 当球处于ARAARAARA的状态#xff08;即有一个向右的球在两个AAA机器人之间…AGC011D - Half Reflector
Solution
先考虑改变一次。 我们令LLL表示往左走的球RRR表示往右走的球xxx表示任意种类的球(−x)(-x)(−x)表示与xxx相反种类的球。 当球处于ARAARAARA的状态即有一个向右的球在两个AAA机器人之间时状态会这样改变ARA→ALB→BRB→BARARA\to ALB\to BRB \to BARARA→ALB→BRB→BAR。 当球处于ARBARBARB的状态ARB→AARARB\to AARARB→AAR。
观察这两种变化可以得到下列信息
按此过程进行时做完一个ARxARxARx之后会变成(−x)AR(-x)AR(−x)AR然后RRR的位置后推一个单位。进行一次该过程会让RRR前面的球的种类变成RRR后面一个球的种类当RRR前面有一个AAA之后后面的所有状态RRR前面都是AAA。也就是如果某一时刻能做了这个过程能一直做直到RRR在最末尾。结束之后最末尾是AAA。
因此倘若初始时第一个球是AAA那么我们必然不能进行该过程则把它改成BBB。 否则会把前面连续一段BBB变成AAA状态变成AAA...RAxx...xAAA...RAxx...xAAA...RAxx...x的形式然后开始做上面的过程从RRR左边的AAA开始的每个球变成它后面一个球的种类取反这个过程相当于循环左移一个单位再整体取反。
于是我们可以维护一个revrevrev表示全局翻转的次数用类似队列的东西O(k)O(k)O(k)做了。
然后这题还有一个性质 最多2n2n2n次之后序列会循环变化这个循环大小为111或222。 每整体循环位移一次之后都会在末尾加一个AAA而每次循环位移之前的整体取反会让之前的AAA变成BBB因此最多2n2n2n次之后会变成xBABABAxBABABAxBABABA的形式。
因此我们做min(k,2n(kmod2))min(k,2n(k\;mod\;2))min(k,2n(kmod2))次操作得到的序列就是答案了。
时间复杂度O(k)O(k)O(k)
Code
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods998244353;
const int MAXN600005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
char st[MAXN];
int flag[MAXN];
signed main()
{int nread(),kread(),tmin(k,n*2(k1)),nw1,rev0;scanf(%s,st1);for (int i1;in;i) flag[i]st[i]-A;for (int i1;it;i){if (flag[nw]^rev) rev^1,flag[nwn]flag[nw],nw; else flag[nw]^1;}for (int inw;inwn-1;i) putchar((flag[i]^rev)A);return 0;
}
