8.1 NOIP模拟11

8.1 NOIP模拟 11

今天上午返校之后，颓了一会，然后下午就开始考试，中午睡着了，然后刚开始考试的时候就困的一匹，我一看T1，woc，这不是之前线段树专题的题啊，和那道题差不多，所以我......想起来了，我当时没有做，完了，这就是之前坑哇的太大的缘故。我的内心当时就在滴血，心想推正解还不如先打个暴力，然后愉快的5分钟吗了一个暴力，整个就是俩sort，又花了五分钟改成了桶排，然后就愉快的交上去了，然后我T1还是没有思路，就15分钟的时候转了T2，T2一看就开始推组合数的柿子，但是由于我的误判成数学题，就完犊子了，那还等啥，一看20%的数据，就果断摔了一个dfs上去，然后就转T3，（此时内心虚的一批），T3一看，先想了一个啥都没有的暴力，然后又想到了前缀和优化，就优化一下，自己有造了几个极限数据，发现20%和40%应该都能过（当时心花怒放，但是其实60是不存在的），然后开考50分钟，打完了三个暴力，就歇菜了，剩下的时间就开始刚正解，最后的提交我也是挂着暴力交上去的，所以最后我的分数并没有因为我的覆盖而降低，但是也没有因为我的“正解”而分数增高，刚考完我就知道我这次凉凉，只打了3个暴力，肯定又垫底了，但是竟然还有暴力都没打对的大佬然后，我就和13个同学并列rank7，100分，虽然rank7，但是这是在别人失误的情况下得的，所以如果别人都没失误，那我这次就又垫底了，所以这次还是失败的考试。

T1 string

这这，一看就是之前学长讲过的那道用线段树维护的题，好像还带了二分，但是仔细一看略有不同，之前的那个是指询问地q个数，而这个是询问整个结果，所以我就（缨缨婴）只能打暴力，但是好像全场都没几个打正解的。在下面改题的过程中我就想到了一种奇爬的方法，就是维护一个每个字母出现次数的前缀和，然后通过一系列操作实现对字符串的变化，但是时间复杂度是$ O(n*m*26) $交上去T40，和我的暴力跑的时间一样，然后我就想怎么优化，有这么一种思路，就是我把前缀和的图像画在了之上，然后发现他是单调上升函数（这不是废话吗！），那么我就想到使用链表吧图像的拐点存下来，这样就可以知道了一些信息，而且可以 $ O(1) $计算出一些信息，但是需要 $ O(m*26) $的复杂度进行转移，所以应该比正解跑的还要快，但是男就难在了这个思路不好实现，所以我还是老老实实的打了线段树，最后还是没有忍住话了一点时间打了一下，发现确实很难条，我就暂且哇个坑，有神犇愿意为我条一下的也可以，后来我看cbx的T1快到飞起，其实他的思路和我的这个思路是一样的，就不赘述了;

我的T40暴力代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<cstdlib>
 6 #include<algorithm>
 7 using namespace std;
 8 int read()
 9 {
10     int x=0,f=1;char cc;cc=getchar();
11     while(cc>'9'||cc<'0'){if(cc=='-')f=-1;cc=getchar();}
12     while(cc>='0'&&cc<='9'){x=(x<<3)+(x<<1)+cc-'0';cc=getchar();}
13     return x*f;
14 }
15 char s[100005];
16 int n,m,l,r,x;
17 inline bool cmp1(char a,char b){return a<b;}
18 inline bool cmp2(char a,char b){return a>b;}
19 int main()
20 {
21     //freopen("cnm.txt","r",stdin);
22     n=read();m=read();
23     scanf("%s",s+1);
24     for(int i=1;i<=m;i++)
25     {
26         l=read(),r=read(),x=read();
27         if(x==1)sort(s+l,s+r+1,cmp1);
28         else sort(s+l,s+r+1,cmp2);
29     }
30     for(int i=1;i<=n;i++)
31     printf("%c",s[i]);
32     puts("");
33     return 0;
34 }

T40

