玄学,从入门到炼丹 — 初识遗传算法

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" );
	}
}
Continue reading “Codeforces Round 1467 题目大意 & 解题报告”

NOIP 2020 游记

0 说在之前

本来把,今年是没有打算写 NOIP 游记的

但是题目实在是太神仙了,所以还是来写写把

-2 Day -1

传统是周五中午吃香锅,结果拜疫情所赐,现在中午是吃不了香锅了(现在连三楼香锅都没得了<(%>_<%)>)

于是就周三吃了

Rush 到食堂,环视一圈。诶,怎么就我一个高一的来了。

算了,和高三一起恰就行了。

Continue reading “NOIP 2020 游记”

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}$

Continue reading “Luogu P4616 [COCI2017-2018#5] Pictionary”

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$ 个数字

问剩哪个数字的概率最大

Continue reading “POJ 3071 Football”

LibreOJ 2789 「CEOI2015 Day2」世界冰球锦标赛

题意

题目链接: https://loj.ac/problem/2789

给定 $m$ 和一个长度为 $n$ 数列 $a$

一种方案为从 $a$ 中选择 $k (0 \leq k \leq n)$ 个数字出来(在一个方案中,每一位只能选择一次)

一种合法的方案为选择的所有数字加起来不超过 $m$

$n \leq 40$

Continue reading “LibreOJ 2789 「CEOI2015 Day2」世界冰球锦标赛”

AtCoder Regular Contest 084 D Small Multiple

题意

题目链接: https://atcoder.jp/contests/arc084/tasks/arc084_b

要求 $ 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) 题目大意 & 解题报告”