「Jump up HIGH!!」
原题链接：https://codeforces.com/contest/1549/problem/E
给定 $n$，$q$ 次询问。
每次询问给定一个 $x$，求 $\sum_{i=0}^n \binom{3i}{x}$
考虑定义 $f_{i,j}$ 表示 $\sum_{k=0}^{n-1} \binom{3k + j}{i}$，令 $0 \leq j < m$
注意到
发现可以解出 $f_{i,0}$
$O(n)$ 递推即可。
Continue reading “Codeforces 1549E / 1548C”为了适应传统的 Day1 Day2 定义，本文中 Day 1 为 2021/07/26，Day1.5 为一个地球日。
正睿提供了一场信心赛，打开发现是大家都做过的题目，便回去看各自之前做过的题目了。
中午去忆九家吃的饭，恍惚间发现是可能最后一顿在忆九家吃饭，心情竟有点沉重。怀着敬重的心情吃完了这顿饭。
下午则是看看题目顺便唆使还在新疆的选手快跑，结果催着催着 CCF 突然发通知要求 07/23 到校。
走之前大家都拍了几张照
审核也过了我就顺手发一下
实际上主要是想吐槽 Web 出题人题目里夹带私货，但是没什么好地方吐槽。
我当时看 Web1 的时候还不知道这个 HS 是啥ㄟ<(=▔.▔=)>ㄏ，结果下午打美团杯的时候恍然大悟。
有一说一，我也挺喜欢 Hanser 的歌的
以下是正文
Continue reading “MSSCTF 2021 Writeup”给定一棵树，每个结点两个权值 a,b 。
令一个合法的方案为一个点 u 和一个点集 v，满足以下要求
令一个方案的贡献为 $a_u \cdot |b|$
求最大贡献
Continue reading “Luogu P1552 「APIO2012」派遣”在今年五月的时候突然发现 PKU 和 THU 要举办夏令营的消息先后到来
THU 的报名不需要学生做什么，我就没有在意。
PKU 的报名需要填写不少资料还需要去打印并盖章申请书。人不在鸟市，就让教练帮忙了。
随后前往镇海中学参加训练。
天天都有的考试一直持续到 10 号，虽然 THU 方面似乎抛弃了新疆一直没有给我们教练回话，但是 PKU 还是通过了我的申请。
5.13 镇海中学 -> 宁波火车站 -> 余姚北站 -> 余姚中学
在上午考试的时候向镇海教练询问，发现他们将会于明天早上出发。考虑到由镇海到余姚由 1h + 的车程，但我并没有教练或者家长随行，故选择在 13 日自行前往余姚。
Continue reading “PKUSC 2021 游记”正常来说，一个正常的 Oier 是不会碰这种东西
但是我们综合实践小组的组长不知道为啥对这东西出奇的感兴趣， 我就试着理解一下
因为也仅仅是试着理解，如有理论错误还往各位在评论区斧正
本文的代码实现可以在 https://gitee.com/yingziyu/task 看到
Continue reading “玄学，从入门到炼丹 — 初识遗传算法”我并没有找到比较正式的定义，在这里引用 OI Wiki 里的
启发式算法是基于人类的经验和直观感觉，对一些算法的优化。
例子：并查集的按秩合并
基于「减少节点多的子树的处理次数」的思想为主的算法
我们希望节点多的子树处理次数尽可能少，也就是我们希望重儿子的处理次数尽可能少
注意到许多树上问题的处理过程是可延续的，即当前子树的处理完后可以直接将数据移交到父亲节点继续处理
基于这点，我们可以优先处理重儿子，然后直接继承到父亲节点。这样对于一个节点来说，其重儿子只需要处理一次，其轻儿子需要处理两次。
因为从树上任意一条路径上，关键点（即轻儿子）在 $O(\log(n))$ 范围内，所以这东西的复杂度是 $O(n\log(n))$ 的。
Continue reading “树上启发式合并(dsu on tree)简介”即 Codeforces Round #695 (Div. 2)
许久不打变得更菜了…
给定 $n$ 个板子，每个板子上有一个相同的数字 $x ( 0 \leq x \leq 9 )$
随机选择一个数字 $y(1 \leq y \leq n)$，令板子 $i$ 上的数字变成 $ x + |y – i| \pmod 10$
显然，输出 $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" );
}
}
本来把，今年是没有打算写 NOIP 游记的
但是题目实在是太神仙了，所以还是来写写把
传统是周五中午吃香锅，结果拜疫情所赐，现在中午是吃不了香锅了（现在连三楼香锅都没得了<(%>_<%)>）
于是就周三吃了
Rush 到食堂，环视一圈。诶，怎么就我一个高一的来了。
算了，和高三一起恰就行了。