方差 题解noip 2021
考场(NOIP2023模拟4联测25)
T1 peter的烟的加强版,算水题吧,一眼顶针 T2 从小的推到大的???从一个点的合法情况推多个点的合法情况??? 也许和菜狗可爱内一场的菜一样用个链表维护???】 发现性质当两个点连边,则两个点中间的点可以直接扔去不管 也许是将大问题一点一点缩小到小问题??? 转化题意为:对于一个序列,每次消 ......
CF777B题解
分析 思考对于 \(M\) 的每个数而言,贡献是一定的,它最多只能换掉一个数。 那么贪心地能换就换,但是如果换小的可能会导致更小的数换不掉,那么就换能换的最大的,这样不会干扰只能换小数的其他数,能换这个数的可以去换其他数,如果连其他数都换不掉说明这两个数等效,换谁都一样,所以这样换一定是最优的。 如 ......
P8867 [NOIP2022] 建造军营
缩点 首先考虑对于一个边双内的边是可以任意看守或者不看守的,所以可以缩点,这样缩完点的图就成了一棵树。 对于缩完点后的每一个边双,我们设 \(E_{i}\) 表示边双 \(i\) 内的边的个数,\(siz_{i}\) 表示边双内点的个数。 那么只考虑一个边双的情况的话,边能任选的方案数就是 \(2^ ......
CF777A题解
分析 发现操作 \(6\) 次后就会回到初状态,于是将状态打表,将 \(n\bmod6\) 即可。 代码 #include <iostream> using namespace std; constexpr int MAXN(1000007); int a[6][3] = { {0, 1, 2}, ......
CF888G题解
分析 看到异或不难想到 01Trie。 不难想到,当两个数的值相等的时候,我们可以当这两个点是一个点,因为连边的费用为 \(0\)。 那么对于一个序列 \(n\),若存在 \(m\) 种不同的权值,那么在 Trie 树上子节点数为 \(2\) 的节点就有 \(m-1\) 个(因为如果一个数新加进来与 ......
NOI2021 路径交点
洛谷传送门 LOJ 传送门 两条路径的交点数量只和起点数量有关。容易发现是终点排列的逆序对数的奇偶性。求一个 \(f_{i, j}\) 表示从第 \(1\) 层的第 \(i\) 个点到第 \(k\) 层的第 \(j\) 个点的路径数量,对这个矩阵求行列式即可。 对于相交的路径数不用考虑,因为总存在和 ......
P3400 仓鼠窝 题解-单调栈典题
20231026 P3400 仓鼠窝 题解-单调栈典题 Statement 传送门 输出 01 矩阵中不含 0 的子矩阵的个数。\(n,m \le 3000\) Solution 很妙的做法,典题,于是写了题解。 做法也很简单,就是你枚举每一个节点作为右上角的点的方案数, 发现其实有很多无用的点,比 ......
P8865 [NOIP2022] 种花 题解
前言 去年多测不清空导致即便 CCF 放过了我的 \(O(n^2 m)\) 的代码但依然挂成了 \(0pts\)。 当时看清空数组后能过 CCF 数据就没再管。 时隔 \(1\) 年,重做这道题写了 \(O(nm)\) 的正解,终于完成了当年的心愿。 \(O(n^2 m)\) 思路 想到计算方案的话 ......
SP4082 MBLAST - BLAST 题解
几万年前做的 dp 题了,有亿点点水 题意简述 求一个字符串添加多少个空格距离最小 解法 求距离最小,可以考虑动规,其实这题的写法和最长公共子序列的写法类似。 我们设 \(f(i,j)\) 表示 \(a[1] \sim a[i]\) 和 \(b[1] \sim b[j]\) 的距离 不加空格的时候为 ......
CF596B Wilbur and Array题解
同步发布与洛谷(太懒了不想写东西直接搬过来了(((逃 ) 原题链接 简单贪心。 题意 求一个起始全为 \(0\) 的数列 \(a_1,a_2 \cdots a_n\) 每次可以选择一个数 \(i\) 使 \(a_i \cdots a_n\) 都加上或减去 \(1\),求修改成给定的序列 \(b_1, ......
[AGC061A] Long Shuffle 题解
题意 给定一个满足 \(A_i=i\) 的排列 \(A\),求对其进行一次 \(\mathrm{shuffle}(1,N)\) 操作后其第 \(K\) 项的值。其中 \(\mathrm{shuffle}(L,R)\) 的定义如下: 若 \(R = L + 1\),那么交换 \(A_L\) 和 \(A ......
NOIP2023模拟3联测24-博弈树
NOIP2023模拟3联测24-博弈树 目录NOIP2023模拟3联测24-博弈树题目大意思路code 题目大意 \(Alice\) 和 \(Bob\) 又开始玩游戏了: 给定一颗 \(n\) 个节点的树,\(Alice\) 和 \(Bob\) 随机选择一个节点作为起点放上棋子,由 Alice 先手 ......
NOIP 2020
NOIP 2020 xjb乱做 时间:7:30~9:50 分数:100+80+0+40 T1 [NOIP2020] 排水系统 根据题目所给信息 有若干点没有出度 有若干点没有入度 且图不成环 一眼拓扑 直接做就可以了 (感觉应该不会炸long long罢 但为了保险起见仍然用的__int128) # ......
P4678 [BalticOI 2005] Bus Trip 题解
P4678 [BalticOI 2005] Bus Trip 题解(RE:题解再改造!!) 贴码 #include<bits/stdc++.h>#define MAXN 500010using namespace std;//ifstream is("trip.in",ios::in); //ofs ......
The 2021 ICPC Asia Macau Regional Contest
\(C. Laser Trap\) 根据题意不难判断出需要极角排序,然后对于每个点寻找更小的一个 \(180\) 度的点数。即使听说是用双指针实现查找依旧没什么思路。后来看了别人的实现方法发现确实比较简单,甚至只需要维护极角就可以了。 const long double pi=acosl(-1); ......
CF888F题解
分析 手玩样例发现连一条边实际上是将一个多边形分割成两个部分,而且不能在这两个部分直接连边,发现这两个部分是完全独立的,于是考虑区间 DP。 设状态 \(f_{l,r}\) 表示将 \([l,r]\) 区间连成树的方法数量。 那么存在两种转移,一种是 \(l,r\) 间不直接连边,这样中间的点都需要 ......
P9753 [CSP-S 2023] 消消乐 题解
考虑预处理。 处理 $a$ 数组,每次走到一个位置 $i$,往前搜索。 当前位置不等于 $i$ 则通过这个位置继续往前查找。一直到当前位置等于 $i$,或者到达最前端则停止。 接下来进行第二次处理。 由于已经对 $a$ 进行过预处理,在计算时只需要从有值的点分别往前统计即可。 最后求一遍和。 /* ......
CF1586I 题解
CF1586I 题解 传送门 更好的阅读体验 简化题意:有 $n\times n$ 的网格,你需要进行黑白染色,使得每个格子的颜色恰好与 2 个与其四联通的格子的颜色相同,其中有些位置已经确定,问是否有解及是否有唯一解。 思路: 很神仙的构造题。 先从特殊的地方入手。对于 4 个角,它们只和 2 个 ......
Sudo 缓冲区溢出漏洞(CVE-2021-3156)复现-CentOS7
2021-01-26,MITRE 公开披露了一个由 Sudo 堆缓冲区溢出导致的本地提权漏洞——CVE-2021-3156,MITRE 相关页面显示,1.9.5p2 版本之前的 Sudo 存在该问题。利用该漏洞,普通用户可以将自身身份提升为 root。判断你的 Linux 是否受该漏洞影响,一个简单 ......
NOIP 模拟赛合集
CSP考完打算写题解了 写题解有啥用呢,大抵是总结吧。。 总不能让博客一直没东西 第一场走丢了(确信) 10.25 模拟2 mp场 100+70+0+0=170 pts rk13 T3暴力 INT_MAX,给我输出了mp的题解密码(蚌),T4暴力没时间测就交了。 T1挺能签的,大部分时间花在 T2 ......
[HDU 3483] A Very Simple Problem 题解
题目描述 快速求出下面式子的值: \[\left(\sum\limits_{k=1}^{N}k^{x}x^{k}\right)\bmod M \]其中 \(1 ≤ N, M ≤ 2\times 10^9\), 并且 \(1 ≤ x ≤ 50\)。 题解 (solution) 对于该类题目,\(N\) ......
P5537 【XR-3】系统设计 题解-哈希+线段树二分
20231026 P5537 【XR-3】系统设计 题解-哈希+线段树二分 这个东西怎么会和哈希有关?!直接寄。 Statement 这个系统首先需要输入一棵 \(n\) 个点的有根树和一个长度为 \(m\) 的序列 \(a\),接下来需要实现 \(q\) 个操作。 操作分两种: 1 x l r 表 ......
「NOIP2016 提高组」天天爱跑步题解
题目背景NOIP2016 提高组 Day1 T2 题目描述小 C 同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。 这个游戏的地图可以看作一一棵包含 n 个结点和 n-1 条边的树, 每条边连接两个结点,且任意两个结 ......
2023noip赛前20天冲刺 Day11 Day12
死了,自闭了。 不写力。 我有玉玉症。 我有玉玉症。 我有玉玉症。 我有玉玉症。 我有玉玉症。 我有玉玉症。 我有玉玉症。 我有玉玉症。 我有玉玉症。 我有玉玉症。 我有玉玉症。 我有玉玉症。 我有玉玉症。 我有玉玉症。 我有玉玉症。 我有玉玉症。 我有玉玉症。 我有玉玉症。 我有玉玉症。 我有玉玉 ......
题解 QTREE7 - Query on a tree VII
题目描述 一棵树,每个点初始有个点权和颜色。 0 u :询问所有 \(u,v\) 路径上的最大点权,要满足 \(u,v\) 路径上所有点的颜色都相同。 1 u :反转 \(u\) 的颜色。 2 u w :把 \(u\) 的点权改成 \(w\) 。 \(color_i\in[0,1]\),\(w_i\ ......
CF1746F Kazaee 题解
对集合的一些判断可以考虑随机化哈希。 给每个数随一个权,如果集合 \(S\) 中每个数的出现次数都是 \(k\) 的倍数,那 \(S\) 中元素的权值之和就会是 \(k\) 的倍数,否则会是一个在 \([0,k)\) 中随机的值。 也就是说如果这个集合不满足要求,我们做一次这个检测,有 \(\fra ......
【洛谷 9231】 [蓝桥杯 2023 省 A] 平方差
# [蓝桥杯 2023 省 A] 平方差 ## 题目描述 给定 $L,R$,问 $L \leq x \leq R$ 中有多少个数 $x$ 满足存在整数 $y,z$ 使得 $x=y^2-z^2$。 ## 输入格式 输入一行包含两个整数 $L,R$,用一个空格分隔。 ## 输出格式 输出一行包含一个整数 ......
考场(NOIP2023模拟3联测24)
T1 质因数,怎么分解呢。。。。。。 奥,能不能用欧拉筛,真的行,欧拉筛,启动!!! 喜报,我输出T了 喜报,我会打快输 T2 奥,是不是树的直径,具体咋写呢。。。分情况讨论? 1.在树的直径上。。。不会QAQ 问题可以简化为如先手可以让后手走到直径的一个端点,那么先手必胜,So,然后呢???不会了 ......
CF888E题解
分析 看到 \(n \leq 35\) 的数据范围就想到了 meet-in-middle。 先爆搜出对于 \(1 \sim \frac{n}{2}\) 和 \(\frac{n}{2} \sim n\) 两个下标范围内在模意义下所有的和。 然后用一个常见 trick,就是枚举第二个部分的和,然后匹配第 ......