0 说在之前
正常来说，一个正常的 Oier 是不会碰这种东西
但是我们综合实践小组的组长不知道为啥对这东西出奇的感兴趣， 我就试着理解一下
因为也仅仅是试着理解，如有理论错误还往各位在评论区斧正
本文的代码实现可以在 https://gitee.com/yingziyu/task 看到
Continue reading “玄学，从入门到炼丹 — 初识遗传算法”分类： 算法竞赛
树上启发式合并(dsu on tree)简介
1 树上启发式合并
1.1 启发式算法
我并没有找到比较正式的定义，在这里引用 OI Wiki 里的
启发式算法是基于人类的经验和直观感觉，对一些算法的优化。
例子：并查集的按秩合并
1.2 树上启发式合并
基于「减少节点多的子树的处理次数」的思想为主的算法
1.3 实现
我们希望节点多的子树处理次数尽可能少，也就是我们希望重儿子的处理次数尽可能少
注意到许多树上问题的处理过程是可延续的，即当前子树的处理完后可以直接将数据移交到父亲节点继续处理
基于这点，我们可以优先处理重儿子，然后直接继承到父亲节点。这样对于一个节点来说，其重儿子只需要处理一次，其轻儿子需要处理两次。
因为从树上任意一条路径上，关键点（即轻儿子）在 $O(\log(n))$ 范围内，所以这东西的复杂度是 $O(n\log(n))$ 的。
Continue reading “树上启发式合并(dsu on tree)简介”Codeforces Round 1467 题目大意 & 解题报告
即 Codeforces Round #695 (Div. 2)
许久不打变得更菜了…
A. Wizard of Orz
0 大意
给定 $n$ 个板子，每个板子上有一个相同的数字 $x ( 0 \leq x \leq 9 )$
随机选择一个数字 $y(1 \leq y \leq n)$，令板子 $i$ 上的数字变成 $ x + |y – i| \pmod 10$
1 Code
显然，输出 $98\{987654321\}$ 的前 $n$ 位即可
#include <cstdio>
int main() {
int T;
scanf( "%d", &T );
while( T -- ) {
int n;
scanf( "%d", &n );
if( n == 1 )
printf( "9" );
else {
printf( "98" );
int cur = 9;
for( int i = 3; i <= n; i ++ ) {
printf( "%d", cur );
cur ++;
if( cur >= 10 )
cur = 0;
}
}
printf( "\n" );
}
}
Luogu P4616 [COCI2017-2018#5] Pictionary
1 题意
在第 $i$ 天，如果 $\gcd(a,b) = m – i + 1$，那么 $a,b$ 之间会建立一条边
给定 $a,b$，求 $a,b$ 最早什么时候连通
多组询问，离线
$1 \leq n ,q \leq 10^5, 1 \leq m \leq n, 1 \leq a, b \leq n$
$n,m,q,a,b \in \mathbb{Z}$
POJ 3071 Football
1 题目大意
给定 $2^n$ 个整数，从 $1$ 到 $2^n$ 编号
给定 $p_{i,j}(1\leq i \leq n, 1 \leq j \leq n)$
定义一次操作为
选中 $2k$ 和 $2k+1$ ( $0 \leq k, k \in Z, 2k+1 \leq n$ )
其中有 $p_{2k,2k+1}$ 的概率选中 $2k$
其中有 $p_{2k+1,2k}$ 的概率选中 $2k+1$
把所有选择的数字组成一个新的数列，大小为 $\frac{n}{2}$
显然最后会只剩 $1$ 个数字
问剩哪个数字的概率最大
LibreOJ 2789 「CEOI2015 Day2」世界冰球锦标赛
题意
给定 $m$ 和一个长度为 $n$ 数列 $a$
一种方案为从 $a$ 中选择 $k (0 \leq k \leq n)$ 个数字出来（在一个方案中，每一位只能选择一次）
一种合法的方案为选择的所有数字加起来不超过 $m$
$n \leq 40$
AtCoder Regular Contest 084 D Small Multiple
题意
要求 $ x = ak(a \in N) $，定义 $f(x)$ 为 $x$ 在十进制下每一位数字的和
思路
一开始肯定想的是大力枚举，但是很快就可以发现大力枚举可以被卡掉，因为另一个数字可以非常大
然后就考虑缩小另一个数字的范围
一开始的思路顺着质因数分解走的，但是想了半天没有想出来
考后发现顺着质因数的过于复杂，我们可以直接考虑 $x \bmod k$ 意义下的情况
从 $ x $ 到 $ x + 1 $，答案显然增加 1
但是如果 x 一直加 1 会加到 10 ，这个情况答案在事实上没有增加 1
我们可以发现只有其在某一步变成 10 倍才会发生这种事件，那么再加一条边
从 $x$ 到 $10x$，答案不增加
这样就构成了一条图，从 $0$ 到 $1$ 的最短路就是所求答案
Continue reading “AtCoder Regular Contest 084 D Small Multiple”
Codeforces Round #666 (Div. 2) 题目大意 & 解题报告
即 Codeforces Round 1397
比赛链接: https://codeforces.com/contest/1397
A Juggling Letters
题目大意
给你 $n$ 个字符串，问能不能打乱成相等的三个字符串
思路
因为可以随意打乱，所以统计每个字母个数，只要每个字母的个数模 $n$ 余 $0$ 即可
Continue reading “Codeforces Round #666 (Div. 2) 题目大意 & 解题报告”
Codefoces #1382 解题报告 & 部分翻译
A Common Subsequence
0 题目大意
给你两个序列 $a,b$，求两个序列最短的公共子序列
1 代码
对，是最短……
AC 自动机 — LOJ 3089 「BJOI2019」奥术神杖
0 说在之前
我吐了，这题我写了两天……
考虑到我自己写的博客还没有 AC 自动机的，我会简单写一下
1 AC 自动机
1.0 什么是 AC 自动机
有一个说烂但是很形象的说法 Trie + KMP
AC 自动机用于多模式串匹配
就是你拿一个字符串，和一堆字符串
然后 AC 自动机可以让你快速的知道这一堆字符串中，那些是你这一个字符串的子串