信行散记

但行好事，莫问前程

0%

发表于

并查集

优化方式

  1. 路径压缩
  2. 按秩合并 (merge时size小的当儿子)

可撤销并查集

路径压缩是无法撤销的。
但按秩合并可以。
所以只写按秩合并就行。记一下 merge 的时候连的哪条边。
时间复杂度 O(nlog⁡n)O(n \log n)

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
template <const int N> struct dsu
{
    int f[N], g[N];
    stack<pair<int *, int>> s;
    void init(int n)
    {
        for (int i = 0; i <= n; i++)
            f[i] = i, g[i] = 1;
    }
    int get(int u)
    {
        return f[u] == u ? u : get(f[u]);
    }
    bool find(int u, int v)
    {
        return get(u) == get(v);
    }
    void merge(int u, int v)
    {
        u = get(u), v = get(v);
        if (u == v)
            return;
        if (g[u] > g[v])
            swap(u, v);
        s.push({f + u, f[u]}), f[u] = v;
        s.push({g + v, g[v]}), g[v] += g[u];
    }
    unsigned tag()
    {
        return s.size();
    }
    void undo(unsigned tag)
    {
        while (s.size() > tag)
            *s.top().first = s.top().second, s.pop();
    }
};

Kruskal 重构树

并查集在合并集合的时候是直接加一条边上去。
考虑另一种做法：找到 u,vu, v 所在树的根节点 u′,v′u', v'，然后新建一个结点 zz作为 u′,v′u', v' 的父亲。
这样我们就得到了 kruskal 重构树。
原树上的点在重构树上都是叶子结点，并且 kruskal 重构树是一棵二叉树。可以理解为一种特殊的三度化(树转二叉树)

发表于
  1. 今天输出多组数据没有换行。
    puts("");puts("");puts("");puts("");puts("");puts("");puts("");puts("");puts("");puts("");puts("");puts("");puts("");puts("");puts("");putchar('\n')
  2. 尝试检查变量，交换变量
  3. 看清求什么
  4. 01背包倒着枚举，看清v,w
  5. 一定要看数据范围
  6. dp的max,min要看好
  7. 看与标答相差几，找对应debug
  8. 下标从1开始！ （特殊题除外)
  9. 多数据注意换行
  10. 无限扩展注意模坐标和原坐标
  11. 差分要开第二个数组(否则会出现奇奇怪怪的问题)
  12. 要bfs时看清数据范围，若超时，尝试双向bfs,但是可以用两个队列bfs，而不是压入两个差不多吧
  13. 单层图解决不了，试试多层图。
  14. 统计方案的时候答案一定要开 long long 啊啊啊啊啊啊.
    long long f[N], g[N], ans

发表于 更新于

矩阵乘法

乘 A, B 得 C

C 中的 [i][j][i][j] = A 中的第 ii 行和 B 中的第 jj 列相乘 YYH

阅读全文 »

发表于 更新于

题面

[NOIP2017 提高组] 列队

题目描述

Sylvia 是一个热爱学习的女孩子。

前段时间，Sylvia 参加了学校的军训。众所周知，军训的时候需要站方阵。

Sylvia 所在的方阵中有 n×mn \times m 名学生，方阵的行数为 nn，列数为 mm。

为了便于管理，教官在训练开始时，按照从前到后，从左到右的顺序给方阵中 的学生从 11 到 n×mn \times m 编上了号码（参见后面的样例）。即：初始时，第 ii 行第 jj 列 的学生的编号是 (i−1)×m+j(i-1)\times m + j。

然而在练习方阵的时候，经常会有学生因为各种各样的事情需要离队。在一天 中，一共发生了 qq 件这样的离队事件。每一次离队事件可以用数对 (x,y)(1≤x≤n,1≤y≤m)(x,y) (1 \le x \le n, 1 \le y \le m) 描述，表示第 xx 行第 yy 列的学生离队。

在有学生离队后，队伍中出现了一个空位。为了队伍的整齐，教官会依次下达 这样的两条指令：

  1. 向左看齐。这时第一列保持不动，所有学生向左填补空缺。不难发现在这条 指令之后，空位在第 xx 行第 mm 列。

  2. 向前看齐。这时第一行保持不动，所有学生向前填补空缺。不难发现在这条 指令之后，空位在第 nn 行第 mm 列。

教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后， 下一个学生才能离队。因此在每一个离队的学生要归队时，队伍中有且仅有第 nn 行 第 mm 列一个空位，这时这个学生会自然地填补到这个位置。

