【AC_CWJ_LCC】WF 2011 Practice #2 (坑爹比赛……)

这场比赛太过坑爹……

E题全世界(我指的是真的全世界)只有OpenGL Y。而且是1Y。

这个题目就是个约瑟夫问题,问最后3个死的是谁……

题目限定n>=5,实际上却有n=1以及n=2的情况……纯粹坑爹……

完全不知道如何输出。

经我们开小号暴力乱搞尝试各种输出未果……

我捉了3个题目。

A:属于送分模拟题,1Y了。好像除了小号,来参加的都Y了。

C:有两个通道,中间连着一个起飞跑道。输入n,接下来n个时间单位里两个通道会先分别加Ai,Bi部飞机。然后再飞走飞走一步飞机。问这两个通道最少要开多大。

n^2 dp 但是我的dp对那种通道上没飞机的情况下会疼……T_T,于是各种修修补补,总算Y了。

D:给定一个01串,求一个长度大于等于lower_bound的区间,使得Sum(s[i]=1)/区间长度 最大。

很Orz的题目。与斜率有很大关联……我看到有O(n)的,我n lg n的就算了>_<。反正真正理解斜率优化的,YY着就出来(其实我不理解都YY出来了)。

其实C和D都是不错的题目……

后来J题据lcc说又是坑爹数据

今晚SRM  O_O 又要被虐啦~

题目:

http://acm.hust.edu.cn:8080/judge/contest/standing2.action?cid=999

 

ZOJ Monthly, February 2011 (ZOJ3467~3476) 【lack of 3472】

月赛时必须回宿舍zzzzZZZZZZ,于是当时没怎么捉。

我太蒟蒻了T_T

3472暂时还没看题目

3476被虐了一早上,现在在死皮赖脸地看shi哥的题解

【ZOJ3467】

一只3D骑士给定他跳的方法(x,y,z),问两点间点字典序最小的路径

就是双向BFS,但是那个字典序不太好搞。然后最近学了map就果断使用了

判重时就要注意不是重复就给删掉……而是先比较步数,如果步数一样,则和原来的解一起从父节点link回去比较一下是哪一个的字典序优,如果现在的比较优,那么就把map里的指针指向该结点(相当于把原来那个点删掉,当然是lazy delete)。

因为WA重写了几遍= =,已经疼了,于是直接把两边3步都搜完最后再来判……

于是得到悲壮的8700MS。

Code:https://ideone.com/fqVUE

【ZOJ3468】

送分题。直接dp或者爆搜 T_T。

Code:http://ideone.com/8VheC

【ZOJ3469】

一个一维的数轴上,一个人初始站在X处送外卖,他跑的速度为V^(-1)。然后每个客户由两个元素(x,b)来描述,分别表示其位置以及纠结指数增长率。一个人收到外卖时的纠结指数为增长率*时间。求所有客户的纠结指数之和最小能是多少。

初看题目好像是最小哈密顿回路>_<,其实不然,如果你从X向右最远跑到某个地方,中间的肯定已经顺便送过了。然后时间的增长会增加所有未收到外面的纠结指数……于是乎每一段可以看成是单独的,于是就可以dp了。当然先要把结点按x排个序。

F[i,j,0]表示最左跑到i,最右跑到j,最后停在i上时最小纠结指数之和是多少。

F[i,j,1]表示最左跑到i,最右跑到j,最后停在j上时最小纠结指数之和是多少。

令tmp=b[1]+b[2]+..+b[i-1]   +  b[j+1]+...+b[n] (这些顾客都是没送到的)

于是

F[i,j,0]=min(  F[i+1,j,0]+(tmp+b[i])*(x[i+1]-x[i])    ,     F[i+1,j,1]+(tmp+b[i])*(x[j]-x[i])  )

F[i,j,1]=min(  F[i,j-1,0]+(tmp+b[j])*(x[j]-x[i])         ,     F[i,j-1,1]+(tmp+b[i])*(x[j]-x[j-1]))

Code:http://ideone.com/IAF8Y

【ZOJ3470】

这个转圈圈很难描述>_<,反正就是找到他变化的规律以后可以得出一个等差数列,然后我二分了一下,利用等差数列求和,找出第几圈的,然后分类讨论。

看着挺复杂,没想到1Y了。

Code:http://ideone.com/mWWUc

