Linux添加Qt库的方法
阿里云服务器上添加Qt库的方法（会自动根据当前已安装的版本下载对应版本）：sudo apt-get install libqt5websockets5-dev会安装libqt5websockets5.so
K-th occurrence （后缀自动机上合并权值线段树+树上倍增）
You are given a string $S$ consisting of only lowercase english letters and some queries.For each query $(l,r,k)$, please output the starting position of the k-th occurence of the substring $SlS{l+1}\cdots S_r$ in $S$.InputThe first line contains an integer $T(1≤T≤20)$, denoting the number of test cases.The first line of each test case contains two integer $N(1≤N≤10^5),Q(1≤Q≤10^5)$, denoting the length of $S$ and the number of queries.The second line of each test case contains a string $S(|S|=N ...
Minimum Sum LCM
UVA10791
思路：由$N=lcm(a,b)=\frac{ab}{gcd(a,b)}$可知，当且仅当$gcd(a,b)=1$时，$a+b$的值最小。因为若$gcd(a,b)>1$，则有:
lcm(a,b)=\frac{ab}{gcd(a,b)}=\frac{\frac{a}{gcd(a,b)}b}{1}此时，$\frac{a}{gcd(a,b)}+b<a+b$，结论即证。那么，目标就变成了将$N$分解为若干素数。由唯一分解定理：
N=\sum\limits_{i=1}^{n}p_i^{a_i},p为素数即N可被唯一分解为若干素数的积。那么答案是否就是$\sum\limits{i=1}^{n}(a_ip_i)$了呢？由$lcm(p,p)=p$可知，若将若干个$a$直接加入集合，那么该集合的$lcm=\sum\limits{i=1}^{n}pi\neq N$ 。那咋办呢？由唯一分解定理，$N=\sum\limits{i=1}^{n}pi^{a_i}$，其中由于$p$是素数，所以对于任意的$1\leq i,j\leq n,i\neq j$，有$p_i^{a_i}$与$p_j^ ...
Nature Reserve（三分）
CodeForces - 1059D
题目大意：
平面上有n个点，现在需要找这么一个圆，它与y=0相切，且这n个点都在圆上或圆内，求这个圆的最小半径Input输入n，1 <= n <= 10^5接下来n行，每行表示一个点的坐标，依次是x,y，坐标都是整数且绝对值不超过10^7，同时不存在y=0的点Output这样的圆如果不存在，输出-1，存在则输出其最小半径，误差小于10^-6视为正确，即你的输出可以与样例不同，只要误差在范围内即可Examples Input 10 1 Output 0.5 Input 30 10 20 -3 Output -1 Input 20 11 1 Output 0.625NoteIn the first sample it is optimal to build the circle with the radius equal to 0.5 and the center in (0, 0.5).
思路：由于圆和x横坐标相切，因此所有点必须在x轴得一侧，否则圆势必穿过x轴。已只圆于x轴相切，即$y=r$，根据圆的公式：
r^2= ...
Longest Common Substring（最长公共子串）
SP1811
题目描述A string is finite sequence of characters over a non-empty finite set Σ.In this problem, Σ is the set of lowercase letters.Substring, also called factor, is a consecutive sequence of characters occurrences at least once in a string.Now your task is simple, for two given strings, find the length of the longest common substring of them.Here common substring means a substring of two or more strings. 输入格式 The input contains exactly two lines, each line consists of no more than 250000 low ...
New Distinct Substrings
SP705
Given a string, we need to find the total number of its distinct substrings. Input $T$- number of test cases.$T<=20$; Each test case consists of one string, whose length is $<= 50000$ Output For each test case output one number saying the number of distinct substrings. Example Input:2CCCCCABABAOutput:59
两种做法：1.DP由于在SAM中每一条路径都能走出不同的子串。定义：dp[u]为从状态u出发能到达的所有路径，包括长度为0的。转移方程：
dp[u]=1+\sum\limits_{u->v}{dp[v]}加1是含不往下走，到此为止。那么答案就是dp[0]-1，去除空串。2.后缀连接树的性质：根据自动机和后缀连接树的性质，当前状态的子 ...
Party at Hali-Bula
UVA1220这是一个树上dp问题，求树的最大独立点集。首先，将所有名字都赋予一个编号，这里使用map。定义：$dp[i][0]$为以第$i$名员工为根且第$i$名员工不参加晚会的最优答案，$dp[i][1]$为第$i$名员工参加晚会的答案；$IsRepeat[i][0]$为$dp[i][0]$的答案是否重复，$IsRepeat[i][1]$同理。初始化：
dp[i][0]=0,dp[i][1]=1即表示该根节点没有孩子的情况
IsRepeat=false即一开始没有任何方案，所以都不会重复$\textit{\textbf{dp}}$的状态转移：
dp[i][1]+=dp[Son][0]即i如果参加了晚会，则他的直接下属就不能参加晚会，将他所有的下属不参加晚会的答案累加即可。
dp[i][0]+=max(dp[Son][1],dp[Son][0])即i如果不参加晚会，他的直接下属可来可不来，选择最优的方案。$\textit{\textbf{IsRepeat}}$的状态转移：
IsRepeat[i][1]|=IsRepeat[Son][0]若i选择参加晚会，当且仅当他存在至少一个直接下属 ...
Perfect Pth Powers（唯一分解定理）
UVA10622
由唯一分解定理，将$n$分解后求每个素数项对应的指数的最小公约数即可。虽然$n$在int范围内，但仍要long long，因为int的负数的绝对值比整数大1。
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <cstdio>#include <cstring>using namespace std;int gcd(int a, int b) { while (b) { int temp = a % b; a = b; b = temp; } return a;}int Compute(long long n) ...
Pairs of integers
HDOJ 1554
You are to find all pairs of integers such that their sum is equal to the given integer number N and the second number results from the first one by striking out one of its digits. The first integer always has at least two digits and starts with a non-zero digit. The second integer always has one digit less than the first integer and may start with a zero digit.InputThe input file consists of several test cases.Each test case contains single integer N (10 ≤ N ≤ 10^9), as decribed abov ...
Plants vs. Zombies
ZOJ - 4062
BaoBao and DreamGrid are playing the game Plants vs. Zombies. In the game, DreamGrid grows plants to defend his garden against BaoBao’s zombies. (Image from pixiv. ID: 21790160; Artist: socha) There are nnn plants in DreamGrid’s garden arranged in a line. From west to east, the plants are numbered from 1 to nnn and the iii-th plant lies iii meters to the east of DreamGrid’s house. The iii-th plant has a defense value of did_idi and a growth speed of aia_iai. Initially, di=0d_i = 0d ...
