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。输出时不要暴力判断，而是去每一棵线段树里跑一跑。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
const int N=100005;
int n,m;
int sum[26][N<<2],laz[26][N<<2],ans[N];
void pd(int o,int i,int s,int t){
    int l=i<<1,r=(i<<1)|1,mid=(s+t)>>1;
    laz[o][l]=laz[o][r]=laz[o][i];
    sum[o][l]=laz[o][i]*(mid-s+1);
    sum[o][r]=laz[o][i]*(t-mid);
    laz[o][i]=-1;
}
void add(int o,int l,int r,int s,int t,int i,int num){
    if(r<l)return;
    if(!num&&!sum[o][i])return;
    if(num&&sum[o][i]==t-s+1)return;//加速！加速！再加速！ 
    if(l<=s&&t<=r){laz[o][i]=num,sum[o][i]=num*(t-s+1);return;}
    int mid=(s+t)>>1;
    if(laz[o][i]!=-1)pd(o,i,s,t);
    if(l<=mid)add(o,l,r,s,mid,i<<1,num);
    if(mid+1<=r)add(o,l,r,mid+1,t,(i<<1)|1,num);
    sum[o][i]=sum[o][i<<1]+sum[o][(i<<1)|1];
}
int find(int o,int l,int r,int s,int t,int i){
    if(!sum[o][i])return 0;//注意要加上这个
    if(l<=s&&t<=r)return sum[o][i];
    int mid=(s+t)>>1,re=0;
    if(laz[o][i]!=-1)pd(o,i,s,t);
    if(l<=mid)re+=find(o,l,r,s,mid,i<<1);
    if(mid+1<=r)re+=find(o,l,r,mid+1,t,(i<<1)|1);
    return re;
}
void ask(int o,int s,int t,int i){
    if(!sum[o][i])return;
    if(s==t){ans[s]=o;return;}
    int mid=(s+t)>>1;
    if(laz[o][i]!=-1)pd(o,i,s,t);
    ask(o,s,mid,i<<1),ask(o,mid+1,t,(i<<1)|1);
}
char s[N];
int main(){
    freopen("string.in","r",stdin);
    freopen("string.out","w",stdout);
    int i,j,kl,js,x,y,bj;
    memset(laz,-1,sizeof(laz));
    n=read(),m=read();
    scanf("%s",s);
    for(i=0;i<n;++i)add(s[i]-'a',i+1,i+1,1,n,1,1);
    for(i=1;i<=m;++i){
        x=read(),y=read(),bj=read();
        if(bj==1)kl=x;
        else kl=y;
        for(j=0;j<=25;++j){
            js=find(j,x,y,1,n,1);
            if(bj==1){
                add(j,x,y,1,n,1,0),add(j,kl,kl+js-1,1,n,1,1);
                kl=kl+js;
            }
            else {
                add(j,x,y,1,n,1,0),add(j,kl-js+1,kl,1,n,1,1);
                kl=kl-js;
            }
        }
    }
    for(i=0;i<=25;++i)ask(i,1,n,1);
    for(i=1;i<=n;++i)putchar('a'+ans[i]);
    return 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 数的不同排列个数，公式我就略啦。

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

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define LL long long
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
const int N=3005;
LL mod=998244353;
int n,m;
LL f[N][N],l[N],r[N],jie[N],ni[N];
LL work(LL x,LL y){
    if(x>y)return 0;
    return jie[y]*ni[y-x]%mod;
}
LL ksm(LL x,LL y){
    LL re=1;
    while(y){
        if(y&1)re=re*x%mod;
        x=x*x%mod,y>>=1;
    }
    return re;
}
int main(){
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    int i,j,x,y;
    n=read(),m=read();
    jie[0]=1;for(i=1;i<=m;++i)jie[i]=jie[i-1]*i%mod;
    ni[m]=ksm(jie[m],mod-2);
    for(i=m-1;i>=0;--i)ni[i]=ni[i+1]*(i+1)%mod;
    for(i=1;i<=n;++i)x=read(),y=read(),++l[x],++r[y];
    for(i=1;i<=m;++i)l[i]=l[i-1]+l[i],r[i]=r[i-1]+r[i];
    f[0][0]=1;
    for(i=0;i<=m;++i)
        for(j=0;j<=i;++j){
        if(i)f[i][j]=f[i][j]*work(l[i]-l[i-1],i-j-l[i-1])%mod;
        f[i+1][j+1]+=f[i][j]*(r[i+1]-j)%mod,f[i+1][j]%=mod;
        f[i+1][j]+=f[i][j];f[i+1][j+1]%=mod;
    }
    printf("%lld",f[m][n]);
    return 0;
}

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$（应该没写错吧？）

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
const int N=100005;
int n,m,mx,ans1,ans2,cn;
int a[N],b[N],pre[N],suf[N],bin[33];
int tr[N*33][2];
void work(int x){
    int i,from=0,t;
    for(i=n;i>=1;--i){
        if(bin[i]&x)t=1;
        else t=0;
        if(tr[from][t])from=tr[from][t];
        else ++cn,tr[from][t]=cn,from=cn;
    }
}
void dfs(int x,int d,int num){
    if(tr[x][0]&&tr[x][1])
        dfs(tr[x][0],d-1,num),dfs(tr[x][1],d-1,num);
    else if(!tr[x][0]&&!tr[x][1]){
        if(num>ans1)ans1=num,ans2=1;
        else if(num==ans1)++ans2;
        return;
    }
    else if(tr[x][0])dfs(tr[x][0],d-1,num+bin[d-1]);
    else dfs(tr[x][1],d-1,num+bin[d-1]);
}
int main(){
    freopen("big.in","r",stdin);
    freopen("big.out","w",stdout);
    int i;
    n=read(),m=read();
    mx=1<<n;bin[1]=1;
    for(i=2;i<=n;++i)bin[i]=bin[i-1]<<1;
    for(i=1;i<=m;++i)a[i]=read(),b[i]=(2*a[i]/mx+2*a[i])%mx;
    for(i=1;i<=m;++i)pre[i]=pre[i-1]^b[i];
    for(i=m;i>=1;--i)suf[i]=suf[i+1]^a[i];
    for(i=0;i<=m;++i)work(pre[i]^suf[i+1]);
    dfs(0,n+1,0);printf("%d\n%d\n",ans1,ans2);
    return 0;
}