方差 题解noip 2021

\(\text{Links}\) 原题传送门 题意 求给定序列中有多少个子区间满足众数出现次数严格大于区间长度的一半。 题解 题目要求满足条件的子区间，一个很直接的想法是每次固定左（右）端点，求有多少个右（左）可以与其匹配对答案造成贡献。 那么考虑一个暴力做法：每次固定左端点，然后往后面一直扫，枚举 ......

day 1 抽象场。 T1是诈骗题，剩下三题都是撒币概率期望。赛事没有人过t3t4。 毫无意义。 T2想不到可以把相似的状态归在一起。从 \(O(2^{3n})\) 到 \(O({\begin{pmatrix}n+m\\n\end{pmatrix}}^3)\)，很难想到。不过foi的时候甚至听说过拆 ......

[POI2015] LOG 题目描述 维护一个长度为 \(n\) 的序列，一开始都是 \(0\)，支持以下两种操作： U k a 将序列中第 \(k\) 个数修改为 \(a\)。 Z c s 在这个序列上，每次选出 \(c\) 个正数，并将它们都减去 \(1\)，询问能否进行 \(s\) 次操作。 ......

传送门 题目背景 小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。 题目描述 这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会 ......

题目描述 给你一个 \(n\) 个点 \(n\) 条边的有向图，若选了当前节点，那么当前节点的儿子节点至少有一个不能选。求最多能选多少个点。 具体思路 显然是一棵基环树，因此考虑基环树 dp。 我们先不管环的条件，先考虑朴素的树形 dp。 设 \(f_{x,0}\) 表示 \(x\) 节点不选，最多 ......

easy_RE 先exeinfo 没有壳，直接上ida 看到有关键信息，但没有显示完，按f5反编译一下 拼接一下输入，注意字符串的部分字母由近似数字代替，提交 KE 运行一下，看到是KE，想着可能是壳的意思？exeinfo看一下 upx壳，尝试upx脱壳 呃呃 权限好像不对 尝试了一下用管理员权限打 ......

题目描述 给出一个长度为 \(n\) 的序列 \(a_i\)，求出下列式子的值： \[\sum_{i=1}^n \sum_{j=i}^n (\max \limits_{i \le k \le j} a_k-\min \limits_{i \le k \le j}a_k) \]即定义一个子序列的权值为 ......

题解： CF768D Jon and Orbs 一句话体面：有k种不同的物品,每天等概率任取一种（不一定是新的种类）。q组询问，每组给出一个p，问取完这k件物品的概率不小于\(\frac{p}{2000}\)的最小天数 不用说，肯定是概率DP了 1.定义 :\(f_{i,j}\) 表示前\(i\)天 ......

2021 CCPC 桂林 ADEGIK https://codeforces.com/gym/103409 女队vp。就做了四道比较签到的题，后续补了两题，感觉比较考察思维。本身的代码不难写。其中，D题要能明白那个贪心的思想，尽量把大的放在前面，并且要知道怎么才能把大的放在前面！！！K题非常神奇，想 ......