【ZOJ3471】

有n个星球,n<=10,然后给出一个邻接矩阵,w[i,j]表示i把j撞爆以后获得w[i,j]这么多分。问最后最多能得多少分?

直接状态压缩dp。F[i](i用2进制位表示,1表示该星球已经被撞爆,0表示还在)表示i这种状态下的最高得分。转移随意。

Code:http://ideone.com/uv9qP

【ZOJ3472】

T_T还没搞

【ZOJ3473】

F[1,1,1]=1

F[i,j,k]=max(F[i',j',k'])+1    其中(i'|i j'|j k'|k   但是i',j',k'不等全部等于i,j,k)

求Sum(F[i',j',k'))  i'<=i && j'<=j && k'<=k

实际上这个函数就是从1,1,1这个点每次将某位乘一个数,然后变成i,j,k的最长路嘛>_<。

于是F[i,j,k]=1+i分解成素因子的个数+j分解成素因子的个数+k分解成素因子的个数。

显然他们是单独的。令d[i]表示这个数字分解成素因子的个数(可以用筛法求得),Sum[i]=d[1]+d[2]+...+d[i]

那么ans=

i*j*k(都+1的那一部分)

+Sum[i]*j*k

+Sum[j]*i*k

+Sum[k]*i*j

后面的YY一下就知道了= =

Code:http://ideone.com/wGe5T

【ZOJ3474】

dp一下以后变成这样的题意:有n个对手,你要将他们全部打败,打某个的条件是当前体力值>Limit[i],打完以后体力-Limit[i]+R[i]。

这个其实和JSOI某题本质是一个样的。这里有师父之前的证明。

首先如果打完会加血的,顺序随意,每次打能打的就行了。

打完了这些以后,下处理打完减血的。

假如给定一个成功的顺序,对于相邻的两个(i,j),我们围观限制 (S是之前打了一些累积的体力变化值)

init_energe + S > Limit[i]                             -----------------1

init_energe + S - Limit[i] + R[i] > Limit[j]      ------------------2

如果说(i,j)可以交换成(j,i)那么需要

init_energe + S > Limit[j]                            //由于-Limit[i]+R[i]<0,所以由上面第二条不等式自动获得

init_engerge+ S -Limit[j]+R[j]  >  Limit[i]      --------------------3

把左边移剩init_energe+S

init_energe+S > Limit[j]+Limit[i]-R[i]      -------------------2

init_energe+S > Limit[i]+Limit[j]-R[j]     --------------------3

于是令2式右边>=3式右边。(这样必然能满足条件,使得可以交换)

Limit[j]+Limit[i]-R[i] >= Limit[i]+Limit[j]-R[j]

化简后……R[j] >= R[i] 。

就是说原来的顺序,如果满足R[j]<=R[i],就可以交换,所以任何一个满足的顺序都可以调成R[i]递减的顺序。

于是贪心即可。

Code:http://ideone.com/k8cok

【ZOJ3475】

对于NOIER来说= =,这种程度的最小割大概都是秒杀类型的吧。

一看除了隔开以外没有什么其它要求了,那就是最小割了……

顺便制作了sap的模板。

Code:http://ideone.com/yq3cN

【ZOJ3476】    [email protected]

围观了shi哥的解题报告以后没看懂神马意思= =,后来又问了叉姐,终于懂了。

就是说我们这个包围圈最外围必然是一条轮廓线,然后这条轮廓线实际上就是一个环。然后这个环有没有包含一个点呢?实际上就是判断点是否在多边形内的方法,向上作射线,如果穿过这个环的次数为奇数,那么就在环的包围内。

然后我们枚举环的起点,尝试跑一个环回来,但是我们需要知道我们跑了这个环以后,有哪些点被包围在里面。

我们先对每个在输入中存在的国家向上作射线(包括入侵者国家),假设,我们枚举的这条外围路径跑去和某条射线相交了,那么对应这条射线的国家的存在性就要xor一下(因为对应的奇偶性变了)。

那么设d[x][y][z]为跑到(x,y)这个格子,状态为z(z是一个2进制数,表示每个国家在不在这个包围圈里面),这时的最短路径是多少。

然后就spfa转移跑来跑去就行了……最后当然要和起点闭合才能形成合法的包围圈,最后就用d[Start_x][Start_y][z]去更新dp[z]。

现在的dp[z]表示如果要用一个包围圈,把z这个集合中的点,都包围在内,那么至少需要多少代价。

然后dp[z]还不一定是就是对应包围z个国家的最小代价。因为不一定是一个包围圈把它们包起来就行了。

还有可能外面一个大圈,中间有几只入侵者,然后再把它们围起来

所以后面还要一个枚举子集的状态压缩动态规划,来挖空这些中间部分。

T_T,看着挺复杂,其实写起来很简单。1Y了。

Code:http://ideone.com/gAPv1

【AC_LCC_CWJ第五场】ZOJ Monthly, January 2011(ZOJ3457~ZOJ3466)

……这场比较久了,只记得当时被屠了。

【ZOJ3457】

模拟题,主要是模拟1/x的这个除法。细节比较多,比较繁琐……

最后打表搞之。

【ZOJ3458】

题目大意:计算floor((sqrt(a)+sqrt(b))^n) % 2(a+b)    保证 0 < b-a < 1+2sqrt(a) 且 n%2==0

算法分析:

师父当时告诉偶们一个结论 (sqrt(a)+sqrt(b))^(2n) + (sqrt(a)-sqrt(b))^(2n)是整数。

把^(2n)里的2放进去,变成     (题目保证了n%2==0,所以可以这样变形……)

令A=       B=

然后求该数列的母函数:1 , A^1+B^1 , A^2+B^2 , A^3+B^3 ……   ------------------------令这个数列第i项为Z[i]

G(x)=1 + (A^1+B^1)x + (A^2 + B^2)x^2 + (A^3+B^3)x^3  ......

G(x)=

然后把两个分母乘起来(1-Ax)(1-Bx)得到1 -(A+B)x +ABx^2

∴Z[n] - (A+B)Z[n-1] + (A*B)Z[n-2]=0

然后A+B=2*(a+b),A*B=(a-b)^2

移项即得到递推式。然后用矩阵乘法可以很轻易得到Z[n]。

回归到原题,0 < b-a < 1+2sqrt(a),那么容易得到0

然后题目求floor((sqrt(a)+sqrt(b))^n) % 2(a+b) ,那么就等于求(Z[n/2]-1) % 2(a+b)

里面因为是% 2(a+b),所以有点特殊性,最后的式子可以化简,不过矩阵暴力之也差不多……

【ZOJ3459】

题目大意:台上有4张牌,司马和张角都有一定数量的手牌(每个人的手牌数量∈[1,6]),司马先手,然后每个人轮流换台上的牌。如果某个人在这个回合选择不换牌,那么游戏结束,这时候如果台面上的4张牌可以组成算出24点,那么司马赢,否则张角赢。特别地,司马在第一回合即使不换牌,游戏也不会结束。

算法分析

先暴力求24点的所有可能。然后博弈树搜索之,基本上就是极大极小过程。

【ZOJ3460】

题目大意:在二维平面上m个导弹发射塔,和n个目标,发射塔发射一枚导弹需要T1这么多时间,然后发射完以后,发射塔就可以准备下一次发射,这个准备时间为T2,导弹发射以后会以速度V直线飞到目标处。问最少要多少时间将所有的目标摧毁。

算法分析

二分答案,然后将发射塔拆点,对于发射塔i他所拆出的第j个点就表示第j次发射,然后再看时间允不允许飞到目标进行连边。

然后二分图最大匹配之,看是否可行。

【ZOJ3461】

题目大意:每个人有一个钱数(有正有负),保证所有人的钱数之和为0。接下来给定m条带权无向边,如果这条边一旦启用,那么就要付上面的费用。最后问最少用多少费用可以使得这些人能够分钱分到每个人身上的钱数都为0。

人数<=16。边数可以接近完全图。

算法分析

……比赛时一直把他当有向边,然后果断悲剧。做法就是枚举每一个权和为0的子集,然后作最小生成树。然后再dp枚举子集合并之。

>_<其实这个做法是很显然的哎。后面dp枚举子集合并的复杂度是C(n,1)*2^1+ C(n,2)*2^2 + C(n,3)*2^3 + ... + C(n,n)*2^16<=2097120,所以不会超时。另外此题后面dp直接用2^16 * 2^16判子集的方法合并也不会超时……因为数据好像没有全0的情况。

【ZOJ3462】

题目大意:给定n(n<=1024)个文件,每个文件有几个Tags和一个大小。然后有m(m<=8192)个询问,每个询问给出一些Tags,如果一个询问中的Tags是某个文件的Tags的子集,那么将这个文件的算进符合这个询问,最后输出对于每个询问,符合条件的文件大小之和是多少。

算法分析

本题我的复杂度很不靠谱,理论上根本过不了……= =,不知道是否有正解。

就是对于所有文件的Tags建一棵Tire树,然后每个Tags建立一个邻接表,表示包含这个Tags的文件有哪些。

然后对于一个询问,就把这些Tags对应的文件搞出来求个交……当然这里有优化,如果某个文件在前面处理到的某个Tags里没有出现,那么后面就不用再枚举它了。接着就这样就过掉了……

【ZOJ3463】

题目描述十分不靠谱。他说一只手可以弹9个键,我和lcc都认为是5个白键,4个黑键……,谁知道他根本忽略了黑键。

算法

很简单的dp。F[i,j,k]表示左手拇指在i,右手拇指在j,弹完第k个音符需要的最小费用,然后暴力转移。

计算量是:52*52*1000*16 (16是转移复杂度)

【ZOJ3464】

水题,尽量让速度快的接球就可以了。

【ZOJ3465】

体力模拟题。

【ZOJ3466】

插头dp,基本概念就看cdq的ppt吧。

这个题不需要判断连通性,所以接进这个点的插头只需要计算数量,而这个点可引申出去的插头也只需要记录是哪几个,这样就可以拓展了。特别地,边界要处理一下。然后这个题目比较恶心的地方就是轮廓线会变。所以要分奇列和偶列讨论。

对于图中红色的插头,由于比较特殊,我就多弄了两位专门用来存……然后就是2进制储存是否有插头伸出来,hash便行。

 

【CODE】

【3457 打表的……】https://ideone.com/GQd73

【3458】https://ideone.com/JjnTV

【3459】https://ideone.com/SUwZr

【3460】https://ideone.com/1OUbx

【3461】https://ideone.com/YD6rA

【3462】https://ideone.com/OAzw8

【3463】https://ideone.com/BdF0V

【3464】https://ideone.com/Xa2go

【3465】https://ideone.com/c4Boa

 【3466】https://ideone.com/gORz0    (注意代码地址,ORz !!)

[email protected]/2/12

【AC_LCC_CWJ 第四场】Algorithmic Engagements 2009 & 【第一把SRM】

【AC_LCC_CWJ】

 本场纯打酱油……

就切了J题这个线段树。

http://acm.hust.edu.cn:8080/judge/contest/viewProblem.action?pid=22200

【题目大意】

给一个A[1..n],问是否存在1~n的一个排列,满足所有p[i]<=A[i]。然后后面还有m次修改,每次修改某个位置的A[i]的值。

n,m<=200000     1<=A[i]<=n

【算法分析】

……令Sum[k]表示数组A[i]里包含多少个<=k的数字。然后这个判定性问题转化为是否所有Sum[k]<=k。

然后就用线段树维护所有Sum[k]里,Max(Sum[k]-k)是不是小于等于0,如果是就满足,否则不满足。

【其它】

还想了好一会儿,真是太弱了。

【CODE】

http://xiudaima.appspot.com/code/detail/4489019

哎,弱得一塌糊涂……神马都弱

========================================================================================================

然后是昨天晚上的第一把SRM。

Orz,一进去就见到WJMZBMR和zbwmqlw!!!

WJMZBMR还被人用中文膜拜……

然后看到很多熟悉的ID,像swgr,RoBa之类的…

膜拜完以后开始比赛,显然第一把必须DIV2。

250神马二叉算法都能秒,直接暴力枚举。然后编译了半天不成功,都不知道干神马……

弄了好久,发现语言选了JAVA

接着打开500,据说就是DIV1的275。

觉得就是左边扫一遍右边扫一遍,得到每个位置的上限和下限,于是直接枚举。复杂度就是O(N√N + M)。

Orz表示1000^2 * 50毫无压力的神犇们!!!原来TC的精髓就是暴力……

搞完以后看到最后一题瞬间被秒。。。最后没有交1000。

其实当时的想法很接近正解,也是求连通块,就是没想出每个连通块有n!/2种方案。

好像DIV2里面也没有多少个交1000的……居然搞了DIV2里面第6,Rating一下变到1700+,然后名字就变成黄色了。。。

今天听说别人TC都用插件,下了个KawigiEdit,导入了以后再里面点Run Test Case显示神马g++不行之类的,鸭梨山大。改天再搞一搞。

刚在调这个KawigiEdit的时候被zbwmqlw神牛喊了一声没有听到Orz~罪过罪过

【AC_LCC_CWJ 第三场】NWERC 2008

今天拔完牙的Lcc大爆发!!!

一个人秒了4题Orz

师父有点事,又跑了一会儿,然后一回来就说:D题数论,然后就Y了。。。

然后我就切了2个题,虽是每个队都秒的水题,但是对于我来说都不算水。。。

于是总共7题……在当时的Board里面第一9,第二6

关于D题,师父写的O( PlogP),后来发现别人都是O(P^2)水过的,更后来听说一个O(P^3)的都水过了

顿时崩溃……

【地址】http://acm.hust.edu.cn:8080/judge/contest/viewContest.action?cid=940

(还可以继续交的)

然后我说说我做的题目:

首先是I题:

http://acm.hust.edu.cn:8080/judge/contest/viewProblem.action?pid=22107

【题目大意】

有一个音乐播放器,它采用随机播放形式。它工作流程是:先随机产生一个1~n的排列,然后就按这个排列播放接下来的歌曲。然后播完了n首以后呢,它会再次随机产生一个1~n的排列,然后按新的排列播放。

现在给你一段从某个时刻开始的播放音乐的历史记录,以及播放器里一共有多少首歌。

问历史记录中第一首歌可能是某个完整排列里的第几首歌?输出可能的位置的个数。(其实每首歌可能在排列的位置的个数都是一样的,往后推而已)

【做法】

显然相同的不能出现在同一组,除此之外根本没有其它限制。

那么枚举每一个记录,很容易利用hash得出前面一个和a[i]相等的a[j]在何方。然后就得出一个区间的限制,限制形式为第i个字符不能是序列中的第L~第R个字符。这个限制跑去mod一下歌曲的总数,在剩余系上就可以用线段树Cover一下,最后标记下传就可以知道还有哪些是没有被覆盖了,就都可以用了= =

【CODE】

 http://xiudaima.appspot.com/code/detail/4456022

 

接下来是C题

【题目链接】http://acm.hust.edu.cn:8080/judge/contest/viewProblem.action?pid=22101

【题目大意】

给定一个二分图,然后给出N条有向边,然后让你决定二分图里每个点取还是不取,一条边能够计算进结果当且仅当它的起始点被选,终点不被选,结果最多能有多少条边?

【算法分析】

用最小割求解:
(i只表示左边的点,j只表示右边的点)

map[i][j]表示从i到j之间有多少条边
1、S->i  c=Sum(map[i][j])
2、j->T  c=Sum(map[j][i])
3、i->j  c=map[i][j]+map[j][i]
最后Ans=总边数-Flow

一个割把图中的点分在两个集合S集和T集。如果在二分图左边的点被分到S集,那么当做取,否则不取,在二分图右边的点被分到T集,那么当做取,否则不取。

先假设所有的边都选上,然后按照上面的意义YY出每条边的流量就可以了。

【疑问】

一开始第三类边我加了双向的= =,就是WA,改成单向的立马AC。按照这个割的意义应当是符合的啊?问了叉姐,还是似懂非懂的样子。我还得想一想……路过神牛求指点。

【CODE】

 http://xiudaima.appspot.com/code/detail/4502017

 

后来赛后我和lcc都切掉了恶心的F题

【题目链接】http://acm.hust.edu.cn:8080/judge/contest/viewProblem.action?pid=22104

【题目大意】

给出n(n<=50)个立方体,立方体所有边平行于坐标轴,然后问这个立方体浸在水中的,与水接触的表面积以及,排除水的体积分别是多少?

【算法分析】

3维离散化,暴力染色,然后从最外围再弄多一圈边界,然后在最外围弄一个点,以这个点为起点BFS……然后碰到的面都算。

最后没有被BFS到的格子,就是可以算体积的格子,最后加起来就行。

【CODE】

http://xiudaima.appspot.com/code/detail/4521017