万物皆虚 万事皆允

0%

发表于 更新于 分类于 Valine：

P4219 [BJOI2014]大融合

题目大意

  • 给定 $n$ 点, $m$ 个操作如下
    • 加入一条边，保证连边的两点原来不连通
    • 询问有多少条路径通过某条边
  • $1 \leq n,m \leq 10^5$

分析

网上大多题解都是使用 LCT 来维护, 然而蒟蒻并不会 LCT, 所以这里提供一种仅使用树链剖分的解法.

不难发现某条边路径数为 $siz_x \times (siz_{root} - siz_x)$, 其中 $x$ 为边所连的点中深度较大的一个, $root$ 为树根, $siz$ 为子树大小.

发现最后 $n$ 个点的形态为一个森林, 所以我们可以先离线下来, 建好森林再倒序删边同时回答询问.

假设删去的边连接 $x, y$, 且 $x, y$ 原来的深度 $dep_x < dep_y$. 删边会影响 $x$ 到根路径上的点的子树大小, 以及以 $top_a$, 其中 $a$ 为 $y$ 所在重链中 $y$ 一下的节点.

我们可以用树剖来维护 $siz$ 和 $dep$, 断开边时, 将 $x$ 到根的路径上的点的 $siz$ 都减去 $siz_y$, 将 $x$ 一下的重链上节点的 $top$ 修改为 $y$. 查询时, $siz_y \times (siz_{root} - siz_y)$ 即为答案.

本做法为真·用树剖来维护树剖, 复杂度为 $O(m\log^2n)$, 还是很快的.

代码

只放出修改和查询时的核心代码, 细节较多, 注意更新 $dep$ 和 $siz$, 完整代码可以看我的提交

修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
fa[y] = 0;
top[y] = query(1, 1, n, dfn[y]).top;
top[x] = query(1, 1, n, dfn[x]).top;
// 更新 top
if(top[y] != y){
	modify(1, 1, n, dfn[y], dfn[y] + dep[tail[top[y]]] - dep[y], y); // 修改 y 所在重链 top
	top[y] = y;
	tail[top[y]] = tail[top[x]];
	tail[top[x]] = x;
}
siz[y] = query(1, 1, n, dfn[y]).siz; // 更新 siz
while(x){
	top[x] = query(1, 1, n, dfn[x]).top;
	mul(1, 1, n, dfn[top[x]], dfn[x], -siz[y]); // 修改 x 到根的 siz
	x = fa[top[x]];
}

查询

1
2
3
4
5
6
7
8
9
10
11
siz[y] = query(1, 1, n, dfn[y]).siz;
top[x] = query(1, 1, n, dfn[x]).top;
// 更新 siz 和 top
while(fa[top[x]]){
	x = fa[top[x]];
	top[x] = query(1, 1, n, dfn[x]).top;;
}
x = top[x];
// x 跳到根
siz[x] = query(1, 1, n, dfn[x]).siz;
ans[i] = 1LL * siz[y] * (siz[x] - siz[y]); //注意 long long

发表于 更新于 Valine：

OI 常用术语

这里会写一些 OI 当中的一些”术语”，想到啥写啥吧。

术语 全称 含义
AC Accept 程序通过所有测试点。
AK ALL KILL 完成了本次题集或比赛的全部题目。
WA Compile Error 程序输出结果与标准答案不符。
TLE Time Limit Exceed 程序运行超时，一般是时间复杂度太高或者死循环。
MLE Memory Limit Exceed 内存使用超过了题目的规定。
RE Runtime Error 程序在运行时出错。
CE Compile Error 程序在编译时出错, 基本语法存在问题。
fst Fail in System Test 指 CF 赛制的比赛中通过测试，而在赛后的 system test 中挂掉。
UB Undefined Behavior 也就是语言的官方标准未定义的地方，在不同系统，编译器上行为可能不一致。
orz 形状像一个跪着的小人，表示膜拜
STO 同上
%%% 同上

发表于 更新于 分类于 Valine：

NFLS 集训日志

5.30

rank: 21/22

score: 100 + 0 + 0 = 100

第一题比较套路, 但是因为 [数据删除] 用了树剖 + 主席树整了 3.9K. 其实可以用树剖 + 树上差分短短几行水过的, 还是经验太少. 但是在写第一题的时候也想到了一个主席树树区间赋值的小 trick, 还是比较有收获的, 不知道有没有用.

第二题动态 DP 没学过, 下午恶补了动态 DP. 动态 DP 学习笔记

