AGC011D - Half Reflector

Solution

先考慮改變一次。
我們令$L$表示往左走的球，$R$表示往右走的球，$x$表示任意種類的球，$(?x)$表示與$x$相反種類的球。

• 當球處于$ARA$的狀態（即有一個向右的球在兩個$A$機器人之間）時，狀態會這樣改變：$ARA\to ALB\to BRB\to BAR$。

• 當球處于$ARB$的狀態，$ARB\to AAR$。

觀察這兩種變化，可以得到下列信息：

• 按此過程進行時，做完一個$ARx$之后會變成$(?x)AR$，然后$R$的位置后推一個單位。
• 進行一次該過程會讓$R$前面的球的種類變成$R$后面一個球的種類
• 當$R$前面有一個$A$之后，后面的所有狀態$R$前面都是$A$。也就是如果某一時刻能做了，這個過程能一直做直到$R$在最末尾。
• 結束之后最末尾是$A$。

因此倘若初始時第一個球是$A$，那么我們必然不能進行該過程，則把它改成$B$。
否則會把前面連續一段$B$變成$A$，狀態變成$AAA...RAxx...x$的形式，然后開始做上面的過程，從$R$左邊的$A$開始的每個球變成它后面一個球的種類取反，這個過程相當于循環左移一個單位再整體取反。

于是我們可以維護一個$rev$表示全局翻轉的次數，用類似隊列的東西$O(k)$做了。

然后這題還有一個性質：
最多$2n$次之后，序列會循環變化，這個循環大小為$1$或$2$。
每整體循環位移一次之后，都會在末尾加一個$A$，而每次循環位移之前的整體取反會讓之前的$A$變成$B$因此最多$2n$次之后，會變成$xBABABA$的形式。

因此我們做$min(k,2n+(kmod2))$次操作得到的序列就是答案了。

時間復雜度$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;template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; } template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }typedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int,int> PR; typedef vector<int> VI;const lod eps=1e-11; const lod pi=acos(-1); const int oo=1<<30; const ll loo=1ll<<62; const int mods=998244353; const int MAXN=600005; const int INF=0x3f3f3f3f;//1061109567 /*--------------------------------------------------------------------*/ inline int read() {int f=1,x=0; char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }return x*f; } char st[MAXN]; int flag[MAXN]; signed main() {int n=read(),k=read(),t=min(k,n*2+(k&1)),nw=1,rev=0;scanf("%s",st+1);for (int i=1;i<=n;i++) flag[i]=st[i]-'A';for (int i=1;i<=t;i++){if (flag[nw]^rev) rev^=1,flag[nw+n]=flag[nw],nw++; else flag[nw]^=1;}for (int i=nw;i<=nw+n-1;i++) putchar((flag[i]^rev)+'A');return 0; }

總結

以上是生活随笔為你收集整理的AGC011D - Half Reflector(模拟)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。