なんとかのところ

Pty loves string 只能说还是太菜了…一百多个队过的题看题解还想了一个小时才想明白。 题意是给一个字符串S，每次询问前x个字符和后y个字符拼起来的字符串T在字符串S中的出现次数。 对于一个出现情况来说s[l..r]s[l..r]s[l..r]来说，必然有s[l..l+x−1]=s[1..x]s[l..l+x-1]=s[1..x]s[l..l+x−1]=s[1..x]，s[l+x...r]=s[n−y+1,n]s[l+x...r]=s[n-y+1,n]s[l+x...r]=s[n−y+1,n]​，即s[l..r]s[l..r]s[l..r]的前xxx个字符和S串的前xxx个字符相同，后yyy​个字符和S串的后yyy个字符相同。所以对于一个出现情况来说，存在一个位置iii，包括当前位置往前xxx个字符与S串前xxx个字符相同，不包括当前位置往后yyy个字符与S串后yyy个字符相同。 考虑kmp。kmp的nextinext_inexti​的意义是在s[1..i]s[1..i]s[1..i]中的与后缀相同的前缀，这里刚好符合我们需要的，iii位置前xxx个字符与S串前缀相同。观察 ...

E - Mocha and Stars nnn颗星星，每颗星星的亮度aia_iai​取值范围为[li,ri][l_i,r_i][li​,ri​]，问满足∑ai≤m\sum a_i\le m∑ai​≤m同时gcd(a1,a2,...,an)=1gcd(a_1,a_2,...,a_n)=1gcd(a1​,a2​,...,an​)=1的亮度取法有多少种。 首先考虑没有gcd限制的情况下的取法要怎么做、、最朴素的做法是枚举每个物品的aia_iai​取值，然后做背包，但是这样是O(nm2)O(nm^2)O(nm2)​的复杂度。考虑对于一个物品取值aia_iai​，一个固定容量jjj是从j−aij-a_ij−ai​转移过来的，那么对于取值在全部lil_ili​到rir_iri​的取值，固定容量是∑j−rij−lidpj\sum_{j-r_i}^{j-l_i}dp_j∑j−ri​j−li​​dpj​，所以可以记录前缀和，快速计算dpjdp_jdpj​ 然后再来考虑没有∑ai≤m\sum a_i\le m∑ai​≤m​​​​​​限制的情况。我们设g(a1,a2,...,an)当gcd(a1,a2,.. ...

最近这两天vscode的调试突然抽风了，点击调试后几秒就会自动结束，也没有继续进行下去，调试控制台没有输出，终端也没有自动输入应有的那些参数。 卸载重装，彻底删除重装都不行，最后都绝望了…结果某一次重装的时候不知道为什么C/C++这个插件版本没有升级到最新版，这时候还能用，但重启后升级到最新版又不行了，这才找到问题是这个插件刚更新的1.6.0版本。 有两种解决办法，一种是直接把版本回退到上一版，但是这种比较麻烦而且还得关闭自动更新，不是很利于今后的使用。 另一种是把 %USERPROFILE%.vscode\extensions\ms-vscode.cpptools-1.6.0-insiders\install.lock %USERPROFILE%.vscode\extensions\ms-vscode.cpptools-1.6.0-insiders\debugAdapters 这两个都删除掉之后，重启vscode，等待它自动下载正确的调试器后就可以了。 %USERPROFILE%文件夹是用户文件夹，可以WIN + R 输入%USERPROFILE%回车打开。 来源：https:/ ...

前言 后缀数组是一种应用很广的字符串算法。与kmp或AC自动机这类字符串匹配算法不同，后缀数组以及后缀自动机这种后缀数据结构，主要用于解决字符串中与子串有关的问题。 从字符串的后缀角度来考虑，其所有后缀的所有前缀，便是字符串的所有子串，而后缀数组可以在在O(n)O(n)O(n)[DC3算法]或O(nlogn)O(nlogn)O(nlogn)​​​[倍增算法]的时间复杂度里，快速求出每个后缀按照字典序排序后的位置，以及排序后相邻后缀的最长公共前缀。如此一来，我们便可以利用字典序或最长公共前缀等等，来解决与子串有关的大部分问题。 首先是暴力 参照上述我们希望得到的功能，我们可以得到一个最暴力的做法：记录每个后缀字符串并按照字典序排序。但很明显这么拉的复杂度是谁都不想看到的，所以我们需要再进一步。 直接排序相当于是对于两个对象的全部值进行比较，这样显然存在许多冗余的操作。我们可以考虑倍增思想。 对于每一个后缀我们可以设置两个关键词，每次只按照这两个关键词进行排序。

概率相关知识点 1、P(X=K)=P(X>=K)−P(X>K)P(X=K)=P(X>=K)-P(X>K)P(X=K)=P(X>=K)−P(X>K) 2、E[x]=∑1∞P(X≥i)E[x]=\sum_1^\infty P(X\ge i)E[x]=∑1∞​P(X≥i) 3、P(A)=PP(A)=PP(A)=P，则一直随机直到发生事件A的期望次数为1P\frac{1}{P}P1​ 每次随机一个[1…n]的数，期望随机几次能随机出全部的数 Ti:T_i:Ti​:当前有i个数，第一次随机到新的数 E[x]=∑0n−1E[Ti]E[x]=\sum_0^{n-1}E[T_i]E[x]=∑0n−1​E[Ti​] P(Ti)=n−inP(T_i)=\frac{n-i}{n}P(Ti​)=nn−i​ E[Ti]=1P(Ti)=nn−iE[T_i]=\frac{1}{P(T_i)}=\frac{n}{n-i}E[Ti​]=P(Ti​)1​=n−in​ E[x]=∑0n−1nn−i=∑1nniE[x]=\sum_0^{n-1}\frac{n}{n-i}=\sum_1^n ...

说在前面： 算是第一个还有一点点用的小程序，最初是因为集训队里统计codeforces信息太麻烦了，就翻了翻api写了一个小爬虫，按照集训队里的统计格式输出了一下。 程序写的很简陋，如果有幸有大佬需要用到的话…喷的时候轻一点。 介绍： 基于codeforces api，快（慢）速批量统计近一个月用户分数变化，当前分数，正式赛场数和虚拟赛场数。 使用： 将codeforces账号放到account中，使用Scripts中的python.exe运行main.py即可。 链接：https://github.com/rwbyblake/cfcount

Codeforces Round #728 (Div. 2) 题意： 给定一棵有nnn个节点的树，第一次可以在树上等概率选择一个节点，之后每次在与已选择节点相连的未选择节点里等概率选择一个节点，直到全部选完。问按选择顺序排序的数组中，逆序对数量的期望。 解析： 这个问题可以看做为固定一个节点，并从固定的节点开始逐渐拓展节点的过程。固定节点之后，我们可以求以当前固定节点为根的一种期望。 考虑一对节点(a,b)(a,b)(a,b)，其中a<ba<ba<b，那么这对节点对答案有贡献当且仅当bbb在aaa之前被遍历到。由于树当中根节点到达一个点仅有一条路径，且在到达lca(a,b)lca(a,b)lca(a,b)节点前的概率，和选择不在路径上的节点的概率，对bbb和aaa谁先选择到的概率无影响，故仅需考虑lca(a,b)lca(a,b)lca(a,b)分别到aaa和bbb的情况即可。 对于上述情况，可以将其上述概率，抽象为两个栈，其中分别有从lca(a,b)lca(a,b)lca(a,b)到aaa和bbb路径上的节点。每次随机从两个栈中取出一个节点，直到b栈先被取空的概率。设 ...

C - Joyride 题意： 游乐园有nnn个游乐设施，mmm条路，游玩第iii个游乐设施需要TiT_iTi​的时间和PiP_iPi​的金钱，走过一条路需要ttt的时间，每遇到一个游乐设施强制游玩，问从1号游乐设施开始到1号游乐设施结束，花费时间为xxx的最小金钱花费。 解析： 这道题xxx较小，可以枚举每一个xxx所对应的从111号设施开始的最小花费，可以直接跑最短路。 代码： 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768#include <bits/stdc++.h>using namespace std;#define fast \ ios_base::sync_with_stdio(false); \ cin.tie(NULL);const int N = 3e3 + 10;const ...

H - Figurines 题意： 有一个展览架，N个不同编号的模型，每天会往上放上模型或拿走模型。同时有一个算法，xi+1=(xi+yi)modNx_{i+1}=(x_{i}+y_i) mod Nxi+1​=(xi​+yi​)modN，其中yiy_iyi​为did_idi​天时，展览架中编号大于等于xix_ixi​的个数。给出每天放上和拿走模型的情况，和每个did_idi​，求xNx_NxN​ 解析： 由于N为1e5级别，无法直接开线段树或者set存每一天的状态，所以需要用可持久化线段树优化一下，基本属于模板题。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081#include <bits/stdc++.h>using namespace std;#define fast ...

D - Shortest Path Query 题意： 给定一个图，图中每一条边的两点符合以下条件：两点编号二进制表示下一个位另一个的前缀。给出q次询问，每次给出u，v，询问u和v之间的最短路。 解析： 字典树符合一个点的为其所有子节点的前缀，故使用字典树对所有点建树，并将原图中的边附加上去，得到一颗有附加边的完全二叉树。对于该图中的任一节点，一个点无法不经过该点从左子树走到右子树，故对于询问的u，v，只需求u和v的所有公共祖先，并对所有公共祖先求min(dis[Lca][u]+dis[Lca][v])min(dis[Lca][u]+dis[Lca][v])min(dis[Lca][u]+dis[Lca][v])即可。对每个公共祖先求最短路可以在用到的时候再求，可以提高速度。 代码： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081 ...