首页 > 代码库 > 暑假集训0808

暑假集训0808

来HIT参加暑假集训也有将近一周了,一直什么都没写= =。

记一下今天的比赛吧,以后争取每天更新一篇总结。


我是弱比。只能出6题。

A:POJ1417 很容易发现yes表示两个人是同一类,no是不同类,然后怎么判断方案是否唯一我就不会了。。。我是有多么的弱。。。类似于背包DP,就是用前i个大类填满j个人数的方案。

B:HDU1711 裸KMP

C:POJ 2503 一个字典的实现。很显然的Trie。(我就想说出题人就不能给个n么。。读入麻烦死。。)

D:POJ2828  比赛的时候还是想的有问题。就是想法题。倒着处理,第i个人放入现有的第a[i]+1个空里就行。我们需要查询一段区间里第i个空是哪一个。这里用线段树维护一段区间内空的个数,然后在线段树内二分。

E:HDU4893 奇怪的线段树。这东西其实是不敢写。。。打标记的思想很显然。

F:POJ3067 求逆序对。答案要用long long !!! 我在这卡了很久。。。J题也是一样。。这种细节比赛时要注意啊。。

G:POJ2001 挺简单的一题怎么出的人数这么少呢。。。就是直接建成Trie,每个节点记录一下下面有多少个单词,如果只有一个就输出到这里。

H:HDU1272 判断一个图是不是树。 这题应该是并差集。。但是多麻烦啊,直接bfs。

I:ZOJ 3632 (我不会DP。。嗯。。一定是这样)f[i]表示前i天都有西瓜吃的最小花费,f[i]=min(f[j-1]+v[j]) (d[j]+j>=i)

然后单调队列转移一下状态就行。

(比赛的时候我就想前i-1天有西瓜吃的最小代价和第i天的最小代价没关系啊。不能DP吧 。。然后就不会了。。WTF。。。)

J :POJ 2299 和F一样


 

我觉得比赛的时候还是要注意long long这种细节,不然卡题了就会很慌张,然后智商大幅度下降,然后就完蛋。。。

还要提高1A率啊。。