Q779’s Blog

洛谷P1234 小A的口头禅 题解 题目链接：P1234 小A的口头禅 给出了一个矩形，让你求出里面有几个hehe（方向无所谓，斜着不算） 数据范围很良心，嗯~ 所以暴力枚举即可 值得注意的是 \(\tt{eheh}\) 这种也算 顺便说一句，关了同步流的cin,cout还是很快的 qwq 鬼畜的代码如下 #include <bits/stdc++.h> using namespace std; #define int long long #define MAXN (int)(1005) #define A (j+3<=m&&a[i][j]=='h'&&a[i][j+1]=='e'&&a[i][j+2]=='h'&&a[i][j+3]=='e') #define B (j-3>=1&&a[i][j-3]=='e'&&a[i][j-2]=='h'&&a[i][j-1]=='e'&&a[i][j]=='h') #define C (i+3&l...

洛谷P2804 神秘数字 题解 题目链接：P2804 神秘数字 题意：询问有多少段连续区间的平均值大于 \(m\) 可以发现将每个数都减去 \(m\) 后任意和大于 \(0\) 的连续区间都满足题意 区间和可以用前缀和优化，记为 \(s\) 问题转化为了求 \(s_j-s_i>0,0\le i <j\) 移项可得 \(s_i<s_j,0\le i <j\) 问题又转化为了求顺序对（与逆序对相反） 于是可以用树状数组解决 更多解法？ 注意当 \(s_j>0\) 时 \(i=0\) 也是一个解 时间复杂度 \(O(n\log n)\) 代码如下 #include <bits/stdc++.h> using namespace std; #define int long long #define MAXN (int)(2e5+5) #define mod 92084931 int n,m,ans; int a[MAXN],bit[MAXN],b[MAXN]; int lowbit(int x){return x&(-x);
...

洛谷P1522 [USACO2.4]牛的旅行 Cow Tours 题解 题目链接：P1522 [USACO2.4]牛的旅行 Cow Tours 题意：给定一张无向图，有至少 \(2\) 个连通分量，定义直径为每个连通分量中任意两结点的最短路径的最大值，其中相邻结点边权为它们的欧几里德距离，现在要求添加一条边使得连通分量的数量减少 \(1\) ，并使得这个新连通分量的直径尽可能地小，求这个最小值 题意已经简化过了 应该很好懂 由于 \(N\le 150\) 显然我们可以用 Floyd 来求这个最短路径 任意两个连通块 \(A,B\) 连边，可能出现以下三种情况 \(A\) 的直径最大 \(B\) 的直径最大 \(A\) 和 \(B\) 相连后的新直径最大，即 \(w(i,j) + d(i) + d(j)\) ， 其中 \(d(i)\) 指从结点 \(i\) 出发的最长路径的长度 那我们求一下就好了 qwq 就这么简单 注意这个最大值不能在Floyd的时候更新，因为那个时候还不是最短路径… 时间复杂度 \(O(n^3)\) 代码如下（无视我的垃圾卡常） #include &l...

洛谷P5764 [CQOI2005]新年好 题解 题目链接：P5764 [CQOI2005]新年好 题意：从 \(1\) 号结点出发，要访问其他 \(5\) 个结点，顺序随意，访问一个结点后不用返回 注意到 \(5! = O(1)\) 那我们可以在 \(1\) 和其他 \(5\) 个点跑一下dijkstra，然后枚举所有可能的顺序即可 这里给出了两种枚举方式，分别为dfs和next_permutation() 实测（C++14 O2）后者快30ms左右，不过均可轻松通过此题 我才不会说我是因为先写后者没调出来才有的这篇题解呢 QAQ dfs #include <bits/stdc++.h> using namespace std; #define int long long #define INF (int)(5e10+233) #define gc() getchar() #define pc(a) putchar(a) #define MAXN (int)(5e4+5) template<typename T>void read(T &k) {...

