相关链接0
相关链接1

NOI2012结束了,对本沙茶来说就是鸡肋之战,因为不管得多少分都木有用,只能得到像废纸一样的成绩证明(其实就连这个,本沙茶都木有拿到囧)
而AHOI2012选出来的安徽省队,成绩史上最差,正式选手首次Au、Ag都木有,在忽略团体对抗赛的情况下,团体分全场Rank20,东部倒数第二……
唯一值得庆幸的是团体对抗赛得了Rank4,而且是在决赛时RP耗尽导致的……

真真切切希望:
(1)2012~2013赛季中,自己的水平能快速提高,早日脱菜;
(2)NOIP2012 AH 1=分数线不低于全国划线;
(这个梦想已经破灭了……唯一能希望的就是CCF NOI2013省队名额改革,要是真改不了就用尽全力挤进前4吧囧……毕竟2011年本沙茶都干出过这个,2013年应该也可以囧)
(3)AHOI2013不要再出像今年这样的题了,至少要保证每题都有正解、数据范围不骗人;
(4)NOI2013上,AH今年的悲剧不要重演,团体分至少进Rank12……

其它就木有神马可说的了囧。

(本沙茶曾经在网络上消失了很长一段时间,现在回来了,原来那个帖子删除)

posted @ 2012-08-05 00:32 Mato_No1 阅读(947) | 评论 (7)编辑 收藏

     摘要: 【异或(XOR)运算由于与“奇偶性”密切相关,经常出现在有关奇偶性和二进制的题目中】很多异或问题都要涉及到解异或方程组,因此首先要搞懂异或方程组的解法。(1)异或方程组的格式(设有n个未知数,m个方程):a11*x1 XOR a12*x2 XOR ... XOR a1n*xn = b1a21*x1 XOR a22*x2 XOR ... XOR a2n*xn = b2R...  阅读全文

posted @ 2012-05-20 10:17 Mato_No1 阅读(9810) | 评论 (4)编辑 收藏

【dispatching】
(这题国内数据极弱,暴力能80,下面的解法1,平衡树即使用Splay Tree实现都能AC)
枚举管理者所在的结点,然后在这个结点及其所有后代中找到权值前K小的,使得它们的权值和不超过限制,要求求出K的最大值。
解法1:将每个结点及其所有后代的权值存在一个平衡树里,然后,对于每个结点,若不是叶结点,就将其所有的子树中,找到最大的那棵子树,它所表示的平衡树不动,将其它的子树表示的平衡树上的所有结点强行拆开,并插入到这个子树表示的平衡树中(这叫启发式合并),别忘了将该结点本身也合并到这棵平衡树里。合并好了以后,通过每个点记录的sum(下面说明),用类似于求结点排名的方法,就可以求出K的最大值了。
容易证明,这样合并的话,在整个过程中插入的次数是O(NlogN)的,加上平衡树插入本身的O(logN),总的时间复杂度为O(Nlog2N)。
具体实现起来有一些技巧:
(1)可以发现,在合并过程中,各个点本身并没有变,而只是它们之间的关系发生了变化(从不在同一棵树上变成在同一棵树上了),因此为了节省空间,可以预先将所有的结点建好,每个结点除了自身权值以外还记录mul(初始为1)、sz(初始为1)、sz0(初始为1)、sum(初始等于权值)等信息,其中mul为重复次数,sz为考虑mul情况下的树的大小,sz0为不考虑mul的情况下的树的大小(也就是实际结点个数),sum表示树上所有结点的总权值(这个当然要考虑mul了)。之所以维护sz0,是因为每次可以通过找到sz0最大的子树不动来加速。插入的操作是void ins(int r, int No),表示将结点No(是结点不是值)插入到以r为根的子树里,注意这个结点No的mul可能大于1,因此在插入后维护的时候需要注意;
(2)由于在过程中会同时有多棵平衡树存在,因此每个点还需要记录一个额外的域rf,rf=-1表示该结点不是任何一棵平衡树的根结点,rf>=0表示该结点是原树中编号为rf的结点表示的平衡树的根结点,同时记录root[i]表示结点i表示的平衡树的根结点编号,这样就可以很方便地实现树内外的对接(注意这两个值的维护,尤其是将结点i本身合并到平衡树里的时候,别忘了把root[i]改掉)。
解法2(正解):合并的时候使用可并堆(用左偏树或斜堆实现),时间复杂度O(NlogN)。

