usaco08dec专题

(Luogu) P2922 [USACO08DEC]秘密消息Secret Message (字典树)

传送门 解题思路:查询前缀的个数,典型的字典树问题(字典树入门和例题),给你一个前缀,如果单词(都称为单词了)与这个前缀的前部分重合时,res也++,这是需要注意的,例如:前缀10111,那么101也算一个答案;用一个sum数组记录到root这个点为前缀个数,同时flag数组为以root为结尾的单词的个数(flag从标记结尾,变成个数,因为可能有相同的单词数),查询前缀时,遇到flag不为0,那

P2921 USACO08DEC 在农场万圣节Trick or Treat on the Farm

万圣节又要到了(大雾),可恶机智的农场主又要给欺骗奶牛们发糖果了。 题目描述 Every year in Wisconsin the cows celebrate the USA autumn holiday of Halloween by dressing up in costumes and collecting candy that Farmer John leaves in the N

P2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm(Tarjan+记忆化)

P2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm 题意翻译 题目描述 每年,在威斯康星州,奶牛们都会穿上衣服,收集农夫约翰在N(1<=N<=100,000)个牛棚隔间中留下的糖果,以此来庆祝美国秋天的万圣节。 由于牛棚不太大,FJ通过指定奶牛必须遵循的穿越路线来确保奶牛的乐趣。为了实现这个让奶牛在牛棚里来回穿梭的方案,FJ在第i号隔间上张贴了一

P2921 [USACO08DEC] Trick or Treat on the Farm G

Portal. 每只奶牛的终止条件是到达自己已经访问过的点,换言之,就是该奶牛的路线构成了一个环。并且,每一个房间通往的房间都是固定且唯一的,所以说只要进入的这个房间在环上,这个房间之后会获得的糖果数已经固定了。 我们开一个数组 s 记录当前位置的糖果数量,用 vis 数组记录房间的访问情况。对于一个已经访问过得房间,我们只需要用在这个房间的糖果数量减去上一次来这个房间的糖果数量,就可以得到当