题解1203 div cf

**第一次vp。** 9.2 15:10 开始。 之前因为补作业没有打这个 154 场，但是就vp表现来看如果打了可能就要加 $-154$ 了 ( )。 遇到思路卡住的就直接看 jiangly 写的题解，最后开出 $4$ 题，rk1400左右，真实水平应该低于 rk5000。 ##### T1 很简 ......

Problem - C - Codeforces 题意：给你一个字符串有加号有减号还有0 和 1 +代表给数组加一个数字在末尾 -代表末尾减一个数，0代表这个数组是一个严格降序的数组 1代表当前这个数组是一个升序数组 问你当他询问0或者1时符不符合条件（如果数组元素小于2那么就是1） 题解：这个首先 ......

[题目传送门](https://www.luogu.com.cn/problem/AT_dp_j) 一道 dp 题。 发现以前课上讲的题能水题解。 在 `dp` 之前，我们需要明确以下几个东西： **状态的表示**，**状态转移方程**，**边界条件**跟**答案的表示**。 ### 状态的表示 $ ......

[题目传送门](https://www.luogu.com.cn/problem/B3608) 一道网络流题。 费用流板子题。费用流实际上是在给最大流套个最短路，而费用流一般边权会有负数，所以用 SPFA 算法，~~关于 SPFA，它复活了~~。 可以在最大流做 bfs 的时候将 SPFA 套上去。 ......

我直接从第三题开始讲了。 [T3](https://atcoder.jp/contests/abc318/tasks/abc318_c) 把数组 $A$ 从大到小排序。 然后从前往后把前 $q$ 个数加起来，然后判断这 $q$ 个数的和与 $d$ 的大小关系，如果大了就变成 $d$。 然后有些细节就 ......

# Preface 太FW了现在，纯纯给队伍拖后腿，马上要成为我们队CF Rating最低的了 但换句话说徐神和祁神都这么猛，我直接躺着被嘎嘎带飞好像也很爽啊 不管怎么样还是要多练，不过接下来可能要按专题重点突破了，明天队里开个会确定下大家的主攻方向再说 # A. Prime Deletion 因为 ......

咕咕咕的东西总是要补的。 ## A.报数 ### 题目描述： 报数游戏是一个广为流传的休闲小游戏。参加游戏的每个人要按一定顺序轮流报数，但如果下一个报的数是 $7$ 的倍数，或十进制表示中含有数字 $7$，就必须跳过这个数，否则就输掉了游戏。 在一个风和日丽的下午，刚刚结束 SPC20nn 比赛的小 ......

# Preface 唉懒狗了这把比赛的时候突然不想打了跑去看AIR了，所以就没打了，后面补题的时候发现前面题挺合我口味的如果打了大概率能上橙 不过这种第二天早上有早八的时间还是很难打的，苦路西苦路西 # A. Channel 统计当存在某个时刻在线人数为$n$时就是```YES``` 否则把所有的` ......

[Link](https://www.luogu.com.cn/problem/P7706) 一道很有意思的线段树题。 **第一步分析**，我们要求最大的 $a_i+a_k-\min{(b_j)}$，事实上我们可以直接省去这个 $\min$ 因为要最大化这个东西，选出来的 $b_j$ 必然是最小的， ......

# [A. Prime Deletion](http://codeforces.com/contest/1861/problem/A "A. Prime Deletion") ## 思路： 从1到9，每个数后面都可以加一个数构成一个含有两个数的质数，只需要从s[1]~s[9]中找到一个数与s[0]构 ......

每次打都想感叹一句，Educational 名不虚传。 ## A.Not a Substring ### 题目描述： 有 $t$ 组数据，对于每一组数据，你需要判断能否构造一个只由左右括号组成且长度为已经给定字符串的 $2$ 倍且已经给定的字符串不是子串的合法字符串。注：合法的字符串是左右括号能完全 ......

写了 $358$ 行，$11.94 \mathrm{KB}$，有这么几个地方写挂了： - 反猪决斗一定选主猪。 - 游戏结束判定是主猪死亡或全部反猪死亡。 - 决斗可能被反杀，之后不能再出牌。 点击查看代码 ```cpp #include using namespace std; int n,m; ......

# CF1863B Split Sort 题解 ## Links [洛谷](https://www.luogu.com.cn/problem/CF1863B) [Codeforces](https://codeforces.com/problemset/problem/1863/B) ## Desc ......

# CF1863C MEX Repetition 题解 ## Links [洛谷](https://www.luogu.com.cn/problem/CF1863C) [Codeforces](https://codeforces.com/problemset/problem/1863/C) ## ......

# P1463 [POI2001] [HAOI2007] 反素数 题解 可以发现，最大的不超过 $n$ 的反素数就是 $1\sim n$ 中因数最多的数字。 > 证明： > > 设 $x, x\in[1, n]$ 为 $1\sim n$ 中因数最多的数字，则 $x #define x first # ......

# CF1863D Two-Colored Dominoes 题解 ## Links [洛谷](https://www.luogu.com.cn/problem/CF1863D) [Codeforces](https://codeforces.com/problemset/problem/1863/ ......

之前整理的时候忘记写，现在补上。 # 思路 拉插求自然数幂和。 关于自然数幂和 $\sum\limits_{i = 1}^n i^k$，已知是关于 $n$ 的 $k + 1$ 次多项式，可以用伯努利数 $O(k \log k)$ 求，也可以直接拉插 $O(k)$ 求。 拉插结论：若一个 $n$ 次多 ......

[题目链接](https://www.luogu.com.cn/problem/AT_agc004_d) 躺在床上想到重要性质的题目。。。 首先，由于每个城市只有一个可以直接到达的城市，所以 $n$ 个城市就有 $n$ 条边，容易发现这是一棵基环树，那么我们先从普通树的角度考虑，若要求每个点走 $k ......

## 题意 有一棵有 $n$ 个节点的树，第 $i$ 个节点有点权 $a_i$。 定义 $g(x,y)$ 为 $x$ 到 $y$ 的树上路径所经过的点的点权 $\gcd$。 对于每一个正整数 $k\in[1,2\times 10^5]$ 求出满足以下条件的 $x,y$ 的对数: + $1\le x\ ......

## 题意 给定 $n, k$，对于所有的 $m \in \left[1, k\right]$，求长度为 $n$，值域为 $\left[1,m \right]$ 且最大公约数为 $1$ 的序列种数，对 $10^9 + 7$ 取模。 （$1 \le n,k \le 2 \times 10^6$）。 # ......

[题目传送门](https://www.luogu.com.cn/problem/P7735) 一眼数据结构 考虑树上有什么数据结构支持 $x$ 到 $y$ 节点的修改和查询，那就是：树链剖分。 那么这道树链剖分的题有个 $trick$：**边点转换&染色法，对于每次修改，考虑将修改路径上的点全部染 ......

感觉edu的题目都比较有新意； A.Prime Deletion 题意：给定长度为9的数，且1-9每个数字出现一次，求按照原定顺序选几个数组成的质数（起码选择两个）； 下意识写了一个dfs，过了； 1 #include<bits/stdc++.h> 2 using namespace std; 3 ......

**不要相信这篇题解的任何一个字，包括标题和这句话。** 省流-恶搞题目：A，B，C，M，Q。 [题目](https://vjudge.net/contest/578685) # [A](https://vjudge.net/contest/578685#problem/A) ## 思路 这道题实在 ......

[题面传送器](https://codeforces.com/contest/1863/problem/F "题面传送器") 首先有一个 $naive$ 的做法。 直接 $O(n^3)$ 暴力判断。 考虑寻找突破口。 假如给了你一个序列，异或值为 $S$ ，那么实际上假如中间有一个断点 $mid$ ......

# P1450 [HAOI2008] 硬币购物 题解 首先考虑只有一种硬币的情况。 如果取的数量没有限制，就是一个完全背包，$f_i$ 表示背包体积为 $i$ 的选择方案数，显然 $f_j = f_{j - v}$。 如果取的数量有限制，用多重背包做一遍会超时，考虑以下思路：所有方案数 - 不合法方 ......

## 在CF上比赛中反映出的问题总结 [toc] ### 总是存在的问题： 总想把前面的做对，浪费了宝贵的时间AC后面的 ### Educational Codeforces Round 154(8.31） #### 结果(+164) 在比赛中，前面两道题25分钟结束，但是第三题怎么也写不对，能力不 ......

[题目链接](https://www.luogu.com.cn/problem/P2431) 由于每个质量的月饼只有一个，并且质量恰好是2的整数倍，所以考虑将一个质量看成一个二进制位。 那么也就是说，我们要构造一个二进制数 $x$，使得 $x$ 的 $1$ 的个数最多，且满足 $a\le x \le ......

## Description 有一天 Masha 回到家，发现有 $n$ 只老鼠在它公寓的走廊上，她大声呼叫，所以老鼠们都跑进了走廊的洞中。 这个走廊可以用一个数轴来表示，上面有 $n$ 只老鼠和 $m$ 个老鼠洞。第 $i$ 只老鼠有一个坐标 $x_i$ ，第 $j$ 个洞有一个坐标 $y_j$ ......

[原题链接](https://ac.nowcoder.com/acm/contest/64384/C) 先不考虑车子的容量问题，因为结束位置保证是在起始位置之后的，那我们从前往后扫，发现是可以知道每个点时的车内的商品。 但是现在有了容量限制，我们怎么办呢，如果对于一段，k 都是大于每个点的货物量时， ......

## 题意 给定长度为 $n$ 的数组 $a$ 和一个整数 $k$ ，执行下面的代码： ```cpp long long ans = 0; //定义一个初始值为0的长整型变量 for(int i = 1; i typedef long long valueType; typedef std::vec ......