【guard】
(这题其实很容易想到网络流的话说……不过仔细研究一下就可以发现,由于报告上来的只是某一个区间内有木有人,而不是有几个人,因此无法用网络流的流量平衡来表示)
首先,某些区间报告木有人,这些区间内的点肯定不符合要求了,可以将它们删掉,然后对于剩下的(可能是若干段)区间,合并起来,对结点从左到右重新编号(这一步可以用线段树,也可以排序后直接扫描,见这里,本沙茶比赛时为了省事直接上线段树了),然后就只需要考虑那些报告有人的区间了囧……当然,这些区间的端点也是要对应地重新编号的,编号完了以后,将所有包含别的区间的区间删去(因为它们的存在木有意义),方法:对于所有重编号后的区间,将其按照先左端点递增,后右端点递减排序,然后设置一个栈,保证栈中的区间左右端点均严格递增,按照排序之后的顺序扫描每个区间,每次一个新区间入栈时,栈顶所有右端点大于等于这个新区间右端点的区间出栈,再将新区间入栈,这样最后栈中的区间就是保留下来的区间了囧……而且已经排序……
然后,如果问题是求至少要多少个人的话,就是一个经典的贪心模型了,扫描排序后的区间,如果一个区间内还木有任何人,就在它的右端点处放一个人。显然,除了这些放了人的区间的右端点之外,其余的点肯定都不是必须放人的(因为现在已经有一个方案使它们不放人了)。现在的问题是,这些右端点处是否必须放人。
设F[i]为第i个区间及其之后的区间当中,若要每个区间内都有人,至少要几个人。若第i个区间的右端点不小于最后一个区间的左端点,则F[i]=1(在第i个区间右端点放一个人即可),否则,找到最小的j,使得第i个区间的右端点小于第j个区间的左端点(这个显然可以二分查找得到),则F[i]=F[j]+1。这样从后到前推一遍即可。然后,再从前到后,按照上面的贪心算法的流程扫一遍,如果遇到第i个区间的右端点需要放人:若第i个区间的长度为1,显然这里必须放人,否则尝试在第i个区间的倒数第2个位置(即右端点之前的那个位置)放人,而右端点不放人(可以证明,不会后来又把这个右端点这里放上人的),类似用二分查找的方式找到这个j,然后看一下(_F + F[j] + 1)(_F为第i个区间前面放人个数)是否大于K,若大于K,则第i个区间的右端点必须放人,否则不必须放人。
此外还有两种特殊情况,一是M=0的时候在去包含的时候要特判一下(其实这时可以直接特判,若N=K,则所有的地方都必须放人,否则就是-1);二是,如果去掉那些肯定木有人的点后,剩下的点的个数刚好等于K(不可能小于K的,因为肯定有解),则不用贪心了,剩下所有的地方肯定都必须放人。
总时间复杂度O(NlogN + MlogM);
这里千万要注意的一点是,应该先将所有区间重编号再去包含,而不应该先去包含再重编号!!!因为可能有两个区间本来是不包含的,但重编号以后,包含了。(本沙茶比赛的时候就是这里木有注意到,跪了3个点,杯具了)

【kunai】
40分的暴力做法:枚举两个动点,求出它们是否会相撞以及相撞的时间,然后将所有相撞事件按照时间排序,扫描排序后的每个事件,如果相撞的两个动点都还在,就将它们消去,然后可以求出每个动点移动的距离,求一下并集(线段树)即可;(本沙茶当时主要是实在木有时间写这题了,因此连暴力都木有写)
AC做法:很明显,一个动点一旦被消去,就不会再次出现了,因此对于每一个点,只需要找到最先和这个点相撞的点即可。显然能够相撞的两个点必然位于同一行/列/对角线上且方向满足一定限制(其实一共只有6种情况:同一行一种,同一列一种,同一左上右下对角线两种,同一右上左下对角线两种)。因此,枚举这6种情况,直接用扫描法得到最先与它相撞的动点,取相撞时间最小的那个即可,如果都找不到,这个点就是永存的。这样相撞事件的总数就减少到了O(N)级别,总时间复杂度就是O(NlogN)。
注意:有可能在同一时间有多个动点在同一位置相撞,因此,对于同时发生的相撞事件,应该将它们一起处理,涉及到的点一起消去。

posted @ 2012-05-12 21:41 Mato_No1 阅读(2882) | 评论 (6)编辑 收藏

【网络流问题可以说是OI中最灵活的问题之一了,建模方法很多,但还是有一定规律的囧……当然,由于本沙茶做题暂时还比较少,可能这里总结的东东只是网络流建模技巧的一小部分,希望各位题海神犇进行补充】

网络流建模主要分为两类:直接用最大流建模、用最大流—最小割定理转化为最小割来建模。这里主要总结的是前一种。

