ZJOI2010 网络扩容
【题目】给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求：
1、 在不扩容的情况下，1到N的{zd0}流；
2、 将1到N的{zd0}流增加K所需的最小扩容费用。
【做法】如题所述，1.求{zd0}流2.k次重建图：对于未满流的边，费用为0；满流边，费用为所给。费用流k次增广即可。
【我的代码】点
ZJOI2010 基站选址
【题目】有N个村庄坐落在一条直线上，第i(i>1)个村庄距离第1个村庄的距离为Di。需要在这些村庄中建立不超过K个通
讯基站，在第i个村庄建立基站的费用为Ci。如果在距离第i个村庄不超过Si的范围内建立了一个通讯基站，那么就成它被覆盖了。
如果第i个村庄没有被覆盖，则需要向他们补偿，费用为Wi。现在的问题是，选择基站的位置，使得总费用最小。
{bfb}的数据中，K<=N，K<=100，N<=20,000，Di<=1000000000，Ci<=10000，Si<=1000000000，Wi<=10000。
【做法】很容易想到：用F[i,j]表示在前i个村庄建立j个站点的最小费用（第i个村庄也为基站，这是方便计算），
F[i,j]=min{F[k,j-1]}+Ck+Pki , Pkj表示在i和j为相邻基站时，ij中间的村庄要付的补偿费W的和，
由于N并不小，显然这是不可行的。要用线段树来维护。
首先，对每个村庄预处理，b[i]=d[i]-s[i],e[i]=d[i]+s[i]，这样在b[i]~e[i]之间建立基站的话，村庄i不必付补偿费。
Before[i]为{dy}个d[i]>b[i]的村庄，即i之前{dy}个让村庄不必付补偿费的村庄，before可二分求出。
线段树维护序列F[k,j-1]+Pki,
这样，我们在做F[i,j]的时候，i向后推的过程中，发现在村庄i建立基站的话无法覆盖到村庄p(d[i]>e[p])的话，我们就把
村庄p的补偿费用加到区间[0,before[p]-1]，因为k∈[0,before[i]-1],f[k,j-1]也是无法覆盖到p的。
但是，这里会有个小问题，就是e[p]并不是单调的，i向后推的过程中，你不知道哪些p是无法被i覆盖到的，枚举一遍是
不可能的。发现每个p其实在一个大的j的循环中只计算过一次，所以只要把按e从小到大排序就可解决。
这样的话，答案就是min{F[i,k]+Pi(n+1)}，可以预设一个点n+1,d[n+1]=+inf。如果你嫌麻烦的话，可以自己加一个基
站k+1，限定这个基站必须建在n+1这个村庄，因为d[n+1]=inf，所以第k+1个基站覆盖不到任何点，不影响结果，这时答案是F
[n+1,k+1]。k这维可用滚动省掉空间。
【我的代码】点
SCOI2010 序列操作
【题目】lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，
现在对于这个序列有五种变换操作和询问操作：
0 a b 把[a, b]区间内的所有数全变成0
1 a b 把[a, b]区间内的所有数全变成1
2 a b 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成0
3 a b 询问[a, b]区间内总共有多少个1
4 a b 询问[a, b]区间内最多有多少个连续的1
对于每一种询问操作，lxhgww都需要给出回答，聪明的程序员们，你们能帮助他吗？
对于{bfb}的数据，1<=n, m<=100000
【做法】显然是ws的线段树题，
结点维护9个值：zero,zmaxl,zmaxr,zmaxn,one,omaxl,omaxr,omaxn,sign
分别表示含义：0的个数，从区间最左边l开始的{zd0}连续0个数，xxx最右边r xxxxxx,区间内{zd0}连续0个数，
1的个数，从区间最左边l开始的{zd0}连续1个数，xxx最右边r xxxxxx,区间内{zd0}连续1个数，
标记。
然后各种ws操作就可以过了。
【我的代码】点
SCOI2010 游戏
【题目】不解释
【做法】{zd0}匹配水之
【我的代码】点
ZJOI 数字计数
【题目】给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。
【做法】各个数位计算即可
【我的代码】点
SCOI2010 股票交易
【题目】最近lxhgww又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。
通过一段时间的观察，lxhgww预测到了未来T天内某只股票的走势，第i天的股票买入价为每股APi，第i天的股票卖出价为每股BPi
（数据保证对于每个i，都有APi>=BPi），但是每天不能无限制地交易，于是股票交易所规定第i天的一次买入至多只能购买ASi股
，一次卖出至多只能卖出BSi股。
另外，股票交易所还制定了两个规定。为了避免大家疯狂交易，股票交易所规定在两次交易（某{yt}的买入或者卖出均算是一次交
易）之间，至少要间隔W天，也就是说如果在第i天发生了交易，那么从第i+1天到第i+W天，均不能发生交易。同时，为了避免垄
断，股票交易所还规定在任何时间，一个人的手里的股票数不能超过MaxP。
在第1天之前，lxhgww手里有一大笔钱（可以认为钱的数目无限），但是没有任何股票，当然，T天以后，lxhgww想要赚到最多
的钱，聪明的程序员们，你们能帮助他吗？
对于所有的数据，T,maxP<=2000,1 < =BPi < =APi < =1000,1 < =ASi,BSi < =MaxP
【做法】F[i,j]表示到第i天，手上还有j股股票的{zd0}收益。
F[i,j]=max{F[i-1,k]-APi*(k-j),F[i-1,k]+BPi*(j-k)},k由ASi,BSi限定。
开个单调队列存下F[i-1,j-1]的信息即可。
【我的代码】点
JSOI2010 下棋问题
【题目】两人轮流下棋子，下该棋子得分为此时棋盘上的无障碍矩形个数，无障碍的矩形定义为由两个棋子作为矩形的
对角线，并且这个矩形内无其它棋子。给出N个棋子的坐标，输出两人的得分。N<=5000
【做法】TAT..我自己的方法都自己觉得麻烦，限于表达能力，还是不讲了~供各位神牛BS
大概的做法是，每下一个棋子，把之前的棋子划分到4个象限里，通过求单调可算出与当前棋子相关多出的矩形数，
当然，同时当前棋子可能破坏了位于对角两个象限构成的矩形数，可通过一系列映射求出个数。
P.s.我做的时候写得很麻烦，写的是N^2logN的，{zd0}点大概要7s，v7完善了我的做法，是N^2的（orz）
【我的代码】点（慎重= =是O(N^2logN)的）
JSOI2010 缓存交换
【题目】在计算机中，CPU只能和高速缓存Cache直接交换数据。当所需的内存单元不在Cache中时，则需要从主存里
把数据调入Cache。此时，如果Cache容量已满，则必须先从中删除一个。
例如，当前Cache容量为3，且已经有编号为10和20的主存单元。
此时，CPU访问编号为10的主存单元，Cache命中。
接着，CPU访问编号为21的主存单元，那么只需将该主存单元移入Cache中，造成一次缺失（Cache Miss）。
接着，CPU访问编号为31的主存单元，则必须从Cache中换出一块，才能将编号为31的主存单元移入Cache，假设我们移出了编
号为10的主存单元。
接着，CPU再次访问编号为10的主存单元，则又引起了一次缺失。我们看到，如果在上一次删除时，删除其他的单元，则可以避
免本次访问的缺失。
在现代计算机中，往往采用LRU(最近最少使用)的算法来进行Cache调度——可是，从上一个例子就能看出，这并不是{zy}的算法
。
对于一个固定容量的空Cache和连续的若干主存访问请求，聪聪想知道如何在每次Cache缺失时换出正确的主存单元，以达到最少
的Cache缺失次数。
N,M<=100000
【做法】(显然是FJOI省选题的出处，我再次囧rz)贪心+堆
【我的代码】点
HNOI2010 最长公共子序列
【题目】输出两串的最长公共子序列及方案总数。长度<=50000
【做法】（显然我被第二问虐了）F[i,j]表示A串前i个字符，B串前j个字符的最长公共子序列。
仅当A[i]=B[j]时，F[i,j]有值。G[i,j]为其方案总数。维护F[i-1,1]~F[i-1,j-1]的{zd0}值，更新F[i,j]即可。
【我的代码】点
HNOI2010 订货
【题目】某公司估计市场在第i个月对某产品的需求量为Ui，已知在第i月该产品的订货单价为di，上个月月底未销完的单
位产品要付存贮费用m，假定{dy}月月初的库存量为零，第n月月底的库存量也为零，问如何安排这n个月订购计划，才能使成本
{zd1}？每月月初订购，订购后产品立即到货，进库并供应市场，于当月被售掉则不必付存贮费。假设仓库容量为S。
0<=n<=50, 0<=m<=10, 0<=S<=10000
【做法】F[i,j]表示前i个月，库存量为j的最少花费。
F[i,j]=min{F[i-1,k]+(j+Ui-k)*di}+j*m , j+Ui>=k
把式子拆开F[i,j]=min{(F[i-1,k]-k*di+Ui*di)+j*di}+j*m
这样F[i,j]只和k的取值有关，只要找一个k使()内值最小即可，
发现j+Ui>=k,k的取值范围随j增加扩大，所以只要存一个最小值即可。
【我的代码】点
HNOI2010 软件安装
【题目】现在我们的手头有N个软件，对于一个软件i，它要占用Wi的磁盘空间，它的价值为Vi。我们希望从中选择一些
软件安装到一台磁盘容量为M计算机上，使得这些软件的价值尽可能大（即Vi的和{zd0}）。
但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作（
软件i依赖软件j）。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为0。
我们现在知道了软件之间的依赖关系：软件i依赖软件Di。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安
装一次，如果一个软件没有依赖则Di=0，这时只要这个软件安装了，它就能正常工作。
0<=N<=100, 0<=M<=500
【做法】明显的树型动规。麻烦点就是软件的依赖可能存在环，这时候我们需要强连通缩点，我比较ws的用Floyd缩点
【我的代码】点
HNOI2010 工厂选址
【题目】某地区有m座煤矿，其中第i号矿每年产量为ai吨，现有火力发电厂一个，每年需用煤b吨，每年运行的固定费用
（包括折旧费，不包括煤的运费）为h元，每吨原煤从第i号矿运到原有发电厂的运费为Ci0（i=1，2，…，m）。
现规划新建一个发电厂，m座煤矿每年开采的原煤将全部供给这两座发电厂。现有n个备选的厂址。若在第j号备选厂址建新厂，每
年运行的固定费用为hj元。每吨原煤从第i号矿运到j号备选厂址的运费为Cij（i=1，2，…，m；j=1，2，…，n）。
试问：应把新厂厂址选取在何处？m座煤矿开采的原煤应如何分配给两个发电厂，才能使每年的总费用（发电厂运行费用与原煤运
费之和）为最小。
对于所有数据, n<=50, m<=50000, b<=10000
【做法】一看题，直接可以想到用费用流来做，但是点数太多，只能过7个点。其实贪心就可以过了，一开始当作全是送
到旧发电厂，然后选sigma(Ai)-b个差价{zd0}的移送到新的去= =
【我的代码】点
AHOI2009 行星序列
【题目】老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。
有长为N的数列，不妨设为a1,a2,…,aN 。有如下三种操作形式：
(1)把数列中的一段数全部乘一个值;
(2)把数列中的一段数全部加一个值;
(3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。
【做法】裸裸的线段树。我一开始做，一碰到标记不同的马上就下传，结果只过了3个点的说= =
果断被众人BS.....原来传递值换成*a+b的形式即可。乘一个值的时候用*A+0，加一个值的时候用*1+A。
标记的值可以用乘法分配律修改。
【我的代码】点
AHOI2009 同类分布
【题目】在模拟飞行的过程中，小可可发现在一个未知星球周围分布着许多同类的小行星带，而这些小行星带的分布非
常有规律，经过研究发现实些小行星带到未知星球的距离为x（x为非负整数）与如下的函数有一定的关系：
dsum（x）=0 （x=0）
dsum（x）=dsum（x div 10）+x mod 10 （x<>0)
即x可以被dsum（x）整除。小可xx常希望能研究出距离这个未知星球的某一区域内小行星带的分布规律，具体来说，就是在与
未知行星距离a和b的范围内分布了多少个小行星带，你能帮助他解决这个问题吗？
100％的数据中，a，b不超过100000000000000000（10的18次方）
【做法】F[i,j,k,l]表示位数为i，各位上的值和为j，模k余l的数的总数。然后根据读入的a,b计算。
我一开始这样写结果MLE了，所以i这一维要滚动...
【我的代码】MLE代码（递归） 点
AC代码 点
AHOI2009 中国象棋
【题目】在N行M列的棋盘上，放若干个炮可以是0个，使得没有任何一个炮可以攻击另一个炮。
请问有多少种放置方法，中国像棋中炮的行走方式大家应该很清楚吧.
N,M<=100
【做法】显然是要求每行每列的炮个数<=2。
从{dy}列扫过去，F[i,j,k]表示填到第i列，N行中，有j行没有棋子，k行只有一枚棋子，其余行都是放2枚棋子的方案总数
。 显然这一列最多放2枚棋子，在j和k这两种状态中枚举即可。
【我的代码】点
AHOI2006 上学路线Route
【题目】可可和卡卡家住合肥市的东郊，每天上学他们都要转车多次才能到达市区西端的学校。直到有{yt}他们两人参
加了学校的信息学奥林匹克竞赛小组才发现每天上学的乘车路线不一定是{zy}的。
可可：“很可能我们在上学的路途上浪费了大量的时间，让我们写一个程序来计算上学需要的最少时间吧！”
合肥市一共设有N个公交车站，不妨将它们编号为1…N的自然数，并认为可可和卡卡家住在1号汽车站附近，而他们学校在N号汽
车站。市内有M条直达汽车路线，执行第i条路线的公交车往返于站点pi和qi之间，从起点到终点需要花费的时间为ti。(1<=i<=M,
1<=pi, qi<=N)
两个人坐在电脑前，根据上面的信息很快就编程算出了{zy}的乘车方案。然而可可忽然有了一个鬼点子，他想趁卡卡不备，在卡卡
的输入数据中删去一些路线，从而让卡卡的程序得出的答案大于实际的最短时间。而对于每一条路线i事实上都有一个代价ci：删去
路线的ci越大卡卡就越容易发现这个玩笑，可可想知道什么样的删除方案可以达到他的目的而让被删除的公交车路线ci之和最小。
2<=N<=500, 1<=M<=124 750, 1<=ti, ci<=10 000
【做法】先 SPFA求最短路，然后根据最短路建图，求最小割。方案的输出：从S开始，遍历残余网络，将图划分为两个
部分，两个部分之间的满流边即为可行的割。
【我的代码】点（慎，巨长）
AHOI2006 基因匹配Match
【题目】卡卡昨天晚上做梦梦见他和可可来到了另外一个星球，这个星球上生物的DNA序列由无数种碱基排列而成（地
球上只有4种），而更奇怪的是，组成DNA序列的每一种碱基在该序列中正好出现5次！这样如果一个DNA序列有N种不同的碱基
构成，那么它的长度一定是5N。
卡卡醒来后向可可叙述了这个奇怪的梦，而可可这些日子正在研究生物信息学中的基因匹配问题，于是他决定为这个奇怪星球上的
生物写一个简单的DNA匹配程序。
为了描述基因匹配的原理，我们需要先定义子序列的概念：若从一个DNA序列（字符串）s中任意抽取一些碱基（字符），将它们
仍按在s中的顺序排列成一个新串u，则称u是s的一个子序列。对于两个DNA序列s1和s2，如果存在一个序列u同时成为s1和s2的子
序列，则称u是s1和s2的公共子序列。
卡卡已知两个DNA序列s1和s2，求s1和s2的{zd0}匹配就是指s1和s2最长公共子序列的长度。
[任务]
编写一个程序：
从输入文件中读入两个等长的DNA序列；
计算它们的{zd0}匹配；
向输出文件打印你得到的结果。
【做法】题目很长，其实很水，树状数组水之。(P.s.v7的另类方法很巧妙~不过我没实现过= =）
【我的代码】点
AHOI2008 聚会Meet
【题目】Y岛风景美丽宜人，气候温和，物产丰富。Y岛上有N个城市，有N-1条城市间的道路连接着它们。每一条道路
都连接某两个城市。幸运的是，小可可通过这些道路可以走遍Y岛的所有城市。神奇的是，乘车经过每条道路所需要的费用都是一
样的。
小可可，小卡卡和小YY经常想聚会，每次聚会，他们都会选择一个城市，使得3个人到达这个城市的总费用最小。
由于他们计划中还会有很多次聚会，每次都选择一个地点是很烦人的事情，所以他们决定把这件事情交给你来完成。他们会提供给
你地图以及若干次聚会前他们所处的位置，希望你为他们的每一次聚会选择一个合适的地点。
{bfb}的数据中，N<=500000，M<=500000。
【做法】Lca转RMQ，答案定为三人其中两人的LCA，枚举下即可~
【我的代码】点
