方差 题解noip 2021
[国家集训队] Tree II 题解报告
#### [[国家集训队] Tree II](https://www.luogu.com.cn/problem/P1501) 一道·真·板子·题 就是练习LCT**懒标记**的题目 除了翻转标记以外还要维护乘法标记和加法标记 注意加法标记和乘法标记的维护！！！ ##### 加法标记 因为splay的 ......
题解 P8085 [COCI2011-2012#4] KRIPTOGRAM
[题目链接](https://www.luogu.com.cn/problem/P8085) 题目问的是相对位置是否一样，即若 $s$ 的第 $1,2,3$ 个字符串相等，$t$ 的第 $1,2,3$ 个字符串也相等，则 $s=t$。 由于 $t$ 的长度是固定的，所以我们使用哈希进行快速匹配。 那 ......
『MGOI』Simple Round I | B. 魔法照相馆 题解
[题目传送门](https://www.luogu.com.cn/problem/P9503) 一道模拟题。 并不复杂的模拟题，也不需要用到贪心。 我们可以创建一个数组来记录每个幕布是否被拉上，统计答案的时候，就看看这块幕布前面有多少个没拉上的，最后如果这块幕布拉上了，就重新放下来就行了。 ```c ......
[第五空间 2021]pklovecloud
[第五空间 2021]pklovecloud 题目来源：nssctf 题目类型：web 涉及考点：POP链 1. 先做代码审计 ```php cinder = new pkshow; } function __toString() { if (isset($this->cinder)) return ......
P1002 [NOIP2002 普及组] 过河卒
[过河卒](https://www.luogu.com.cn/problem/P1002 "过河卒") ## 题目描述 棋盘上 $A$ 点有一个过河卒，需要走到目标 $B$ 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 $C$ 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控 ......
【题解】Codeforces Round 890（CF1856）
赛时过了 A-E1，rk195 可惜是 E2 傻逼了不会背包优化了，直接连普及组水平都不到了。 ## A.Tales of a Sort ### 题目描述： 给定长度为 $n$ 的序列 $a$，每次操作为对于所有 $i$ 将 $a_i$ 变为 $\max(a_i-1,0)$，询问最少多少次操作之后可 ......
【kruskal重构树，倍增】2021 ICPC Asia Shanghai - H. Life is a Game
# 【kruskal重构树，倍增】2021 ICPC Asia Shanghai - H. Life is a Game 题目链接：[Problem - H - Codeforces 问题 - H - Codeforces](https://codeforces.com/gym/103446/pro ......
【题解】Luogu[P9504] 『MGOI』Simple Round I C. 魔法禁林
[Link](https://www.luogu.com.cn/problem/P9504) 这题我们发现如果直接去枚举生命和法力值显然是不行的，又看到说最小的生命值，不禁想到最短路，但是怎么跑？ 我们令经过一条边之前魔力值为 $k$，那么该边的边权为 $\lfloor\dfrac{w}{k}\rf ......
[ABC310] D~F 题解
# [ABC310] D~F 题解 ## **D - Peaceful Teams** 暴力搜索，搜索每个人在的队伍，为了去重，在一个人第一次加入新的队伍之后跳出。 ```cpp bitset st; void dfs(int u) { for(int i = 1; i n) return (voi ......
GDOI2021普及组 游记
## 前言 - 众所周知，2021年是GDOI第一年有普及组，~~所以本蒟蒻才敢报~~ - 一场比赛也异常的贵，800元 - 不过可以去深圳游一游，还是挺期待的 ## Day-0 傍晚差不多5:30到**深圳耀华实验学校**，第一眼就爱上了这个学校，教学楼的实际风格十分现代化 去食堂吃晚饭,~~这不 ......
2023年多校联训NOIP层测试2
## T1 斐波那契树 ### 题目  ### 思路 题解做法： 可以先把白色边权看成1，黑色边权看成0 ......
P9499 「RiOI-2」change 题解--zhengjun
思维妙妙题。 赛时的错误做法： - 找到每个点往后进位变优的位置，最多 $O(\log)$ 个； - 然后从前往后能变优就变优，往后贪心进位。 hack 数据： ``` 0 1 3 3 5 100 2 1 0 2 2 ``` 输出：`100` 这样子由于 $1$ 到 $2$ 不优，而 $1$ 到 $ ......
Codeforces Round 890 (Div. 2) supported by Constructor Institute 题解
# A. Tales of a Sort 关键就是找逆序对 记一组逆序对下标为 $l,r$，则求出最大的 $a_l$ 即可 # B. Good Arrays 记要构造的 Good Array 为 $b$ 前置：$\forall 1\le i\le n,b_i=1$ 然后 $O(n)$ 扫一遍看一下有 ......
Codeforces Round 882 (Div. 2) 题解
# A. The Man who became a God 求出相邻两个元素的差值，去掉前 $m$ 个大的差值以后的差值和即为答案 # B. Hamon Odyssey 由按位与的性质可以知道，**前缀与和** 的值只会越来越小，只要和为 $0$ 的时候我们就清空按位与前缀和，增加一下次数，如果最终 ......
2023年多校联训NOIP层测试1
## T1 打字($50pts$) ### 题目  ### 思路 字符串处理，注意所有情况如： `B` ......
2023年多校联训NOIP层测试4
## T1 幸运数字 ( $100pts$ ) ### 题目  ### 思路 $4$ 的倍数一定满足最后 ......
【题解】PermuTree (easy version) - Codeforces 1856E1
**链接：** https://codeforces.com/contest/1856/problem/E1 **题目大意：** 给定一棵以节点 $1$ 为根的树，树的大小不超过 $n(1\leq n\leq 5000)$ ，给树的节点赋各不相同的权值（可以简化为某个 $[1,n]$ 的排列），使得 ......
abc313D 题解
[[abc313D Odd or Even]](https://atcoder.jp/contests/abc313/tasks/abc313_d)。 好有趣捏。 我们考虑 $N=K+1$。 设 $s_i$ 为 $\displaystyle\sum_{j\neq i}a_j\bmod 2$。 因为 ......
Nule 题解
## 1.题意简述： 给定一个N行N列的非负整数方阵，从左上角(1,1)出发，只能向下或向右走，且不能到达值为0的方格，求出一条到达右下角的最佳路径，所谓最佳路径是指途径的数的乘积的末尾连续的0最少。 ## 2.样例解释： ```cpp 4 1 3 0 0 0 8 2 25 6 5 0 3 0 15 ......
2023年多校联训NOIP层测试4+洛谷 8 月月赛 I & RiOI Round 2
# [2023年多校联训NOIP层测试4](http://www.accoders.com/contest.php?cid=4467) # 爆零了  ## T1 [幸运数字] ......
P4426 [HNOI/AHOI2018] 毒瘤 题解
# P4426 [HNOI/AHOI2018] 毒瘤 题解 非常好虚树题目，融合了容斥的内容。 ## 简化题意 给定一张 $n$ 个点、$m$ 条边的图，求图的独立集个数。其中 $n \leq 10^5$，$n-1 \leq m \leq n+10$。 独立集：对于图 $G(U, E)$ 的一个点集 ......
Treasure 题解
[题目传送门](https://www.luogu.com.cn/problem/CF494A) 一道贪心题。 贪心策略是除了最后一个 `#` 其他的都变成 $1$ 个 `)`，这样前面的 `)` 就尽可能的少，最后的 `#` 变成的 `)` 数量加上前面的 `)` 数量等于 `(` 的数量，这样在 ......
Permutations 题解
[题目传送门](https://www.luogu.com.cn/problem/CF513B1) 一道枚举题。 数据范围非常小，考虑暴力枚举全排列。 可以 `dfs` 两次，第一次求出能使 $f(p)$ 取得的最大值。第二次求出第 $m$ 个排列。 注意一下，第二次 `dfs` 的时候需要按字典序 ......
String Game 题解
[题目传送门](https://www.luogu.com.cn/problem/CF778A) 一道二分题。 $|p|\le2\times10^6$，考虑 $O(n\log n)$ 的算法，而又要输出最大值，不难想到二分答案。 二分删除字母的数量，用一个数组将删掉的字母的下标存起来，然后判断删除字 ......
Maximum Median 题解
[题目传送门](https://www.luogu.com.cn/problem/CF1201C) 一道二分题。 熟悉的 $n \le 2 \times 10^5$，一眼二分。 在 `check(x)` 函数里，我们需要判断的是在 $k$ 次操作以内是否能将 $x$ 变为中位数。显然的，我们只需要往 ......
Painting the Fence 题解
[题目传送门](https://www.luogu.com.cn/problem/CF1132C) 一道枚举题。 我们可以直接枚举那 $2$ 个去掉的粉刷匠。先统计一下每个栅栏会被多少个粉刷匠刷到，然后枚举第一个被去掉的粉刷匠，然后计算剩下的粉刷匠会将每个栅栏刷到多少次，我们只需要看只能被刷 $1$ ......
Primes on Interval 题解
[题目传送门](https://www.luogu.com.cn/problem/CF237C) 一道二分题。 我们需要用二分在 $O(n\log n)$ 的时间复杂度内得到答案，也就是说我们的判断函数时间复杂度必须为 $O(n)$，因此考虑前缀和。 $sum_i$ 表示出现在区间 $\left[a ......
Vanya and Brackets 题解
[题目传送门](https://www.luogu.com.cn/problem/CF552E) 一道枚举题。 枚举左括号和右括号的位置括号，为了答案最优，左括号只能在开头或者 `*` 的右边。右括号只能在末尾或者 `*` 的左边。每一次枚举都计算一下这个加了括号后表达式的值，最后取最大值即可。 # ......
Prefixes and Suffixes 题解
[题目传送门](https://www.luogu.com.cn/problem/CF1092C) 一道字符串题。 我们考虑还原字符串后再一个一个的判断。很显然，这个字符串是由一个长度为 $n-1$ 的前缀和后缀组成的。因此我们可以找到这 $2$ 个长度为 $n$ 的字符串，然后枚举哪个是前缀，哪个 ......
From S To T 题解
[题目传送门](https://www.luogu.com.cn/problem/CF1194C) 一道模拟题。 首先判断 $s$ 是否是 $t$ 的子序列，如果不是就直接输出 `NO`。证明一下，$s$ 一定是 $s$ 插入 $p$ 后得到的字符串的子序列，但如果 $s$ 不是 $t$ 的子序列， ......