月度归档:2016年07月

蒟蒻的自暴自弃的暑假生活(week3.5)

补了一下多校题目

hdu 5752  Sqrt Bo(水题)

暴力算出边界,用Java艹过,注意特判n=1的情况。

hdu 5753  Permutation Bo(期望计算)

计算期望。因为相邻三个数h1,h2,h3三个数(h1<h2<h3)的排列有6种,那么只有h1h3h2和h2h3h1两种可以选择c值,概率为1/3,其他的均是0的情况。对于边界,因为h0=hn+1=0,那么有1/2的概率选择c值。特判n=1的情况,因为这个WA了一次。

hdu 5754 Life Winner Bo(博弈)

可以看一下matrix67关于这个问题的一些神奇讲解.车和国王移动相对简单,因而画个图就看出来了。马的话就是对角线隔三个点会出现先手必败的情况,皇后则是威佐夫博弈,有关讲解可以直接看matrix67的博客。

hdu 5761 Rower Bo(物理,微积分,数学)

clearY大爷在比赛的时候就按照题解的思路积分出来啦,太神了,%%%…然后我尝试自己推倒了一次,写出来还是WA,原来存在a=0得情况,这时候不用判断无解直接输出0.。菜不成声QAQ

hdu 5762 Teacher Bo(抽屉原理)

直接暴力两两枚举,然后在一个dis数组里打标记,如果已有这个距离打上了标记,那么就输出yes。这样做为什么不会超时呢?因为最多只会有2*1e5个曼哈顿距离,所以就算你有很多个点,那么也只需要最多枚举这么多次就找到了。反之如果点很少,就可能出现no的情况。

hdu 5763 Another Meaning(kmp+dp)

字符串上的dp,知道思路后还是写挂了n次。。。首先我们可以用kmp预处理出来所有发现串匹配的位置,在那个位置(模式串的末尾位置打上一个标记1),再开始dp。dp[i]代表前面到i-1位置时的母串的含义数目,dp[0]=1,因为母串至少有一个含义。那么匹配到字符i时:如果没有之前预处理出来的标记,那么直接dp[i+1]=dp[i].如果有的话dp[i+1]=dp[i]+dp[i-lenB+1]。这就是状态转移方程了。

hdu 5774 Where Amazing Happens(map水题)

大水题

 

Educational Codeforces Round 14 除草

打了一次调教场,补补题。。。马上就要开始集训啦,要被学弟学长同学虐,好紧张QAQ争取不爆零

A. Fashion in Berland(水题)

B. s-palindrome(map)

map艹过。

C. Exponential notation(模拟科学计数法)

模拟恶心死辣,这道题一直WA,瞄了眼题解, 哦,原来是处理的时候太复杂啦。确定好输入的时候小数点的位置,以及输出的时候的位置。赶快把这个模拟加到板子里,就不怕用的时候调不出来啦!

D. Swaps in Permutation(dfs)

我们把可以换位置的点放到一个集合里,这样相当于把n个数搞出了个一些连通块的森林。那么在每个连通块内按照字典序较大的排序,那么就可以保证整体字典序最大。那么直接dfs来一波算了。每dfs完一个连通块,就把确定位置的点放到数组里。

E. Xor-sequences(dp+矩阵快速幂优化)

一开始没搞懂题目,往数学方面想,然后不会,跑去问ClearY大爷,结果看了一眼说这不是快速幂。然后再一问发现自己没看清题,原来必须保证选出的点相邻异或啊!!晕,然后就是搞出个任意两个ai异或的结果的矩阵,然后快速幂。为了防止爆int直接全用longlong.

F. Couple Cover(暴力筛法)

既然我们要找大于等于p的组数我们可以先预处理出来小于等于p的答案(用筛法)。然后查询p,因为这里有等于的结果,所以我们直接查p-1即可。暴力出奇迹QAQ

 

蒟蒻的自暴自弃的暑假生活(week 3)

这周主要是颓废,各种颓废….

