codeforces 145 E. Lucky Queries (线段树lazy标记)

题目链接

题意:给出一串只由数字’4’和’7’组成的串。两种操作,一种是询问整个串中最长非下降子序列的长度,另一种给出区间[l,r],将区间中的没个数反转,反转的定义为,4变成7,7变成4.

思路:线段树lazy标记。

线段树的域记录5个信息,c4,c7,c47,c74,flip,[……]

Read more

codeforces 52 C. Circular RMQ (线段树区间更新,区间询问)

题目链接

题意:一个循环数列,两种操作,一种是把某段区间中加上v,另一种是询问某区间的最小值。对于每个询问,输出答案。

思路:区间更新+区间询问的模板题….

注意体会pushdown以及update的时候。。。

要同时更新tree数组和lazy数组。。。

读入的时候[……]

Read more

重要的事情

我学不会dp不是因为我智商低,而是因为没有足够好的资料。
我学不会dp不是因为我智商低,而是因为没有足够好的资料。
我学不会dp不是因为我智商低,而是因为没有足够好的资料。

hdu 5904 LCIS (dp)

题目链接

题意:
给定两个序列,求它们的最长公共递增子序列的长度, 并且这个子序列的值是连续的
思路:以值为连续做入手点。

很显然个鬼咯
dp[a[i]]表示以a[i]结尾的最大长度。
dp[a[i]] = dp[a[i-1]] + 1
对于b序列一样。

答案为 MAX([……]

Read more

2017 小米 软件工程师 校招 笔试题 (模拟)

题意:一串电话号码,每个数字+8取各位后,把每个数字写成对应的大写英文,从”ZERO”和“NINE”,然后打乱字母的顺序。现在给出打乱的字母顺序,问可能的字典序最小的电话号码是是多少(可能有前导0)

思路:分析0..9 每个数字的英文组成。。。然后大概类似解方程。。可以根据字母的个数确定每个数[……]

Read more

codeforces 380 C. Sereja and Brackets (线段树区间合并)

题目链接
题意:给出一个由‘(’和‘)’组成的字符串。。。然后给出若干查询。。。每个查询一个区间,问区间中能匹配的括号数。。。

思路:考虑某一个区间中的括号匹配。。。其实是一个不断寻找'()’然后删去的过程。。。

因此对于某个区间的括号匹配数。。。等于左边区间和右边区间和合法匹配数之和[……]

Read more

codeforces 594 D. REQ (树状数组+欧拉函数+逆元)

题目链接

题意:给出n个数,q个查询,每组一个区间,询问区间中所有数的乘积的欧拉函数%1E9+7的答案是多少。

思路:这道题需要一点欧拉函数的知识。

phi(n)是欧拉函数,意义为小于等于n并且与n互质的数的个数。

To calculate the answer on eve[……]

Read more

poj 2886 Who Gets the Most Candies? (线段树模拟加强版约瑟夫问题+反素数)

poj 2886 题目链接

题意:n个人围成一圈,每个人身上由一个数,可正可负。从第k个人开始出圈,如果第k个人身上的数是X,X>0,就左边第x个没有出圈的人出圈,否则右边第-X个人出圈。 第k个人出圈得到的糖果数目为f(k),f(x)表示x的因子个数。现在问谁能拿到最多的糖果,并且拿到[……]

Read more