发表于 更新于 分类于 ， ， ， ， ， ， ， Valine：

动态 DP 学习笔记

很神奇的一个算法, 结合了线段树, 矩阵, 树剖等多个算法, 老缝合怪了.

简介

动态 DP 是一个可以解决带修改的树上问题的利器. 许多小清新的树上问题带上修改的时候就会非常棘手, 使用动态 DP 就可高效地解决了.

另: 本文不讲解全局平衡二叉树, 因为本人也不会.

前置知识

线段树, 基本的矩阵知识(最起码会矩阵乘法), 树剖.

讲解

由于动态 DP 的特殊性, 我们通过一个模板题来讲解.

例

题目:P4719 【模板】”动态 DP”&动态树分治

题目大意:

  • 给定一棵 $n$ 个节点带点权的树, 第 $i$ 个节点全职为 $a_i$.
  • $m$ 次修改, 每次修改将点 $x$ 的权值改为 $w$, 并输出此时的最大独立集.
  • $1 \leq n,m \leq 10^5, -10^2 \leq w \leq 10^2$

分析

我们发现, 如果没有修改, 这是一道树形 DP 的板子. 设 $f_{i,0/1}$ 表示 点 $i$ 不选 / 选的最大独立集, 则答案为 $\max(f_{1,0}, f_{1,1})$, 有状态转移方程:

但题目要求修改, 我们发现每次修改只会对从 $x$ 到根的链上的节点信息产生影响, 所以我们容易想到用树剖来加快修改. 为了能够实现区间的快速修改, 我们需要对状态转移做出改变, 使其可以通过线段树加速修改.

我们定义状态 $g_{i,0/1}$ 表示 $i$ 不选 / 选时, 轻儿子对 $f_{i,0/1}$ 的贡献, 则有转移方程:

我们发现 $a_i$ 很多余, 于是将其加入 $g_{i,1}$. 则最终的转移方程为:

我们发现这个转移本质是一种递推, 所以我们想到用矩阵来维护. 考虑一个矩阵序列 $F$, 其中 $F_i$ 为:

我们希望其可以通过矩阵乘法来转移, 但我们发现转移方程中有 $\max$ 运算阻止我们进一步转化, 于是我们大胆定义一种矩阵运算 $*$ 满足如下规则:

则有如下转移:

我们发现转移方程中一个数字只与 $f$ 有关, 另一个只与 $g$ 有关, 而且转移符合结合律, 我们可以用线段树快速计算一段区间的 $g$. 至于怎么想到的, 只能说当初发明这个算法的人的天才般的大脑了.

整个算法的精髓就在于此了, 我们可以通过树剖 + 线段树修改一段重链上的矩阵 $*$. 由于转移是由深度由大到小转移的, 所以我们需要将重链的末尾 $tail$ 保存方便使用.

一个小 trick 是结尾的矩阵可以表示为 $\begin{bmatrix} 0&a_i\\\ 0&-\infty \end{bmatrix} $, 这样就可以将矩阵转移统一为 $g$, 不用区分 $f$ 了.

如果还有不懂的可以看代码.

代码

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<stack>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define frep(i,a,b) for(int i=a;i<(b);++i)
#define drep(i,a,b) for(int i=a;i>=(b);--i)
#define mid ((l + r) >> 1)
#define ls (p << 1)
#define rs (p << 1 | 1)
typedef long long ll;
typedef unsigned long long ull;
#define Maxq priority_queue<int,vector<int>,greater<int> >
using namespace std;
int mylog(int a) {
	int ans=0;
	if(a&0xffff0000) {
		ans+=16;
		a>>=16;
	}
	if(a&0x0000ff00) {
		ans+=8;
		a>>=8;
	}
	if(a&0x000000f0) {
		ans+=4;
		a>>=4;
	}
	if(a&0x0000000c) {
		ans+=2;
		a>>=2;
	}
	if(a&0x00000002) {
		ans+=1;
		a>>=1;
	}
	return ans;
}
inline int read() {
	register int a=0,b=0;
	register char c;
	c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-')b=1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		a*=10;
		a+=c-'0';
		c=getchar();
	}
	return b?-a:a;
}
const int MAXN = 2e5;
const int INF = 0x3f3f3f3f;
struct Matrix{
	int c[2][2];
	struct Matrix operator * (Matrix b){
		Matrix tmp;
		tmp.c[0][0] = max(c[0][0] + b.c[0][0], c[0][1] + b.c[1][0]);
		tmp.c[0][1] = max(c[0][0] + b.c[0][1], c[0][1] + b.c[1][1]);
		tmp.c[1][0] = max(c[1][0] + b.c[0][0], c[1][1] + b.c[1][0]);
		tmp.c[1][1] = max(c[1][0] + b.c[0][1], c[1][1] + b.c[1][1]);
		return tmp;
	}
};

