20171006考试总结

考试策略

花了1个小时看题和想题,成功发现都不会,所以就掐指一算,T1有40分暴力,T2有20分,T3有40分。好了,然后随便把三个暴力打完了,又想了一会儿正解,还是不会,就交了。

以及:这真的是联赛模拟?我读书少你别骗我。

T1

期望得分:40 实际得分:40

题目描述

给定一个由小写字母组成的字符串 s。有 m 次操作,每次操作给
定 3 个参数 l,r,x。如果 x=1,将 s[l]~s[r]升序排序;如果 x=0,将 s[l]~s[r]
降序排序。你需要求出最终序列。

数据范围

对于 40%的数据,n,m $\leq$ 1000。
对于 100%的数据,n,m $\leq$ 100000。

解题思路

一开始肯定是没思路啦。后来想了一下,想出了一个分块做法,约莫是会被卡成暴力分的,所以就写了暴力。

正解是建立26棵线段树啦,维护区间每一个字母的个数,使用区间查询和区间赋值操作可以完成。注意几个优化:如果我要把一个区间赋值为1且当前区间已经全部是1,返回。如果我要把一个区间赋值为0且当前区间已经全部是0,返回。如果我要查询一个区间且当前区间全部是0,则查询值一定是0。输出时不要暴力判断,而是去每一棵线段树里跑一跑。

代码

T2

期望得分:20 实际得分:20

题目描述

求出满足以下条件的 n*m 的 01 矩阵个数:
(1) 第 i 行第 1~li 列恰好有 1 个 1。
(2) 第 i 行第 ri~m 列恰好有 1 个 1,li+1~ri-1列没有1。
(3) 每列至多有 1 个 1。

数据范围

对于 20%的数据,n,m $\leq$ 12。
对于 40%的数据,n,m $\leq$ 50。
对于 70%的数据,n,m $\leq $ 300。
对于 100%的数据,n,m $\leq$ 3000 , $1\leq l_i$<$r_i \leq$ m。

解题思路

20分当然是乱搜啦。

感谢xcc为我这个大蒟蒻的详细讲解,%%%xcc。

1.首先我们会发现左右区间在哪一列并没有什么区别。

2.我们需要定义一个l[i]和r[i],l[i]:在第i列及其左边有多少左区间端点,r[i]:在第i列及其左边有多少右区间端点。然后我们定义f(i,j):前i列的1有j个被放置在了右区间

3.假设现在我们求出了f(i,j),那么对于第i+1列,它有两种情况:要么上面的1在一个右区间,要么空出来不放,留给接下来的左区间或者干脆空着。

4.考虑放在一个右区间,则在前i+1列,还没有被放置一个1的右区间有r[i+1]-j个,所以f(i+1,j+1)+=f(i,j)*(r[i+1]-j)

5.考虑空着,f(i+1,j)+=f(i,j)

6.现在我们dp到了一个新的f(i,j),开始考虑左区间了。我们只需要考虑端点正好在i上的左区间(在i前的已经考虑过了,在i后的暂时不用考虑),那么这些端点在i上的左区间必须找一列获得它的1啦。前i列有多少列还空着呢?显然是i-j-l[i-1]。端点在第i列的左区间有多少呢?l[i]-l[i-1]

所以:f(i,j)*=A(l[i]-l[i-1],i-j-l[i-1])

A(x,y)表示从y个数里选x数的不同排列个数,公式我就略啦。

以及这题出题人的脑回路异于常人啊!!!!

代码

T3

期望得分:40 实际得分:40

题目描述

你需要在$[0,2^n)$中选一个整数 x,接着把 x 依次异或 m 个整数a1~am。
在你选出 x 后,你的对手需要选择恰好一个时刻(刚选完数时、异或一些数后或是最后),将 x 变为$(\lfloor \frac{2x}{2^n} \rfloor +2x) \bmod 2^n$
你想使 x 最后尽量大,而你的对手会使 x 最后尽量小。
你需要求出 x 最后的最大值,以及得到最大值的初值数量。

数据范围

对于 20%的数据,n $\leq$ 10,m $\leq$ 100。
对于 40%的数据,n $\leq$ 10,m $\leq$ 1000。
对于另外 20%的数据,n $\leq$ 30,m $\leq$ 10。
对于 100%的数据 n $\leq$ 30,m $\leq$ 100000,$0 \leq a_i$<$2^n$。

解题思路

40分嘛,由于异或具有结合律和交换律,所以我们可以预处理出m个数异或的前缀和和后缀和,然后枚举每一个数x,暴力瞎搞出答案。

感谢xcc为我这个大蒟蒻的详细讲解,%%%xcc。

首先$(\lfloor \frac{2x}{2^n} \rfloor +2x) \bmod 2^n$是什么呢?我们先看,$\lfloor \frac{2x}{2^n} \rfloor$=$\lfloor \frac{x}{2^{n-1}} \rfloor$,当$x \geq 2^{n-1} $的二进制取后n位,第1位一定为1.(比如n=2,则3的二进制是11,2的二进制是10)。否则第1位为0.然后$2x$显然是把x左移1位,再模一下$2^n$就是取后面n位。所以整个流程出来就是把x二进制下的第一位移到最后一位。

这说明了什么?原来x的取值范围是$[0,2^n)$,在被你的对手搞事之后的数取值范围还是$[0,2^n)$。

现在你的对手很心急,他决定在你异或i个数后再对你的x搞事,可是你还没开始异或他就要搞事了。怎么办?前i个数也只能做同样的操作(即将二进制下第一位移到最后一位),这样你在异或前i个数的时候二进制数位和搞事后的x是一一对应的。

我们令a[i]为异或的第i个数,b[i]为a[i]被搞事的结果。那么我们求出suf[i]为a的后缀异或和,pre[i]为b的前缀异或和。因为异或具有结合率和交换率,所以我们可以看作是你的x被搞事后异或上某个(pre[i]^suf[i+1]),这样的(pre[i]^suf[i+1])一共有m+1个。

我们以这m+1个数的二进制建立一棵trie树。然后dfs这棵trie树,如果某个节点有两个子节点:0和1,那么你开始选的(被搞事了的)x这一位无论是0还是1,你的对手都有选择的方法使这一位异或后变成0.但是如果这个节点只有一个子节点,那么聪明的你就可以做出选择,使得异或后这一位还是1,统计答案就变得easy啦!

当然了,trie树应该是每一个二进制数从前往后每一位去建立。因为你的对手想要让你选的数某一位异或后为0,一定先考虑前面的几位,再考虑后面的几位。(因为$\sum_{i=0}^n 2^i =2^{n+1}-1$(应该没写错吧?)

代码