codeforces 501 B. Obtaining the String

题目链接:http://codeforces.com/contest/1015/problem/B

题意: 给出字符串s和字符串t,问一个将s变为t的策略。 可以做的变换为,交换s中相邻的字符串,该操作最多不能超过4000次,字符串长度最大为50.

思路:

首先可以确定,当两个字符串的组成相同时(也就是有同样的字符组成,只是位置可能有所不同)一定有解。

考虑最坏情况,每个字符都要交换到最远的地方,总的操作数<50*50<4000,因此一定有解。

判断组成是否相同可以用multiset

 

 

codeforces edu #51 C. Vasya and Multisets (思维题)

题目链接

题意:有n个数,现在要分成2个集合,使得2个集合中,仅出现1次的数的个数相同,问是否有解,以及具体的分法。

思路:

一开始考虑出现多个的数的思路麻烦了,比如对于出现2次的某个数x,与其一个集合中分得一个,使得两个结合中,仅出现1次的数的个数各+1,还不如都放在同一个集合中,使得仅出现1次的数的个数不增加。

因此思路是这样的:

先考虑出现1次的数的个数,如果为偶数,那么均分,然后把其他出现多次的数全都放在第一个集合;

如果出现1次的数的个数为奇数,我们还是尽可能均分,然后不妨假设第一个集合中的只出现1次的数的个数比第二个集合中多1个。

我们现在需要让第二个集合中,仅出现一次的数增加一个。

什么样的数可以满足这个条件呢? 出现2次的数是不行的,因为这会使得两个集合中的数字各自+1

因此需要至少有一个出现3次或者以上的数。

具体见代码:

 

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

codeforces 123D. String(后缀自动机)

题目链接:http://codeforces.com/problemset/problem/123/D

题意:

如果字符串y在字符串x中出现n次,那么F(x,y)=n*(n+1)/2

现在给一个字符串,求所有的F(s,x)的和,x为字符串的所有不相同的子串.

思路:

这道题可以考虑用后缀数组做,麻烦一点:codeforces-123D-解题报告(SA)

直接SAM

right[v]就是SAM上状态表示的所有字符串出现的次数。

那么每个状态的答案就是right[v](right[v]+1)/2(st[v].len-st[st[v].link].len)

累加即可。

 

 

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

题目链接:

题目链接

题意:

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

思路 :

关键在于想起,位运算还是按照二进制位的运算。我们考虑每位即可。

如果初始是0,现在变成了1,那么实际上我们并不确定,这个操作是xor 1 还是 or 1

因此我们需要两个初始的数,一个所有二进制位上都是0,另一个所有二进制位上都是1.

也就是0和1023

对于某个二进制位

如果初始的 (0,1)变成了 (1,1),那么说明这个位置上的位运算是or

如果初始的 (0,1)变成了(1,0) 那么说明这个位置上的位运算是xor

如果初始的 (0,1)变成了(0,0) 那么说明这个位置上的位运算是and

如果初始的 (0,1)变成了(1,0) 那么说明这个位置上没有进行位运算操作。

 

 

 

 

 

 

 

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

题意:

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

思路:

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

因此对于有环的联通块答案为0,没环的答案为1.

 

 

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

Description

lxhgww最近迷上了一款游戏,在游戏里,他拥有很多的装备,每种装备都有2个属性,这些属性的值用[1,10000]之间的数表示。当他使用某种装备时,他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。 游戏进行到最后,lxhgww遇到了终极boss,这个终极boss很奇怪,攻击他的装备所使用的属性值必须从1开始连续递增地攻击,才能对boss产生伤害。也就是说一开始的时候,lxhgww只能使用某个属性值为1的装备攻击boss,然后只能使用某个属性值为2的装备攻击boss,然后只能使用某个属性值为3的装备攻击boss……以此类推。 现在lxhgww想知道他最多能连续攻击boss多少次?

Input

输入的第一行是一个整数N,表示lxhgww拥有N种装备 接下来N行,是对这N种装备的描述,每行2个数字,表示第i种装备的2个属性值

Output

输出一行,包括1个数字,表示lxhgww最多能连续攻击的次数。

Sample Input

3
1 2
3 2
4 5

Sample Output

2

HINT

【数据范围】
对于30%的数据,保证N < =1000
对于100%的数据,保证N < =1000000

Source

 

 

思路:

看到了二分图匹配的题解,但是感觉很错啊?

正确的做法是,将武器看成边,将每个武器的2种属性看成点。

使用某种属性,就要消耗一条边。

因此如果一个联通快是树形结构,k个点,k-1条边,因此有一个属性无法被使用。

由于要求是从1开始递增得攻击,因此显然使得属性最大的点不被使用是最优的。

