POJ 2955 Brackets

题意

给出一个由小括号喝中括号组成的括号序列,定义正规括号序列为(),[],(s),[s],其中s也是正规括号序列。求最长正规括号序列的长度。

思路

考虑区间DP,设计状态时着眼于“最后一次加括号”。

状态表示:dp[i][j] = 从 i 到 j 的(包含i,j)最长的括号序列长度。

状态转移:

  • dp[i][j] = dp[i][j-1] 继承上一个区间的结果
  • 令k为i,j之间的一个位置,str是给出的括号串(令下标从1开始)
  • 如果str[k]与str[j]正好是一对匹配的括号,可以考虑在最后一步放这个括号,用dp[i][k] + 2 + dp[k+1][j-1]尝试更新dp[i][j]

答案:dp[1][len]

初始化:直接令整个dp数组都为0,既可以完成初始化,也可以无效化所有无效状态。

代码

 

位运算有关小技巧

基本运算

以下a指一个二进制位。

NOT

  • ~1 = 0
  • ~0 = 1

如果智商正常应该不会不能理解取反运算吧

AND

  • 1&a = a
  • 0&a=0

由此可见善加利用AND运算,可以保证某个二进制数的特定位为0,其余的位保持原样。

OR

  • 1|a=1
  • 0|a=0

由此可见善加利用OR运算,可以保证某个二进制数特定位为1,其余位维持原样。

XOR

XOR/异或运算具有重要性质:

  • a^a = 0
    XOR可以代替等于
  • 0^a = a
    0是XOR运算的单位元
  • 1^1=0 1^0=1
    用1去做XOR运算可以实现“开关”某个二进制位的效果
  • abs(a^1-a)=1
    用1对一个数去做XOR可以实现求与这个数相邻的数的效果
    比如2^1=3 3^1=2
  • 1^1 = 0;1^1^1 = 1;1^1^1^1 = 0
    XOR与奇偶性紧密相连

SHL/SHR

左移运算相当于除以2,右移运算相当于乘2.

运算技巧

scanf

while(~scanf(” %d”,&n)){}
while(scanf(” %d”,&n) != EOF){}

两种形式等价

判断奇偶性

if a&1 == 1 then a is odd
if a&1 == 0 then a is even

取出最低位

lowbit(x) = x&(-x)

制作全1掩码

mask = (1 << n) – 1

理论最大最小值

INTMAX = ~(1 << 31)
LLMAX = ~(1ll << 63)

INTMIN = 1 << 31
LLMIN = 1ll << 63

常用最大值

memset(dp,0x3f,sizeof(dp))

装逼

swap

a= a ^ b
b = a ^ b
a = a ^ b

绝对值

abs(n) = (n ^ (n >> 31)) – (n >> 31)

最大值

max(a,b) = b & ((a-b) >> 31) | a & (~(a-b) >> 31)

最小值

min(a,b) = a & ((a-b) >> 31) | b & (~(a-b) >> 31)

集合

表示集合

用二进制位表示集合是很简单也是很直观的,直接举个例子:假设全集是{a,b,c,d,e,f,g,h},这样我们一共有8种不同的元素,怎么表示{a,c,e}这个集合呢,很简单,我们拿出8个二进制位,从左到右分别表示“a,b,c,d,e,f,g,h”,那么{a,c,e}就可以用二进制”10101000″ 表示。

操作用二进制表示的集合

加入元素:使用“或等”运算

删除元素:使用“和等”运算

确认元素是否在内:使用“和”运算

并集:使用“或”运算

交集:使用“和”运算

补集:先使用“取反”运算,再使用“和”运算

开关:使用“异或”运算

枚举

枚举全部的集合形态:从0枚举至11111111…

枚举某个集合的自己:-1,然后和求子集的集合做“和等”

图论

获取反向边

i i^1互为反向边,要求插边时必须同时插入正边和反边,边数组编号从2的倍数或0开始。

数据结构

二叉树

令根节点为1

编号x的节点的左儿子编号: (x << 1)
编号x的节点的右儿子编号: (x << 1) + 1
编号x的节点的父亲编号: (x >> 1)
编号x的节点的兄弟编号: (x ^ 1)

二叉树两个节点节点是否相邻

使用堆存储,根节点编号为1,如果a^b=1,则两个点必定同属一个父亲

二叉堆

先坑着,看需求

动态规划

滚动数组

模运算很慢,所以我们用XOR代替mod2。

int tick = 0;
for(){
dp[tick^1] = dp[tick];
tick ^= 1;
}

快速幂

这里暂时不详细提供代码了。

 

LA2678 Subsequence

题意

给出一个由n个整数组成的数列,要你求长度最短的连续序列,使得序列中所有元素的和大于等于S。

思路

单调性优化,或者说是尺取法。

暴力O(n^3)显然无法接受,套用前缀和优化再枚举O(n^2),还是无法接受。

在套用前缀和的基础上,可以枚举终点,二分查找起点,这样是O(nlogn),可以过了。

然而还有更好的办法,设两个指针,表示连续区间的左端点和右端点,一开始不断右移右端点,直到序列大于等于S,记录长度。然后右移左端点,再开始不断尝试右移右端点,直到条件再次满足,停下纪录,右移一下左端点。。。如此往复,直到右端点无法右移,且左端点无论怎么移动也无法满足条件。

这就是尺取法(名字来源于挑战程序设计竞赛),CF上面也叫Double Pointers,是一种基于单调性的优化手段。

