Always on the way

题目链接题目要求两个串的最长公共子序列（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 - 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 ...

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

UVA11105 线性筛即可。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include <iostream>#include <algorithm>#include <cmath>#include <vector>using namespace std;const int MAXN = 1000001;bool IsNotHPrimer[MAXN + 1];bool IsSemiHPrimer[MAXN + 1];int sum[MAXN + 1];vector<int> HPrimer;void InitIsHPrimer() { for (int i = 5; i <= MAXN; i += 4) { if (IsNotHPrimer[i]) { continue; } HPrimer.push_ba ...

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

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

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 (sis{i+1}s{i+2}s{i+3}) of (s) is “good”, if and only if (si = s{i+1} = s{i+3} =) ‘C’, and (s{i+2} =) ‘P’, where (si) 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 (sjs{j+1}s{j+2}s{j+3}) are differ ...

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

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