六校联考第三场day2——2018.9.9

比赛总结

讲课录像：
T3~T6：https://www.bilibili.com/video/av31417889

10 + 40 + 1.5

后来参加的，T1读错了题，T2发现和马英杰以前出的一道题很像，然后最后也没想出，T3乱搞，时间很少了，没写出来。

T1

最长公共子串，可以允许修改k次（即可以k次失配），然后子串要求必须是连续的。读成了不要求是连续的，多读题！！！由于样例是连续的，往这里想了，但是没有再去读一读！！！

枚举一个起点，枚举另一个起点，往后一个一个走，如果不匹配了，直接修改就行，最多修改k次。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
char A[305], B[305];
int main() {
    freopen("D.in","r",stdin);
    freopen("D.out","w",stdout);
    int n = read(), k = read(), ans = 0;
    scanf("%s", A + 1);
    scanf("%s", B + 1);
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<=n; ++j) {
            int cnt = 0, p1 = i, p2 = j, now = 0;
            while (p1 <= n && p2 <= n) {
                if (A[p1] != B[p2]) {
                    cnt ++;
                    if (cnt > k) break;
                }
                p1 ++, p2 ++, now ++;
            }
            ans = max(ans, now);
        }
    }
    cout << ans;
    return 0;
}

如果不连续的话，dp一下，f[i][j][k]第一个串到i，第二个串到j，修改了k次的最长长度。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 301;
int f[N][N][N];
char A[N], B[N];
int main() {
    freopen("D.in","r",stdin);
    freopen("D.out","w",stdout);
    int n = read(), m = read();
    scanf("%s", A + 1);
    scanf("%s", B + 1);
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<=n; ++j) {
            if (A[i] == B[j]) {
                for (int k=0; k<=m; ++k) {
                    f[i][j][k] = max(f[i - 1][j][k], f[i][j - 1][k]);
                    f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k] + 1);
                }
            }
            else {
                for (int k=0; k<=m; ++k) {
                    f[i][j][k] = max(f[i - 1][j][k], f[i][j - 1][k]);
                    if (k >= 1) f[i][j][k] = max(f[i][j][k], max(f[i-1][j-1][k-1] + 1, max(f[i-1][j][k-1], f[i][j-1][k-1])));
                }
            }
        }
    }
    int Ans = 0;
    for (int i=1; i<=n; ++i) 
        for (int j=1; j<=n; ++j) 
            Ans = max(Ans, f[i][j][m]);
    cout << Ans;
    return 0;
}
*/

T2

https://www.cnblogs.com/SovietPower/p/9626940.html

解释一下最后的容斥：
对于一个转移后得到的点集假设是这样的（为s|t的状态，设为$S$） o o o o o o 一个圈表示一个数
考虑余集大小为1个转移到它的（就是从上面选一个为余集t，剩下的为初始点集s）:
可能是这样的：

s1 : o $\ $ o o o o
t1 : $\ \ $ o
设上面的连向下面的边的条数为$cnt1$，$f[S]+=f[s1] \times 2^{cnt1}$，$S=s1|t1$。

s2 : o o $\ $ o o o
t2 : $\ \ \ \ \ \ $ o
设上面的连向下面的边的条数为$cnt2$，$f[S]+=f[s2] \times 2^{cnt2}$。

这时发现，多加了一些方案。
o $\ \ \ \ \ $ o o o
设此状态为$s'$，即$23$空着。
$s'$连向$3$号点条数为$tmp1$，连向$2$号点条数为$tmp2$。一定有一步转移是这样的：
$f[s1] += f[s'] \times 2^{tmp1}$
$f[s2] += f[s'] \times 2^{tmp2}$
现在$f[S] += f[s']\times2^{tmp1}\times2^{cnt1} + f[s']\times2^{tmp2}\times2^{cnt2}$
第一个式子是$s'$先选了3再选了2，第二个式子是先选了2再选了3，最后的结果是一样的，但是因为不同的顺序导致多加了一部分。
多加的部分：前面一个式子在选的过程中，这用1456选的2，然后后面的式子也是用选的3，那么这就是多了的方案数：$f[s']\times2^{1456连向2的条数}\times2^{1456连向3的条数}$。就是余集为2的方案数。
剩下的就是用1456选了3，然后用3选了2；和用1456选了2，用2选了3。
同样余集为3的时候在加上。

余集为2的方案数
s3 ：o $\ \ \ \ \ \ $ o o o
t3 : $\ \ $ o o
当前就是：设上面的连向下面的边的条数为cnt3，方案数为$f[s3] \times 2^{cnt3}$。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int mod = 1e9 + 7;
const int N = 20;
int mi[N * N], mp[N][N], g[N][(1 << 17) + 5], f[(1 << 17) + 5];
int Calc(int s) {
    int res = 0;
    for (; s; s>>=1) res += (s & 1);
    return res;
}
int main() {
    freopen("E.in","r",stdin);
    freopen("E.out","w",stdout);
    int n = read(), m = read();
    mi[0] = 1;
    for (int i=1; i<=m; ++i) mi[i] = 1ll * mi[i - 1] * 2 % mod;
    for (int i=1; i<=m; ++i) mp[read() - 1][read() - 1] = 1;
    int S = (1 << n) - 1;
    for (int s=0; s<=S; ++s) {
        for (int i=0; i<n; ++i) 
            if ((1 << i) & s) 
                for (int j=0; j<n; ++j) g[j][s] += mp[j][i]; // j向余集s连向多少条边 
    }   
    f[0] = 1;
    for (int s=0; s<=S; ++s) { // 当前点集 
        if (!f[s]) continue; 
        int C = S ^ s;
        for (int t=C; t; t=(t-1)&C) { // 余集 
            int sz = Calc(t), cnt = 0; // sz：余集大小，cnt：点集中所有点向余集连向的边数 
            for (int i=0; i<n; ++i)
                if ((1 << i) & s) cnt += g[i][t];
            if (sz & 1) f[s|t] = (f[s|t] + 1ll * f[s] * mi[cnt] % mod) % mod;
            else f[s|t] = (f[s|t] - 1ll * f[s] * mi[cnt] % mod + mod) % mod;
        }
    }
    cout << f[S];
    return 0;
}

T3