题意 给定一个长度为 \(n\) 的正整数序列 \(a\)，对该序列进行 \(m\) 次操作，定义每次操作如下： 从 \(\left[1, n\right]\) 中等概率选取一个 \(i\)，对于 \(j \in \left[i, n\right]\)，执行操作 \(a_j \leftarrow a ......

Day \(\text{M}_r(\text{O}_2)\)。 这东西原来叫减半报警器？？ 首先这题肯定和数论没啥关系，因为 \(10^5\) 之内的 \(\max \omega(n)=6\)，即一个数至多只有 \(6\) 个质因子。 然后我们发现如果 \(x\) 有 \(k\) 个不同的质因子，这 ......

题目描述 为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有 \(n\) 张地毯，编号从 \(1\) 到 \(n\)。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。 地毯铺设完成后，组 ......

解题思路: 确实是一道很好的贪心，但由于加上了水这个影响因素，使题目复杂度上升了不少。（考虑的东西多了嘛） 输个入。 对饼干温度无脑排序。 求最小值。 求最大值（用双指针做，后面会讲）。 解题过程: 先输入（这个步骤就不用我讲了） int a[1000005]; long long n,ws; lo ......

题意 \(A\), \(B\) 两人轮流在一张图上移动一个点。要求这次移动的边权必须大于上次的。 \(A\) 希望游戏进行的轮数多，\(B\) 希望游戏进行的轮数少。 对于每个 \(s = 1, 2, ..., n\) 作为起点，若双方都采用最优策略，游戏会进行多少轮。 Sol 考虑将所有边按照从大 ......

询问若干个问题，每个问题用一段字符串表示，存在空格。每个问题一行，对于每个回答，只需要输出 \(NO\) 。 view1 #include <bits/stdc++.h> char s[1000005]; void solve(){ while (fgets(s, 1000005, stdin) ! ......

原题 容易想到最短路 DAG 求出来，起初我以为要求最小割，但这是错误的，因为可能有多条边联通了一个点的情况，这时候选择最小割不一定是最优的 我们猜想一个思路：答案一定是包含 \(1\) 号节点的连通块全部填 \(N\) ，剩下的填 \(S\) 。发现在最短路 DAG 中， \(1 \rightar ......

#618. 【JOISC2021】聚会 2 就是相当于选中的点在整棵树上的重心 首先，当\(i\)为奇数时，答案为\(1\) 当\(i\)为偶数时，可以将选中的点分为两个子树，分别记其根节点为\(x\)和\(y\) 那么可以发现，所以合法的\(x\)和\(y\)构成一个连通块，那么当前答案就是连通块 ......

Party DP 是门艺术。 \(n\leq 22\) 一眼状压。但是怎么状压就比较困难，因为同一个 \(f[x]\) 可以代表成千上万种含义。 这里我们采用，设 \(f[x]\) 表示当 \(x\) 集合中所有的点都处于同一个团内的最小代价。 则我们有 \(f[x \operatorname{or ......

Piling Up 一个很好的思路就是设 \(f[i][j]\) 表示当前进行了 \(i\) 步，并且盒子中剩下了 \(j\) 个白球的方案数，然后直接 DP 即可。 但是这样是有问题的，它没有考虑到重复计算的问题。 我们不妨令 \(+\) 符号表示取出黑球，\(-\)符号表示取出白球。 则一种方式 ......

BubbleSquare Tokens 神仙构造题。 首先，我们令所有点初始都没有放币，所有边上都放了一个币。则此时每个点的权值即为它的度数。 然后，我们考虑从小到大计算每个点的权值。对于每个点 \(i\)，我们枚举它所有相邻且编号比它小的点，假如该点上没有币，就把币从连接两点的边上移到另一端的点上 ......

Connecting Vertices 这个奇怪的限制（两条边不能有交点）让我们想到什么？ 对于任何一种方案，不存在 \(x_0<x_1<y_0<y_1\)，其中连边 \((x_0,y_0),(x_1,y_1)\)。 也就是说，对于任何一段区间 \([i,j]\)，如果里面所有点全都连通： 要么 \ ......

Dead Ends \(n\le10\)，我还是第一次见到这么小的状压 我们设 \(f[S][s]\) 表示：将集合 \(S\) 内的点连成一棵树，且集合 \(s\) 里的节点是叶子节点的方案数。 则有 \[f[S\cup\{j\}][\{s\setminus i\}\cup\{j\}]+=f[S] ......

Long Colorful Strip 中间如果有那些地方看不懂，可以先去看看前面一道，这是我的题解。 首先，每一次染色，最多把一整段连续的同色格子，分成了三段。 并且，明显我们可以把连续的同色格子，直接看作一个。 这就意味着，在这么压缩后，有 \(m<2n\)。 这就意味着 \(O(m^3)\) ......

[ARC143D] Bridges 题意：给定 \(2n\) 个点和 \((u_1,v_1) , \cdots , (u_m,v_m)\)，选择让 \(u_i\) 连 \(v_i+n\) 或 \(v_i\) 连 \(u_i+n\)，以最小化图中桥的个数。 有种技巧叫拆点，把一个点拆成入点和出点，看这 ......

奇怪装置 找到循环就很简单了。 很显然 \(y\) 是每 \(B\) 次一循环的，对于每个相邻的 \(y\) 循环 \(x\) 的值均相差 \(B+1(\bmod A)\)。 因此总的循环就是 \(B+1\) 对于 \(A\) 的循环乘上 \(B\)。 即 \(\frac{A}{\gcd(A,B+1 ......

Short Colorful Strip 考虑设 \(f[i,j]\) 表示：假设区间 \([i,j]\) 里面一开始所有格子的颜色都是相同的，那么，染成目标状态共有多少种染法。 我们找到 \([i,j]\) 中最小的那个颜色，设为 \(mp\)。则显然，我们下一步要染上 \(mp\) 这种颜色。 ......

所有的 \(DP\) ，只要式子一推出来（不管复杂度），那就很简单了，因为优化是成千上万种的…… 思路1: 我们考虑设 \(f[i][j][k]\) 表示：当前 \(DP\) 到第 \(i\) 块木板的第 \(j\) 个位置，共涂了 \(k\) 次，所能获得的最大收益。因为还要枚举当前这次涂是从哪到 ......

[SDOI2013] 城市规划 题意：给你一个 \(6 \times n\) 的网格题，单点修改，询问区间联通块数，\(n \le 10^5\)。 解：看起来就很显然的一道题......线段树每个点用一个 ufs 维护连通性； 我为了方便思考把图转成横着的了。 写起来真是毒瘤...... 重点在于： ......

AtCoder Beginner Contest 320 Problem C - Slot Strategy 2 (Easy) 题解 题目简述 给定 \(3\) 个长度为 \(m\) 的转盘，转动过后三个转盘分别可以在不同的时间停下，求停下时所有转盘都显示相同数字的最小时间。 思路 由于这题 \(m ......

AtCoder Beginner Contest 320 Problem D - Relative Position 题解 题目保证不矛盾，就可以直接 vector 建图，然后 dfs 一遍，边权为 \((w_x,w_y)\) 表示坐标的差，从 \(u=1\) 开始搜索，设点 \(u,v\) 有一条 ......