Xiao Luo

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

题目链接题目要求两个串的最长公共子序列（LCS） LIS（最长上升子序列）最长子序列可以采用动态规划的方法求解。定义：A为一个序列，现在求他的最长上升子序列 （1）$O(N^2)$算法定义：dp[i]为以A[i]结尾的子序列的LIS的长度初始化：$dp[i]=1,0\leq i<|A|$(每个字符本身都可以作为字串，长度为1)转移方程：$dp[i]=max(dp[i],dp[j])$，其中，$j$满足：$0\leq j < i$并且$A[i]>A[j]$结果=$max(dp[i]),0\leq i< |A|$12345678910111213141516171819202122232425#include<iostream>using namespace std;int Array[100001],DP[100001];int main(){ int n; cin>>n; for(int i=0;i<0;++i){ cin>>Array[i]; DP[i]=1; } for(int i= ...

ZOJ - 3993 PUBG is a multiplayer online battle royale video game. In the game, up to one hundred players parachute onto an island and scavenge for weapons and equipment to kill others while avoiding getting killed themselves. BaoBao is a big fan of the game, but this time he is having some trouble selecting the safest building.There are nnn buildings scattering on the island in the game, and we consider these buildings as points on a two-dimensional plane. At the beginning of each round, a circ ...

HDU4622 Now you are back,and have a task to do: Given you a string s consist of lower-case English letters only,denote f(s) as the number of distinct sub-string of s. And you have some query,each time you should calculate f(s[l…r]), s[l…r] means the sub-string of s start from l end at r.Input The first line contains integer T(1<=T<=5), denote the number of the test cases. For each test cases,the first line contains a string s(1 <= length of s <= 2000). Denote the length of s by n. ...

ZOJ - 3985 BaoBao has just found a string (s) of length (n) consisting of ‘C’ and ‘P’ in his pocket. As a big fan of the China Collegiate Programming Contest, BaoBao thinks a substring (s_is_{i+1}s_{i+2}s_{i+3}) of (s) is “good”, if and only if (s_i = s_{i+1} = s_{i+3} =) ‘C’, and (s_{i+2} =) ‘P’, where (s_i) denotes the (i)-th character in string (s). The value of (s) is the number of different “good” substrings in (s). Two “good” substrings (s_is_{i+1}s_{i+2}s_{i+3}) and (s_js_{j+1}s_{j+2}s_{ ...

UVA1210 筛出素数，处理成前缀和，$O(n^2)$枚举每一种和的可能。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <cstdio>#include <cstring>using namespace std;const int MAXN = 10000;bool IsPrime[MAXN + 1];vector<int> PTable;int sum[1230];void InitPTable() { for (int i = 2; i <= MAXN; ++i) { if (IsPrime[i] == false) { PTable.push_back(i); for ...

SP8222 You are given a string S which consists of 250000 lowercase latin letters at most. We define F(x) as the maximal number of times that some string with length x appears in S. For example for string ‘ababa’ F(3) will be 2 because there is a string ‘aba’ that occurs twice. Your task is to output F(i) for every i so that 1<=i<=|S|. Input String S consists of at most 250000 lowercase latin letters. Output Output |S| lines. On the i-th line output F(i). Example Input:ababaOut ...

UVA10375 显然，题目要求有多少二元组$(x,y)$满足$1\leq x,y\leq n且x,y互素$。根据欧拉函数$\phi$的定义，$\phi (n)$为小于n且与n互素的整数个数。定义$f(n)=\sum\limits_{i=2}^{n}\phi(i)$那么对于$x< y或x>y$，都有$f(n)$个整数对满足条件，再加上$(1,1)$，答案为$2*f(n)+1$。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include <iostream>#include <algorithm>#include <cmath>#include <vector>using namespace std;const int MAXN = 50001;int phi[MAXN + 1];int sum[MAXN + 1];//欧拉函数和埃式筛融合void Initphi() { phi[1] = 1; ...

UVA437一种砖块的三个边都可以当作高度，因此n中砖块对应有3n中搭砖方式。定义：dp[i]为一第i中方式为底的最大高度，blocks[i]为第i中搭砖方式。初始化：dp[i]=0，即什么也不放。转移方程：123456789101112int DFS(int Node) { if (dp[Node]) {//如果当前节点已经被搜索过，就直接返回。 return dp[Node]; } dp[Node] = blocks[Node].z;//对应只放当前方式的高度 for (int i = 1; i <= 3 * n; ++i) {//枚举每种搭建方式 if (blocks[Node].Fit(blocks[i])) {//如果第i种方式能放在第Node种上 dp[Node] = max(dp[Node], DFS(i) + blocks[Node].z);//Node放在最底层，然后上面放i的最大高度 } } return dp[Node];}AC代码：123456789101112131 ...

UVA10214 思路：对于坐标为$(x,y)$的树，需要满足$gcd(x,y)=1$这棵树才不会被阻挡。（同一条直线上的树从第二颗起会被遮挡）。根据对称性，设第一象限的答案为$K$，则四个象限的答案为$4K$，再加上，每个坐标轴上能看见一棵树，答案为$4K+4$。由于列比较小，考虑枚举列，对于列x，$1\leq y\leq x$，素数的数量为$\phi(x)$。$\phi$为欧拉函数。根据题目提示$gcd(m,n)=gcd(m+n,n)$，那么得$gcd(x+i,x)=gcd(x,i)$。那么执行$k-1$次$gcd$转换有：$(k-1)x+1\leq y\leq kx\rightarrow 1\leq y \leq x$对于区间$kx+1\leq y\leq b$，直接统计即可。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include <iostream>#include <algori ...