(1)增广路思想:
应用范围较小,但是确实有一些模型用增广路思想很容易解释,用流量平衡思想却很难解释(比如下面举的例子)。
增广路思想可以概括为:原题的方案的得出可以很明显地分为一些阶段,每一阶段都会对一些变量(这些变量可能是实的也可能是虚设的)产生同样的效果值累加,而这些变量恰好有各自的限制,且互不关联。这刚好相当于网络中的一条从源点到汇点的一条增广路,对路上所有边的流量都会增加,且流量有各自限制(容量),且互不关联。并且,该模型满足下面(3)中的两条原则(可行性原则和最优性原则)。在比较多的时候,用增广路思想能够解释的模型往往是一个很明显的“物质路径”模型,某一种物质(可以是实的也可以是虚的)从源点往汇点“走”,边上的流量代表物质经过的量。
例1:[NOIP2011]观光公交
首先,由于来出发地的时间已知且一定,所以“旅行时间总和最小”其实就是所有人下车的时间总和尽可能小,因此,先求出在不用任何加速器(初始)情况下,到达每一站的时间,设为S[i],又设M[i]为在第i站上车的来的最晚的人来的时间,则很显然可以得到初始的递推式:S[i]=max{S[i-1], M[i-1]}+D[i-1](初始的D值),边界S[0]=0。
下面来看一下D[i]的减少是如何影响S值的。看下面这个例子:
N=5
i                  :  0   1   2   3   4
D[i](初始):  3   4   3   2   \
M[i]              : 1   2   6  14   \
S[i](初始):  0  4   8  11  16
现在将D[0]的值减小1之后:
i    :  0   1   2   3   4
D[i]:  2   4   3   2   \
M[i]: 1   2   6  14   \
S[i]:  0  3   7  10  16
可以发现,D[0]值减小1之后,S[1..3]的值都减小了1,而S[4]的值不变。这是因为在D[0]减小1之前,对于1<=i<3均有S[i]>M[i],D[0]若减小1,显然S[1]会减小1,而由于S[1]>M[1],S[1]=max{S[1], M[1]},所以S[1]的值减小1会使得max{S[1], M[1]}减小1,从而S[2]的值减小1,然后由于初始的S[2]>M[2],同样会使得S[3]减小1,而初始的S[3]<=M[3],故S[3]减小1不会使得max{S[3], M[3]}发生变化,所以S[4]的值不会受到影响。
所以,可以得到:D[i]减小1,会使得S[i+1..j+1]均减小1,其中j是使任意i+1<=k<=j0均满足S[k](减小前)>M[k]的最大的j0值。
从这个当中可以发现,对于原题的每一个可行方案,必然都是分为若干个阶段,其中每一阶段是将某个D[i]值减小1(当然,要满足D[i]在减小前>0),每一阶段进行后都会将从S[i+1]开始的连续的一段S值都减小1,恰好可以抽象成一条连续的路径,又因为当S[i]减小到<=M[i]的时候就必须停止了(准确来说是不能再往后延伸了),所以每个S[i]的能够继续延伸的减小的量都是有限的,为初始的S[i]-M[i](如果这个值<0,则取0),刚好是一个上限。这很明显是增广路思想。
所以,经过整理,可以建立一个网络流模型:
<1>设立两个源点s和s'(其中s是真正的源点)及汇点t,连边<s, s'>,容量为K,费用为0,表示最多只能有K个阶段;
<2>将每一站i拆成两个点i'和i'',连边<i', i''>,容量为max(S[i]-M[i], 0),费用为0,表示该点最多只能接受max(S[i]-M[i], 0)次加速器作用;
<3>对于所有的i满足1<=i<N,连边<(i-1)'', i'>,容量为INF,费用为第i站下车的人数(这是因为即使S[i]<=M[i],加速器对于本站仍然有效,只是不能继续延伸,所以表示加速器起的效果的边应该在本站的限制之前);
<4>对于所有的i满足0<=i<N-1,连边<s', i''>,容量为初始D[i],费用为0,表示使用加速器的地方,从下一站开始对S[i]起效果;
<5>对于所有的i满足1<=i<N,连边<i', t>,容量为INF,费用为0,表示加速器作用的结束。
(其实,0'和(N-1)''这两个点是木有任何意义的,可以从图中删掉)
这样,每一阶段加速器的作用都可以表示为一条从s到t的增广路,该网络流模型中的各种限制也反应了题目中的限制。对该网络求最大费用最大流,得到的总的最大费用从初始的总旅行时间中减去(注意总旅行时间是long long的),即为答案。可以证明,这个模型符合“两条原则”,所以是正确的。

(2)流量平衡思想:
这个思想的应用非常广,可以解释绝大多数网络流模型。
所谓流量平衡,就是指在一个可行流里,除了源点和汇点外,其余每个点的入边流量总和都等于出边流量总和。可以证明,一个流是可行流当且仅当其:(1)每条边的流量都不超过容量限制;(2)符合流量平衡。
流量平衡思想的主要用处是:可以把图中的每条边的流量(当然必须是非负的)都想像为一个变量的值,对于每个点,满足流量平衡,也就是一些变量的和值满足某种等量关系,如果这些等量关系刚好能够反映题目中的所有信息,边的容量限制也反映题目中的条件,且这个模型符合“两条原则”,则该模型就是正确的了。在建模的时候,应先单独考虑各个点,找到它们的所有入边和出边代表的变量是什么,然后再将这些边合并,构成图。
在用流量平衡建模时有一些技巧:
<1>要注意每条边都同时作为一个点的出边和一个点的入边,因此,每个变量必然同时关联两个等量关系,且分别出现在这两个等量关系的等号的左边和右边(或者是以一对相反数形式出现);
<2>如果题目中给出的变量和值关系不是等量关系,而是不等关系,那么可以将剩余的流量通过从源点或往汇点连边的办法,使其平衡。比如,若题目中有y1+y2>=x1+x2>=y1+y2-5这样的关系,则可以这样做:设置一个点,将y1、y2代表的边作为该点的入边,将x1、x2代表的边作为该点的出边,然后从该点往汇点连一条容量为5的边;
<3>如果点内部有限制(比如某个点自身的权值不能超过X等等),那么该点内部也“暗含”一个变量,此时就需要拆点(不一定拆成两个点,可能拆成更多的点),然后在拆出的点当中再连边,附加一些限制,然后再考虑流量平衡;
<4>如果一条边有上下界,且上下界相等(也就是该边的流量已经定死了),则可以改装成费用流,将这条边的费用设为一个绝对值很大的负数,这样就肯定能保证该边满流了。
例2:餐巾计划问题(经典问题)
这个的模型用增广路思想根本就不能解释。其实,可以用增广路思想建立一个模型,但是是错误的,可以用下面的“两条原则”检查出来。
<1>对于每天,要处理的餐巾总数=当天买的餐巾总数+当天洗好的餐巾总数+上一天保留下来的未处理的餐巾总数,这三个当作入边;
<2>对于每天,要处理的餐巾总数=送快洗部的餐巾总数+送慢洗部的餐巾总数+保存起来留到下一天处理的餐巾总数,这三个都当作出边;
<3>每天的内部有限制:要用的餐巾总数>=当天的需求量,其实,总可以构造出要用的餐巾总数=当天的需求量的最优方案,所以这些限制其实是上下界相等的。
而<1>和<2>刚好描述了每天这个整体的流量平衡,<3>是一个内部限制,用拆点解决。仔细观察所有的边可以发现,“当天洗好的餐巾总数”与“送快洗部的餐巾总数”和“送慢洗部的餐巾总数”可以合并,“上一天保留下来的未处理的餐巾总数”与“保存起来留到下一天处理的餐巾总数”也可以合并。
这样,可以构造出两种模型:
1):第i天拆成两个点i'和i'',连边<i', i''>,容量为第i天需求量,费用为0;对于任意0<=i<N-1,连边<i'', (i+1)''>,容量INF,费用0;对于任意0<=i<N,连边<S, i'>,容量INF,费用p,连边<i'', T>,容量INF,费用0;对于任意0<=i<N-m,连边<i'', (i+m)'>,容量INF,费用f;对于任意0<=i<N-n,连边<i'', (i+n)'>,容量INF,费用s;求最小费用最大流,最小的总费用就是结果;
2):第i天拆成两个点i'和i'',连边<S, i''>和<i', T>,容量均为第i天需求量,费用均为0;对于任意0<=i<N-1,连边<i'', (i+1)''>,容量INF,费用0;对于任意0<=i<N,连边<S, i'>,容量INF,费用p;对于任意0<=i<N-m,连边<i'', (i+m)'>,容量INF,费用f;对于任意0<=i<N-n,连边<i'', (i+n)'>,容量INF,费用s;求最小费用最大流,最小的总费用就是结果。
以上两种模型,看上去都符合题目中的限制,也符合流量平衡,但是,模型1)是错误的,模型2)是正确的,这是为什么呢?