vector<int> nxt[MAXN];
int a[MAXN], f[MAXN][2];
struct Matrix tree[MAXN], g[MAXN];
int siz[MAXN], dfn[MAXN], id[MAXN], dep[MAXN], top[MAXN], tail[MAXN], son[MAXN], fa[MAXN], end1;
void dfs1(int p, int ff){
	fa[p] = ff;
	siz[p] = 1;
	dep[p] = dep[fa[p]] + 1;
	f[p][1] = a[p];
	int maxx = 0;
	for(auto x : nxt[p]){
		if(x == fa[p]) continue;
		dfs1(x, p);
		siz[p] += siz[x];
		if(siz[x] > maxx){
			maxx = siz[x];
			son[p] = x;
		}
		f[p][1] += f[x][0];
		f[p][0] += max(f[x][0], f[x][1]);
	}
	return;
}
void dfs2(int p){
	dfn[p] = ++end1;
	id[end1] = p;
	if(!top[p]) top[p] = p;
	tail[p] = p;
	g[p].c[0][1] = a[p];
	g[p].c[1][1] = -INF;
	if(son[p]){
		top[son[p]] = top[p];
		dfs2(son[p]);
		tail[p] = tail[son[p]];
	}
	else return;
	for(auto x : nxt[p]){
		if(x == son[p] || x == fa[p]) continue;
		dfs2(x);
		g[p].c[0][0] += max(f[x][0], f[x][1]);
		g[p].c[0][1] += f[x][0];
	}
	g[p].c[1][0] = g[p].c[0][0];
	return;
}
void build(int p, int l, int r){
	if(l == r){
		tree[p] = g[id[l]];
		return;
	}
	build(ls, l, mid);
	build(rs, mid + 1, r);
	tree[p] = tree[rs] * tree[ls];
	return;
}
void modify(int p, int l, int r, int x){
	if(l == r){
		tree[p] = g[x];
		return;
	}
	if(dfn[x] <= mid) modify(ls, l, mid, x);
	else modify(rs, mid + 1, r, x);
	tree[p] = tree[rs] * tree[ls];
	return;
}
struct Matrix query(int p, int l, int r, int x, int y){
	if(x <= l && r <= y) return tree[p];
	if(y <= mid) return query(ls, l, mid, x, y);
	else if(x > mid) return query(rs, mid + 1, r, x, y);
	else return query(rs, mid + 1, r, x, y) * query(ls, l, mid, x, y);
}
int main(){
	int n = read(), m = read();
	rep(i, 1, n) a[i] = read();
	frep(i, 1, n){
		int x = read(), y = read();
		nxt[x].push_back(y);
		nxt[y].push_back(x);
	}
	dfs1(1, 0);
	dfs2(1);
	build(1, 1, n);
	rep(i, 1, m){
		int x = read(), w = read();
		g[x].c[0][1] += w - a[x];
		a[x] = w;
		while(x){
			struct Matrix last, now;
			last = query(1, 1, n, dfn[top[x]], dfn[tail[top[x]]]);
			modify(1, 1, n, x);
			now = query(1, 1, n, dfn[top[x]], dfn[tail[top[x]]]);
			x = fa[top[x]];
			g[x].c[0][1] += now.c[0][0] - last.c[0][0];
			g[x].c[0][0] += max(now.c[0][0], now.c[0][1]) - max(last.c[0][0], last.c[0][1]);
			g[x].c[1][0] = g[x].c[0][0];
		}
		Matrix ans = query(1, 1, n, 1, dfn[tail[1]]);
		printf("%d\n", max(ans.c[0][0], ans.c[0][1]));
	}
	return 0;
}

发表于 更新于 分类于 Valine：

5.1 基本恒等式 BASIC IDENTITIES

$\tbinom{n}{k}$ 为二项式系数, 读作”$n$ 选取 $k$”. 组合解释: 从 $n$ 个元素的集合中选取 $r$ 个元素的子集的个数.

高中学到的组合数定义为

