Tag: 状态压缩

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2471
神犇题解：http://www.cnblogs.com/clrs97/p/5993606.html

解题报告

我们考虑从高位开始，逐位枚举。那么每枚举一位相当于将序列划分为10分，并且取其中一份。
对于一段连续的序列来讲，我们只需要关注其进入这段序列之前会匹配到x的哪一位、匹配完这一段之后匹配到了x的哪一位、这期间总共贡献了多少次成功的匹配。
不难发现这个状态是很少的，于是我们可以记忆化搜索。

另外这题很容易扩展到：“左右边界为任意值的情况”
然后我把这题搬到了今年的全国胡策里，不知道有没有人能切掉

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 16;
const int M = 10;
const int SGZ = 10;
const int MOD = 1000000007;
 
int n, m, nxt[M];
char s[M];
struct Transfer{
    LL pos, cnt;
    inline Transfer() {
    }
    inline Transfer(LL a, LL b):pos(a), cnt(b) {
    }
    inline Transfer operator + (const Transfer &T) {
        return Transfer(T.pos, cnt + T.cnt);
    }
}t[M][SGZ];
map<int, Transfer> f[N][M];
struct MatchStatus{
    int HashVal;
    Transfer t[M];
    inline void GetHashVal() {
        const static int MOD = 1000000007;
        const static int SEED1 = 13, SEED2 = 131;
        HashVal = 0;
        for (int i = 0; i < m; i++) {
            HashVal = (HashVal + (LL)t[i].pos * SEED2 + t[i].cnt) * SEED1 % MOD;
        }
    }
    inline bool operator < (const MatchStatus &MS) const {
        return HashVal < MS.HashVal;
    }
};
 
inline Transfer DFS(int w, int p, const MatchStatus &cur) {
    if (w <= 0) {
        return cur.t[p];
    } else if (f[w][p].count(cur.HashVal)) {
        return f[w][p][cur.HashVal];
    } else {
        Transfer ret(p, 0);
        for (int i = 0; i < SGZ; i++) {
            MatchStatus nw = cur;
            for (int j = 0; j < m; j++) {
                nw.t[j] = nw.t[j] + t[nw.t[j].pos][i];
            }
            nw.GetHashVal();
            ret = ret + DFS(w - 1, ret.pos, nw);
        }
        return f[w][p][cur.HashVal] = ret;
    }
}
 
int main() {
    while (~scanf("%d %s", &n, s + 1) && n) {
        m = strlen(s + 1);
        for (int i = 1; i <= m; i++) {
            s[i] -= '0';
        }
        nxt[1] = 0;
        for (int i = 2, j = 0; i <= m; nxt[i++] = j) {
            for (; j && s[j + 1] != s[i]; j = nxt[j]);
            j += s[j + 1] == s[i];
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < SGZ; j++) {
                int k = i;
                for (; k && s[k + 1] != j; k = nxt[k]);
                k += s[k + 1] == j;
                t[i][j] = k == m? Transfer(nxt[k], 1): Transfer(k, 0);
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < m; j++) {
                f[i][j].clear();
            }
        }
        Transfer ans(0, 0);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < SGZ; j++) {
                MatchStatus cur;
                for (int k = 0; k < m; k++) {
                    cur.t[k] = t[k][j];
                }
                cur.GetHashVal();
                ans = ans + DFS(i - 1, ans.pos, cur);
            }
        }
        printf("%lld\n", ans.cnt);
    }
    return 0;
}

相关链接

题目传送门：http://codeforces.com/contest/741/problem/D
中文题面：https://blog.sengxian.com/solutions/cf-741d

解题报告

看起来这个串的定义非常强的样子，但仔细观察不难发现，就是出现次数为奇数的字母最多出现一个
于是我们定时一个二进制状态$f_{i,j}$表示$i$到$j$这段路径中哪些字符出现了奇数次

我们考虑在每一条合法路径的LCA处将其统计
于是就变成了子树相关问题，于是非常自然想到启发式合并

考虑从子树最大的儿子那里继承集合，其他的儿子的集合暴力加入
因为走一条边，需要异或一个值，整个集合的转移我们可以记录一个标记，然后在插入时使其生效
考虑统计的话，我们在暴力插入的时候，枚举是哪一位不同，单次查询是$O(22)$的
又因为加入是$O(1)$的，所以总的时间复杂度$O(n \log n \cdot 22)$

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1770
离线版题目：http://paste.ubuntu.com/18956597/
数据生成器：http://paste.ubuntu.com/18956646/

首先，这道题状态压缩的方法很显然，但是状态太多了，会T（然而黄学长说：折半搜索也可过QAQ）
然后开始想高斯消元。一开始不知道高斯消元能解异或方程组，于是想了两个多小时QAQ
然后去补了解异或方程组，一开始对自由元的理解有问题，正确的应该是：
自由元可以随便定，每一组不同的自由元可以导出一组方程的解
换一句话说，消完元之后，非自由元的未知数的解，并非最终解

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 50;
const int INF = 50;

int n,m,vout=INF;
int mat[MAXN][MAXN],tag[MAXN];

inline int read(){
	char c=getchar(); int buf=0,f=1;
	while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
	return buf*f;
}

inline void Gauss(){
	for (int k=1,w=k;k<n;w=++k){
		for (int i=k+1;i<=n&&!mat[k][w];i++) if (mat[k][i]) w = i;
		for (int i=1;i<=n+1;i++) swap(mat[i][w],mat[i][k]);
		for (int i=k+1;i<=n;i++) if (mat[k][i]) 
			for (int j=1;j<=n+1;j++) mat[j][i] ^= mat[j][k];
	}
}

void DFS(int w, int cost){
	if (cost >= vout) return;
	else if (!w) vout = min(vout, cost);
	else {
		if (mat[w][w]) {
			int t = mat[n+1][w];
			for (int i=w+1;i<=n;i++)
				if (mat[i][w]) t ^= tag[i];
			tag[w] = t;
			DFS(w-1, cost+(t?1:0));
		} else {
			tag[w] = 1;
			DFS(w-1, cost+1);
			tag[w] = 0;
			DFS(w-1, cost);
		}
	}
}

int main(){
	n = read(); m = read();
	for (int i=1;i<=n;i++) 
		mat[i][i] = 1, mat[n+1][i] = 1;
	for (int i=1,a,b;i<=m;i++){
		a = read(); b = read();
		mat[a][b] = mat[b][a] = 1;
	}
	Gauss(); 
	DFS(n,0);
	printf("%d\n",vout);
	return 0;
}