Q779’s Blog

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] <<...

洛谷P1204 [USACO1.2]挤牛奶Milking Cows 题解 题目链接：P1204 [USACO1.2]挤牛奶Milking Cows 题意：给定 \(n\) 个区间，求这些区间覆盖后最长的区间和未被覆盖的最长区间（未被覆盖区间的范围在最左端到最右端内，否则就没有意义了） 正如简化的题意，我们可以使用类似于差分的思想，如图 我们可以保存左右端点，然后从左向右遍历（排序一下就行，如果左右端点相同左端点优先） 每次碰到端点加一下就行，和为0时更新答案即可 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define MAXN (int)(5005) int n,pos,ans1,ans2,sum,last; struct node { int isleft,x; const bool operator <(const node &o)const { if(x==o.x)return isleft>o.isleft; ...

Chrome 自动操纵谷歌小恐龙 全自动谷歌小恐龙 qwq 代码来自网络（链接） function TrexRunnerBot() { const makeKeyArgs = (keyCode) => { const preventDefault = () => void 0; return {keyCode, preventDefault}; }; const upKeyArgs = makeKeyArgs(38); const downKeyArgs = makeKeyArgs(40); const startArgs = makeKeyArgs(32); if (!Runner().playing) { Runner().onKeyDown(startArgs); setTimeout(() => { Runner().onKeyUp(startArgs); }, 500); } function...

三角函数常用公式总结 下文所有与开根结果有关的 \(\pm\) 号均与角 \(\alpha\) 有关。 一、基本公式 1. 诱导公式 \[ \begin{aligned} &\sin ^{2} \alpha+\cos ^{2} \alpha=1 &&&& \sin (\alpha+2 \pi)=\sin \alpha &&&& \sin (\pi+\alpha)=-\sin \alpha \\[6pt]&\tan \alpha=\dfrac{\sin \alpha}{\cos \alpha} &&&&\cos (\alpha+2 \pi)=\cos \alpha &&&& \cos (\pi+\alpha)=-\cos \alpha \\[6pt]&\tan\alpha=\dfrac{1}{\cot \alpha} &&&& \tan (\alpha+2 \pi)=\tan \alpha &...

ubuntu 释放缓存脚本 注意：缓存\(\ne\)内存 内存占用过高解决办法 首先在主目录新建一个free.sh，输入 echo 3 > /proc/sys/vm/drop_caches 保存后打开终端 sudo su crontab -e 在crontab里输入（/home/qry是我的主目录） */5 * * * * /home/qry/free.sh 按ctrl+x保存并退出即可 意思是每隔5分钟释放一下缓存，具体参数配置不说了

洛谷P4315 月下“毛景树” 题解 题目链接：P4315 月下“毛景树” 题意：请维护一个数据结构，支持 改第 \(k\) 条边的边权 结点 \(u\) 到 \(v\) 路径上的边权改为 \(k\) 结点 \(u\) 到 \(v\) 路径上的边权增加 \(k\) 询问结点 \(u\) 到 \(v\) 路径上的边权最大值 一看树链剖分，敲了个板子发现给的是边权 那么就只要把边权转化为点权就可以用线段树维护了 显然把父亲到儿子的边权存在儿子上更好维护 也就是把边权存在深度大的结点上 在跳出top[x]!=top[y]循环时 id[x],dep[x]<dep[y]其实是原来 \(u\) 和 \(v\) 的lca，这个lca的边权显然不是 \(u\) 和 \(v\) 路径上的边 所以维护id[x]+1 然后就是少见的区间赋值操作，别跟我说ODT，怕被卡 主要难在代码实现上，直接贴了（3.79KB） #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3...