URAL - 1996

题意:

URAL - 1996 给两个长度分别为$n, m$的字节串$A,B$,$A$串的最后一位可以修改,代价为$1$,求使得$B$串为$A$串字串的最小代价

Solution :

因为$A$串只有最后最后一位可以修改,所以可以用KMP求出可能匹配的位置,然后计算每个位置的$cost$

记$A$串最后一位构成的串为$a$, $B$串的为$b$, 假设$pos(0\le pos \le n-m)是可能匹配的位置$,如果将$b$反转得到$b’$, 在此处的的代价为

$$ \sum_{i+j=pos+m-1} [a_i \ne b’_j ] $$

$$ \sum_{i+j=posm-1} a_j * b’_j $$

可以算出来相等的$1$的个数$cnt_1$,再将$a,b$串取反,再做一次卷积就可以算出$0$相等的个数$cnt_2$,$ans=m-cnt_1-cnt_2$

#include <cstdio>
#include <stack>
#include <set>
#include <cmath>
#include <map>
#include <time.h>
#include <vector>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <memory.h>
#include <cstdlib>
#include <queue>
#include <iomanip>
#include <unordered_map>
#define P pair<int, int>
#define LL long long
#define LD long double
#define PLL pair<LL, LL>
#define mset(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for (int i = a; i < b; i++)
#define PI acos(-1.0)
#define random(x) rand() % x
#define debug(x) cout << #x << " " << x << "\n"
using namespace std;
const int inf = 0x3f3f3f3f;
const LL __64inf = 0x3f3f3f3f3f3f3f3f;
#ifdef DEBUG
const int MAX = 2e3 + 50;
#else
const int MAX = 1e6 + 50;
#endif
const int mod = 1e9 + 7;

#include <complex>
namespace FFT
{
    int rev[MAX];
    int cnt[MAX];
    void fft(complex<double> *a, int n, int inv){
        int bit = 0;
        while((1 << bit) < n) bit++;
        for(int i = 0; i < n; i++){
            rev[i] = (rev[i>>1]>>1) | ((i & 1)  << (bit-1));
            if(i < rev[i])
                swap(a[i], a[rev[i]]);
        }
        for(int mid = 1; mid < n; mid <<= 1){
            complex<double> wn(cos(PI/mid), inv*sin(PI/mid));
            for(int i = 0; i < n; i += (mid<<1)){
                complex<double> w(1, 0);
                for(int j = 0; j < mid; j++, w *= wn){
                    complex<double> u = a[i+j], t = w * a[i+j+mid];
                    a[i+j] = u+t, a[i+j+mid] = u-t;
                }
            }
        }
    }
    void work(complex<double> *ss, complex<double> *rev_t, int N, int n, int m){
        FFT::fft(ss, N, 1); 
        FFT::fft(rev_t, N, 1);
        for(int i = 0; i <= N; i++) {
            ss[i] *= rev_t[i];
        }
        FFT::fft(ss, N, -1);
        for(int i = 0; i <= n-m; i++){
            cnt[i] +=  (int)(ss[i+m-1].real() / N + 0.5);
        }
    }
};
complex<double> a[MAX],b[MAX];
int x[MAX], y[MAX];
int s[MAX], t[MAX];
complex<double> ss[MAX], rev_t[MAX];
char ch[10];
void input(int *x, int *s, int n){
    for(int i = 0; i < n; i++){
        scanf("%s", ch);
        for(int j = 0; j < 6; j++) if(ch[j] == '1')
            x[i] += 1 << j;
        s[i] = (ch[7] == '1'); 
    }
}
struct KMP
{
    int next[MAX];
    vector<int> pos;
    void init(int *x, int n){
        next[0] = -1;
        int k = -1;
        for(int i = 1; i < n; i++){
            while(k > -1 and x[k+1] != x[i])
                k = next[k];
            if(x[k+1] == x[i]) k++;
            next[i] = k;
        }
    }
    void work(int *x, int n, int *y, int m){
        int k = -1;
        init(x, n);
        for(int i =0; i < m; i++){
            while(k > -1 and x[k+1] != y[i])
                k = next[k];
            if(x[k+1] == y[i]) k++;
            if(k == n-1) {
                pos.push_back(i-n+1); 
                k = next[k];
            }
        }
    }
}kmp;
int main(){
#ifdef DEBUG
    freopen("in", "r", stdin);
#endif
    int n, m;
    scanf("%d%d", &n, &m);
    input(x,s,n);
    input(y, t, m);
    kmp.init(y, m);
    kmp.work(y, m, x, n);
    if(kmp.pos.empty()){
        puts("No");
        return 0;
    }
    int N = 1;
    while(N <= n+m) N<<=1;
    for(int i = 0; i < n; i++)  ss[i] = complex<double>(s[i], 0);
    for(int i = 0; i < m; i++) rev_t[i] = complex<double>(t[m-1-i], 0);
    FFT::work(ss, rev_t, N, n, m);
    for(int i = 0; i < n; i++) s[i] ^= 1;
    for(int i = 0; i < m; i++) t[i] ^= 1;
    for(int i = 0; i < n; i++) ss[i] = complex<double>(s[i], 0);
    for(int i = n; i < N; i++) ss[i] = complex<double>(0, 0);
    for(int i = 0; i < m; i++) rev_t[i] = complex<double>(t[m-i-1], 0);
    for(int i = m; i < N; i++)
        rev_t[i] = complex<double>(0, 0);
    FFT::work(ss, rev_t, N, n, m);
    int res = inf, id = -1;
    for(int i = 0; i < kmp.pos.size(); i++){
        int pos = kmp.pos[i];
        // pos += m-1;
        int cost = m - FFT::cnt[pos];
        if(cost < res){
            res = cost, id = kmp.pos[i];
        } 
    }
    puts("Yes");
    printf("%d %d\n", res, id+1);
    return 0;
}