(3)判定网络流模型是否正确的两个原则:
<1>可行性原则:原题中的每一种可行方案,在建立的网络流模型中都对应着一个“能求出的”流(一般是满足一定的条件的流,比如某些边必须满流等),注意这里的对应必须是“一一对应”,就是,既不能有可行方案丢失,也不能出现不可行方案;
<2>最优性原则:原题中的最优方案(准确来说是最优方案的结果),在建立的网络流模型中都对应着一个“能求出的”量(最大流量或者满足最大流量的前提下的最小费用),也就是,最优结果必须是可以通过这个模型求出的。
一个网络流模型正确,当且仅当其符合以上两条原则。
这两个原则可以检查所建立的网络流模型是否正确。比如,对于例2中的两个模型,模型1)由于最大流对应的是“买的餐巾总数尽可能多”的方案,不是最优方案,因此原题中的最优结果无法求出,显然不符合最优性原则,因此它是错误的。模型2)中,由于可行方案必然能使所有<S, i''>中的边满流,且能够求出,符合可行性原则;最优方案由于<i', T>这条边的限制,必然是最大流,且是费用最小的最大流,其最小费用为最优结果,符合最优性原则,因此它是正确的。

posted @ 2012-05-11 21:32 Mato_No1 阅读(3760) | 评论 (3)编辑 收藏

【首先热烈祝贺一下进入国家队的神犇:
chnlich
sevenkplus
zw7840
plokzfadai
雅礼再次屠场不解释)

也祝贺一下虽然未能进入国家队,但已经足够虐爆全场的神犇:
WJMZBMR
s-quark

CTSC2012得出的最主要的几条道理:
(1)实力强≠比赛成绩好,实力弱≠比赛成绩差;
(2)现在所有的比赛都不是比谁得分多,而是比谁丢分少;
(3)每个人都会遇到颓废、迷茫、进步慢的时期,关键是如何寻求出路,以及如何通过自己与外界共同的力量来解决;
(4)在将某个东东讲给别人之前,首先要考虑一下自己是否熟练掌握了这个东东;
(5)在分析问题,解决问题的过程中,可以通过很多另类的途径,找到又好想又好写的办法。

