Xiao Luo

UVA11400定义：$dp[i]$为考虑前种中灯泡的最小花费，$PrefixSum[i]$为前i种灯泡的需求量之和（前缀和）。初始化：123for (int i = 0; i < n; ++i) { dp[i] = lamps[i].K + PrefixSum[i] * lamps[i].C; }即前i种灯泡的需求都由第i种灯泡满足。转移方程:显然，一个种类的灯泡要么不替换，要么全部替换成另一种灯泡。首先先将灯泡种类按电压由底到高排序，这样在考虑$dp[i]$时，第$j(0\leq j <i)$个灯泡都可以被第$i$个灯泡所替换，得到方程： dp[i] = min(dp[i], dp[j] + (PrefixSum[i] - PrefixSum[j]) * lamps[i].C + lamps[i].K)(0\leq j

阿里云服务器上添加Qt库的方法（会自动根据当前已安装的版本下载对应版本）：sudo apt-get install libqt5websockets5-dev会安装libqt5websockets5.so

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

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}p_i\neq N$ 。那咋办呢？由唯一分解定理，$N=\sum\limits_{i=1}^{n}p_i^{a_i}$，其中由于$p$是素数，所以对于任意的$1\leq i,j\leq n,i\neq j$，有$p_i^{a_i}$与 ...

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

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.后缀连接树的性质：根据自动机和后缀连接树的性质，当前状态的子 ...

ZOJ - 3987 DreamGrid has a nonnegative integer n. He would like to divide n into m nonnegative integers $a_1, a_2, \dots, a_m$​ and minimizes their bitwise or (i.e. $n=a_1 + a_2 + \dots + a_m$​ and $a_1 \text{ OR } a_2 \text{ OR } \dots \text{ OR } a_m$​ should be as small as possible).InputThere are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:The first line contains two integers n and m ($0 \le n < 10^{1000}, 1 ...

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

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选择参加晚会，当且仅当他存在至少一个直接下属 ...

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