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

2016 ICPC 大连 区域赛 A Wrestling Match (交叉染色法判断二分图)

题意:

给出n个点m条边,以及已知的好点和坏点。一个边连接的2个点一定是一好一坏,问是否有合法方案,使得每个点被确定好坏。

思路:

判断二分图。

先染已知的,再染未知的。

注意判掉没有出现的点。

注意有多个联通块。

 

 

 

2016 CCPC 长春 I 题 | hdu 5919 Sequence II (可持久化线段树求区间第k大+可持久化线段树求区间不同数个数)

题目链接

题意:

给定一个序列 n,有 m次查询,每次查询一个区间[l,r],求区间中每一种数在区间中第一次出现的位置的中位数,强制在线。

思路:

先分解一下问题,我们要求一段区间位置的中位数,其实可以分解成,求区间中不同数的个数+求区间中第k大的下标。

对于求区间中不同数的个数,离线可以随便线段树,树状数组,或者莫队也行(观察到数据范围<=2E5)

在线的话,就只能可持久化线段树了。

看到一些题解中说要倒序处理…但是之前写求区间不同数的个数,我都是倒序处理的啊? (回想一下,当时似乎正序处理也行…

倒序处理是为了,处理到第i个的时候,第i个一定是当前后缀区间中,第一个出现的…

然后第二个问题,求区间中第k大的下标,离线做法不少,在线的话,也可以用可持久化线段树求。

所以感觉就是板子题,可持久化线段树的2个应用放在了一起orz

 

 

 

hdu 5531 | 2015 ICPC 长春 regional onsite Rebuild (三分)

题目链接

题意:

有n个点,表示n个圆的圆心,问一组圆的半径,满足相邻(i,i+1)或者(n,1) 圆相外切

思路:

我们发现确定第一个半径之后,其他的圆的半径似乎能解出来?

然后发现,其实只有n为奇数的时候能解出来,n为偶数不行。

那么我们可以奇数偶数分别处理。

对于奇数,直接解出来。式子不写了,很好推。

对于偶数,我们发现,最后会是一个关于r1的二次表达式。

一眼三分。然后训练的时候我就直接三分了。。???

三分的过程中判断一下是否所有圆的半径都满足实际意义。。。

然而这是错得,而且错得很显然。因为。。如果不满足实际意义,是根本没办法判断,该往哪个方向继续三分的。

然而这是错得,而且错得很显然。因为。。如果不满足实际意义,是根本没办法判断,该往哪个方向继续三分的。

然而这是错得,而且错得很显然。因为。。如果不满足实际意义,是根本没办法判断,该往哪个方向继续三分的。

正确的做法是,三分之前一定先确定定义域范围,在定义域内三分。

正确的做法是,三分之前一定先确定定义域范围,在定义域内三分。

正确的做法是,三分之前一定先确定定义域范围,在定义域内三分。

 

所以我们先解一个不等式组,把三分的范围解出来之后再进行三分orz

我对三分一无所知…

 

 

 

 

2016-2017 ACM-ICPC, NEERC, Northern Subregional Contest G Gangsters in Central City (LCA)

题意:

有一棵树,水源在根节点1,房子在叶子节点。有若干操作,操作可能是歹徒占领或者离开一个房子。我们不想给歹徒供水,可以通过切断边实现(如果某个叶子节点到根节点的路径上有一条边被切掉,那么就不能供水了。)对于每次操作后,问不给所有歹徒供水最少要切多少条边,并且问在切满足前面最小的情况下,最少使得多少个良民受影响。初始没有歹徒。

思路:

 

我们先考虑第一个问题。容易知道,假设与根相连的有k条边,那么最多只需要切k次,就切断了所有房子的水源。

也就是说,从最少切的次数角度的考虑,切与水源相连的边一定是最优的。

我们可以考虑把树根1去掉,这样得到k棵子树

然后可以预处理出,对于每个叶子节点,其非根的最远祖先是谁,也就是k棵子树的根节点都是谁。

那么对于每次出现歹徒,假设其非根的最远祖先是x,只需要切1-x这条边即可。

 

现在考虑第二个问题,在保证问题一最小的情况下,一个比较直观的想法是,我们尽量往低了切,也就是尽量往原理根的边上切,这样才能使收到影响的良民比较少。

容易想到,一个子树上该切的点是,所有被歹徒占领的坏点的LCA。这样可以使得受到影响的良民最少。

因为我们要得到受到影响的良民的数量,所以用siz[i]维护以i为根的子树的叶子数量,以及歹徒的数量。

这道题的关键结论是,:树上多个点的LCA,就是DFS序最小的和DFS序最大的这两个点的LCA”

这道题的关键结论是,:树上多个点的LCA,就是DFS序最小的和DFS序最大的这两个点的LCA”

这道题的关键结论是,:树上多个点的LCA,就是DFS序最小的和DFS序最大的这两个点的LCA”

因此这题就是写个LCA就可以了,切掉的坏点的dfs序可以用个set维护下。

 

 

 

 

uvalive 7675 | 2016 北京 regional onsite H – A New Ground Heating Device (二分+多个圆面积并)

题目链接

题意:

在一个二维平面上,有n个加热设备,每个加热设备加热一个圆形,加热设备需要信号源才可以工作,信号源在原点上,但是高度不确定。假设设备的加热半径是一个与{信号源与设备的距离}有关的表达式。现在想要满足,至少有k个加热设备加热的面积大于s,问信号源的最高高度是多少。

思路:

训练的时候一眼二分,但是求圆并的时候gg了。。毫无思路。

搞定了多个圆面积并。。这题就很easy了。。

需要注意,每次二分的时候,记得初始化圆的d…

 

hdu 5992 Finding Hotels (kd-tree 裸题,查询)

题目链接

题意:

有若干个(2E5)旅馆,分别给出旅馆的坐标和价格。有m个查询,每个查询给出一个人的位置(x0,y0),以及其能接受的最高价格。问在该人能接受的价格内,距离其最近的旅馆的坐标和价格是多少。

思路:

kd-tree学习笔记

加了价格的限制其实无所谓,只要在更新的时候,先判一下价格就行了。

训练的时候不会kd-tree。。感觉有点可惜了。不然就6题了orz

 

 

 

2016 NEERC Northern Subregional Contest A Anniversary Cake (水题)

题意:

WH的方格纸,共有(w+1)(H+1)个整点,现在将2个蜡烛放在2个不同的整点上。蜡烛不会被放在边界上。现在给出方格纸的尺寸和2个蜡烛的坐标,求一条线段将方格纸拆成2部分,而且这条线段不经过任何一个蜡烛且使得每一部分恰好有一个蜡烛。问线段的起点和终点。

思路:

为了方便讨论,我们将x坐标小的设为蜡烛1,另一个设为蜡烛2.

分两种情况讨论,即横坐标相同和不同2种情况。

需要注意的是…要交文件orz

 

 

 

Mutual Training for Wannafly Union #1

比赛链接

题外话:

wannafly union:可能有的学校不能很好得传承……可能某一时间可以进过两三次final ……但是final队过后,这个学校就退出了历史的舞台……

 

说实话我依然记得我入学那年,也就是14年,看到了华科又一次进final,然后15年仿佛已经开始走下坡路,到了16年,icpc连快银都没有….见证了hust的衰落,我的内心是格外凄凉的。

而又不仅仅是见证…内心是有些愧疚的….总觉得自己没能把某些传统传承下去。。。。

曾经我以为学校的荣誉轮不到我去争取,毕竟我实力很弱,高中noip虽然有全省第二…但是大弱省….其实我当年只有275分…

14级的一队…pyy+zk+tm,三个人都是初一就开始参加比赛了….而且湖南+广东+安徽….

其他人,也至少比我发展均衡….

所以之前想着…弱鸡如我好好提高学校的下限就好了….

但是现在发现并不是那么一回事…

其实每个人…都是和学校相关的….

即使最后轮不到我…但是应该仍然有这个想法才对吧….

 

好了正题:

这次比赛只做出了三道题,A题之前遇到过,当时不会,忘记补了。目测E题也可以补,不过明天约了妹子自习估计要早睡,所以考完试再说吧。

A:

题意:有一个3*n的maze,一个人初始在最左边的某个格子里(3个中的一个,用s表示),然后有若干由大写字母组成的火车…

每一次运动中:人先向右移动一个格子,然后选择不动,或者向上或者向下(具体取决于现在处在3行中的哪一行),之后每列火车向左移动2个格子。如果某个时刻人和火车位于同一个格子,那么人就狗带了。人的获胜条件是到达最右边。

思路:比赛的时候脑抽。。。竟然觉得是指数模型。。。。然后就觉得想错了orz

这道题可以考虑物理的相对运动,我们可以认为火车是不动的,而人时先向右一个格子,然后换行(或者不换),然后再向右两个

这样直接bfs搞一下就好咯。。。。果然是水题。。。。

 

B: 题意:一个字符串,长度最长为10,由小写字母组成,恰好插入一个字母使其变成回文串的方法…

思路:一开始竟然傻傻得分情况讨论。。。。各种漏。。日。。。后来一看数据范围。。。直接暴力。枚举插入的位置和插入的字母。。然后check。复杂度。。10×10*10*26.。。

 

D:n*n的格子,初始白皇后在(1,1),黑皇后在(1,n),其他点被士兵覆盖(士兵不会动。。。)皇后每次可以横竖或者对角线,走到一个有士兵(或者地方皇后)的位置并吃掉。。。(每次移动必须吃掉士兵或者地方皇后)

白皇后先走,问双方都最优策略。。。谁必赢。。如果白必赢,输出第一步的走的方案。

思路:其实算是构造题。。。?手画一下发现。。。只和奇偶性有关2333,结论很容易发现。。

 

F:题意:猜数游戏。。四种猜法。。大于,大于等于,小于,小于等于。。。并且给出每次猜得对还是错。。。问最后这个数是否存在。。

思路:维护一个L,R。。。最后看L<=R是否成立即可。。。

 

 

 

 

poj 1379 Run Away (模拟退火)

poj 1379题目链接

题意:给出一个矩形区域的长宽,给出区域中若干点,问距离所有点的最近距离的最大值是多少。

思路:很容易想到模拟退火。

比赛的时候因为忘记判断矩形边界导致答案错得离谱2333

加上之后1A

 

 

seerc 2014 Circle of digits (二分+后缀数组)

题目链接

题意:把一个长度为n的只由数字构成的串分成k个不为空的字串,使得最大的串最小(大小是说串所对应的十进制数的大小)

思路:由于长度为x的串肯定大于长度为x-1的串,因此很容易想到,我们要尽可能使得k组串的长度尽可能平均(避免出现某一个串的长度非常大的情况)

我们可以知道,最大值的串的长度一定为 LEN=(n+k-1)/k;

而每一组的长度,只可能是LEN或者LEN-1。

然后build_sa

注意循环串的几个地方记得%n

接下来二分sa数组的下标。

二分check的时候,先枚举断点,断环为链。

由于每部分最长的长度为LEN,所以0..LEN-1中一定存在一个断点。

然后贪心,尽可能取LEN

根据rk值来决定某一段的长度是LEN还是LEN-1(如果rk值比当前的大,那么就只能取LEN-1,否则取LEN)

如果此时k段的长度之和超过了n,说明此时的最大值还可能更小。

于是继续二分区间的前一半。

 

 

seerc 2014 D – Frame (傻逼题)

题目链接

思路:注意xy-(x-2)*(y-2)=2x+2y-4,一定被2整除。因此siz为2的也是合法的。这个比较容易忘掉。

其他的判定条件都很好想。具体见代码;

 

seerc 2014 A Banks (暴力)

题目链接

题意:n个数围成一圈,对于负数可以进行magic操作,也就是取反,但是会影响到左右相邻的,加上这个负数。问最少进行多少次magic操作,使得所有数都是非负。

思路:我们知道,如果一个负数想变成整数的话,只能通过magic 操作。唯一可能影响次数的就是顺序。

不过手动写了几个发现顺序好像无关紧要?

于是大胆猜测,写了发暴力2333。

 

hdu 5763 || 2016 multi #4 1001 Another Meaning (kmp+dp)

hdu 5763 题目链接

题意:给定两个字符串A和B,每个出现在A中的B(可以overlap)都有两种含义,问A串一共可能有多少种含义。

思路:kmp+dp.

考虑dp[i]为前i个字符(也就是从开始长度为i,注意不是字符串的下标为i)的含义数。

我们考虑第i个字符对其他位置字符的贡献。

首先第i位的含义数可以无条件得转移到i+1位。也就是dp[i+1]+=dp[i];

此外,如果第i位是一个B串开始的位置,那么第i位对i+len2位就有贡献。也就是dp[i+len2]+=dp[i];

初始化dp[0]=1,其他为0.

剩下我们要做的就是处理出A串中的哪些位置是B串开始的位置。

kmp处理下就好,用一个布尔数组标记。