部分总结:
【一试】
showhand:
可以将所有的牌型(C(52, 5)=2598960种)全部存储起来,按照题目中的规则进行排序,存储在一个线性表里,然后,枚举A的所有可能的牌型,从上面的线性表中找到比A大且不和A共用同一张牌的方法总数,可以使用容斥原理(方法:设F[i][t]为牌型i及比i大的牌型中,与i共用牌的属性压缩值为t,0<=t<=31表示5位二进制数,对应位为1表示与i共用,0表示不共用)。而对于B的某些牌一开始就被定死了的情况,用求出的F类似办法也可搞;

shortest:
很好的一道提交答案题。
先说一下各个测试点的特点:
点1:N<=20,K=10,从1到N的最长路径若要成为最短路径,需要删掉至少11条边;
点2~3:N、M较大,K较小(分别为20和10);
点4:N<=20,边可以想肿么删就肿么删;
点5~7:原图分为若干块,每块的点数相等且较小(分别为20、10、10),相邻两块之间有唯一的一条边相连,点5的边可以想肿么删就肿么删,点6、7删边有限制;
点8:是一个完整的100*100的网格,边权均为1,从左上角走到右下角;
点9:是一个2*1000的网格,中间随机删掉了约20条边,边权是随机值,从左上角走到右下角;
点10:图中存在一条从1到N的链(称为主链),附加了一些边,边可以想肿么删就肿么删。
解决办法:
点1:搜索(当然,状压求出最长路+将这11条边列出来,枚举保留哪条边,可以得到一个仅比最优解小1的解);
点2、3:贪心+随机化(每次找一条从1到N的最短路,从中随机删掉一条边,这样做K次就得到一个方案,然后多次随机化后取最优方案即可;对于点2,随机几千次就能找到最优解了,对于点3,RP好的话需要随机1000W次,RP差的话可能需要上亿次,估计总共得耗掉1h以上,因此得早写);
点4、5:状压DP;
点6、7:块内状压(当然由于只有10,暴搜也可),块之间DP(设F[i][j]为前i块删掉j条边的最优解……)
点8:直接构造……(可以构造出一个只有一个点走不到的方案,且可以证明不存在走完所有点的方案);
点9:搜索/DP + 构造(具体的实现细节比较难搞啊囧);
点10:这个是Hamilton路径问题,NPC的,因此这个点根本木有办法搞囧……(当然或许有某些经过优化的搜索能较快找到解)

【二试】
cheat:
80分做法1:首先将所有的字符串拼在一起,中间依次用不同的分隔符隔开,然后对这个大串求后缀数组求出height,然后就很容易求得每个属于待查询串部分的位置i与模板串的最大LCP(直接正着扫一遍、反着扫一边即可,注意边界)长度,设为D[i],接下来就是二分L然后DP了:F[i] = min{F[i+1]+1, F[j]},其中0<=i<len,i+L<=j<=i+D[i],边界F[len]=0,这个东东显然是可以用线段树优化的。总时间复杂度O(Nlog2N);
80分做法2:可以发现,对于同一个待匹配串,随着i的减小,(i+D[i])是不增的,因为D[i]最多比D[i+1]大1……这样可以用单调队列进行优化,而不需使用线段树,总时间复杂度降为O(NlogN),但是由于后缀数组常数过大,还是只有80分囧……
100分做法:将后缀数组改为后缀自动机(详见WJMZBMR空间)……
(另外讲题的时候某神犇说可以把后缀数组的长度减半,从而结合单调队列得到90分,不过本沙茶木有理解到底是肿么搞的囧……)

rev:
点1~2:N=1或M=1,可以暴力搞(要开-O2啊啊啊啊啊啊啊啊啊啊……否则慢死)
点6:整个矩阵从左到右、从上到下都严格递减,只要满足坐标限制的都是逆序对,可以直接计算得到;
点7:只有5和9,且相邻的两个格子分别是5和9(其实可以把5和9看成0和1,相当于黑白染色),可以通过枚举不同情况分类讨论计算得到;
点8、9:N=M=1000,询问的区间都是从顶到底的,可以通过预处理得到一个O(N2M)近似暴力的算法,在约5min内跑出(开-O2);
点10:N=M=80,随机数据,可以直接暴力递推得到;
点3~5就比较难搞了,本沙茶至今木有搞懂囧……

posted @ 2012-05-09 22:58 Mato_No1 阅读(1691) | 评论 (0)编辑 收藏

【注:本沙茶完成AHOI2007的题目用了3年多……因为6道题中,有2题是2009年AC的,1题是2010年AC的,剩下3题是2012年AC的……】

box:
要求x2=kn+1(k为整数),即(x+1)(x-1)=kn。因为(x+1)和(x-1)所可能具有的共同的质因数只有2,因此可以分为两种情况:(1)x是奇数,且n是4的倍数,此时可以将(x+1)和(x-1)都除以2,n除以4之后,转化为(x+1)/2或(x-1)/2是n/4的倍数,然后直接求解;(2)其它情况:此时必然是(x+1)或(x-1)是n的倍数,可以直接求解。注意需要特判一下x=0的情况;

