Dyd's Blog

He who has a strong enough why can bear almost any how.

text2021/12/21总结

Posted on Edited on
Symbols count in article: 2.8k Reading time ≈ 3 mins.

爆0了

text2021/12/21总结

题目、成绩和题解

题目：

A、B、C

成绩：

Dyd：0 + 0 + 0 = 0

wfy：0 + 50 + 0 = 50

rusun：0 + 60 + 0 = 60

题解

做题

T1

开考后大家都觉得很难……

T1感觉像个基环树+状压dp，于是开打

思路是定义 $f[i][j][k]$ 表示“前 $i$ 条边选了 $j$ 条当前联通的点集为 $k$ 的方案数”，由于空间不够， $i$ 滚动压掉，求出 $f[j][k]$ 以后直接暴力dfs连通块，时间复杂度为 $O(2^nn^4)$ ，刷表法跑不满

但是考场上没调出来，主要是计数的时候会有重复，于是爆0了

T2、T3

没打

改题

T1

一看题解什么神仙基尔霍夫矩阵啊，完全不会好吧

于是去学习了，鸽之

wdf，学了半天，博客都写了，结果另外的dp可过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
#define LL long long
#define STC static
#define lowbit(x) ((x) & (-(x)))
using namespace std;
const int N = 16, P = 998244353, NN = (1 << N);
int n, m, nn;
int e[N], cnt[NN], id[NN];
int f[NN][2], d[NN][2];
int main()
{
	scanf("%d%d", &n ,&m);
	nn = (1 << n);
	for (int i = 1, u, v; i <= m; ++i)
	{
		scanf("%d%d", &u, &v);
		--u, --v;
		e[u] |= (1 << v), e[v] |= (1 << u);
	}
	for (int i = 1; i < nn; ++i)
		cnt[i] = cnt[i >> 1] + (i & 1);
	for (int i = 0; i < n; ++i)
		f[1 << i][0] = 1, id[1 << i] = i;
	for (int i = 1, t, x, y; i < nn; ++i)
	{
		if (cnt[i] == 1)
			continue;
		t = i;
		x = id[lowbit(t)], t ^= lowbit(t);
		y = id[lowbit(t)], t ^= lowbit(t);
		for (int j = t, sta, lnk; ; j = (j - 1) & t)
		{
			sta = j | (1 << y), lnk = cnt[e[x] & sta];
			f[i][0] = ((LL)f[sta][0] * f[i ^ sta][0] % P * lnk + f[i][0]) % P;
            f[i][1] = ((LL)f[sta][1] * f[i ^ sta][0] % P * lnk + f[i][1]) % P;
            f[i][1] = ((LL)f[sta][0] * f[i ^ sta][1] % P * lnk + f[i][1]) % P;
            f[i][1] = ((LL)f[sta][0] * f[i ^ sta][0] % P * (lnk * (lnk - 1) / 2) + f[i][1]) % P;
			if (!j)
				break;
		}
	}
	d[0][0] = 1;
	for (int sta = 1, t; sta < nn; ++ sta)
    {
        t = sta ^ lowbit(sta);
        for (int i = t, prt; ; i = (i - 1) & t)
        {
            prt = i | lowbit(sta);
            if (f[prt][0])
			{
				d[sta][0] = ((LL)f[prt][0] * d[sta ^ prt][0] % P * cnt[prt] + d[sta][0]) % P;
                d[sta][1] = ((LL)f[prt][0] * d[sta ^ prt][1] % P * cnt[prt] + d[sta][1]) % P;
			}
            if (f[prt][1])
                d[sta][1] = ((LL)f[prt][1] * d[sta ^ prt][0] % P * cnt[prt] + d[sta][1]) % P;
            if (!i) break;
        }
    }
	printf("%d\n", (d[nn - 1][0] + d[nn - 1][1]) % P);
	return 0;
}

T2

暴力可以过，我还能说什么呢？

这说明以后暴力一定要打快读

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
#define LL long long
#define STC static
#define IL inline
#define gh() getchar()
using namespace std;
const int N = 1500 + 5;
int row[N][N], col[N][N], n, m;
char a[N][N];
template<class T>
IL void read(T &x)
{
	x = 0;
	char ch = gh(), t = 0;
	while (ch < '0' || ch > '9')
		t |= ch == '-', ch = gh();
	while (ch >= '0' && ch <= '9')
		x = x * 10 + (ch ^ 48), ch = gh();
	if (t)
		x = -x;
}
int main()
{
	read(n), read(m);
	for (int i = 1; i <= n; ++i)
		scanf("%s", a[i] + 1);
	for (int i = n; i >= 1; --i)
		for (int j = n; j >= 1; --j)
			if (a[i][j] == '1')
				row[i][j] = row[i][j + 1] + 1, col[i][j] = col[i + 1][j] + 1;
	int x, y, ans;
	while (m--)
	{
		read(x), read(y);
		ans = 0;
		for (int i = 1; i + x - 1 <= n; ++i)
			for (int j = 1; j + y - 1 <= n; ++j)
				if (row[i][j] >= y && col[i][j] >= x && row[i + x - 1][j] >= y && col[i][j + y - 1] >= x)
					++ans;
		printf("%d\n", ans);
	}
	return 0;
}

T3

还有别的博客没写完，鸽之