模板建站按年收费,网站建设成都哪家公司好,试用体验网站,南阳建站公司AGC019D - Shift and Flip
很久之前WAWAWA的题#xff0c;终于补掉了。。。这题细节是真的烦。
Solution
这题数据范围较小#xff0c;于是我们枚举最终AAA与BBB的哪一个字符开始匹配#xff0c;设这个位置为SSS。
然后考虑分顺时针/逆时针转到SSS两种情况讨论。 以逆时…AGC019D - Shift and Flip
很久之前WAWAWA的题终于补掉了。。。这题细节是真的烦。
Solution
这题数据范围较小于是我们枚举最终AAA与BBB的哪一个字符开始匹配设这个位置为SSS。
然后考虑分顺时针/逆时针转到SSS两种情况讨论。 以逆时针为例我们可以求出转到SSS之后哪些位置需要010101反转并且容易预处理出这些位置需要向左几步才能接触过BBB中的111向右同理因为只要转的过程中遇到一次BBB的111相当于这个位置就可以任意进行操作333了。
将这两个值记作(Li,Ri)(L_i, R_i)(Li,Ri)我们将所有这样的二元组按RRR降序排列枚举逆时针(向右转)的步数就可以同时统计出向左需要走的步数贡献即为向左的步数∗2*2∗2向右超出SSS的步数∗2*2∗2SSS需要改变的数的个数。
时间复杂度O(n2lgn)O(n^2lgn)O(n2lgn)可以通过计数排序或者左右端点的单调性优化成O(n2)O(n^2)O(n2)但没必要。
Code
#include bits/stdc.husing namespace std;templatetypename T inline bool upmin(T x, T y) { return y x ? x y, 1 : 0; }
templatetypename 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 pairint, int PR;
typedef vectorint 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;
}
