2014 Xi’An ACM-ICPC Regional Contest Problem G. The Problem to Slow Down You (回文自动机(模块化写法))

http://codeforces.com/gym/100548

题意:

切换面板:标签
标签
添加新标签

回文自动机、 给2个字符串,问2个字符串中,相等并且都是回文串的对数。

思路:

构建2个PAM.然后奇偶起点分别跑dfs即可。

PAM写成了模块化的形式orz

[crayon-[……]

Read more

codeforces div 1 443 A. Short Program (位运算的理解)

题目链接:

题目链接

题意:

一段程序,最多5E5个操作,每个操作的格式为 <opt,x> ,opt表示位或,位异或,位与 三种位运算的一种,x表示范围0..1023的数。现在要求将该程序化简至最多 5个操作,使得对于0..1023的输入,输出与该程序同样的结果。

思路 :

关[……]

Read more

codeforces #346 div 2 E. New Reform (和图有关的的计数)

题意:

给出n个点,条边的无向图,无重边,无自环。现在要求把所有的无向边换成有向边,使得入度为0的点最少。问最少的入度为0的点是多少。

思路:

对于每个联通快,如果有环,我们可以顺时针连接环上的点,以指向环的方向连接联通快上的其他点,这样就可以保证所有点的入度都不为0. 如果是树形结构,则不可[……]

Read more

BZOJ 1854: [Scoi2010]游戏 (并查集)

Description

lxhgww最近迷上了一款游戏,在游戏里,他拥有很多的装备,每种装备都有2个属性,这些属性的值用[1,10000]之间的数表示。当他使用某种装备时,他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。 游戏进行到最后,lxhgww遇到了终极boss,这个终极boss[……]

Read more

codeforces 439 C – The Intriguing Obsession (和图有关的计数,组合数学)

题意:

3个岛屿群,每个岛屿群有若干岛屿。现在要在岛屿之间连桥,桥的长度是1,规定2个属于相同岛屿群的岛屿的距离要大于等于3.

思路:

一直在纠结大于等于3的距离的事情。。。其实这句话等价于,同一个岛屿,对于另外两个岛屿群,都最多只能连接1个岛屿。

那么其实,对于每一对岛屿群,是相互独立的。[……]

Read more

codeforces # 440 div2 E. Points, Lines and Ready-made Titles (和图有关的计数,思维题)

题目链接

题意:有n个整点,每个点处可以什么都不画,或者画一条垂直方向的直线,或者画一条水平方向的直线。

现在给出n个点的坐标,问最多右多少种不同的图案。(只要有一处不同,就认为两个不同)

思路:

参考题解

好菜啊不会做,转载一段题解。

bzoj 1854的并查集思路蜜汁契合 // 看[……]

Read more

codeforces edu #29 E. Turn Off The TV (思维,乱搞)

题目链接

题意:有若干线段,给出起点和终点,问是否有一个线段是冗余的。冗余的意思是说,对于该线段所覆盖的所有整数点,没有该线段,也能被其他一个或者多个线段覆盖到。如果有,输出任意一个冗余线段即可。

思路:画画图? 显然可以按照第一关键字左端点升序,第二关键字右端点降序(降序是为了处理 n=2,[[……]

Read more

Codeforces eductional round 29

比赛链接

10个月没写题了,菜啊。进行一点恢复性训练好了。

A: 给一个数,可以在填写若干(或者0)个前缀0,问能否变成回文数。

思路是直接删掉后面可能的出现的0再判断回文数就好。

 

B: 2*n个人,每个人的[……]

Read more

codeforces #425 D. Misha, Grisha and Underground (dfs+rmq在线求LCA,讨论了一年)

题目链接

题意:

给出一棵树,以及三个点(可能重合),问两两组成的3条路径中,哪2条路径重合部分最长。

思路:

LCA还是一下就能想到的,rmq+dfs在线求。

然后我开始分情况讨论,讨论了一年也没讨论完,哭哭

结论是:求出三个lca,并取深度最大的那个,就是我们要的三岔路口K,[……]

Read more

codeforces #425 B. Petya and Exam (暴力)

题目链接

题意:

给出由小写字母,’?’和’*’组成的字符串s,仅由小写字母组成的字符串t,问按照规则s能否变成t.

规则如下:首先给出定义的[好字母]的字符串,[好字母]之外的都是[坏字母],对于s中每个‘?’,规定其必须替换为一个[好字母]

对于s中的每个‘*’,规定其必须替换为[……]

Read more

codeforces #413 C. Fountains (BIT维护前缀max)

题目链接

题意:有2种货币,分别为C和D.给出n种资源的代价和美丽度,每种资源只能用其中一种资源购买。现在拥有货币C的数量是c,拥有货币D的数量是d.然后恰好买2个资源,问最大美丽度,不能的话输出0.

思路:首先显然三种情况。。。CC,CD,DD.

CD直接扫一遍。。重点是CC和D[……]

Read more

codeforces #413 B T-shirt buying (贪心)

题目链接

题意:有n个T恤,每个价格都不同,有三种颜色,分别用1,2,3表示,每件T恤给出前xiong和后背的颜色。现在有m个顾客排成一队,对于每个顾客,给出他喜欢的颜色,只要一个T恤的前xiong或者后背的颜色之一满足该颜色即可。顾客总希望买符合他喜欢颜色的T恤中价格最低的。现在问每个顾客买[……]

Read more