08-01 NOIP模拟测试11

时间:2021-12-20 09:11:38

期望得分:40+20+40

实际得分:40+10+36

A. string

很像莫队专题的排序那题,不少人用桶排卡过去了。因为那题只求一个位置,我打的二分,然而这题最后让你输出整个序列。

鱼和熊掌不可兼得,排序求单点才保住的复杂度,这题一定有另一个宽松的条件降低复杂度。那就是桶的大小只有26。

裸的桶排:每次[l,r]操作,进行一次[l,r]扫描并装桶,然后按照升序或降序倒在[l,r]上。复杂度$\Theta (mn)$

以上算法的瓶颈在于每一次拿或放一个字母,考虑如何优化。显然是个套路,我们如果用维护区间的数据结构来成段拿取就可以把n优化到logn,而这题线段树即可。

于是我们可以建26棵线段树维护1~n上每个区间的单个字母和(每个节点维护一个桶),然后你就愉快地拿到了MLE的好成绩

由于序列上每个位置只有单一字母,所以上面的做法整整浪费了25倍的空间。

所以我们可以只种一棵树,每个结点维护26个桶。

每次修改的区间一定是字符相同的段,所以直接memset盖掉重新赋值即可。对于没有完全覆盖的线段树上的一段,可以用up()保证信息完整。

08-01 NOIP模拟测试1108-01 NOIP模拟测试11
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define reg register
  5 #define F(i,a,b) for(register int (i)=(a);(i)<=(b);++(i))
  6 using namespace std;
  7 const int N=100005;
  8 int n,m;
  9 int lc[4*N],rc[4*N],w[4*N][27],f[4*N],bk[27];
 10 char s[N];
 11 int pt[N];
 12 void up(int k)
 13 {
 14     F(i,1,26) w[k][i]=w[k<<1][i]+w[k<<1|1][i];
 15 }
 16 void down(int k,int l,int r)
 17 {
 18     if(!f[k]) return;
 19     memset(w[k<<1],0,sizeof(w[k<<1]));
 20     memset(w[k<<1|1],0,sizeof(w[k<<1|1]));
 21     int o=f[k];
 22     int mid=(l+r)>>1;
 23     w[k<<1][o]=mid-l+1;
 24     w[k<<1|1][o]=r-mid;
 25     f[k<<1]=f[k<<1|1]=o;
 26     f[k]=0;
 27 }
 28 void build(int k,int l,int r)
 29 {
 30     if(l==r)
 31     {
 32         w[k][s[l]-'a'+1]=1;
 33         return;
 34     }
 35     int mid=(l+r)>>1;
 36     build(k<<1,l,mid);
 37     build(k<<1|1,mid+1,r);
 38     up(k);
 39 }
 40 void ch(int k,int l,int r,int L,int R,int c)
 41 {
 42     if(L>R) return;
 43     if(L<=l&&r<=R)
 44     {
 45         memset(w[k],0,sizeof(w[k]));
 46         w[k][c]=r-l+1;
 47         f[k]=c;
 48         return;
 49     }
 50     down(k,l,r);
 51     int mid=(l+r)>>1;
 52     if(L<=mid) ch(k<<1,l,mid,L,R,c);
 53     if(R>mid) ch(k<<1|1,mid+1,r,L,R,c);
 54     up(k);
 55 }
 56 void ak(int k,int l,int r,int L,int R)
 57 {
 58     if(L<=l&&r<=R)
 59     {
 60         F(i,1,26) bk[i]+=w[k][i];
 61         return;
 62     }
 63     down(k,l,r);
 64     int mid=(l+r)>>1;
 65     if(L<=mid) ak(k<<1,l,mid,L,R);
 66     if(R>mid) ak(k<<1|1,mid+1,r,L,R);
 67 }
 68 void dfs(int k,int l,int r)
 69 {
 70     if(l==r)
 71     {
 72         F(i,1,26)if(w[k][i]){pt[l]=i;return;}
 73         return;
 74     }
 75     down(k,l,r);
 76     int mid=(l+r)>>1;
 77     dfs(k<<1,l,mid);
 78     dfs(k<<1|1,mid+1,r);
 79 }
 80 int main()
 81 {
 82 //    freopen("data.in","r",stdin);
 83     scanf("%d %d",&n,&m);
 84     scanf("%s",s+1);
 85     build(1,1,n);
 86     int l,r,x;
 87     F(i,1,m)
 88     {
 89         memset(bk,0,sizeof(bk));
 90         scanf("%d %d %d",&l,&r,&x);
 91         ak(1,1,n,l,r);
 92         if(x)
 93         {
 94             F(i,1,26)
 95             {
 96                 if(!bk[i]) continue;
 97                 ch(1,1,n,l,l+bk[i]-1,i);
 98                 l+=bk[i];
 99             }
100         }
101         else
102         {
103             for(reg int i=26;i>=1;--i)
104             {
105                 if(!bk[i]) continue;
106                 ch(1,1,n,l,l+bk[i]-1,i);
107                 l+=bk[i];
108             }
109         }
110     }
111     dfs(1,1,n);
112     F(i,1,n) printf("%c",pt[i]+'a'-1);
113     return 0;
114 }
View Code

 

 