因为站方阵真的很无聊，所以 Sylvia 想要计算每一次离队事件中，离队的同学 的编号是多少。

注意：每一个同学的编号不会随着离队事件的发生而改变，在发生离队事件后 方阵中同学的编号可能是乱序的。

输入格式

输入共 q+1q+1 行。

第一行包含 33 个用空格分隔的正整数 n,m,qn, m, q，表示方阵大小是 nn 行 mm 列，一共发 生了 qq 次事件。

接下来 qq 行按照事件发生顺序描述了 qq 件事件。每一行是两个整数 x,yx, y，用一个空 格分隔，表示这个离队事件中离队的学生当时排在第 xx 行第 yy 列。

输出格式

按照事件输入的顺序，每一个事件输出一行一个整数，表示这个离队事件中离队学生的编号。

样例 #1

样例输入 #1

1
2
3
4
2 2 3 
1 1 
2 2 
1 2

样例输出 #1

1
2
3
1
1
4

提示

【输入输出样例 11 说明】

PicFailedPlelaseAskMaster

列队的过程如上图所示，每一行描述了一个事件。 在第一个事件中，编号为 11 的同学离队，这时空位在第一行第一列。接着所有同学 向左标齐，这时编号为 22 的同学向左移动一步，空位移动到第一行第二列。然后所有同 学向上标齐，这时编号为 44 的同学向上一步，这时空位移动到第二行第二列。最后编号为 11 的同学返回填补到空位中。

【数据规模与约定】

测试点编号 nn mm qq 其他约定
1∼61\sim 6 ≤103\le 10^3 ≤103\le 10^3 ≤500\le 500 无
7∼107\sim 10 ≤5×104\le 5\times 10^4 ≤5×104\le 5\times 10^4 ≤500\le 500 无
11∼1211\sim 12 =1=1 ≤105\le 10^5 ≤105\le 10^5 所有事件 x=1x=1
13∼1413\sim 14 =1=1 ≤3×105\le 3\times 10^5 ≤3×105\le 3\times 10^5 所有事件 x=1x=1
15∼1615\sim 16 ≤3×105\le 3\times 10^5 ≤3×105\le 3\times 10^5 ≤3×105\le 3\times 10^5 所有事件 x=1x=1
17∼1817\sim 18 ≤105\le 10^5 ≤105\le 10^5 ≤105\le 10^5 无
19∼2019\sim 20 ≤3×105\le 3\times 10^5 ≤3×105\le 3\times 10^5 ≤3×105\le 3\times 10^5 无

数据保证每一个事件满足 1≤x≤n,1≤y≤m1 \le x \le n,1 \le y \le m。

解法

树状数组

1. 前 50% 离散化

发表于 更新于

T2
回滚莫队
T3

做法

因为给出了首字母，把首字母不符合的全部过滤掉

然后在剩下的里面用mt19937_64瞎猜

下一次猜的时候，依次假设未被过滤的每一个值是答案，求出与上一次猜相符的 good 和 silver

与返回的 good 和 silver 比对，进行过滤

继续用 mt19937_64 瞎猜

循环往复

然后83…

计算一下加权，手写一个决策树，就100pts了 _

发表于 更新于

PicFailedPlelaseAskMaster

看到题目，可能会以为是什么 mg 数学 or 线性筛
其实只要类似埃拉托色尼筛法，这样处理：

因为范围是 10710^7 , 于是只要遍历 1 到 1e7 的每一个数，然后判断这个数里面有没有7，如果有，
就把它的倍数都遍历一下。。。
额，是不是很简单？

本来是会超时的，但是吸了氧。。。额

过了

PS：考场没注意吸氧，写了个打表，傻傻问了监考员说没事，然后爆零了。。

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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e7 + 10;
int a[N];
int b[N];

bool has7(int k)
{
	while(k)
	{
		if(k % 10 == 7) return 1;
		k /= 10;
	}
	return 0;
}

int main(void)
{
	// a[7] = 1;
	for(int i = 7; i < N; i++)
		if(has7(i))
		{
			// if(i == 7) printf("OOOHH!!!\n");
			for(int j = i; j < N; j += i)
			{
				a[j] = 1;
			}
		}

	int cnt = 0;
	for(int i = 0; i < N; i++)
		if(!a[i])
		{
			b[++cnt] = i;
			// if(i < 1000) printf("----%d\n", i);
		}
	
	
    int T, x;
    scanf("%d", &T);
    for(int i = 1; i <= T; i++)
    {
        scanf("%d", &x);
        int *p = lower_bound(b + 1, b + cnt + 1, x);
        // printf("%d", )
        if(*p == x) printf("%d\n", *(p + 1));
        else printf("%d\n", -1);
    }
    return 0;
}