我们称 $n$ 为上指标(upper index), 而称 $k$ 为下指标(lower index). 组合解释指标仅限于取非负整数, 但是除了组合解释, 二项式系数还有许多用途, 所以我们可以对它推广. 事实上, 最有用的是允许上指标取任意实数(甚至复数), 下指标取任意整数. 这样, 二项式系数定义如下:

发表于 更新于 分类于 Valine：

具体数学笔记

前言

整了本具体数学读读, 把学到的写下来便于复习. 不会按照书的顺序读, 先读自己想看的, 但会把坑留下慢慢填.

持续更新, 可能会咕.

第1章 递归问题

第2章 和式

第3章 整式函数

第4章 数论

第5章 二项式系数

5.1 基本恒等式

第6章 特殊的数

第7章 生成函数

第8章 离散概率

第9章 渐近式

发表于 更新于 Valine：

Test

著名的质能方程 $\eqref{eq1}$ 由爱因斯坦提出 …

发表于 更新于 分类于 Valine：

如果注定要落下, 那就趁现在努力发光. ——SXOI2022 游记

本来不打算写的, 但现在进队了, 还是写了国赛前的最后一个游记吧. 真情实感, 望读者不要以知道结局的态度看故事.

背景

NOIP 通过一系列骚操作和一点实力拿了全省第五, 虽然和前面的四位来说差距不是一点半点. WC 通过河里的时间规划拿了压线 Cu. NOI online 开摆.

山西已经弱出新低了, 省队就 6 个, 去掉女生就 5 个, 相当于我压线. 而且没有 1/3 限制, 这… 某附中直接省队变校队好吧. 今年可谓天时地利人和一个都没有.

战况

day-1month

由于疫情在家上网课, 省选由 4.4 -> 4.15 -> 遥遥无期. 听说有可能按 NOIP, 是不是可以压线最后一名进队了?

听说和山东一起举办, 猪国杀, 立体图.

不要和山东, 让我躺进队吧… 以我的水平再考省选说不定就掉出省队了. 哎……

官宣了, SDOI

预计开学后一周省选, 省选上下午个 4.5h, 这是人能想出来的? 咱不能办就别办, 建议取消! 虽然时间长对我这种经常熬夜的人来说有一定优势.

开学了

day-5

开学了, 每天晚上最后一节晚自习可以到机房刷题. 开始狂补字符串知识, 发现连 KMP 都不会写了.

教练问我系统, 我求稳选了 Windows, 后面来看我这个决定太对了.

考场是笔记本, 心凉了一半, 问教练可不可以自己带键盘, 笔记本键盘有些连 end 都没有. 貌似有学校申请带键盘了.

day-4

理解了 AC 自动机, 但没有写代码.

day-3

过了普通的 AC 自动机, 简化代码后十分巧妙. 加强版貌似不难写, 明天 AC.

day-2

过了二次加强版, 优化较容易想到.

day-1

尝试打了些板子就睡了, 明天感受一下 9h 马拉松.

day0

按照省选时间起床, 给自己整了几道模板题目.

怎么连主席树都打不出来了? 就这还省选? 洗洗睡吧.

day1

5.15 注定是难忘的一天.

早上五点起床没胃口, 很有精神, 希望可以发挥好.

很早到了清创, 考点就我一个人, 一会儿来了个吕梁的选手, 看得很强, 甚至自己带了键盘. 我也带了, 万一让带呢?

进考场的时候问是否让带键盘, 得到了肯定的答复, 属于是带善人了😍, 早知道带青轴了.

解压密码很复杂, 包含 SDOI, SXOI, NOI2022 等元素.

开题就给爷吃了一惊, Windows 系统 lemon 测评, 那我用的岂不是最正宗系统? 用 Linux 岂不是大怨种? ❤️

第一题是个双序列问题, 昨天洛谷灌水区有一道也是双序列的个人想的题, 不会是另一个 FJOI 吧. 连最低的部分分都不会, 感觉树形数据结构不好维护, 应该是根号的奇技淫巧. 考到一般说第一题改为 7s, 进一步加深我的判断. 一个小时过去不知道怎么优化, 写了 O(nq) 的暴力走了.

第二题一个不知道什么题. 数位 DP? 先跳了.

第三题字符串. 好耶, 上周才看. 然而写了 AC 自动机发现用不着, 用 trie 就行了, 结果发现空间不够, 改成哈希又太慢. 一下给爷整不会了.

收题的时候工作人员跟我说不能用自己的键盘, 我??? 最后解释清楚后是他们搞错了, 可以带.

一试得分: 20 + ? + ? = ? 这还打个毛!😡

