CF1719. A. Chip Game 根据 \(n\) 和 \(m\) 的奇偶性判断即可。 #include<bits/stdc++.h> using namespace std; #define int long long int read() { int a=0, f=1; char c=getchar(); while(!isdigit(c)) {

分析 放一张题面里的图。 能发现走一条边就是除掉或加入一个质因子。 从 \(x\) 走到 \(y\) 的最短路，一定是先除掉若干质因子，再加入若干质因子。中间那个临界点是 \(d=\gcd(x,y)\)。 然后考虑一条节点不断变小的路径，发现它的边权和可以消去中间项，只和首位有关。因此 \((x \rightarrow d)\) 与 \((y \rightarrow d)\)

一道很有趣，也很有益的题目（雾）。 分析 注意到 \(a_i \in [0,N]\)，这是很关键的一个点，可以从每个 \(a_i\) 下手。 当 \(j= a_i\) 时，所有大于 \(a_i\) 的数都会等于 \(a_i\)。也就是说，所有 \(a_i\) 作为较小数的逆序对，全部寄了。这样看起来很难下手。 可是退一步，当 \(j=a_i\) 时，小于 \(a_i\) 的数不变，大

ABC264. A. "atcoder".substr() #include<bits/stdc++.h> using namespace std; #define int long long int read() { int a=0, f=1; char c=getchar(); while(!isdigit(c)) { if(c=='-&#

CF1712. A. Wonderful Permutation 考虑到这是个排列，所以最优解一定是把 \(1 \sim k\) 都放在 \([1,k]\) 里面，因此答案是 \([1,k]\) 中满足 \(p_i>k\) 的 \(i\) 的个数。 #include<bits/stdc++.h> using namespace std; #define int long

分析 先给一组官方题解的数据。 10 10 10 19 18 17 16 15 14 13 12 10 先考虑特殊情况，对于每个 \(i\)，要求从 \(1\) 到 \(i\) 再到 \(n\) 的最短路长度为 \(d_i\)。那么当 \(i=1\) 或者 \(i=n\) 时，都相当于 \(1\) 到 \(n\) 的最短路。于是 \(d_1\) 必须等于 \(d_n\)，且二者必须为 \(\

NowCoderX54. A. Sum 引理：在最优解中，每次操作的 \(k=2\)。 证明：反证法。假设最优解中，存在一次操作 \(k \neq 2\)。那么 \(k \ge 3\)，当 \(k=3\) 时，设选择的数为 \(a\)，\(b\)，\(c\)，那么会得到 \(a+b+c\)，收益为 \(a+b+c\)。如果先选择 \(a\) 与 \(b\) 得到 \(a+b\)，再选择

分析 天数异常大，但是节点数很小，由于异或运算满足结合律，直接考虑矩阵优化。 将初始魔法值搞成一个向量，\(n\) 行 \(1\) 列。 \[ \begin{bmatrix} w_1 \\ w_2 \\ \vdots \\ w_n \end{bmatrix} \] 考虑转移矩阵 \(A\)。 要达到的目的是，如果 \((i,k)\) 之间有边才进行运算。那么设 \(A

分析 下面定义白色黑色石头为染白色黑色。 套路性地断环为链。如图中，把顶点拆成两个点，\(i\) 和 \(i'\)，显然 \(i\) 与 \(i'\) 的颜色必定相同，即上一条链的尾等于下一条链的首，所以每条链首尾的颜色都要记录。 枚举每条链防放置石头的个数 \(k\)，设 \(f_{i,0/1,0/1}\) 为考虑前 \(i\) 条链，它们按顺序首尾相连后形成

分析 问题可以转化为，在一个 \(1 \sim S\) 的数轴上，把数轴划分成段若干段，每一段的长度必须是奇数，且对于 \(i \in [1,n]\)，不能在 \(a_i\) 处划分。 先不考虑限制条件。 设 \(f_i\) 表示划分 \([1,i]\)，且最后一段是奇数的方案数，设 \(g_i\) 表示划分 \([1,i]\)，且最后一段是偶数的方案数。 考虑 \(i-1 \right