发表于

乍一看是数位DP, 其实不用那么麻烦的啦。

题目是要求 [L, R] 内满足 x xor N < N 的 x 个数.

考虑 N 的二进制拆分，若 N 的第 i 位为 1, 则 从 2i2^i 到 2i+1−12^{i+1}-1 都是满足要求的（想一想为什么）
然后统计每一个区间与[L, R] 的交并累加就可以了。。

发表于

SPFA求负环有两种方法:

  1. 统计每个点的入队次数，如果 ≥n\geq n 说明存在负环
  2. 统计最短路包含的边数，如果 \gen n 说明存在负环
阅读全文 »

发表于

普及组

T1 T4 没什么问题
T2 主要是懒惰排序，对于每次修改只修改一个地方，于是只要每次向左 or 右冒泡一下 而且要写稳定排序
T3 check 写崩了 如果一个合法IP端口号是个位数那么会被判定为不合法。

提高组

T1 简单模拟没什么问题 三分好像不行
T2 是区间DP，情况有点多，分析要细致
f(l, r) 为 l 与 r 匹配的超级括号串
g(l, r) 为不匹配的
根据题目要求递推
T3 思路是考虑第一步选择 ‘L’ 或 ‘R’, 并找出与之相同的位置，分成两个栈，再每一次都取栈头栈尾做。
dfs 实现不优秀 40 优秀 100
T4 是由 k = 2 想到对原图求最小割
但是 dinic 太慢, 要建立原图的对偶图跑最短路
考虑将相邻的不同颜色附加点射线间的结点两两配对（容易注意到这样的结点个数一定为偶数或 1；结点数为 1 时显然仅存在一种颜色附加点，答案为 0）并分别按 k≤2k\leq 2 的做法求最短路，再去掉这些最短路对应的原图的边集，那么答案方案所需要去掉的边集一定为某种配对方案对应的边集
这样就可以得到一个方案

发表于

枚举字符串并计算概率

计 p(T, x) =

Π(Stii)A∑si∑ti\cfrac{\Pi(S\frac{t_i}{i})}{A^{\sum t_i}_{\sum s_i}}

然后计算答案 P(T)

P(T)=1−Πx=1n(1−p(T,x))P(T) = 1 - \Pi_{x = 1}^{n}(1-p(T,x))

然后求所有P(T)的总和。

代码

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;
const int N = 110, P = 998244353;
int n, m, ans, vec[N], dm[N][N], cnt[N][10], w[N], dp[N];
char c[N];
int qpow(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = (1ll * res * a) % P;
        a = (1ll * a * a) % P, b >>= 1;
    }
    return res;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", c + 1);
        for (int j = 1; j <= m; j++)
            cnt[i][c[j] - '0']++;
    }
    for (int i = 0; i <= m; i++)
    {
        dm[i][0] = 1;
        for (int j = 1; j <= i; j++)
        {
            dm[i][j] = (1ll * dm[i][j - 1] * (i - j + 1)) % P;
        }
    }
    for (int i = 1; i < (1 << n); i++)
    {
        int cntt = 0, sum = 0;
        for (int j = 0; j < n; j++)
        {
            if (i & (1 << j))
            {
                vec[++cntt] = j + 1;
            }
        }
        dp[0] = 1;
        for (int j = 1; j <= m; j++)
        {
            dp[j] = 0;
        }
        for (int j = 0; j <= 9; j++)
        {
            for (int l = 0; l <= m; l++)
            {
                w[l] = qpow(dm[l][l], P - 2);
                for (int k = 1; k <= cntt; k++)
                {
                    w[l] = (1ll * w[l] * dm[cnt[vec[k]][j]][l]) % P;
                }
            }
            for (int l = m; l >= 0; l--)
            {
                for (int k = l - 1; k >= 0; k--)
                {
                    dp[l] = (dp[l] + (1ll * dp[k] * w[l - k]) % P) % P;
                }
            }
        }
        for (int l = 0; l <= m; l++)
        {
            int tmp = (1ll * dp[l] * dm[l][l]) % P, prod = qpow(dm[m][l], P - 2);
            sum = (sum + (1ll * tmp * qpow(prod, cntt)) % P) % P;
        }
        if (cntt & 1)
            ans = (ans + sum) % P;
        else
            ans = (ans - sum + P) % P;
    }
    printf("%d\n", ans);
    return 0;
}