代码

前缀和+尺取

前缀和+二分

 

LA3905 Meteor

题意

请参考LRJ白书第一章例题20

思路

扫描线。

这个题分为两部分,首先是要求出每一颗流星划过取景框的时间区间,这一步反而是这个题最复杂的地方,因为要讨论许多种情况,具体的讨论策略可以参考下面的代码。

求出来所有的区间之后,问题转化为选出一条线,使得这条线穿过的区间最多,这里就是扫描线算法派上用场的时候了。其实实现很简单,就是对于每个区间的两个端点,分别创建一个表示起始的事件和一个表示结束的事件,然后把所有事件按照出现的时间排序,接下来从小往大检查,遇到开始事件的时候计数器+1,遇到结束事件的时候计数器-1.

这里有一个问题,如果开始事件和结束事件恰好位于同一时点,怎么办?注意到我们的区间都是开的,这样我们只要优先处理结束事件,就不会导致解偏大了(这里面的逻辑需要自己试着理解一下)。

代码

 

UVA 11549 Calculator Conundrum

题意

给出一个数,你要对他反复平方,平方完之后总是取运算结果的前n个十进制位(如果结果大于n位)作为答案,然后对这个答案继续进行刚才的操作。

这是一个循环的过程,你要找出在这个循环节中最大的数。

思路

首先是循环节这一点,意识到形成循环节并不难。从理论上来证明:我们可以设定一个运算#表示相乘取前n位这一操作,初始值为a,a#1=a,1为单位元,N为所有k及k位以下整数组成的集合,两个数做运算得到的结果必然属于N,则<N,#>构成一个有限群,<a^x>必然构成循环群。

取前n位这一操作可以用字符串流,但是那样常数非常大,所以还是考虑利用数学运算来实现,这样会提高速度。

找出循环节的方法有两种,一种是开一个set,算一次insert一次,如果碰到算过的就停下。还有一种是Floyd判圈法,也就是同时维护两个数A和B,每一次令A=A^2,B=B^3,也就是B总是会比A多走一步,这样如果有环,A和B一定会相遇,在相遇时停下。

代码

Floyd判圈法,数学方法求前n位。

 

UVa 11078 Open Credit System

题意

给出一个整数组成的序列,求两个整数A和B,其中A在数列的位置在B前面,令A-B最大,输出这个最大值。

思路

利用问题的单调性优化的典型例子。

暴力是O(n^2)的,显然无法通过。注意到A始终在B的前面,而且一定是A-B,也就是说对于每一个B,只要找到在它前面最大的A就可以了,不妨考虑随着B逐渐后移的同时,维护前面A的最大值,这样做的复杂度是O(n)的,很完美地解决了这个问题。

这种思想经常会被用在其他问题中作为一个需要优化的环节。

代码

 

 

UVA 11462 Age Sort

题意

排序,25MB大数据,都是整数,最大100最小0,内存极其紧张。

思路

面对这种数据范围很小,量很大的情况,考虑计数排序,原理非常简单就是开个数组统计一下不同值有多少个数字就搞定了,时间O(n)。

能做到O(n)的排序算法还有Sleep Sort,不过因为利用多线程睡眠差异太难控制所以也没啥实际意义。

被卡常数的时候,也可以考虑用计数排序进行没什么卵用的优化(结果可能就真卡过了)。

代码

LA3177 Beijing Guards

题意

可以参见LRJ白书第一章例题16.

有n个人,围个圈,每个人想要一定数量的礼物,注意每个人所持礼物不可以重样,两个相邻的人所持的礼物也不能重样,问你至少要准备多少种不同的礼物,才能符合要求?

思路

大概是个构造题综合二分答案。

首先要想到对n的分类讨论:

  • 如果n是偶数,那么你只需要准备两套不同配置的礼物,按照ABABABABAB这样循环下去就可以满足要求了,因此答案是max{r_i+r_((i+1)%n)}
  • 如果n是奇数,情况就比较复杂。我们可以先反向思考,如果给定有r种礼物,如何才能构造合适的礼物配置满足题设要求?白书里面给了这样一种方法:令编号为奇数的尽量选取靠前的种类,编号为偶数的尽量选取靠后的种类,即把r种礼物分成两半(即前、后两组),对于每一个人维护他按照上面策略进行选取的前组后组中元素数量,最后检查第一个人和最后一个人是否相容即可。这样我们就有了二分答案的检查方法了。

代码

 

LA3902 Network

题意

给出了一棵树,和一个初始的黑点(VOD服务器),所有边的边权均为1,你要求出最少还要染黑几个点,才能保证每一个白点到最近黑点之间的距离小于等于k。

思路

大概是贪心。

把给出的初始黑点当成树的根部,从根部dfs一次求出所有节点的深度,然后把深度最大的点(如果深度大于k)染黑,之后以这个点为中心dfs一次标记所有能覆盖的点。然后找第一个没有被覆盖的点,染黑,标记。。。直到所有点都被标记。

代码

 

UVa 11520 Fill the Square

题意

填充一个NxN网格,使得每个格子的字母与其相邻的字母均不相同。输出字典序最小的填充方案。

思路

注意到解的空间非常大,因此只要每一次从’a’~’z’枚举并检查当前格子就可以了。这样也可以保证字典序最小,因为每一次的填充是从最小的字母开始尝试的。

代码

 

Scroll to top