题目链接 题意：已知 f(1, j) = a[j] f[i][j] = min (f[i-1][j],f[i-1][j-1]) 然后给出 n n≤1E5​​ 个数（a[i] a​i​​≤1E4​​)，给出 m组查询（m<=1E5），每组两个数 x,y 问 f(x,y) 是多少。 参考题解：茶姐的回答（下标好像搞错了，领会意思即可 官方题解 以及前置技能点是：斜率优化+线段树 思路：考虑一排数a[1]到a[n]，原问题可以转化成从a[y]走x-1步，每一步原地不动或者向左移动一个格子后的总的代价。 Function is calculated as follows: , k__i — how many times we …

题目链接 题意：n个数，分成若干段，每段的代价为 ，求最小代价。 思路：dp。 状态方程很显然个鬼。。。 dp[i] 表示处理完前面i个数的最小代价。 dp[0] = 0 ; dp[i] = min(dp[j]+(sum[i]-sum[j])^2) ( 0<j <i),sum[i]为a[i]的前缀和。 这复杂度是n^2的。。。然而n最大5E5.....boom.... 斜率优化登场！ 这篇博客讲得非常好 我们假设k两边移项一下，得到：(dp[j]+num[j]^2-(dp[k]+num[k]^2))/(2*(num[j]-num[k]))<sum[i]。我们把dp[j]-num[j]^2看做是yj， …

浅谈数形结合思想在信息学竞赛中的应用 参考博客 这个东西英文好像叫做：convex hull trick Convex_hull_trick_wiki codeforces convex hull trick 简单说说我的理解：斜率优化是一种数形结合的思想。。。 对于一个dp的若干状态。。。有些状态是不会对答案有贡献的。。。这些我们就可以不考虑。。。 简单地说。。。如果把状态的下标和状态对应成二维平面的点。。。 凸起来的点一定不会影响答案。。。 具体证明参考论文。。。。。 也就是维护一个"下凸折线" 具体维护的办法是用单调队列来维护。。。 感觉还是挺简单的。。。。

题意：一串电话号码，每个数字+8取各位后，把每个数字写成对应的大写英文，从"ZERO"和“NINE”，然后打乱字母的顺序。现在给出打乱的字母顺序，问可能的字典序最小的电话号码是是多少（可能有前导0） 思路：分析0..9 每个数字的英文组成。。。然后大概类似解方程。。可以根据字母的个数确定每个数字的个数。。。 然后-8。。。存一下排个序就好了。。。1A #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> …

题目链接 题意：给出一个由‘(’和‘）’组成的字符串。。。然后给出若干查询。。。每个查询一个区间，问区间中能匹配的括号数。。。 思路：考虑某一个区间中的括号匹配。。。其实是一个不断寻找'()'然后删去的过程。。。 因此对于某个区间的括号匹配数。。。等于左边区间和右边区间和合法匹配数之和，再加上左区间和右区间新的能匹配到一起的括号数。 （说“因此”是因为。。。只要左边有没匹配的左括号。。。右边有没匹配的右括号。。。因为他们中间有的都是匹配好的括号，会被删除。。。所以两边的括号总能匹配在一起） 具体做法是： 线段树的节点中有三个域，分别表示，合法的括号匹配数，没有被匹配的左括号数，和没有被匹配的右括号数。 query的时候要合并左右两个 …

。。。。。 代码不会写。。。成绩又烂。。。又不会勾搭妹子。。。。 。。。。。。 对比一下。。。。。算了还是不对比了。。。。。 啊。。。人生啊。。。活得好失败T T

是14年才被提出来的算法... 先%一下该算法的作者：作者的codeforces页 接下来，老规矩，放一波资料： 参考博客1 codeforces上的讲解 20171115 update: emmmm，这篇是学习笔记是１６年９月写的。。。。一转眼13个月过去了啊。。 回文树，也叫回文自动机，简称PAM 学了SAM之后PAM简直是傻逼算法... 该算法时间和空间复杂度都是O(n) 这样的复杂度基于以下结论： 长度为n的字符串的本质不同的回文串的数目不超过n 因此状态数开到和字符串长度一样就可以了orz len表示某个状态所表示的回文串的长度 cnt表示某个状态所表示的回文串的数量 构建PAM的算法仍然是增量算法，在某一时刻，本质不同的 …

题目链接 题意：给出n个数,q个查询，每组一个区间，询问区间中所有数的乘积的欧拉函数9+7的答案是多少。 思路：这道题需要一点欧拉函数的知识。 phi(n)是欧拉函数，意义为小于等于n并且与n互质的数的个数。 To calculate the answer on every query let's use the formula , where _p_1, p_2, ..., p__k — all prime numbers which divided_n. 如果知道欧拉函数的这个公式。。。那么这道题就成了水题。。。。 考虑两个数a,b的欧拉函数。 一开始考虑也许有什么性质。。。查了下欧拉函数的wiki 欧拉函数_维基百科 欧拉函数 …

poj 2886 题目链接 题意：n个人围成一圈，每个人身上由一个数，可正可负。从第k个人开始出圈，如果第k个人身上的数是X,X>0，就左边第x个没有出圈的人出圈，否则右边第-X个人出圈。 第k个人出圈得到的糖果数目为f(k)，f(x)表示x的因子个数。现在问谁能拿到最多的糖果，并且拿到了多少糖果。 思路：看起来好像很麻烦。。其实可以分解成两个问题。 第一个子问题就是约瑟夫问题的加强版。。。每次间隔不是定数，而取决与上一次出队的人。。。 终点是数据有5E5.。。模拟的话会炸掉。。。所以用线段树来模拟这个过程。。。 类似于那道插队的问题。。。线段树的域存的是某区间中空位置的数量。。初始为1.。。 然后每次update的时候优先查 …

1053: [HAOI2007]反素数ant Time Limit: 10 Sec Memory Limit: 162 MB Submit: 2750 Solved: 1559 [Submit][Status][Discuss] Description 　对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足：g(x)>g(i) 0<i<x ，则称x为反质数。例如，整数1，2，4，6等都是反质数。现在给定一个数N，你能求出不超过N的最大的反质数么 ？ Input 　一个数N（1<=N<=2,000,000,000）。 Output 　不超过N的最大的反质数。 …