AGC019D - Shift and Flip

很久之前$WA$的題，終于補掉了。。。這題細節(jié)是真的煩。

Solution

這題數(shù)據(jù)范圍較小，于是我們枚舉最終$A$與$B$的哪一個字符開始匹配，設(shè)這個位置為$S$。

然后考慮分順時針/逆時針轉(zhuǎn)到$S$兩種情況討論。
以逆時針為例，我們可以求出轉(zhuǎn)到$S$之后哪些位置需要$01$反轉(zhuǎn)，并且容易預(yù)處理出這些位置需要向左幾步才能接觸過$B$中的$1$，向右同理（因為只要轉(zhuǎn)的過程中遇到一次$B$的$1$，相當(dāng)于這個位置就可以任意進行操作$3$了）。

將這兩個值記作$(L_i,R_i)$，我們將所有這樣的二元組按$R$降序排列，枚舉逆時針(向右轉(zhuǎn))的步數(shù)，就可以同時統(tǒng)計出向左需要走的步數(shù)，貢獻即為：向左的步數(shù)$?2$+向右超出$S$的步數(shù)$?2$+$S$+需要改變的數(shù)的個數(shù)。

時間復(fù)雜度$O(n^{2}lgn)$，可以通過計數(shù)排序或者左右端點的單調(diào)性優(yōu)化成$O(n^2)$，但沒必要。

Code

#include <bits/stdc++.h>using 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; }#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 secondtypedef 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-9; const lod pi = acos(-1); const int mods = 1e9 + 7; const int oo = 1 << 30; const ll loo = 1ll << 62; const int MAXN = 4005; 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; }PR a[MAXN]; char s1[MAXN], s2[MAXN]; int L[MAXN], R[MAXN]; signed main() { #ifndef ONLINE_JUDGEfreopen("a.in", "r", stdin);freopen("a.out", "w", stdout); #endifscanf("%s", s1);scanf("%s", s2);int n = strlen(s1), flag = 0;for (int i = 0; i < n ; ++ i) flag |= (s2[i] == '1');if (!flag) {int Flag = 0;for (int i = 0; i < n ; ++ i) Flag |= (s1[i] != s2[i]);puts(Flag ? "-1" : "0");return 0;}for (int i = 0, nw; i < n ; ++ i) {nw = i;while (s2[nw] != '1') nw = (nw == 0 ? n - 1 : nw - 1), ++ L[i]; nw = i;while (s2[nw] != '1') nw = (nw == n - 1 ? 0 : nw + 1), ++ R[i]; }int ans = INF;for (int S = 0; S < n ; ++ S) {int num = 1; a[1] = MP(0, 0);for (int i = 0; i < n ; ++ i) if (s1[i] != s2[(i + S) % n]) a[++ num] = MP(L[i], R[i]);sort(a + 1, a + num + 1, [&](PR x, PR y) { return x.se > y.se; });for (int i = 1, mx = 0; i <= num ; ++ i) {upmin(ans, mx * 2 + max(a[i].se - S, 0) * 2 + S + num - 1);upmax(mx, a[i].fi);}sort(a + 1, a + num + 1, [&](PR x, PR y) { return x.fi > y.fi; });for (int i = 1, mx = 0; i <= num ; ++ i) {upmin(ans, max(a[i].fi - (n - S), 0) * 2 + (n - S) + mx * 2 + num - 1);upmax(mx, a[i].se);}}printf("%d\n", ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的AGC019D - Shift and Flip(枚举)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。