CSP-S复习计划-AC自动机

有n个单词和一句话
求出这句话包括几个单词

这就是一道例题了

很好,看了看,其他的都是套个dp,套个建图的憨憨模板,这个就好,其他自己推吧!

[Usaco2012 Dec]First!

[Usaco2012 Dec]First!
这题老旧之前做过,但是好像没调出来T了,然后弃了,现在看到有人在做,然后就顺便丢了出来调了一下调过了。憎恨把true写成false的我。
还找来师兄代码改呀改才改对的。
这题其实真的不难,终点在于你怎么去处理他们之间的关系呢,我们可以先用他们建一棵字典树,然后对所有儿子节点进行拓扑排序,如果有入度为零的点就代表有解。 ......  查看更多

2018-4-13模拟赛:解题报告

比赛题目

2018-4-13模拟赛:A 2018-4-13模拟赛:B 2018-4-13模拟赛:C 2018-4-13模拟赛:D

解题概况

今天是休假后的第一场比赛,所以呢,很多东西都很陌生,这样的话我觉得我还是好好复习文化课吧,不存在的,那么,还是认真的写一下题解吧,加油。

解题详情

2018-4-13模拟赛:A

这题的话其实正负数没什么区别的呢。
最优的策略一定是尽量少走回头路,尽量往终点的方向跳。我们先一直跳,跳到已经超过终点,且离终点的距离为偶数时的步数即为答案,因为此时可以通过调整前面一些跳跃的方向,使得我们刚刚好到达终点,为什么呢?
当没有到达终点时,显然不行。
当超过终点且离终点的距离为奇数时,假设当前的位置在pos,若我们把之前往终点跳x距离的一步改为往终点的反方向跳x距离,那么我们的位置就到了pos-2x,只能到离当前位置为偶数距离的地方,并不能到达终点。
同理,当超过终点且离终点的距离为偶数时,我们就可以通过调整之前某些跳跃的方向,到达终点。
AcceptCode ......  查看更多

2018-4-13模拟赛:B

2018-4-13模拟赛:B
这题就是字典树的基础用法啦,但是呢,作为休假选手,我好久没打过比赛了,打都不会打。
这题就是一个贪心。。你先建立把全部串在字典树上面建出来。然后对于每一个点,如果他是一个原名的结束节点,那么c++,如果是专属名字,那么。c1++显然,如果有一个点,c1c2同时不为0,那么他,那么他们在这里匹配肯定是最优的。然后多出来的一些,就给父亲去处理。容易发现这个做法肯定是对的。 ......  查看更多