Gym 100285G Cipher Message 3

题意

给\(N,M(N,M \le 250000)\)的两个由8位二进制表示的两个序列，允许改变每个数字的第8位的数值（即0→1，1→0），求改变最少次数使得长为\(M\)的序列为长为\(N\)的连续子序列，在次数最少的前提下，找到下标最小的起始位置。

思路

因为只能改变第8位的状态，所以若能匹配的话，前7位数值需要相同，这步通过KMP完成即可。
剩下就是如何快速求每个匹配区间所需要的代价，即找出两个长为\(M\)的序列对应位不同的个数。
考虑位置\(A[i, i + M - 1]\)，若按\(0.. M-1\)对应匹配显然没什么规律，而如果按\(M-1..0\)，则匹配位置的下标和均为\(i+M-1\)，将0和1分开作，用FFT完成计数即可。

#include<cmath>

#include<cstdio>

#include<cstring>

#include<set>

#include<vector>

#include<assert.h>

#include<iostream>

#include<algorithm>

using namespace std;

#define pb push_back

#define mp make_pair

#define sz(x) ((int)(x).size())

#define rep(i,l,r) for(int i=(l);i<(r);++i)

#define setIO(x) freopen(x".in","r", stdin);freopen(x".out","w",stdout);

typedef long long ll;

typedef pair<int, int> pii;

const ll LINF = 1e10 + 7;

const int N = 3e5 + 7;

const int INF = 1e9 + 7;

const int MOD = 1e9 + 7;

const double PI = acos(-1.0);

const double EPS = 1e-8;

//-----------------head-----------------

struct C {

	double r, i;

	C() {

		r = i = 0;

	}

	C(double _r, double _i) {

		r = _r, i = _i;

	}

	C operator+(const C &p) const {

		return C(r + p.r, i + p.i);

	}

	C operator-(const C &p) const {

		return C(r - p.r, i - p.i);

	}

	C operator*(const C &p) const {

		return C(r * p.r - i * p.i, r * p.i + i * p.r);

	}

} A[N * 2], B[N * 2];

int n, m, a[N], b[N], p[N], s[2][N];

void fft(C x[], int n, int rev) {

	int i, j, k, t;

	for (i = 1; i < n; ++i) {

		for (j = 0, k = n >> 1, t = i; k; k >>= 1, t >>= 1)

			j = j << 1 | (t & 1);

		if (i < j)

			swap(x[i], x[j]);

	}

	for (int s = 2, ds = 1; s <= n; ds = s, s <<= 1) {

		C w = C(1, 0), t;

		C wn = C(cos(2.0 * rev * PI / s), sin(2.0 * rev * PI / s));

		for (k = 0; k < ds; ++k, w = w * wn)

			for (i = k; i < n; i += s) {

				t = w * x[i + ds];

				x[i + ds] = x[i] - t;

				x[i] = x[i] + t;

			}

	}

	if (rev == -1)

		for (i = 0; i < n; ++i)

			x[i].r /= n;

}

int read() {

	int x = 0;

	char ch = getchar();

	while (ch != '0' && ch != '1')

		ch = getchar();

	while (ch == '0' || ch == '1') {

		x = (x << 1) | (ch - '0');

		ch = getchar();

	}

	return x;

}

void solve() {

	int L = 1;

	while (L < n + m)

		L <<= 1;

	rep(w, 0, 2)

	{

		rep(i, 0, n)

			A[i] = C((a[i] & 1) == w, 0);

		rep(i, n, L)

			A[i] = C(0, 0);

		rep(i, 0, m)

			B[m - i - 1] = C((b[i] & 1) == w, 0);

		rep(i, m, L)

			B[i] = C(0, 0);

		fft(A, L, 1), fft(B, L, 1);

		rep(i, 0, L)

			A[i] = A[i] * B[i];

		fft(A, L, -1);

		rep(i, 0, n)

			s[w][i] = A[i].r + EPS;

	}

	rep(i, 0, n)

		a[i] >>= 1;

	rep(i, 0, m)

		b[i] >>= 1;

	p[0] = -1;

	for (int i = 1, j = -1; i < m; ++i) {

		while (j >= 0 && b[j + 1] != b[i])

			j = p[j];

		j += b[j + 1] == b[i];

		p[i] = j;

	}

	pii ans = mp(INF, INF);

	for (int i = 0, j = -1; i < n; ++i) {

		while (j >= 0 && b[j + 1] != a[i])

			j = p[j];

		j += b[j + 1] == a[i];

		if (j == m - 1) {

			pii tmp = mp(m - s[0][i] - s[1][i], i - m + 2);

			ans = min(ans, tmp);

			j = p[j];

		}

	}

	if (ans.first < INF) {

		puts("Yes");

		printf("%d %d\n", ans.first, ans.second);

	} else {

		puts("No");

	}

}

int main() {

	scanf("%d%d", &n, &m);

	rep(i, 0, n)

		a[i] = read();

	rep(i, 0, m)

		b[i] = read();

	solve();

	return 0;

}

巴特西

Gym 100285G Cipher Message 3

题意

思路

最新文章

热门文章