补了一场EDU14 round,题目很好玩,暴力出奇迹。随后写个题解算了。这周打了两场多校,基本都是酱油的存在,先写写多校目前做出来的几道题目,然后写一下这周训练的题目。

hdu 5723 Abandoned Country (最小生成树+dfs)

题目中说每条边的权值均不同,所以最小生成树一定是唯一的。那么也就不存在什么最小的最小生成树期望了。直接建好最小生成树,然后从任意一个点dfs,计算出每个节点有多少个子节点个数szie(包括他自己),然后连向他的边的就会被size*(n-size)次计算,那么这条边的期望就是len*size*(n-size)/(n*(n-1)/2)。

hdu 5734 Acperience(数学)

很简单的个数学题,bi只会取1或-1,我们把原式展开后发现这是个关于a的一元二次方程,然后只要保证wi*bi的和最大即可。那么就是wi为负bi取-1,反之取1.

hdu 5742  It’s All In The Mind

贪心一波,倒着确定每个数有没有被安排数字。a1,a2尽可能放100即可。

hdu 5744  Keep On Movin(构造,贪心水题)

计算大小为奇数个数的字符集数目,然后我们可以把他们变成偶数(也就是每组取出来个一个字符放到回文字符串最中间的位置),然后把所有偶数字符集(考虑原来奇数字符集变成的偶数字符集)分到这k组就得到了回文串集合,就直接计算出答案了。

Codeforces 546C Soldier and Cards(模拟队列)

Codeforces 540C Ice Cave(dfs,bfs)

为什么这道题你萌都是上来bfs,窝为啥直接想到dfs了啊,还好没超时。。dfs的话其实就相当于找两条从起点出发到终点的路,找到了就一定有解。bfs的话就是找到终点后看能否向 向四周延伸找到可以在移动一步的格子,找到了就一定有解。

dfs:

bfs:

Codeforces  377A  Maze(dfs)

因为剩下的连通块还要保持连通性,所以我们可以先dfs找到s-k个连通块即可。然后剩余的’.’改变。

sgu 320  The Influence of the Mafia(两重dfs)

两次dfs,第一次dfs是负责找到一个大的黑帮,并且确定出一个小的矩形(也就是这个最大黑帮的左右上下边界)把这个大黑帮框起来,然后在进行一次dfs找到这个矩形内不属于这个黑帮的点打上标记,然后再次扫描如果有没有被标记的点,那么要么是自身就是大黑帮点,要么就是被围住了。

Codeforces 653E Bear and Forgotten Tree 2(dfs连通性判断)

首先判断到底有没有可能k条边与1号节点相连。然后窝就不会了。。。看了看题解,了解了一个很神奇的做法。

我们可以维护两个集合一个是不能连边的点对集合,一个是所有点的集合。先把一号节点去掉,然后判读剩余的可以和1相连的节点可以组成的连通块个数。(类似于缩点么?dfs完成后就可以得到所有可以和1号节点相连的连通块个数,而且他们之间互不连通。这里借助STL的set是为了降低复杂度,否则直接dfs每个点的话就变成n*n了。

这样的话如果全部dfs完后还有剩余的点在点的集合中,那么就说明图不是联通的。如果大于k的话也不行。

这道题还学习了一下如果在遍历set的过程中删除元素,一定要先把迭代器增加再删除,否则set容器就会彻底乱掉。

Codeforces 677D Vanya and Treasure(dp+spfa)

好吧,这道题窝也不会QAQ,瞄了一眼题解smg。以下内容就是题解的做法:

因为当前第i层的点数大小不确定所以根据不同大小采取不同的做法。如果k<sqrt(n*m)的话我们直接暴力枚举相邻两层的点数dp即可。如果大于的话,这时候dp可能退化,不如跑一遍全图的spfa更新一遍从i层节点到别的点的最短距离,然后保存一下第i+1层的距离。这样复杂度均摊下来可以保证在n*m*sqrt(n*m)内.唉,有点神啊= =