Misaka's Blog

前言 一眼题没场切，我是普及 3= 小飞屋，罚自己写篇题解。 题意 平面直角坐标系上有 NNN 个点，每个点 iii 的初始坐标为 (i,0)(i,0)(i,0)。 现在进行 QQQ 次操作： 1 C 代表把编号为 111 的点向方向 CCC 移动一个单位长度（R 代表 xxx 轴正方向，L 代表 xxx 轴负方向，U 代表 yyy 轴正方向，D 代表 yyy 轴负方向），同时对于每个编号大于 111 的点 iii，将点 iii 移动到点 i−1i-1i−1原先的位置； 2 x 代表查询编号为 xxx 的点当前的坐标。 思路 方法 111：O(NQ)\mathcal{O}(NQ)O(NQ)，暴力更新坐标 对于每次操作 1 从点 111 开始暴力更新每个点 iii 的坐标即可。 方法 222：O(Nk)\mathcal{O}(Nk)O(Nk)（kkk 代表操作 1 的次数），暴力递推 我们可以用一个二维数组 f1[N][2]f1[N][2]f1[N][2] 记录点 111 在每一次操作 1 后的坐标，初始值 f1[0]={1,0}f1[0] = \{1,0\}f1[0] ...

前言 我场切了，看来这场题目顺序很诈骗，明明 C 和 D 都没写出来。 等等，这道题竟然评绿了？ 好激动，第一次场切绿，所以来写篇题解。 题意 给定一个 1∼n1\sim n1∼n 的排列 ppp。你需要构造一个长度为 nnn 的序列 aaa，满足： 序列 aaa 中的每个元素均为不大于 nnn 的正整数； 不存在有序整数二元组 (l,r)(l,r)(l,r)，满足 1≤l≤r≤n1 \le l \le r \le n1≤l≤r≤n 且 ∑i=lrai=∑i=lrpi\sum\limits_{i=l}^r a_i=\sum\limits_{i=l}^r p_ii=l∑r​ai​=i=l∑r​pi​；或报告无解。 其中，1∼n1\sim n1∼n 的排列指满足所有不大于 nnn 的正整数恰好出现一次的序列。 数据范围 设 ∑n\sum n∑n 表示单个测试点中 nnn 的和。 对于所有数据，1≤T≤50001 \le T \le 50001≤T≤5000，2≤n≤1062 \le n \le 10^62≤n≤106，∑n≤106\sum n \le 10^6∑n≤106，保证 p ...

题意 有nnn枚硬币，第iii枚硬币有pip_ipi​的概率正面朝上，有1−pi1-p_i1−pi​的概率反面朝上。 扔完所有硬币，求正面朝上的银币数比反面朝上的银币数多的概率。 思路 是一道期望dp的入门题，其实比起dp把他叫做递推更合适。 状态设计 这道题的状态设计需要仔细思考，将状态f[i][j]f[i][j]f[i][j]设为前iii个硬币中有jjj个以上正面朝上的硬币显然不好，转移过于复杂。 于是我们考虑将状态设计为前iii个硬币中正好有jjj个正面朝上的硬币，最后再将f[n][⌈n+1⌉2]f[n][\frac{\lceil n+1 \rceil}{2}]f[n][2⌈n+1⌉​]至f[n][n]f[n][n]f[n][n]的值累加起来即可。 转移方程 那状态转移方程如何编写呢？一个硬币iii的状态一定只有两种可能，有pip_ipi​的概率正面朝上，1−pi1-p_i1−pi​的概率反面朝上。 要让前iii个硬币里有正好jjj个正面朝上，也就有两种可能： 前i−1i-1i−1个硬币里有j−1j-1j−1个正面朝上，并且第iii个正面朝上，概率为f[i−1][j−1]×p[ ...

题意 有一排花，共 nnn 个，第 iii 个的高度是 hih_ihi​​ ，权值是 aia_iai​ ，保证高度互不相同。现在拿走一些花，使剩下的花高度单调递增，问剩下的花权值之和最大是多少。 数据范围与约定： 1≤n≤2×105，1≤hi≤n，1≤ai≤109，h1,h2,⋅⋅⋅,hN1 \leq n \leq 2 \times10^5，1\leq h_i \leq n，1\leq a_i\leq 10^9，h_1,h_2,···,h_N1≤n≤2×105，1≤hi​≤n，1≤ai​≤109，h1​,h2​,⋅⋅⋅,hN​的值均不相等。 前置知识 前置知识：线段树、动态规划 思路 看到这题我们能想到一个很显然的dp做法：设f[i]f[i]f[i]为取前iii朵花中的一些花，且第iii朵最高时能取得的最大权值，则f[i]=max{f[j],j<i,h[j]<h[i]}+a[i]f[i]=max\{f[j],j<i,h[j]<h[i]\}+a[i]f[i]=max{f[j],j<i,h[j]<h[i]}+a[i]，在每次取到iii时再遍历一次f[1 ...

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

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数组，险些爆零，发现暴力时间复杂读太烂 （其实真实原因是我当时码力太烂连暴力 ...

学oi这么多月了第一次场切黄题（尽管不会哈希做法用的是侥幸没被出题人卡掉的umap），所以打算写篇题解，顺带着测试一下自己blog的可用性（反正也没有人看）（连LaTeX都不支持可用个鬼啊） 根据题面，假设两个点在第ttt秒相遇，则编号为iii的AAA类点在第ttt秒时的坐标为(i,ai⋅t)(i,a_i\cdot t)(i,ai​⋅t)，编号为jjj的BBB类点在第ttt秒时的坐标则为(bj⋅t,j)(b_j\cdot t,j)(bj​⋅t,j)。显然，当同时满足i=bj⋅ti=b_j\cdot ti=bj​⋅t且j=ai⋅tj=a_i\cdot tj=ai​⋅t时，两点能在第ttt秒相遇。可以把上式变形为t=ibj=jait=\frac {i} {b_j}=\frac {j} {a_i}t=bj​i​=ai​j​。 到这里就是第一个坑点了，t不一定是一个整数，所以不能直接计算ibj\frac {i} {b_j}bj​i​和jai\frac {j} {a_i}ai​j​的值，c++中除法的自动取整会把两个互不相等的ttt取成同一个整数。于是可以想到把等式两边同时乘以bj⋅aib_j ...