【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

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注