B. matrix

考试的适合打了个95w的clock()暴力卡了我10分。所以说clock()不要在大递归函数里用!

说正解:一个定义清奇的dp

dp[i][j]表示前i列在j个i列及i列前的右区间内放1的方案数。

定义l[i],r[i]为i列的左区间右区间端点的自左向右的前缀和。

循环枚举i,j

 $ dp[i][j]=dp[i][j] \times A_{i-j-l[i-1]}^{l[i]-l[i-1]} \\ dp[i+1][j]+=dp[i][j] \\ dp[i+1][j+1]+=dp[i][j] \times (r[i+1]-j) $

对于第一个柿子:那么到了i列,j个,当前列需要考虑l[i]-l[i-1]个右端点,左侧有i-j-l[i-1]个还能放的位置,由于有位置差别,是排列。更详细的

第二个:不在右区间放1,直接转移

第三个:在i+1列放一个,从r[i+1]-j里选一个。

这个dp好玄学啊。

但比较有启发性的一点在于对于限制过多的计数类dp,我们只考虑其中较少的部分,然后通过计算得到可以和这部分一起形成贡献的部分。类似的有visit和liu_runda的题(problem),枚举一个方向,减少了状态的枚举。这题的dp定义也是这种思想。

08-01 NOIP模拟测试1108-01 NOIP模拟测试11
 1 #include<cstdio>
 2 #include<ctime>
 3 #include<algorithm>
 4 #define ll long long
 5 #define reg register
 6 #define F(i,a,b) for(register int (i)=(a);(i)<=(b);++(i))
 7 using namespace std;
 8 const int N=3005,p=998244353;
 9 int n,m;
10 int l[N],r[N];
11 ll fac[N],inv[N];
12 ll dp[N][N];
13 ll qpow(ll x,ll b)
14 {
15     ll ans=1;
16     while(b)
17     {
18         if(b&1) ans=(ans*x)%p;
19         x=(x*x)%p;
20         b>>=1;
21     }
22     return ans;
23 }
24 void pre_work()
25 {
26     fac[0]=1;
27     F(i,1,m) fac[i]=fac[i-1]*i%p;
28     inv[m]=qpow(fac[m],p-2);
29     for(reg int i=m-1;i>=0;--i) inv[i]=inv[i+1]*(i+1)%p;
30 }
31 inline ll A(int n,int m)
32 {
33     return fac[n]*inv[n-m]%p;
34 }
35 int main()
36 {
37     scanf("%d %d",&n,&m);
38     pre_work();
39     F(i,1,n)
40     {
41         int a,b;
42         scanf("%d %d",&a,&b);
43         ++l[a]; ++r[b];
44     }
45     F(i,1,m) l[i]+=l[i-1],r[i]+=r[i-1];
46     dp[1][0]=1;
47     F(i,1,m-1)
48     {
49         F(j,0,r[i])
50         {
51             int t1=i-j-l[i-1],t2=l[i]-l[i-1];
52             if(t1<t2) break;
53             dp[i][j]=dp[i][j]*A(t1,t2)%p;
54             dp[i+1][j]=(dp[i+1][j]+dp[i][j])%p;
55             dp[i+1][j+1]=(dp[i+1][j+1]+dp[i][j]*(r[i+1]-j)%p)%p;
56         }
57     }
58     printf("%lld",dp[m][n]);
59     return 0;
60 }
View Code

 

