P8094 USACO22JAN Cow Frisbee S 题目概括 给定一个数组，求所有 $1 \leq i \leq j \leq n$，且对于所有 $i \leq k \leq j$，都满足 $a[i] \geq a[k] \cap a[j] \geq a[k]$ 的有序数对 $(i, j)$ 的长度（$j - i + 1$）。 算法 &a…

题目概括 在一个字符串前插入若干个指定字符：l、q、b，使得这个字符串成为一个回文字符串。 算法 & 数据结构 & 思想 洛谷标签：模拟 主要是了解回文串的特点，和题目中只能在字符串前面添加字符这个特点。 错误点 注意在 check 函数中，访问字符串中的位置的时候一定要判断有没有超出字符串长度或者小于 0。 思路 80 分（TLE…

AT_abc169_d [ABC169D] Div Game 看到题解里面好像没有用二分写的，我这个蒟蒻就写一个了。 题意 题目翻译写得很清楚了，我就不多写了。 思路 先把给定的 $N$ 分解质因数，得出： $$N = a_1^{p_1} \times a_2^{p_2} \times a_3^{p_3} \times \dots \times a…

P10877 「KDOI-07」n1gr tS0i 个人认为这道题没有黄的难度。 思路 我先看了 $n=30$ 的样例，有一个猜想是答案是 $2^n$，然后用计算器算了一下 $n=30$ 的这个数据发现猜想是对的。 但是如果 $n=2$ 的情况发现不是这样的，所以又猜测只有当 $n$ 大于一个界限的时候才是 $2^n$。 首先，$n = 2$ 的情…

01-Trie ‍ 如果不理解 Trie 树的可以看我的之前的文章 Trie 树 – ztr 的小窝 (ztrztr.top)。 01 Trie 树，是运用 Trie 的思想储存一些数，从而实现省空间。 实现 01 Trie 树，是把原本是字符串中的都换成了一个数的二进制串。 对于添加数的操作，我们把数按二进制把二进制中的每一位拆分，然后按 Tri…

P2607 [ZJOI2008] 骑士 难度：紫（省选/NOI−）。 知识点：图论，树形 DP，DFS。 知识点难度（知识点模板题）：绿。 代码长度：中偏短（$52$ 行） 代码难度：较低。 思路 这道题是采用树形 DP 的《没有上司的舞会》的模板的，状态定义为： $dp[i][0]$ 是以 $i$ 为根的子树不选择这个节点的最大答案。 同理，$d…

P10801 题目大意 给一个字符串，求通过改变最多 $k$ 个字符后最小化这个字符串的严格循环节的长度。 思路 从题目，我们能初步分析出一下几点： 答案肯定是字符串长度的因子； 由于随着答案的减小，需要操作的次数会增加，那么我们就能想到二分。 我们可以先统计字符串长度的每个因子，然后存到数组里面。 然后二分这个数组，找到最小符合条件的答案。 二分…

题目大意 有一个图，依次删去一些点后有多少个连通块。 思路 一道并查集 + 离线 的题目。 这道题第一眼肯定是想如何维护可以删除节点的并查集，但是这样不太可做。（或许是我太菜了。）但是我们发现他只有一个删除的操作，没有增加的操作，那么就可以想到离线计算。 离线计算，也就是把原本是读入后立马运算的操作都存起来，再算。 这样的好处就是我们可以按操作倒着…

题面 思路 这道题第一眼应该可以看出是一道搜索的题目。 我们先用 bfs 搜索一遍，用来计算出洪水到达每一个位置的最少时间。 这里需要注意的一点是，有可能有多个洪水的初始地点，所以每一个洪水到达一个地点的时间有可能不一样。所以在更新洪水达到时间的时候，我们需要注意不要直接赋值，要取最小值。 第二遍 bfs 是计算能不能达到别墅和最短时间，这个直接 …

题面 思路 50 pts 暴力。我们发现每次操作等于将前面的红的变成蓝的，将第一个蓝的变成红的。 要养成写暴力的好习惯。 #include <bits/stdc++.h> using namespace std; /* */ int n; string s; int cnt = 0; bool check() { for (int i …