Misaka16172's Blog

前言 场上刚开始还天真的以为是个爆搜或者奇怪的背包，浪费了好久。。 思路 看到这个题我们首先想到的一定是暴力 dfs 枚举做菜品 a 还是菜品 b，但复杂度为 O(2ans)\mathcal O(2^{ans})O(2ans)，显然无法通过本题。于是我们来思考一下贪心做法。 实际上，这道题的题意可以简化成 nnn 个不等式，设我们最后做了 xxx 道菜品 a，yyy 道菜品 b，就可以表示成如下形式： a1x+b1y≤q2,a2x+b2y≤q2,⋯ ,anx+bny≤qna_1x+b_1y\leq q_2,a_2x+b_2y\leq q_2,\cdots,a_nx+b_ny\leq q_na1​x+b1​y≤q2​,a2​x+b2​y≤q2​,⋯,an​x+bn​y≤qn​ 并且注意到题意里 a,b,qa,b,qa,b,q 的取值范围都不超过 10610^6106，于是我们可以考虑枚举当前的 xxx 或 yyy（这里选择枚举 yyy），对不等式做变形，得到如下式子： x≤⌊qi−biyiai⌋(1≤i≤n,biyi≤qi)x\leq \lfloor \frac{q_i-b_iy ...

研学游记 Day 1 文章的封面是从萌百上偷的《空奏列车》的曲绘。因为很适合旅行的时候听。 选的是苏杭线。 本来是要跟香香一起去来着，但是香香要和妹妹一起打数学建模，不开心。 还好分房没和老师分到一起。 在车上的几个小时过的很舒服，一直在写题和看《1984》。 可惜的是因为怕打扰坐在旁边的妹妹睡觉而没有去买饭，导致午餐这一块的营养没能补上，最飞屋的一集。 路上把洛谷P4943 密室写掉花了好久，原因是优先队列的优先级写反了，多少有点唐。 在两点的时候到了苏州。 下午去了枫桥，感觉还行吧，除了游船坐起来很舒服以外好像没有什么特别值得说的。 晚饭很丰盛可惜有点凉。 今晚八点甚至有一场abc，但愿晚上不要开会导致阻止我上分。 研学分组把四班其他所有同学分到了一组，把我分到了另一组。这下孤立全班了，玉玉。 晚上的abc爆炸了，c题写了一个小时，果然我只有普及组小学生实力吗。 Day 2 今天去了拙政园和乌镇。 拙政园风景不错，但人真的巨多，跟一群人挤着很有压力。 中午的虾仁很好吃。 在去乌镇的车上本来是打算卷题的，结果对着 SP1684 这道题看了二十分钟没思路，直接就睡着了，很舒服地睡 ...

生活就像流汗黄豆。成绩就像流汗黄豆。OI就像流汗黄豆。全世界都是流汗黄豆。流汗黄豆。 生活就像流汗黄豆。成绩就像流汗黄豆。OI就像流汗黄豆。全世界都是流汗黄豆。流汗黄豆。 生活就像流汗黄豆。成绩就像流汗黄豆。OI就像流汗黄豆。全世界都是流汗黄豆。流汗黄豆。 生活就像流汗黄豆。成绩就像流汗黄豆。OI就像流汗黄豆。全世界都是流汗黄豆。流汗黄豆。 生活就像流汗黄豆。成绩就像流汗黄豆。OI就像流汗黄豆。全世界都是流汗黄豆。流汗黄豆。

日常训练模式已经改为 Misaka’s Daily，因此本页面已经弃用。原内容如下。 从 2024/1/26 开始记录每一道题的罚时。 评分标准：1-10： 1表示代码照着题解打的 5以下代表思路主要由题解启发 7以下代表思路细节参考了题解 8代表参考了讨论区或者下载了数据 9代表看了算法标签 10表示完全独立完成 距离 NOIp 2024 还有\text{距离\ NOIp\ 2024\ 还有} 距离 NOIp 2024 还有 Codeforces *难度未定： *[1300,1500]： CF1914E *1400 9\color{green}99 CF1850F *1300 10\color{green}1010 CF1913C *1300 10\color{green}1010 CF1907D *1400 9\color{green}99 CF1915F *1500 10\color{green}1010 CF1916C *1200 5\color{orange}55 CF1922C *1300 10\color{green}1010 (−2\color{red ...

前言 一眼题没场切，我是普及 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 ...