C. big

并没有想到下面这个性质:

$ (|\frac {2x} {2^n}|+2x) mod2^n $ 这个看起来很复杂的东西其实就是循环左移(左移,溢出位补到低位),那个向下取整就是溢出补低位,类似高精度。

区分下这些位运算

异或满足交换律、结合律,所以我们把x提出来。

$ ((x\ xor\ pre[i])<<1)\ xor\ suf[i+1] \\ (x<<1\ xor\ pre[i]<<1)\ xor\ suf[i+1] \\ num_i=pre[i]<<1\ xor\ suf[i+1] $

由于异或的时刻不同,一共有m+1个数

那么问题转化为:找出一个x使x异或m+1个数得到的最小值最大。

建出01-Trie,贪心。

假设到了节点p,如果p有两个儿子,那么对手一定可以选到一个num使该位xor=0。

如果p有一个儿子,当然要选对手没有的,即取反。

如果p没有儿子,计算答案。

这题把dep弄反了改了半天...

08-01 NOIP模拟测试1108-01 NOIP模拟测试11
 1 #include<cstdio>
 2 #include<ctime>
 3 #include<algorithm>
 4 #define ll long long
 5 #define reg register
 6 #define F(i,a,b) for(register int (i)=(a);(i)<=(b);++(i))
 7 using namespace std;
 8 int n,m;
 9 int mx,mx_cnt;
10 int a[100005],sum[100005];
11 struct Trie{
12     Trie *ch[2];
13     int dep;
14 };
15 Trie* newnode(int dep)
16 {
17     Trie *p=new Trie;
18     p->ch[0]=p->ch[1]=NULL;
19     p->dep=dep;
20     return p;
21 }
22 void add(Trie *root,int num)
23 {
24     Trie *p=root;
25     for(reg int i=n-1;i>=0;--i)
26     {
27         int x=(num>>i)&1;
28         if(p->ch[x]==NULL) p->ch[x]=newnode(p->dep-1);
29         p=p->ch[x];
30     }
31 }
32 void dfs(Trie *p,int w)
33 {
34     if(p->ch[0]!=NULL&&p->ch[1]!=NULL)
35     {
36         dfs(p->ch[0],w);
37         dfs(p->ch[1],w);
38     }
39     else if(p->ch[0]!=NULL) dfs(p->ch[0],w|(1<<(p->ch[0]->dep)));
40     else if(p->ch[1]!=NULL) dfs(p->ch[1],w|(1<<(p->ch[1]->dep)));
41     else
42     {
43         if(mx==w) ++mx_cnt;
44         else if(mx<w)
45         {
46             mx=w;
47             mx_cnt=1;
48         }
49     }
50 }
51 int main()
52 {
53     scanf("%d %d",&n,&m);
54     F(i,1,m)
55     {
56         scanf("%d",&a[i]);
57         sum[i]=sum[i-1]^a[i];
58     }
59     Trie *root=newnode(n);
60     F(i,0,m)
61     {
62         int suf=sum[m]^sum[i];
63         add(root,((((sum[i]<<1)/(1<<n))+(sum[i]<<1))%(1<<n))^suf);
64     }
65     dfs(root,0);
66     printf("%d\n%d",mx,mx_cnt);
67     return 0;
68 }
View Code

 

 

 

 

强迫症又严重了唔...