题解1071 cf
题解 最大加权矩阵
[题目链接](https://www.luogu.com.cn/problem/P1719) 虽然是一道橙题，但还是蕴含了重要算法思想——降维思想。 如果是一维形式，即最大子段和，我们采取先求前缀和，并固定右端点，减去左边最小的办法求。 对于这题，若固定了上下边界，则可以利用列的前缀和将其“压缩”为 ......
CF的VP记录
## CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!) vp时间：2023.7.11 总结记录：考场上过了前三题，第四题没看懂题面，感觉看懂了就会了，第五题不会dp爆寄，还是要总结提升dp能力 #### [A.Tenzing and Tsondu]( ......
P6758 vim 线头 dp 题解
显然，e 在这道题里是无关紧要的。我们知道每删掉一个 e 需要 hx 两步，所以我们把所有的 e 统计出来，标记一下他后面的点（一定要经过后面这个点才能删掉 e），下文中我们叫这些点为关键节点。那么问题就变成了：如何用最少的代价经过所有关键节点。 发现我们最终走过的路径一定是这样的形式：我们 f 到 ......
CF 杂题选做
来源：笔者在vp中认为比较好的一些题目 每道题前会有tag，可以根据自己所需使用。（Ctrl+F请按照表格所给tag） 目前存在tag：难度评分，构造，树形DP ### [CF1515F](http://codeforces.com/problemset/problem/1515/F) tag：构造 ......
题解 醋溜便当
[题目链接](https://www.luogu.com.cn/problem/T351264) 题目让我们找出每个点是否存在长度 $\in[x,k\times x]$ 的回路，若找到一长度为 $a(0>n>>m>>x>>k; for(int i=1;i>u[i]>>v[i]>>w[i]; if(! ......
CF884G Tree Wights
## [CF884G Tree Wights](https://codeforces.com/contest/1844/problem/G) > 给定一棵 $n$ 个点的树，给定 $d_1,d_2,\cdots,d_{n-1}$，其中 $d_i$ 表示 $i$ 到 $i+1$ 在树上简单路径的距离， ......
CF1456E XOR-ranges
[题面传送门](https://www.luogu.com.cn/problem/CF1456E) 好题。 首先比较自然的，相当于按照数位 DP 的方法，将 $[l,r]$ 剖成 $k$ 段，其中每一段都是最高若干位确定，底下若干位任取的形式。这样在 $[l,r]$ 里面选择相当于在这 $O(k)$ ......
CF1486F Pairs of Paths 总结--zhengjun
需要保持： - 写代码前先仔细考虑一下细节，分类讨论清楚再开始码。 警告： - namespace 里面写了个 n，想调用全局 n 的时候没加 2*冒号。 思路大概就是分类讨论然后计数就完事了。 ### 代码 ```cpp #include using namespace std; using ll ......
【题解】CF gym 104337 G. Guess the Polynomial
statement：https://codeforces.com/gym/104337/problem/G 。 即求 $f(x)=\sum\limits_{i=0}^{p-2}a_ix^i$，其中只有不超过 $n$ 个 $a_i$ 非 $0$ 。 记： $$ \begin{aligned} A_{n ......
CF1450C2 题解
[题目传送门](https://www.luogu.com.cn/problem/CF1450C2) 再不写题解社贡要掉到 $0$ 了。 ## 题目分析 显然如果 $3$ 个格子构成了满足获胜条件的情况，这 $3$ 个格子模 $3$ 的余数各不相同。 那么我们将格子按模 $3$ 的余数分为 $3$ ......
arc164_a Ternary Decomposition 题解
# [Ternary Decomposition](https://www.luogu.com.cn/problem/AT_arc164_a) ## 题意 共 $T$ 组数据，对于每组数据，给出两个整数 $n$ 和 $k$，问是否存在一个长度为 $k$ 的非负整数序列 $a$，使得 $\sum\li ......
[AGC052B] Tree Edges XOR 题解
# [AGC052B] Tree Edges XOR 蛮好的题目。 ## 题意 给你一棵树，和每条边的初始权值与目标权值，每次操作可以将一条边相连的两点所连接的其他边全部异或上这条边的边权，请问最后能否使每条边变成目标权值。 ## 思路 首先考虑性质。我们发现每次操作都涉及很多边的变化，很麻烦，考虑 ......
Facetook Priority Wall 题解
[题目传送门](https://www.luogu.com.cn/problem/CF75B) 一道模拟题。 用一个 `map` 存储每个人的优先级因子，然后存进 `vector` 里进行排序。难点在于分辨 $X$ 和 $Y$ 与当前是什么操作。 不过需要注意，只要出现了名字就需要输出，且我们认为与 ......
Codeforeces #1844 A~D题解
# Codeforeces #1844 A~D题解 ## A Subtraction Game 博弈论 ~~A+B problem~~ 由于只有两种数字可选，若石子数量为 `a + b`，先手选完之后必然为 `a` 或 `b`，因此后手可以直接选完 ## B Permutations & Prime ......
【题解】P4931 [MtOI2018] 情侣？给我烧了！（加强版）
不算堂堂的复活 原题链接 [P4921 [MtOI2018] 情侣？给我烧了！](https://www.luogu.com.cn/problem/P4921) # 思路 推导 / 二项式反演 + 生成函数 这个题看到恰好 $k$ 对其实很容易想到二项式反演，但是如果要推反演就需要很复杂的 GF 来 ......
CF1360H Binary Median 题解
提供一份好看的题解。 $2^m-n$ 个数的中位数排名是 $\lfloor\dfrac{2^m-n-1}2\rfloor$（从 $0$ 开始）。因为所有元素是连续的，只要数出被删掉的比中位数小的元素数量，那么 $\lfloor\dfrac{2^m-n-1}2\rfloor$ 加上数量就是中位数了。 ......
P7720 Estahv 题解
国赛前的最后一道多项式大题。 我承诺过我不会再做梦了。仍然放不下，但是只是仍然在死去之前看到一些东西。 言多必失。我会少说话的。只是为了—— 第一眼观察数据范围和出题人知道是多项式题。考虑列生成函数。 第二眼知道这个卡特兰数 $C(z)$ 一定是复合进某个函数里边的。那设这个函数是 $F(x)$。同 ......
「Network」题解
[「CEOI2012」Network](http://222.180.160.110:1024/problem/8625) ## Solution to Question `Ⅰ` 首先缩点（当然也可以不缩？），然后跑一遍 DFS 即可。 ```cpp //w为联通分量里的节点个数 inline vo ......
正方形鱼池题解
首先这道题$T$的范围很小，而$N$的范围却很大，所以我们只能枚举树 那么我们如何枚举呢，树有上下左右之分，看起来十分难枚举，现在让我们仔细分析一下： 水池的边长就等于$min(上下界的距离，左右界的距离)$ 这时我们就可以开始枚举了，我枚举的是左右界 那么我们此时就可以发现上下界的两颗树一定在左右 ......
题解 [NOIP2011 提高组] 聪明的质监员
[题目链接](https://www.luogu.com.cn/problem/P1314) 不难发现，$W$ 越大，$y_i$ 以及 $y$ 就越小，$W$ 越小，$y_i,y$ 就越大。 所以这是一个二分答案。 考虑如何 $check$。 观察 $$ y_i=\sum\limits_{j=l_i ......
CF865D Buy Low Sell High
# CF865D Buy Low Sell High 我发现自己是真的学不会贪心……太玄学了。 这是一道反悔贪心的题目，比较简单的那种。 ## 题意 你是一棵韭菜，喜欢炒股，每天可以买入一股或卖出一股，且最后一天之后你持有的股票数目应该为 $0$。你现在知道 $n$ 天的股票价格，求最大获利。 ## ......
CF1814D Balancing Weapons
[CF1814D Balancing Weapons](https://www.luogu.com.cn/problem/CF1814D) 原题明显可以转化为： 给定一个长度为 $n$ 的数组，初始为 $p_i$。可以调整元素的值，但第 $i$ 个元素必须是 $a_i$ 的 **整数** 倍，并且 ......
CF420E Playing the ball
## Description 程序员不能总是整天坐着编程。有时站起来离开办公桌，休息一下，与同事闲聊，甚至玩一会，也是十分好的主意。F 公司的程序员就特别喜欢一种球类游戏。 让我们想象一个在笛卡尔坐标系平面上玩的游戏。玩家坐落在点 $(0,0)$ 上，选择任意一个方向，扔出球。飞了一会儿的球在距离原 ......
洛谷 P4869 albus就是要第一个出场 题解
[洛谷 P4869 albus就是要第一个出场](https://www.luogu.com.cn/problem/P4869) #### 题意 给定一个长度为 $n$ 的序列 $A$，设**可重**集合 $S=\left\{\operatorname{xor}_{i=1}^nA_ix_i\mid ......
CF878E 题解
# CF878E Numbers on the blackboard 题解 ## Links [洛谷](https://www.luogu.com.cn/problem/CF878E) [Codeforces](https://codeforces.com/problemset/problem/87 ......
AT_abc306_h 题解
# AT_abc306_h Balance Scale 题解 ## Links [洛谷](https://www.luogu.com.cn/problem/AT_abc306_h) [AtCoder](https://atcoder.jp/contests/abc306/tasks/abc306_h ......
luoguP3403跳楼机 题解【同余最短路】
[题面](https://www.luogu.com.cn/problem/P3403) 题意： 可以发现操作四相当于是每次有了回到起点的机会，那么问题就变成了求满足：$Ax+By+Cz = k,k\leq h$ 所有的 $k$。 考虑忽略 $x$，这样只需要求出所有的通过 $y, z$ 能到达的小 ......
CF407E k-d-sequence
## Description 我们称一个数列为一个好的 $k-d$ 数列，当且仅当我们在其中加上最多 $k$ 个数之后，数列排序后为一个公差为 $d$ 的等差数列。 你手上有一个由 $n$ 个整数组成的数列 $a$。你的任务是找到它的最长连续子串，使得满足子串为好的 $k-d$ 数列。 ## Sol ......
2023年7月6日普及组南外集训题解
# A 阿伦 ## 题目描述 Aron要去给朋友买礼物。 前面有$n$个人在排队，其中有一些独自前来的顾客和一些组团前来的顾客。 相邻的穿着一样的衣服的顾客在同一团队里。 一个团队里只要第一个人买了就会离开。 问Aron会在第几个排到 ## 输入格式 第一行一个$n$,表示前面有多少个人 接下来共$ ......