我的AC线段树代码：

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<cstdlib>
  5 #include<algorithm>
  6 const int maxn=100005;
  7 using namespace std;
  8 #define re register
  9 #define debug(x) cout<<x<<" debug!"<<endl;
 10 inline int read()
 11 {
 12     re int x=0,f=1;char cc;cc=getchar();
 13     while(cc>'9'||cc<'0'){if(cc=='-')f=-1;cc=getchar();}
 14     while(cc>='0'&&cc<='9'){x=(x<<3)+(x<<1)+cc-'0';cc=getchar();}
 15     return x*f;
 16 }
 17 int m,n,k,t,sum[27];
 18 char s[maxn];
 19 struct tree{    
 20     int l,r,vv,lev;    
 21 }tr[maxn<<2];
 22 inline void pushup(int x)
 23 {
 24     if(tr[x<<1].vv==tr[x<<1|1].vv) 
 25         tr[x].vv=tr[x<<1].vv;
 26     else tr[x].vv=-1;
 27 }
 28 inline void pushdown(int x)
 29 {
 30     if(tr[x].vv!=-1) 
 31         tr[x<<1].vv=tr[x<<1|1].vv=tr[x].vv;
 32     else tr[x].vv=-1;
 33 }
 34 inline void build(int x,int l,int r)
 35 {
 36     tr[x].l=l, tr[x].r=r; 
 37         tr[x].vv=-1;
 38     if(tr[x].l==tr[x].r)
 39     {    
 40         tr[x].vv=s[l]-'a'; 
 41         return;    
 42     }
 43     int mid=(tr[x].l+tr[x].r)>>1;
 44     build(x<<1,l,mid); build(x<<1|1,mid+1,r);
 45     pushup(x);
 46 }    
 47 inline void query(int x)
 48 {
 49     if(tr[x].vv!=-1)
 50     {
 51         for(register int i=1;i<=tr[x].r-tr[x].l+1;++i)
 52             putchar(tr[x].vv+'a');
 53            return;
 54     }
 55     query(x<<1);
 56     query(x<<1|1);
 57 }    
 58 inline void make(int x,int l,int r)
 59 {
 60     if(l<=tr[x].l&&tr[x].r<=r)
 61     {
 62         if(tr[x].vv!=-1)
 63         {
 64             sum[tr[x].vv]+=tr[x].r-tr[x].l+1; 
 65             return;
 66          }
 67     }
 68     pushdown(x);
 69     int mid=(tr[x].l+tr[x].r)>>1;
 70     if(l<=mid)make(x<<1,l,r);
 71     if(mid+1<=r)make(x<<1|1,l,r);
 72 }
 73 inline void change(int x,int l,int r,int vv)
 74 {
 75     if(l>r) return;
 76     if(l<=tr[x].l&&tr[x].r<=r)
 77     {    
 78         tr[x].vv=vv; 
 79         return;    
 80     } 
 81     int mid=(tr[x].l+tr[x].r)>>1;
 82     if(l<=mid)change(x<<1,l,r,vv);
 83     if(mid+1<=r)change(x<<1|1,l,r,vv);
 84     pushup(x);
 85 }
 86 int main()
 87 {
 88     //freopen("1.txt","r",stdin);
 89     n=read(),m=read();
 90     scanf("%s",s+1); 
 91     build(1,1,n);
 92     while(m--)
 93     {
 94         memset(sum,0,sizeof(sum));
 95         int l,r,x;
 96         scanf("%d%d%d",&l,&r,&x);
 97         make(1,l,r);
 98         if(x==1)
 99         {
100             int L=l;
101             for(register int i=0;i<26;++i)
102             {
103                 change(1,L,L+sum[i]-1,i);
104                 L+=sum[i];
105             }
106         }
107         if(x==0)
108         {
109             int L=l;
110             for(register int i=25;i>=0;--i)
111             {
112                 change(1,L,L+sum[i]-1,i);
113                 L+=sum[i];
114             }
115         }
116     }
117     query(1);
118     puts("");
119 }

还有cbx的代码就不放了，本人懒得征求版权了！

T2 Matrix

这到题是本人感觉正常最难的题，虽然看起来像组合数学（而且我也是按组合数学打的，但是并不是）