如果一个联通块有环,那么所有的树型都可以被使用。

注意这个联通快有无环影响计数的思维,和codeforces # 440 div2 E. Points, Lines and Ready-made Titles  很像

 

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

题意:

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

思路:

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

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

对于任意一对岛屿群,设两边岛屿的数量分别为a,b

我们可以从两边各取0个,1个,最多取min(a,b)

需要注意的是,选取了端点之后有顺序的区别。

所以对于该对岛屿,答案是SUM{C[a][k] * C[b][k] * k!}   (k属于0..min(a,b) )

对于其他 两对同理。

 

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

题目链接

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

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

思路:

参考题解

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

bzoj 1854的并查集思路蜜汁契合 // 看完了题解的我这样想道

首先显然可以将图分为若干个联通块。

且慢,哪里来的图? 那就先考虑建图? 不急不急,先来想想看每一个联通块的性质。

如果该联通块中有环的话,肯定每条边都能取到;如果联通块是一棵树,那么必有一条边取不到(具体阐述见上bzoj 1854),所以只需要知道

  1. 这个联通块中有多少条边
  2. 这个联通块是不是环

这两个信息就可以了

那么可以直接上并查集。

什么样的点可以并到一起呢?横坐标相同的或者纵坐标相同的。

有没有环怎么维护呢?看有没有加进去的边的端点本身就在一个集合里。

联通块中边的数目又怎么知道呢?这倒还挺有意思的,其实只要直接看出现过多少个横坐标或者纵坐标就可以了,因为一个横坐标或者一个纵坐标就代表一条可以选的直线,所以这块联通块的贡献就是2^(x+y)者2^(x+y)-1

然后呢?就做完了。

然而呢?比赛结束。一天了。

相关并且有趣的题目:bzoj1854
codeforces #346 div2

codeforces 385 E. Bear in the Field (先记录想法)

题目链接

题意:

有一只熊,初始在(sx,sy)处,如果当前的位置在(x,y),那么下一秒会在((x+dx-1)%n+1,(y+dy-1)%n+1)处, dx[i] = k[i-1] + dx[i-1],dy[i]=k[i-1] + dy[i-1],k表示的是某个点的花丛数目。

初始点(x,y)的花丛数为x+y,每经过一个时间,所有点的花丛数增加1.

所以,k[i] = x[i] + y[i] + i-1,现在问经过时间t后,熊的位置在哪里。也就是x[t],y[t]的值。

思路:

我们不妨先只考虑x方向的,因为y方向完全相同。

观察x[t]的式子, x[t] = (x[t-1] + dx[t-1] -1) % n +1。。这个%n之后+1简直蛋疼得一逼。。。

我们不妨构造g[t] = x[t]-1,这样原式子就变成了 g[t] = (g[t-1] + dx[t-1]) %n …看起来爽了很多。。。

观察式子g[t] = (g[t-1] + dx[t-1]) % n,我们发现这是一个前缀和的形式。

根据在hdu4686解题报告  中提到的经验,对于求和的式子,我们只需要考虑每一项的构造法。

因此问题转化成构造矩阵dx[t]

dx[t] = k[t-1] + dx[t-1]

其中k[t] = x[t] + y[t] + t-1,我们写成gx[t]和gy[t]的形式

k[t] = gx[t] + gy[t] + t + 1

k[t-1] = gx[t-1] + gy[t-1] + t

因此可以得到k[t-1]与k[t]之间的递推关系: k[t] = k[t-1] + dx[t-1] + dy[t-1] + 1

观察到k[t]的表达式中同时包含dx,dy项,因此之前考虑的单独处理x和y的想法应该是行不通的。我们考虑同事处理x,y。

 

 

codeforces 855 B. Marvolo Gaunt’s Ring (前缀最大,dp)

题目链接

题意:给出n,p,q,r,以及n(1E5)个数,所有数的范围都是[-1E9,1E9],现在问pa[i]+qa[j]+r*a[k]的最大值,满足1<=i<=j<=k<=n

思路:傻逼dp…

我。。好菜啊。。。万年dp苦手。

直接转载官方题解了。。。思路的重点是维护了一个最大前缀值。

dp[i][0] stores maximum of value p·ax for x between 1 and i. Similarly dp[i][1] stores the maximum value of p·ax + q·ay such that x ≤ y ≤ i and dp[i][2] stores maximum value of p·ax + q·ay + r·az for x ≤ y ≤ z ≤ i.

To calculate the dp:

dp[i][0] = max(dp[i - 1][0], p·ai)

dp[i][1] = max(dp[i - 1][1], dp[i][0] + q·ai)

dp[i][2] = max(dp[i - 1][2], dp[i][1] + r·ai)

