Misaka's Blog

CF877E Danil and a Part-time Job 题解 题目大意 给定一棵具有nnn个节点的树，以111号点为根节点，且每个点的权值都为111或000。现在要求进行mmm次操作，get x代表询问节点xxx的子树中有多少个点的权值是111，pow x代表将节点xxx的子树中的所有节点取反。要求对于每个get指令给出答案。 思路 线段树入门题当然就应该由刚入门的蒟蒻来讲解 对一棵树进行维护显然十分不方便，我们考虑将树的每个节点转换为一个区间，每个叶子节点转化成一个值，对区间的值使用线段树进行操作。用线段树进行区间维护需要满足的前提是区间的可加性，而一棵树所有子节点的和的确满足这个特征。那么如何将一棵树转化成一个线性序列以方便使用线段树维护呢？我们可以利用求解树的dfs序来建立树上的节点与序列下标之间的映射。映射完之后我们就可以把这题当作一道板子来写了。 (1) 求解树的dfs序 关于树的dfs序在这篇炒冷饭的题解里就不详细解释了~~（其实是因为其他大佬讲得比我详细得多）~~，用简单的一句话来说就是在从根节点对一棵树进行dfs时每个节点被遍历到的顺序。以下图所示的一棵树举例 ...

CSP-J 2023 & NOIP 2023 同步模拟赛游记 Day -INF J组初赛前一天。 看了看锣鼓上的模拟卷，觉得自己应该能考上50分，于是摆烂睡觉。讲个笑话，本蒟蒻的第一次CSP-J竟然是在高一，CSP-S甚至怕水平不够没敢报，实在是太菜了。 Day -INF+1 初赛是在bsz考的，主场作战，场上rp大爆发，蒙对了四道选择，估分80pts。 可是出分之后不知道哪挂了2.5pts，最后77.5进了复赛，突然感觉自己又行了。 Day -1 J组复赛前一天。 上锣鼓写了几道往年J组的t1 t2，把之前一直没写过的直播获奖a掉了。很难想象这个时候在一个小时内切掉橙题就能让我觉得自己很牛批。 可是写着写着被CSP-J 2019的公交换乘卡住了，交了两发都零分，大大挫伤了自己的信心，为明天的逆天表现埋下了伏笔。 Day 0 J组复赛去了ssf，看见身边都是比我小还比我强的小朋友倍感难受。谁让我耽误了最珍贵的青春呢。 上机之后发现键盘是机械键盘，好评，但是旁边小朋友打字真的很吵。 先看t1，甚至一开始真的开了个1e9的bool数 ...

P9914 「RiOI-03」匀速相遇 题解（使用umap的暴力非正解） 「RiOI-03」匀速相遇 题目背景 当大家都在加速时，我与你，在人生中的十字路口，匀速地相遇了。 确是惊动我心的一瞥，却是无法逗留的遗憾，我们再次，朝着自己的方向匀速奔跑。下次再见，又会是什么时候呢…… 题目描述 平面直角坐标系上有 n+mn + mn+m 个点，其中： 有 nnn 个 A\rm AA 类点，它们在初始时依次位于位置 (1,0),(2,0),(3,0),…,(n,0)(1, 0), (2, 0), (3, 0), \dots, (n, 0)(1,0),(2,0),(3,0),…,(n,0)。 有 mmm 个 B\rm BB 类点，它们在初始时依次位于位置 (0,1),(0,2),(0,3),…,(0,m)(0, 1), (0, 2), (0, 3), \dots, (0, m)(0,1),(0,2),(0,3),…,(0,m)。 在某一个时刻，A,B\rm A, BA,B 类点同时开始运动。具体地： 对于第 iii 个 A\rm AA 类点，其以 aia_iai​ 个单位长度每秒 ...