这是题解，其实就是一个贼神仙的dp，由于时间限制以及任务繁多，本人扔下代码就跑：

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 #define LL long long
 5 #define re register
 6 inline LL read()
 7 {
 8     re LL x=0,f=1;char cc;cc=getchar();
 9     while(cc>'9'||cc<'0'){if(cc=='-')f=-1;cc=getchar();}
10     while(cc>='0'&&cc<='9'){x=(x<<3)+(x<<1)+cc-'0';cc=getchar();}
11     return x*f;
12 }
13 const LL p=998244353;
14 LL n,m,dp[3005][3005],pw[3005],inv[3005],ipw[3005],l[3005],r[3005];
15 int main()
16 {
17     n=read(),m=read();
18     for(re LL i=1;i<=n;++i)++l[read()],++r[read()];
19     for(re LL i=1;i<=m;++i)l[i]+=l[i-1],r[i]+=r[i-1];
20     dp[0][0]=1;
21     for(re LL i=1;i<=m;++i)
22     {    
23         dp[i][0]=dp[i-1][0];
24         for(re LL j=1;j<=r[i];++j)
25             dp[i][j]=(dp[i-1][j]+dp[i-1][j-1]*(r[i]-j+1)%p)%p;
26         for(re LL j=l[i-1];j<l[i];++j)
27             for(re LL k=0;k<=i-j;++k) 
28                 dp[i][k]=dp[i][k]*(i-k-j)%p;
29     }
30     printf("%lld
",dp[m][n]);
31 }

T3 big

本人也是先哇下坑，先沽了;

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define LL long long
 6 #define re register
 7 LL ch[4000005][2],tot;
 8 LL num[10000005],n,m;
 9 LL ans,cnt,sum,pre[1000005],x;
10 LL head[300005],nxt[300005],ver[300005],tot2,vvt[300005];
11 const int pc=29987;
12 inline LL read()
13 {
14     re LL x=0,f=1;char cc;cc=getchar();
15     while(cc>'9'||cc<'0'){if(cc=='-')f=-1;cc=getchar();}
16     while(cc>='0'&&cc<='9'){x=(x<<3)+(x<<1)+cc-'0';cc=getchar();}
17     return x*f;
18 }
19 void inser(LL x)
20 {
21     LL h=x%pc;
22     for(int i=head[h];i;i=nxt[i])
23         if(ver[i]==x)++vvt[i];
24     ver[++tot2]=x;
25     nxt[tot2]=head[h];
26     head[h]=tot2;
27     vvt[tot2]++;
28 }
29 LL query(LL x)
30 {
31     LL h=x%pc;
32     LL op=0;
33     for(int i=head[h];i;i=nxt[i])
34         if(ver[i]==x)
35             op=vvt[i];
36     return op;
37 }
38 LL insert(LL x)
39 {
40      LL u=0,wc=0,xx=x;
41      for(register int i=n-1;i>=0;--i)
42      {
43          wc=(xx&(1<<i))?1:0;
44          if(!ch[u][wc]) 
45              ch[u][wc]=++tot;
46          u=ch[u][wc];
47      }
48 }
49 inline void dfs(int x,int dep,int sum)
50 {
51      if(dep==-1)
52      {
53          if(sum>=ans) ans=sum,inser(ans);
54          return;
55      }
56      if(!ch[x][0]) dfs(ch[x][1],dep-1,sum^(1<<dep));
57      if(!ch[x][1]) dfs(ch[x][0],dep-1,sum^(1<<dep));
58      if(ch[x][0]&&ch[x][1])
59      {
60          dfs(ch[x][0],dep-1,sum);
61          dfs(ch[x][1],dep-1,sum);
62      }
63  }
64 int main()
65 {
66      n=read(),m=read();
67      for(register int i=1;i<=m;++i) 
68          x=read(),pre[i]=pre[i-1]^x;    
69      for(register int i=0,x;i<=m;++i)
70      {
71          x=((2*pre[i])/(1<<n)+2*pre[i])%(1<<n);
72          insert(x^pre[i]^pre[m]);
73      }
74      dfs(0,n-1,0);
75      LL uu=query(ans);
76      printf("%lld
%lld
",ans,uu);
77 }