洛谷P1462 通往奥格瑞玛的道路 题解 题目链接：P1462 通往奥格瑞玛的道路 题意：在艾泽拉斯，有 \(n\) 个城市。编号为 \(1,2,3,\ldots,n\) 。 城市之间有 \(m\) 条双向的公路，连接着两个城市，从某个城市到另一个城市，会遭到联盟的攻击，进而损失一定的血量。 每次经过一个城市，都会被收取一定的过路费（包括起点和终点）。路上并没有收费站。 假设 \(1\) 为暴风城，\(n\) 为奥格瑞玛，而他的血量最多为 \(b\) ，出发时他的血量是满的。 歪嘴哦不希望花很多钱，他想知道，在可以到达奥格瑞玛的情况下，他所经过的所有城市中最多的一次收取的费用的最小值是多少。 本题的数据是真的水，而且也没说清楚 \(b\) 最后可不可以为 \(0\) ，瞎搞的做法都能写 81pts qwq 看到最大值最小，首先可以想到二分 事实上，由于我们不清楚血量和最小值究竟有何关系（没关系），也只能用二分 注：二分的是这个最小值 在二分了一个值后，我们把伤害看作边权，然后跑个最短路，找一下最少伤害的路径，判断一下能不能到达终点即可 细节还是有点多的 qwq 懒得讲了看代码...

UVA11475 Extend to Palindrome 题解 题目链接：UVA11475 Extend to Palindrome 题意： 输入多个字符串。 对于每个字符串 \(S^{*}\) ，求出一个字符串\(S^{*}\)， \(S^{*}\) 需要满足： \(S^*\)为 \(S^{*}\) 的前缀； \(S^*\) 是一个回文字符串； \(|S^{*}|\)应尽可能小； 对于每个 \(S\) ，输出 \(S^{*}\) ，每行输出以换行符结尾。 可以发现我们似乎要从原字符串中找到一个最长的回文串 然后以该回文串的中心为对称轴对称过去 如amanaplanacanal要变换成amanaplanacanalpanama 但是还有一个问题，比如下面这个例子 axxxxxxxxxxxxxxdyyy 由于 \(S\) 为 \(S^{*}\) 的前缀，所以我们要找的是最长的后缀回文串 使用Manacher算法即可 代码如下 #include <bits/stdc++.h> using namespace std; #define int long long #de...

洛谷P3121 [USACO15FEB] Censoring G 题解 题目链接：P3121 [USACO15FEB] Censoring G 题意：给出文本串 \(t\) 和\(n\) 个模式串 \(s\) ，删除在 \(t\) 中第一次出现的子串 \(s_i\) ，并重复这个过程（在产生的新串 \(t’\) 上继续删除操作），求最后的结果（所有模式串都要删掉） 多模式串匹配很容易想到是AC自动机 那删除操作怎么处理呢？ 注意到删除子串后，在删除的子段后继续匹配可能需要该子段前的已经算出（显然）的匹配值 那么我们可以用两个栈分别维护匹配时的经过的点和答案 在每次删除后我们只要跳回原来的点即可 时间复杂度 \(O(|t| + \sum |s_i|)\) 代码如下 #include <bits/stdc++.h> using namespace std; #define int long long #define MAXN (int)(1e5+5) int n,tot,top,trie[MAXN][32]; char ans[MAXN]; char t[MAXN],s[M...

洛谷P4824 [USACO15FEB] Censoring S 题解 题目链接：P4824 [USACO15FEB] Censoring S 题意：给出字符串 \(t\) 和 \(s\) ，删除在 \(t\) 中第一次出现的子串 \(s\) ，并重复这个过程（在产生的新串 \(t’\) 上继续删除操作），求最后的结果 匹配问题可以用KMP来解决 怎么处理删除操作呢？ 可以观察下样例 注意到删除子串后，在删除的子段后继续匹配可能需要该子段前的已经算出（显然）的匹配值 那么我们可以用两个栈分别维护KMP的匹配值和答案 在每次删除后我们只要让top-=m即可，其中m为 \(s\) 的长度 时间复杂度 \(O(|t|+|s|)\) 代码如下 #include <bits/stdc++.h> using namespace std; #define int long long #define MAXN (int)(1e6+5) int n,m,fail[MAXN],top,stk[MAXN]; char t[MAXN],s[MAXN],ans[MAXN]; signed mai...