door:
求逆矩阵的问题。方法:设置N*N的矩阵A和B,A初始为待求逆的矩阵,B为单位矩阵,然后,不断地对A和B同时实施相同的初等行变换,直到将A变成单位矩阵为止,此时B就是A的逆矩阵,若无论如何也不能将A变成单位矩阵,则A无逆矩阵。
初等行变换有3种:(1)两行互换;(2)将一行整体乘以一个非0常数;(3)将一行加到另一行上。
具体操作:类似于高斯消元。第一步,i从0到n-1,在A的第i到(n-1)行中找到一个第i列不为0的(若找不到则A无逆矩阵),并将其与第i行互换(变换1),然后,对第i行后面所有第i列不为0的,将其整行乘以一个非0常数(变换2),使得其第i列的值刚好是-A[i][i],并将第i行加到这一行上(变换3)使得其第i列变为0,这样一直下去,可以把A的下三角全部变为0;第二步,i从n-1到0,对于第i行第(i+1)列及其以后的每个数,若有不为0的,将其乘上一个常数(变换2)使得这个数变为-1,再用后面的已经处理好的单位矩阵对应行加到第i行上(变换3),将这个数变为0,这样一直到最后一列为止,最后,要把第i行乘上一个常数(变换2)使得A[i][i]=1,这样第i行就处理好了,这样一直下去,直到所有的行都处理好为止。

light:
首先对这个字符串A[0..n-1]进行自身exKMP,求出nx数组,nx[i]表示A[i..n-1]与A[0..n-1]的LCP长度。
然后,点灯器的长度为p可行的充要条件是:(1)nx[n-p]==p;(2)对于整个nx数组,取出其所有大于等于p的元素,则相邻两个元素的距离(下标之差)都不超过p。
对于第(2)个条件,只要用一个线段树维护最大距离就可以了,枚举p的时候正、逆序均可,推荐逆序,这样实际上等于不断插入元素,比删除元素要方便。

rock:
超级大水题。只要把矩阵中所有的0变成-1,再求最大子矩阵就行了。

redcross:
求01矩阵中最大的某种性质的子矩阵类的题目。最暴力的做法显然是13个数组(原始数组+上下左右延伸0的长度+上下左右延伸1的长度+左上左下右上右下延伸的0正方形的边长),如果把上下左右延伸0和1的长度进行合并可以减少到9个数组,但这样对于这种如此卡常数的题目还是会TLE的。其实,可以换一种思考方式,最后只用6个数组(包括原始数组)就解决了问题……至于这个是肿么搞的,现在不能说,以后的某一天再说……
另外这里的最优解排序……发现有惊人的地方么囧……

maze:
由于可以随便走,N<=10,因此可以枚举前5步的走法和后面5步的走法(其实全是一样的,枚举一次就行了,只是存储方式不同),把能得到的所有权值和分最后到达位置(前5步)和开始位置(后5步)存在数组里,然后就是二分查找了囧……至于N<10的情况就少几步枚举了囧。其实还是比较难写的,本沙茶2009年写这题的时候写了整整一晚上,当然这或许与本沙茶当时太太太太太……弱了有关(当然现在仍然弱)

posted @ 2012-05-04 18:00 Mato_No1 阅读(642) | 评论 (0)编辑 收藏

【最近很想被各种省选题虐……于是,就开始找各种省选题……发现能虐本沙茶的实在是太多了(谁叫我是沙茶呢囧)】

homework:
很能令人想歪的题目……想到某种数论模型……
正解是递推+矩阵优化。可以这么想,本题如果暴力递推的话,设F[i]为1到i组成的数(具体的数,不是取模以后的结果,虽然这个值是无法存储的),则有F[i]=(F[i-1]*10T)+i,其中T是i在十进制下的位数,边界F[0]=0。这个式子是可以矩阵优化的,矩阵为
10T 0 0
1 1 0
1 1 1
则1*3矩阵[F[i-1], i-1, 1]乘以这个矩阵之后就是[F[i], i, 1],然后对于各个T分开处理一下就行了……这里的取模完全就是个幌子……
(另外,矩阵优化递推是一个很重要的专题……)

race:
(最近刚好在某MO神犇的资料里面看到了柯西不等式……发现此题可以用这个来搞……就囧掉了)
柯西不等式:(a12+a22+...+an2)(b12+b22+...+bn2)>=(a1b1+a2b2+...+anbn)2  【*】,
等号成立当且仅当对于任意1<=i, j<=n, i≠j,有aibj-ajbi=0,也就是(a1, b1), (a2, b2)...(an, bn)这n个点共线。具体证明的话,把两边的乘法列成一个矩阵的形式,去掉主对角线(相同),把关于主对角线对称的位置对应相减,得到类似叉积的平方和的形式即可。

