【LOJ】#2172. 「FJOI2016」所有公共子序列问题

题解

听说是什么序列自动机？

我们考虑对于每个位置的串，下面拼接相同的字符时，拼接最近的一个，这样可以保证不重不漏

为了实现这个我们需要什么呢，我们需要一个链表，记录一下每个位置的下一个字符会转移到哪里

例如

ABAB

ch[1]['A'] = 3 ch[1]['B'] = 2

听起来挺好建的，具体可以看代码

然后我们记录dp[a][b]是第一个字符串a位置的字符为开头，第二个字符串b位置的字符为开头，公共子序列的个数

可以记忆化搜索，每一次枚举下一个位置拼接上哪个字符

输出方案的话也是一样，枚举下一个位置拼上哪个字符

后五个点需要高精度啊= =

#include <iostream>

#include <cstdio>

#include <vector>

#include <algorithm>

#include <cmath>

#include <cstring>

#include <map>

//#define ivorysi

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define mo 974711

#define MAXN 3055

#define RG register

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

	    while(c < '0' || c > '9') {

			if(c == '-') f = -1;

			c = getchar();

	    }

	    while(c >= '0' && c <= '9') {

		res = res * 10 + c - '0';

		c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {putchar('-');x = -x;}

    if(x >= 10) {

		out(x / 10);

    }

    putchar('0' + x % 10);

}

int N,M,MK,ci[205];

char x[MAXN],y[MAXN],ic[205],s[MAXN];

struct segAM {

	int head[62],next[MAXN],ch[MAXN][62],tot;

	segAM() {

		tot = 1;next[1] = 0;

		for(int i = 0 ; i <= 60; ++i) head[i] = 1;

	}

	void Insert(char c) {

		++tot;

		next[tot] = head[ci[c]];

		for(int i = 0 ; i <= 51 ; ++i) {

			for(int j = head[i] ; j && !ch[j][ci[c]] ; j = next[j]) {

				ch[j][ci[c]] = tot;

			}

		}

		head[ci[c]] = tot;

	}

}S1,S2;

const int BASE = 100000000;

const int LEN = 8;

struct Bignum {

	vector<int> v;

	Bignum operator = (int64 x) {

		v.clear();

		do {

			v.pb(x % BASE);

			x /= BASE;

		}while(x);

		return *this;

	}

	friend Bignum operator + (const Bignum &a,const Bignum &b) {

		Bignum c;c.v.clear();

		int p = 0,g = 0;

		while(1) {

			int x = g;

			if(p < a.v.size()) x += a.v[p];

			if(p < b.v.size()) x += b.v[p];

			++p;

			if(!x) break;

			c.v.pb(x % BASE);

			g = x / BASE;

		}

		return c;

	}

	void print() {

		int s = v.size() - 1;

		printf("%d",v[s]);

		--s;

		for(int i = s ; i >= 0 ; --i) {

			printf("%08d",v[i]);

		}

	}

}dp[MAXN][MAXN];

bool vis[MAXN][MAXN];

void get(int a,int b) {

	if(a == 0 || b == 0) return;

	if(vis[a][b]) return;

	dp[a][b] = 1;

	vis[a][b] = 1;

	for(int i = 0 ; i <= 51 ; ++i) {

		int ta = S1.ch[a][i],tb = S2.ch[b][i];

		get(ta,tb);

		dp[a][b] = dp[a][b] + dp[ta][tb];

	}

}

void get2(int a,int b,int dep) {

	if(a == 0 || b == 0) return;

	s[dep] = 0;if(dep != 0) printf("%s\n",s);

	for(int i = 0 ; i <= 51 ; ++i) {

		s[dep] = ic[i];

		get2(S1.ch[a][i],S2.ch[b][i],dep + 1);

	}

}

void Solve() {

	read(N);read(M);

	scanf("%s%s",x + 1,y + 1);

	read(MK);

	for(char i = 'A' ; i <= 'Z' ; ++i)

		ci[i] = i - 'A',ic[i - 'A'] = i;

	for(char i = 'a' ; i <= 'z' ; ++i)

		ci[i] = i - 'a' + 26,ic[i - 'a' + 26] = i;

	for(int i = 1 ; i <= N ; ++i) S1.Insert(x[i]);

	for(int i = 1 ; i <= M ; ++i) S2.Insert(y[i]);

	if(MK == 1) get2(1,1,0);

	get(1,1);

	dp[1][1].print();enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

   	Solve();

    return 0;

}

今天写的题解全是FJOI啊（其实还写了2道JOI的水题，太水了不写题解了）

zxg说让我们看看数学相关的集训队论文，然后做做FJ和SC的省选= =

FJ猫锟 SC YJQ

我们都表示毫不理解该省省选题和该省出题人有什么关系，真的不懂中老年人思维啊

但是反正都是要无脑提高刷题量嘛（大雾）

量变能带来质变

……吗？

39天NOI2018打卡

巴特西

【LOJ】#2172. 「FJOI2016」所有公共子序列问题

题解

最新文章

热门文章