洛谷P5357 【模板】AC 自动机（二次加强版）题解 题目链接：P5357 【模板】AC 自动机（二次加强版） 题意：\(n\) 个模式串 \(s_i\)（不保证互异），要求输出这些模式串在文本串 \(S\) 中出现的次数 建议大家先去做下加强版的，题解在此 我们已经在加强版初步解决了次数统计的问题 可以发现本题的数据范围 \(n\le2\times10^5,\sum |s_i|\le2\times10^5,|S|\le2\times10^5\) 而原来算法的时间复杂度是 \(O\left(|S|\left|\max\{s_i\}\right|\right)\)，T飞了 那么考虑怎么优化暴力跳fail的问题 注意到所有fail连出的有向边构成了一个DAG（有向无环图） 证明很简单，最长后缀一定是单调递减的 我们把这个DAG看作一棵树 那么所有的儿子结点一定会跳到父亲结点，并使父亲结点权值增加1 解法一：直接树形dp统计答案 这个我没写代码 qwq 解法二：拓扑排序 我们只要在拓扑排序的过程中统计答案即可 这样我们就可以把时间复杂度压到 \(O\left(\sum|s_i|+...

洛谷P3796 【模板】AC 自动机（加强版） 题解 题目链接：P3796 【模板】AC 自动机（加强版） 题意： \(T\) 组数据，每组 \(N\) 个模式串 \(s_i\) ，要求输出这些模式串在文本串 \(S\) 中出现次数最多的模式串以及它们的出现次数，按输入顺序输出 可以发现这是个AC自动机的裸题 那怎么处理出现次数呢？ 我们只需要把匹配过程中所有可能产生的字符串都次数+1 例如在匹配到she的时候，可以发现它的任意后缀都可能成为其他模式串的前缀 那我们只要将（如果有的话）she,he,e这三个都加上1 这个过程不就是沿着当前结点的fail指针往上跳吗？（上指结点深度小的，根节点深度为0） 还有，多组数据一定要清空哦！ char数组不一定要，因为在读取的时候会在最后加一个\0的，一般不影响 到此为止，一些题解就直接贴代码了 我们来分析一下单次询问的时间复杂度 AC自动机的时间复杂度 \(O(\sum|s_i|+|S|)\) 而我们统计的时候是暴力跳fail指针，那么最坏时间复杂度 \(O(S\times \max\{|s_i|\})\) 所以整个算法的时间复杂度 ...

RMB找零问题 来自某次研究性学习的作业 前言 可以先考虑这样的问题 给定 \(n\) 种足量多的纸币，每种面额为 \(a_i\) 元 \((0<a[i]≤10000,a[i]\in \mathbb{Z},1\le i\le n\le 100)\) 给出需要找零的金额 \(m (0≤m≤10000)\) 请找到一种方法使得找零所需的纸币数量尽可能地少，输出最小数量 例如：\(68=50+10+5+2+1,12=10+2\) 尽管 \(8=10-2\) ，但是收银员是不能支付 \(-2\) 元的 可以看出这就是一道完全背包模板题 代码如下 #include <bits/stdc++.h> using namespace std; #define int long long int n,m; int a[105],dp[100005]; signed main() { ios::sync_with_stdio(0); cin >> n >> m; memset(dp,0x3f,sizeof(dp));dp[0]=0; for(int i=1; i&l...

洛谷P5116 [USACO18DEC]Mixing Milk B 题解 题目链接：P5116 [USACO18DEC]Mixing Milk B 题意：三个桶有一定牛奶和容积，要循环倒100次 模拟，要注意一些细节 代码： #include <bits/stdc++.h> using namespace std; #define int long long int a[4],b[4]; signed main() { for(int i=1; i<=3; i++) cin >> b[i] >> a[i]; for(int i=1; i<=100; i++) { int x=(i%3)?(i%3):3,y=((i+1)%3)?((i+1)%3):3; if(a[x]>=b[y]-a[y])a[x]-=b[y]-a[y],a[y]=b[y]; else a[y]+=a[x],a[x]=0; } for(int i=1; i<=3; i++) cout << a[i] <<...