对于本题,假设不考虑耗油量为负时取0的情况,设F0=(F-Σ(b*Li*Si))/a,则问题就转化为求一组vi使得ΣLivi=F0且Σ(Li/vi)的值最小。这样,可以设ai=sqrt(Li/vi),bi=sqrt(Livi),代入【*】式……傻眼了囧……不仅能得到最小值,还能发现取得最小值时所有的v都相等,且可以算出来……当然如果F0<0就无解了囧……
不过本题最囧的问题是对于耗油量为负的情况。最好的处理办法是,如果按照【*】式得到的v值会导致某些s<0的路段耗油量为负,则对于这些路段单独处理,使得它们的耗油量刚好为0(除非此时的速度已超过上限),并将它们删去,然后对于剩下的路段,重新代入(*)式计算v,直到不出现耗油量为负的情况即可。当然,如果在此过程中出现F0<0,就无解了。

brackets:
这个应该不用再说了,直接看这里

rectangle:
思想比较巧妙的话说……应该枚举线段,按照中点和线段长度进行排序(因为两条线段若能组成矩形的两对角线,则它们必然等长,且中点重合),然后扫一遍,顺带枚举就是了……表面上来看时间复杂度可能到O(N3)级别,其实根本无法出卡这种方法的数据……

canon:
这个没什么好说的,就是硬推公式,结果为
(C(2n, m) - C(2n-1, m/2)) / 2n + C(2n-1, m/2) (当m % 4 == 0或3时)
(C(2n, m) + C(2n-1, m/2)) / 2n - C(2n-1, m/2) (当m % 4 == 0或3时)
对于当中的取模问题:加、乘直接取模;减法要在取模后判定是否小于0,若小于0再加上待取模数;除法要转化为乘逆元(反正这里的MOD都是质数……)

posted @ 2012-04-24 21:25 Mato_No1 阅读(816) | 评论 (0)编辑 收藏

相关链接
今天在回顾以前的题目的时候,秃然发现COCI 2011~2012 #5的后两题并非神犇题(至少一般人可以捉的)……是我当时想傻掉了囧……

blokovi:
首先很容易发现最优方案必然是从顶到底,先尽量往右边放,放到某一个转折点处再尽量往左边放……
然后就是枚举这个转折点,乱算一下就行了,暴力O(N2)的可以过7个点(本沙茶现场赛时就是用这个的)……
优化:可以从上到下依次枚举转折点,设目前的转折点为i,则在下一次枚举时((i+1)为转折点),把(i+1)往右平移2单位,然后根据那个重心计算公式可以得出,第(i+2)个及以后的必然是整体向右平移(2*m2)/(m1+m2),其中m1为前i个的质量和,m2为第(i+1)个的质量……在此基础上维护转折点前重心位置、转折点的重心的横坐标(相对于最上面的那个)以及最下面的那个的重心的横坐标(相对于最上面的那个)就行了(注意转折点是第一个或最后一个的特殊情况要单独处理),时间复杂度O(N)。

poplocavanje:
其实这题只要用AC自动机随便乱搞一下就行了……Trie上的每个结点维护一个KK,表示该结点所代表的字符串的后缀的最大匹配长度(当然前提条件是该结点是危险的),则:(1)若该结点本来就代表一个待匹配的子串,则KK值为子串长度;(2)若该结点是通过失败指针上溯到一个危险结点的,则该结点的KK就是上溯到的那个危险结点的KK。然后做一次匹配,记下所有的匹配区间,再求出未被区间覆盖的总长度(排序+扫描即可,不需任何数据结构)就行了。

注意几个易疵的地方:
(1)Trie的大小要开到4M才能过(不过再大就要MLE了囧……);
(2)在建自动机计算KK的时候,如果一个结点本来就是危险的(即上述第1种结点),此过程中又发现它是上述第2种结点,则能重新计算KK
(3)最后求未被区间覆盖总长度的方法:先记下所有的区间,按照先左端点递增序后右端点递增序排序,当中去掉被别的区间覆盖的区间,然后先看一下排序后的第一个区间和最后一个区间,得出第一个区间之前与最后一个区间之后的未被覆盖的部分,中间的扫描求解时,如果某区间的左端点大于(前一区间的右端点+1),则计入中间的空当……不过还有一种方法就是不去掉被别的覆盖的区间,而是在扫描过程中维护右端点最大值maxr,然后把上面方法中的所有右端点改为maxr即可。

代码:
blokovi poplocavanje

posted @ 2012-04-18 20:26 Mato_No1 阅读(756) | 评论 (0)编辑 收藏

【很难过吧……考得完爆了……
……其实也没什么可以说的……都是蒟蒻的借口罢了……
……自己果然还只是半吊子水平呢……】


(结果:Rank36……我是“真”沙茶!!!!!!!!!!!!!!!Orz Mike_Qiao神犇虐人)


题解以后再发。


posted @ 2012-04-15 01:19 Mato_No1 阅读(918) | 评论 (3)编辑 收藏

历经千辛万苦总算搞定了COCI 2011 OPEN的所有题……真WS啊囧……
(不过除了sort的满分算法稍微看了一下题解之外,其它的题目都是自己想出来的……这说明本沙茶想算法的能力并不差……只是所用的时间有点……)

