T1

题目

给定n个括号序列,要求从中选出若干个拼起来,使得拼成的序列为合法的括号序列,在此基础上使得长度尽量长.

n <= 1000,总长度 <= 10000

解法

对于一个括号序列来说,如果将其中匹配的括号去掉的话,它的形式会变成左边一串右括号,右边一串左括号.比如)()))((,去掉匹配括号之后就形如)))((,可以用二元组(3,2)来表示.

设f[i][j]表示考虑了前i个序列,前缀和为j.左括号为1,右括号为-1,那么一个括号序列合法的充要条件是任意一个前缀和都>=0.所以只要两个括号序列合并的时候前缀和大于等于0就可以转移.

再来考虑顺序.比如(())和))((相比,(())更优,因为它的最小前缀和更大.或者考虑二元组的形式(A,B)和(A’,B’).当A<B,A’<B’,此时比较A和A’的大小,将A小的放在前面.A>B,A’>B’,

T2

题目

给定n个括号序列,要求删掉一些位置,并且把所有序列适当排列,使得接起来组成一个合法括号序列,且长度最长.n<=100000.

解法

此题跟DP没有关系.(大雾)考虑一个括号序列表示成(A,B),那么要使得它合法,就要去掉A+B个位置.

T3

题目

令S是一个括号序列,定义f(S)表示把所有匹配括号删除之后S的长度。给定一个括号序列，求一个子串S，使得f(s)最大.

长度 <= 100000

解法

[不会]

T4

题目

给定一个矩阵,每个位置有全职.一个子矩阵的权值定义为包含的每个位置的权值和.两个不相交的子矩阵的pair的权值定义为两个子矩阵的权值的积.求所有pair的权值和
矩阵大小不超过1e6

解法

将情况分成三种可能

  1. 被横线分开
  2. 被竖线分开
  3. 被两种线同时分开

利用容斥算出来,再加上二位前缀和.
为了不重复计算,我们假定被横线分开时,上矩阵贴横线,被竖线分开时,左矩阵贴竖线,其他同理.
设f[x][y]表示右下角是(x,y)的矩阵的权值和

f[x][y]=ΣiΣjsum(i,j,x,y);

T5

问题

有n个白点和m个黑点.求是否存在一个由白点组成的简单凸多边形,内部恰好有k个黑点.为了方便假设不存在三点共线的情况.

n,m,k<=100

解法

[不会]

T5

题目

有n个数a[1]到a[n],你可以把每个数+1,-1或不变,要求他们最终的gcd最大.

n <= 100000, a[i] <= 10^12

解法

[不会]

T6

问题

有n个数a1到an,要从中选出一个长度为k的子序列形成b,满足b[i]>b[i-1],b[i+1]-b[i]>b[i]-b[i-1],要求输出一组方案,没有输出无解.

n <= 20000,k <= 100

解法

记f[i][j]表示结尾是i,目前长度为j,最小的b[i]-b[i-1].f[i][1]=0.

T7

问题

有一个程序包含m个嵌套的for,每个for形如for(x=l;x<=r;x++);其中x互不相同,l和r可能是之前某一层的变量可能是常数,若l是常数则一定是1,若r是常数则一定是n.求这个程序的复杂度分析中,n的最高次方以及最高次方上的常数.

n <= 20

解法

[不会]

T8

问题

给定一个二叉树的前序遍历和中序遍历的结果,其中一些位置丢失了,求有多少种合法的二叉树

n <= 100

解法

——Gensokyo