题目 小G是一个出色的诗人，经常作诗自娱自乐。但是，他一直被一件事情所困扰，那就是诗的排版问题。 一首诗包含了若干个句子，对于一些连续的短句，可以将它们用空格隔开并放在一行中，注意一行中可以放的句子数目是没有限制的。小G给每首诗定义了一个行标准长度（行的长度为一行中符号的总个数），他希望排版后每行的长度都和行标准长度相差不远。显然排版时，不应改变原有的句子顺序，并且小G不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下，小G对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的P次方，而一个排版的不协调度为所有行不协调度的总和。 小G最...

题目 You have been hired to supervise the project of a new amusement park. The park will have a special gimmick: directed slides that can get customers from one attraction to another quickly and in an entertaining way. The park owner has given you the current project: a list of planned attractions a...

题目 机器上有N个需要处理的任务，它们构成了一个序列。这些任务被标号为1到N，因此序列的排列为1,2,3...N。这N个任务被分成若干批，每批包含相邻的若干任务。从时刻0开始，这些任务被分批加工，第i个任务单独完成所需的时间是Ti。在每批任务开始前，机器需要启动时间S，而完成这批任务所需的时间是各个任务需要时间的总和。注意，同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数Fi。请确定一个分组方案，使得总费用最小。 思路 首先显然是\(dp\)划分状态。 \[ dp[i]=min(dp[j]+t[i]*(f[i]-f[j])+s*f[n]-s*f[j]) \] 不...

题目 给你一个N*N的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第K小数。 思路 整体二分。 整体二分主要适用于对于二分状态的改变，可以在可接受的复杂度内修改的题目。 就本题而言，二分答案，如果考虑将[1,mid]的区间内的点加入树状数组中，在二维平面上标记为1，然后比较每个询问与K的关系，接着将询问分组，接着二分。 以上应该是整体二分的基本模型。 代码 #include<bits/stdc++.h> #define M 60005 using namespace std; struct node{ int x,y,val; bool opera...

题目 佳媛姐姐过生日的时候，她的小伙伴从某宝上买了一个有趣的玩具送给他。玩具上有一个数列，数列中某些项的值可能会变化，但同一个时刻最多只有一个值发生变化。 现在佳媛姐姐已经研究出了所有变化的可能性，她想请教你，能否选出一个子序列，使得在任意一种变化中，这个子序列都是不降的？请你告诉她这个子序列的最长长度即可。 注意：每种变化最多只有一个值发生变化。 在样例输入1中，所有的变化是 1 2 3 2 2 3 1 3 3 1 1 3 1 2 4 选择子序列为原序列，即在任意一种变化中均为不降子序列在样例输入2中，所有的变化是: 3 3 3 3 2 3 选择子序列为第一个元素和第三个元...

题目 平面上有若干个点，现在要求用最少的底边在X轴上且面积小等A的矩形覆盖所有点，这些矩形可以重叠。 N<=100，A<=2000000 思路 一开始想的是简单的区间dp。 \(f[l,r]\)表示覆盖完\([l,r]\)一段区间的所有点的最小矩形数，然后很快就发现了不对之处： 对于图中所示情况，单纯考虑区间之间的分割是行不通的，也就是说，对于相互重叠的矩形，高度那一维也很有必要记录。 重新定义状态：\(f[i][j][k]\)当\([i,j]\)区间，高度\(>k\)的点被覆盖的最优情况。 接下来考虑从上往下转移： 对于当前区间\([l,r,h]\)，一...

题目 LOJ链接 思路 首先认识到：对于好几堆石子来说，它们总的SG值等于每一个石子的SG值的亦或和。 证明： 参见： 浅谈算法——博弈论（从零开始的博弈论） 对于每一个需要求SG值的\(x\) 首先考虑70分的暴力写法： 可以直接暴力求SG void GetSG(int n,int f){ for(int i=f;i<=n;i++){ memset(mark,0,sizeof(mark)); for(int j=2;j<=i;j++){ int t=i/j,d=i%j; int...

题目 The repetition number of a string is defined as the maximum number R such that the string can be partitioned into R same consecutive substrings. For example, the repetition number of "ababab" is 3 and "ababa" is 1. Given a string containing lowercase letters, you are to find...

题目 loj题目链接 思路 研究代码发现，她的树状数组实际上询问的是\([l-1,r-1]\)的抑或和，所以题目的询问实际上就可以转化为\(l-1\)上的元素与\(r\)上的元素相同的概率。 一开始想的是，线段树维护每一个元素是\(1\)的概率是多少，然后进行数学运算，得到答案，然后发现，两点之间的概率不是相互独立的。 比如说修改了\([l,r]\)的区间，那么如果这次修改的结果是\(l\)，那么\(r\)在此次收到的影响就必然是\(0\)，但是如果按照上文的思路，我们实际上对于这两个数都施加了影响，这显然是不对的。 所以对于查询的点对而言，暴力的写法就是循环一遍每一个询问，然后具...

题目 Byteland一直以奇妙的跳舞蝇而闻名于世。驯养的苍蝇能和着音乐的节奏精确地做每一次飞跃。通常，训练者会在 桌上放一排硬币，这些硬币的排列并不按照特定的顺序。每枚硬币上都有一行题字：i→j，i是这枚硬币的编号，j 是站在硬币i上的苍蝇下一步应该飞往的硬币编号。训练者在每个硬币上放一只苍蝇，然后开始放音乐。那些苍蝇 就跟着音乐的节拍开始跳舞，在每一拍中苍蝇都会直接跳到编号为j的硬币上。在舞蹈中，可能会出现多只苍蝇在 同一硬币上的情况。这样，跳舞蝇就会一起继续表演。假定有n只苍蝇，n枚硬币。则一旦确定了n枚硬币上的题字 ，那么这场表演也就确定了。然而，对硬币不同的设置也可能导致相同的表演...