sort:很容易想到该置换的循环分解,然后对每个长度大于1的循环进行一次操作就成了,总操作次数是长度大于1的循环个数。但是,这并不是最优解(在官方数据中,这个算法能过4个点,加上剩下6个点的一半分总共是70分,所以现场结果中多数人都是70分……)。最优解是先通过一次操作把各个长度大于1的循环搅乱,使得整个置换只有一个循环,然后再来一次操作就行了,也就是任何置换都最多只要两次操作就行……至于搅乱的方法,只要在原来的各个循环(当然是长度大于1的)中各抽出一个元素,再对这些抽出的元素执行一次题目中的操作即可(证明是很容易的)。不过要注意只需0次或1次操作的情况:当原置换长度大于1的循环总数为0或1时;
至于具体的操作构造方法随便乱搞一下就行了囧……

telka:应该算是最水的一题……树状数组的裸模型“改段求段”(具体见这里),唯一值得注意的就是在改段求段模型中的一个注意点:当l=1的时候,不能执行opr(l-1, c),因为凡是下标递增的数组都不能以0作为初始下标;

rijeka:这题比较坑人啊囧……如果任意时刻最多只能载一个人,可以把每个人的要求(也就是每条有向线段)都拆成若干个元线段,然后统计正反元线段的个数,乱搞一下就成了……不过这题目里面是可以载任意多的人……那么最优策略是:先把所有反方向线段覆盖的总区间求出来,比如有4->2、6->3、9->8三条反方向线段,则覆盖的区间就是[2, 6]和[8, 9],然后在送人的时候,每送到一个区间的右端就回头去把这个区间内的要走反方向的人全送到,然后再回头往正方向开(比如上例中先从0到6,回到2,再从2到9,回到8,再回头往前一直开到终点),这样开到终点时,所有的人就都送到了,因此,总时间就是(M+反方向线段覆盖的总长度),用线段树来搞。此外,由于M太大,需要离散化。

后面两题就是猥琐题了。

kamion:很明显是个递推……但是按照常规方法根本无法划分状态。不过,要发现本题和括号序列类的动态规划神似,因此就可以用括号序列的来搞。关键是,对于那些第3种边(既不含左括号也不含右括号的)比较难搞,另外本题还允许到终点的时候有左括号(就是大写字母)剩余,这就明显加大了难度。
状态设计应是这样的:F[i][j][k][s0][s1],表示从i到j走正好k步,且满足单多段限制(s0)和多余左括号限制(s1)的合法路径总数,s0、s1为bool,s0表示是单段还是多段的规则括号序列,0:单段,1:单段或多段;s1表示是否可以有多余左括号,0:不能有;1:可以有(当然也可以木有,也就是s0和s1都是0包含在1之中的)。
递推式:
F[i][j][k][0][0]=ΣF[t1][t2][k-2][1][0](其中<i, t1>边有一左括号,<t2, j>边有一右括号,且两括号匹配);
F[i][j][k][1][0]=ΣF[t1][t2][k-2][1][0] + Σ(F[i][t][k'][0][0] * F[t][j][k-k'][0][1]) (注意0<k'<k,其它的类似);
F[i][j][k][0][1]=ΣF[t1][t2][k-2][1][0] + ΣF[i][t][k-1][0][1](其中<i, t>边有一左括号,其它的类似);
F[i][j][k][1][1]=
ΣF[t1][t2][k-2][1][0] + Σ(F[i][t][k'][0][0] * F[t][j][k-k'][1][1]) + ΣF[i][t][k-1][1][1](与上面的限制类似);
边界:F[i][i][0][0..1][0..1] = 1,当<i, j>边为第3种边(不含括号)时,F[i][j][1][0..1][0..1] = 1,其余的均为0。
这几个式子还是比较好理解的,要注意的是在计算F[i][j][k][1][1]时,是F[i][t][k'][0][0]而不是F[i][t][k'][0][1],这是为了防止重复计数(否则,对于序列AB,到底是A是附加上的,B是原来就有的,还是都是附加上的?显然被计2次了);
时间复杂度O(N3K2),官方题解里面说这个就能AC了,可是本沙茶实测的结果却有5个TLE,最慢的点达14+s,可见其常数之大,本沙茶暂未想出神马好的优化方法,神犇们可以提供一些啊囧(最好能降一维);

lovci:(这题本沙茶调了3个晚上啊啊……)
本沙茶所见过的最猥琐的暴搜题目了。由于当M>0时,初始位置就会被计入(本题的真正意思是每个格子只被计入一次,而不是每次移动中初始位置控制不到的地方就计入一次),因此不用考虑初始位置。仔细分析题目发现,可以对矩阵进行黑白染色,这样两个初始位置一个只能控制黑格,一个只能控制白格,这样就把两个分开了。然后,把所有的黑格和白格给旋转45度,变成一个十字型,剩下的任务就是枚举哪些列被占用,然后再选出哪些行能被占用就行了。
问题是,有的列不能随便选,有的行也不能随便选,这下就囧了,需要很多东东来控制,当然,本题需要注意的点太多了,实在列举不完,见代码吧囧。

代码:
sort telka rijeka kamion lovci

posted @ 2012-04-01 20:42 Mato_No1 阅读(707) | 评论 (0)编辑 收藏

仅列出标题
共12页: 1 2 3 4 5 6 7 8 9 Last