发现大家大多都不会, 甚至有人说第一题写了 O(n ^ 2 * q) 不稳, 给爷整笑了🤣.

其实我心态挺好的, 觉得上午考的都是不会的, 下午就全是擅长的 DP 和树论了.

中午吃饭, 饭吃完发现汤没喝, 先睡觉养足精力.

一睁眼又该开考了, 凭借我多年在机房睡觉的经历, 很快调整好了状态. 看着别人睡眼惺忪的样子, 一瞬间有点感谢 9h 马拉松.

压缩包只看见两个文件夹, 完了, 不会是提答吧, 没练过啊!

解压后发现是传统题, 有一个题没有样例.

第一题最大独立集, 忘了, 当时有点慌了.

先看第二题, 不卡空间是树剖模板题, 可是卡了. 研究了一下快读和数据的特殊性质, 发现可用空间微乎其微. 发现根号大小的数组随便开, 于是先把链状的 30pts 用根号分块拿了. 考虑将这一思想拓展无果.

本来都打算放了, 但感觉分不够, 虽然题目不是给人写的, 但这点分数进队有点困难, 于是强迫自己看第一题.

发现第一题跟最大独立集其实没啥关系, 先把 k = 1 的点写了, 又把 n <= 8 的点用暴力写了.

看着状态转移方程写了一个 O(n ^ 5) 大暴力 DP, 在考试前最后 10min 调出来了, 感觉优化的空间很大, 但没时间了.

交了题笑着走出了考场, 一瞬间感觉进不进队都不重要了, 这种感觉如同我当年无数次重要的考试一样, 小升初, 中考, 这是竭尽全力不计结果的感觉. 我已经把能做到做到最好, 我一直相信我的运气一向很好, 奇迹终将发生.

玻璃幕墙外, 夕阳一点点落下, 染红了西山, 染红了考场内的一切, 也染红刚出考场的选手们(可能选手们这时候更喜欢绿荫吧), 把他们头上的汗水照的晶莹剔透, 把他们的影子一点点拉长. 似乎只有我注意到了这难得的美景, 大家都只是在急切的交流做法, 问候出题人.

我知道, 这里面很多人都是我与他们的最后一次见面了, 其中大部分我都不认识, 但我们都曾为了相同的目标拼搏过.

教练让我, lsh, djl 一起合影留念, 于是我们迎着夕阳留下了可能是最后一次并肩作战的记忆.

我的 OI 生涯如同这落日一样, 有过光鲜, 如今正一点一点走向黄昏.

夕阳无限好, 只是近黄昏.

即便是夕阳, 也在努力地照亮大地啊.

如果注定要落下, 那就趁现在努力发光.

Y老师送我们回家, 还给我们仨买了奶茶, 以前从来没喝过欸, 在这种时候, 一杯奶茶简直是享受.

一路上我们一起聊题目做法, 聊题目的难度, 聊未来的规划, 不知不觉到家了.

回到家边找数据边吃饭, 吃完饭躺在床上, 好困, 可我还有作业, 先眯一下吧…

day2

水了水知乎发现出题人正在在线讲解爬.

晚上本来打算去机房做生物思维导图, 结果省选出分了.

奇迹真的出现了? 翻盘了, 不过有人因为用 pbds 抱灵了.

果然上午就拿了 35pts, 但下午翻盘了, 多亏了我打满暴力的指导方针.

lsh 退役了, 只能祝他文化课碾压我吧.

未完待续

后记

犹忆当年 SXOI2021, 我因为执着正解和稀烂的 NOIP 没能进队, 当时附中课件的铃声让我记忆犹新, 后来我才知道那是卡农 (Canon), 从此我喜欢上了卡农, 喜欢上了他如同诗经一般循环往复的旋律. 卡农也是唯一一支可以让我只要听见旋律就会落泪的曲子. 过去一年, 听到这旋律, 我的思绪总会回到那个在附中 SXOI2021 考场的上午.

但我落泪不是因为省选的失利, 而是我从卡农当中听出了我的 OI 生涯. 我的 OI 生涯当中, 除了普及组的奖, 没有一个奖是首次参加就拿到的, 这使我可以深深体会到卡农想表达的那种循环中不断加深的感情. 在 SXOI2022 前, 每当我做不下题时, 打开收藏的卡农, 热泪盈眶, 继续充满动力的刷题. 如今, 终于, 实现了进省队的愿望.

那么, NOI2022, 最后的音符.

发表于 更新于 Valine：

