#SCOI2007

BZOJ1071 [SCOI2007]压缩 其他

  有两个序列a[1..n],b[1..n],其编号为1..n,设为s序列。现在我们要求出最长的满足条件的s的子序列s',设va=min(a[s[i]]),vb=min(b[s[i]]),满足对于所有的j=s'[i],A*(a[j]-va)+B*(b[j]-vb)<=C。   设v[i]=A*a[i]+...

BZOJ1073 [SCOI2007]kshort K短路,A*

  以距离为第一关键字,字典序为第二关键字,在所有的从S到T的路径中,选择不重复经过某一节点的第k条路径。   第k短路模板题。  A*跑一跑就可以了。UPD(2018-08-24):  这题是以前坑下的。就让他坑着吧。要做k短路的读者请移步BZOJ1975魔法猪学院   这后面的东西就不要看了吧&...

BZOJ1067 [SCOI2007]降雨量 线段树

  给定n组整数对(Xi,Yi),当Xi<Xj且Yi>=Yj时,如果对于任意的Xk,有Xi<Xk<Xj,Yk严格小于Yj,则称Xi是Xi到Xj中最牛的点。例如4个整数对(2002,4920),(2003,5901),(2004,2832),(2005,3890),则可以说&l...

BZOJ1068 [SCOI2007]压缩 区间动态规划 字符串

   (其实是复制的)  给一个由小写字母组成的字符串,我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以(但不必)包含大写字母R与M,其中M标记重复串的开始,R重复从上一个M(如果当前位置左边没有M,则从串的开始算起)开始的解压结果(称为缓冲串)。bcdcdcdcd可以压缩为b...

1069: [SCOI2007]最大土地面积|旋转卡壳

旋转卡壳就是先求出凸包。然后在凸包上枚举四边形的对角线两側分别找面积最大的三角形因为在两側找面积最大的三角形的顶点是单调的所以复杂度就是n2单调的这个性质能够自行绘图感受一下,似乎比較显然#include<algorithm>#include<iostream>#include<cstdl...

BZOJ 1074: [SCOI2007]折纸origami

TimeLimit:20Sec MemoryLimit:162MBSubmit:354 Solved:212[Submit][Status][Discuss]Description  桌上有一张边界平行于坐标轴的正方形纸片,左下角的坐标为(0,0),右上角的坐标为(100,100)。接下来执行n条折...

BZOJ 1073: [SCOI2007]kshort

TimeLimit:20Sec MemoryLimit:162MBSubmit:1456 Solved:365[Submit][Status][Discuss]Description  有n个城市和m条单向道路,城市编号为1~n。每条道路连接两个不同的城市,且任意两条道路要么起点不同要么终点不同,因...
代码星球 ·2020-04-05

BZOJ 1072: [SCOI2007]排列perm

TimeLimit:10Sec MemoryLimit:128MBSubmit:2599 Solved:1624[Submit][Status][Discuss]Description  给一个数字串s和正整数d,统计s有多少种不同的排列能被d整除(可以有前导0)。例如123434有90种排列能被2...

BZOJ 1071: [SCOI2007]组队

TimeLimit:3Sec MemoryLimit:128MBSubmit:2420 Solved:769[Submit][Status][Discuss]Description  NBA每年都有球员选秀环节。通常用速度和身高两项数据来衡量一个篮球运动员的基本素质。假如一支球队里速度最慢的球员速度...
代码星球 ·2020-04-05