A - qh与复读机I A、每次按顺序给出$ n $个字符串，求出每个字符串是前面多少个字符串的前缀和后缀 tire树因为题面给定数据范围$\sum |S_i| < 1e6$，也就是说如果建一棵树的话结点数是不会超过这么多的，而且遍历的时候也是，那么考虑正序和逆序建树，每次建树的同时到达最后一个结点返回当前结点已经记录的单词数量，也就分别对应了前缀和后缀时间复杂度$O(n)$ 123456789101112131415161718192021222324252627282930313233343536373839404142#define maxn 1000007struct Node{ int child[26]; int sum; void init(){ for(int i = 0;i < 26;i++) child[i] = 0; sum = 0; }}Tree[2][maxn];int cnt1 = 0,cnt2 = 0;int insert(bool statu,const string& s){ ...

A - 迷宫 给出一个带权有向图，翻转一条边的代价是其权重，求出翻转边后图中无环的最小代价 二分 拓扑判环一开始只能想到要让图中没有环，但是想不清楚怎么操作，于是等到题解emmmm考虑对于要改变的边，相当于删去之后反向加回来，那么代价就是边里面权值最大的二分权值，权值越大的可以改变的边越多，二分最少的代价使得不存在环即可 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253int n,m;int u,v;ll w;int top[maxn],in[maxn];vector<Edge> G1;vector<int> edges[maxn];bool check(ll now){ int cnt = 0; for(int i = 1;i <= n;i++) edges[i].clear(); mst(in,0); mst(top,0); for(int i = 0;i < m;i++){ i ...

A - oy环游世界 A、给定n个点，求出从起点开始遍历到最后一个点的最短曼哈顿距离 状态压缩n最多有17个点，可以考虑将17个点压缩到一个int里面，这个时候可以考虑一个状态$f _ {S,i}$，表示遍历了集合S后以i为终点的路径的最短的距离，状态转移方程为:$$f_{S,j} = min(f_{S,j},f_{S_j,j + dist(j,k)})$$$S_j$表示集合$S$除去点$j$后的集合 12345678910111213141516171819202122232425262728293031323334struct Point{ ll x,y; ll operator - (const Point& a) const{ return abs(x - a.x) + abs(y - a.y); }}all[20];ll n,s;ll f[1<<20][20];int main(){ cin>>n>>s; mst(f,0x3f3f3f); for(ll i = 0;i < ...

A、对一个有n个数的区间进行四种操作，该区间内每个数的初始值为$ a_i $，在输入的第二行进行输入 op = 1时，输入三个数$ L、R、k $,表示对区间$ [L,R] $的数全部加上$ k $op = 2时，输入三个数$ L、R、k $,表示对区间$ [L,R] $的数全部乘上$ k $op = 3时，输入三个数$ L、R、k $,表示对区间$ [L,R] $的数全部变成$ k $op = 4时，输入两个数$ L、R $,要求输出区间方差乘上样本数的平方后的结果 线段树 lazy标记 答案最后要求输出的是$ n^2S^2 $ 那么把方差的公式展开：$$\begin{align}n^2S^2&= n \sum ^ {n} _ {i = 1}(X_i - \bar X)^2 \&=n\sum ^ {n} _ {i = 1} (X_i ^ 2 - 2 X_i \bar X + \bar X^2) \&=n\sum ^ {n} _ {i = 1} X _ i ^2 - 2n\bar X \sum ^ {n} _ {i = 1}X_i + n\sum ^ ...

相关概念 对于字符串$ S $,其前缀为$ pre(s,r) = s[0…r] $,后缀为$ suf(s,r) = s[|s| - r - 1 …..|s|] $，其中$ 0 < r < |s| $如果对于字符串有$ pre(s,r) = suf(s,r) $，则称$ pre(s,r) $是该字符串的$ border $,此时可以得到字符串的一个周期为$ |s| - r $ 相关算法及数据结构KMP算法 对于模式串和匹配串在一个字符串中匹配另外一个字符串的时候，如果一位一位的匹配，在发现某个字符不一样的时候将匹配串进行右移进行匹配，算法的效率是十分低下的，这个时候可以考虑在匹配失败的时候直接移动到匹配失败的位置那么就需要求一个$ next $数组，即字符串在该位置已匹配的字符数量‘$ next $数组是当前位置之前的字符串字串前缀与后缀的最大长度 求一个字符串的next数组，需要将其本身作为匹配串，从第2位开始匹配，这里令$ nest[0] = 0 $，然后依次匹配求出该数组 123456789101112131415char s[len];int next[len]; ...

A. Sea Battle给出四个整数w1,h1,w2,h2 计算在方格上围出w1h1与w2h2的方形所需要的方块的数量 数学显然ans = (max(w1,w2)+h1+h2+2) * 2，凹入的部分可以换到方形凸出的地方，使得两个方形被围住 12345678int w1,h1,w2,h2,ans;int main(){ cin>>w1>>h1>>w2>>h2; ans = (max(w1,w2)+h1+h2+2) * 2; cout<<ans<<endl; return 0;} B. Draw!给出n个数对，对应某个时刻的比分，输出最大的平局的次数6 对于数对(a,b)和数对(c,d)，要平局次数最大，则中间可能出现(x,x)是最好的，而x小于c,d中最小的，大于a,b中最大的，所以取平均值，如果a，b不相等，则可能出现x = min(a,b)的情况，有1的贡献，所以每次输入的时候，ans = ans + max(0,min(c,d) - max(a,b) + (a!=b)) 12 ...