The answer will be stored in dp[n][2]

 

 

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

题目链接

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

思路:画画图? 显然可以按照第一关键字左端点升序,第二关键字右端点降序(降序是为了处理 n=2,[1,2],[1,3] 这样的case容易一些),先考虑2种最简单的情况。

第一种是a[i+1]完全被a[i]包裹在里面,准确得说不一定是a[i],而是之前所有线段的最大右端点的那条线段,此时a[i+1]就是冗余的线段。

第二种是a[i+1]的左端点在之前所有线段的最大右端点右边,此时没有冗余,继续进行。

接下来考虑比较复杂的相交情况,我们画图发现,当前线段是否冗余,只与a[i-1]和a[i+1]有关。

如果第i条线段的左端点,不超过第i-2条线段的右端点的右边一个位置,此时第i-1条线段就是冗余的。

wa了2次。。原因是没认真看题,l,r的范围的最小值是从0开始而不是1。所以总体来说是道水题(调教场的题这么水了么。。。

 

 

 

 

Codeforces eductional round 29

比赛链接

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

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

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

 

B: 2*n个人,每个人的重量为w[i],要分成n-1组,每组2个人,以及2个单独的人。单独的人的不稳定性为0,每组的不稳定是该组的2个人的重量的差的绝对值。总的不稳定为所有组的不稳定性之和。问可能的最小不稳定性是多少。

思路:由于n才50,100个人,暴力枚举单独的人,复杂度O(nnnlg(n)),很稳。 注意n给的是组数,所以数组最大值应该为100而不是50.

 

C: Ali和Bob两个机器人进行一个类似”石头剪子布”的游戏,每次2个机器人同时出{1,2,3}中的一个。 2 beats 1, 3 beats 2 , 1 beats 3. 赢的得1分,输的得0分。数字一样2人都不得分。2个机器人当前回合的策略(也就是出哪个数字)只取决于上一回合2个机器人出的数字。并且规则完全已知,会用2张3*3的表的形式给出。现在要进行k场游戏,问最后的分数是多少。

思路:由于k比较大,所有可能的分数序列(x,y)又非常有限,因此显然是求个循环节搞。

需要注意几点:

  1. k的大小太小,比循环节开始的第一个位置还小
  2. K是LL类型,各种和k有关的变量也要记得是LL类型
  3. 为了寻找循环节第一次出现的位置,将循环节第二次的开始存了进去,但是在算一个循环节的分数以及其他的时候,记得不要把这个多余的一次算进去。

D:有n(2e5)个数的序列,q(2E5)个区间操作,操作有2种类型,一种是将区间[L,R]循环右移一位。另一种是将区间[L,R]中的数整体反转。最后m(100)个询问,每个询问问b[j] (j属于1..m,b[j]属于1..n)位置上的数是多少。

思路:观察发现m比较小,可以暴力。对于所有操作进行完,b[i]位置上的数是多少, 因为所有的数只是位置改变,大小没有改变.我们想要还原,到最后的b[i]位置,应该对应的是初始序列中的哪个位置。
如果当前位置是pos,那么在进行上一个反转操作之前的位置就是(L+R)-pos, 进行上一个移位操作的位置就是pos-1(注意边界)

 

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

题目链接

题意:

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

思路:

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

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

结论是:求出三个lca,并取深度最大的那个,就是我们要的三岔路口K,然后分别求出K到a,b,c三点的路径长度,取最大值+1就是答案。

所以我的问题在于,没有试图往一般性的方向考虑,以为讨论一下就可以了…

这大概就是所谓的猜结论?

感性的理解的话,LCA越深,意味着另一个点到LCA的距离越远,也就是相交的路径越长

但是我的话,估计还是很难在短短不到一个小时内得出这样一般性的结论orz…

这大概就是数学方面的天赋差距把…T T

 

 

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

题目链接

题意:

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

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

对于s中的每个‘*’,规定其必须替换为0个或者多个坏字母。

思路:

显然带*的会比较难搞。所以只说带*的情况

我WA了好多次,原因是一开始读错题(或者题意不太清楚?),认为*只能最多替换一个[坏字母]

后来在这个思路上改,越改越复杂orz

仔细想一下,关键点有两个,一个是当前位置有三种情况{没有经过*,经过*且仍在*的作用域内,经过*且已经出了*的作用域}

如何知道*的作用域呢?由于*的替换是连续的,因此只要对比s和t的长度差就可以了。

对于不同的作用域,普通字母的判断位置是不同的,在经过*的作用域之后,普通字母(包括‘?’)记得加一个offset

所以第二个关键点就是,对于*的替换,一次判断完多个。

除此之外,注意下*可能为空的特殊情况,特判一下比较保险。