hexo博客同步方法

今天终于实现了随时写博客的想法, 对 git 的使用也有了更深的了解. 于是写一篇博客来记录, 以免以后忘记如何同步.

前置

  • git
  • node.js
  • 一个 hexo 博客

开整

上传

首先需要在已经有 hexo 博客的电脑 ( 记为 A 端 ) 的博客目录下使用一下命令

1
2
3
4
5
6
git init #git 命令初始化
git remote add origin https://github.com/用户名/你的GitHub用户名.github.io.git #添加仓库地址
git checkout -b 分支名 #新建分支并切换到新建的分支
git add . #添加所有本地文件到git
git commit -m "这里填写你本次提交的备注，内容随意" #git提交
git push origin 分支名 #文件推送到hexo分支

需要注意的是, 由于 GitHub 政策变更现在已经不能通过地址来 push, 需要 ssh 完成. 因此上文地址应改为 GitHub 仓库的 ssh , 可以从仓库页面 -> code -> ssh 复制. 分支名可以自己定, 一般为 hexo.

下载

在想要写博客的电脑 ( B 端 ) 使用如下命令

1
2
3
4
5
git clone -b 分支名 https://github.com/用户名/你的GitHub用户

sudo npm install -g hexo-cli #安装hexo,注意这里不需要hexo初始化,否则之前的hexo配置参数会重置
sudo npm install #安装依赖库
sudo npm install hexo-deployer-git #安装git部署相关配置

博客便从 GitHub 上同步至了本地, 然后重新配置 hexo 写新的博客. 写完后再通过以下命令上传至 GitHub.

1
2
3
git add .
git commit -m "这里填写你本次提交的备注，内容随意"
git push origin 分支名

在A端使用

1
git pull

这样，你的数据就全部同步到 A 端了.

发表于 更新于 分类于 Valine：

NOIP2021退役记

视频游记

战况

day-14

为了更好准备NOIP翘掉了每天晚上定时作业到机房刷题. (弱省不重视竞赛也没有办法长期停课. 翘课已经是最好的结果了)

day-7

翘课一周, 进步明显, 希望可以天天翘课哎

day-2

期中考试数学一题卡住直接去世, 后面考试也没有太复习, 重点还是NOIP.

day-1

期中考完把下午的课翘了. 关于机房有老师上课我连听了四节通用这件事

day1

  • 7:00 想着早点起来看看板子结果睡过头了，只好草草看看kmp(貌似没有考,也有可能我太菜没看出来)
  • 7:30 草草吃完饭去往太原五中
  • 8:00 准时到达五中. 天气灰蒙蒙的, 心不在焉地洛谷签到, 忘了是什么了貌似是大凶.
  • 8:10 候场, 据说停电了.好耶 恐禁三. 不会扣除省选名额吧. (CSP2019江西)
  • 8:30 有电了, 准时开考. 考完才发现有发电机, 后勤工作不错.
  • 10min 第一题就不会, 我就是个伞兵. 先看第二题吧.
  • 45min 50分貌似是个状压. 想法挺多但都不太行, 下来发现很接近正解了. 为了得分先写了状压. 因为把权值当成加调了40分钟就离谱. 不过好歹有分了.
  • 1hour30min 回头看t1, 发现是个简单的筛子, 但不会优化到线性, 试图套素数筛也失败了.
  • 2hour15min 开t3, 发现变换相当于交换差分, 问题转化为排列差分使得方差最小, 感觉要把大的放两边, 小的放中间. 试了试离答案很接近但不知道怎么更加接近, 貌似要模拟退火, 但不知道怎么寻找更优解. 还是太菜了, 打了30分暴力走人
  • 3hour30min t4看到题目背景已经不想做了, 骗分走人
  • 4hour 查重定向, 文件.
  • 1:00 出来问别人怎么做的. djl说他t1写出线性筛了, 看来我应该被优先队列了. 但别人好像没人写t2 50分状压. 然后合影留念. 貌似*大名校都集齐了.

期望

70 + 50 + 30 = 150

总结反思

感觉题目难度不是特别变态, 但是t4题目背景不太友好, 个人不喜欢满满一页题目背景. 相比之下前三题十分友好. 主要还是自己太菜

关于策略感觉还是可以的, 开场选t2也是不错的选择, 做t2打开了思路.

不足是后期时间有点拖延导致后期得分效率低, 应该多考虑考虑t2或t1, 不过这都是后话了.

希望不挂分. OI生涯还能再续.