2019 计蒜之道复赛

外教 Michale 变身大熊猫

https://nanti.jisuanke.com/t/39611

way1.

对不同长度的lis建一颗线段树，用动态开点。

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cstring>
  4 #include <string>
  5 #include <cmath>
  6 #include <algorithm>
  7 #include <iostream>
  8 using namespace std;
  9 #define ll long long
 10 #include <vector>
 11 
 12 const int maxn=5e5+10;
 13 const ll mod=998244353;
 14 
 15 int a[maxn],b[maxn];
 16 
 17 struct node
 18 {
 19     int l,r;
 20     ll sum;
 21 }tr[maxn*30];///可离散化把范围从1e9变为5e5(n)
 22 int be[maxn],num,maxg=5e5,maxv=1e9;
 23 
 24 ll tot[maxn],tot1[maxn],x[maxn],y[maxn],x1[maxn],y11[maxn];
 25 
 26 ll query(int ind,int l,int r,int x,int y)
 27 {
 28     if (x<=l && r<=y)
 29         return tr[ind].sum;
 30     int m=(l+r)>>1;
 31     ll sum=0;
 32     if (x<=m && tr[ind].l)
 33         sum=(sum+query(tr[ind].l,l,m,x,y))%mod;
 34     if (m<y && tr[ind].r)
 35         sum=(sum+query(tr[ind].r,m+1,r,x,y))%mod;
 36     return sum;
 37 }
 38 
 39 void update(int ind,int l,int r,int y,ll z)
 40 {
 41     if (l==r)
 42     {
 43         tr[ind].sum=(tr[ind].sum+z)%mod;
 44         return;
 45     }
 46     int m=(l+r)>>1;
 47     if (y<=m)
 48     {
 49         if (!tr[ind].l)
 50             tr[ind].l=++num;
 51         update(tr[ind].l,l,m,y,z);
 52     }
 53     else
 54     {
 55         if (!tr[ind].r)
 56             tr[ind].r=++num;
 57         update(tr[ind].r,m+1,r,y,z);
 58     }
 59     tr[ind].sum=(tr[tr[ind].l].sum + tr[tr[ind].r].sum)%mod;
 60 }
 61 
 62 ll mul(ll a,ll b)
 63 {
 64     ll y=1;
 65     while (b)
 66     {
 67         if (b & 1)
 68             y=y*a%mod;
 69         a=a*a%mod;
 70         b>>=1;
 71     }
 72     return y;
 73 }
 74 
 75 int main()
 76 {
 77     int n,i,j,l,r,m;
 78     ll v;
 79     scanf("%d",&n);
 80     for (i=1;i<=n;i++)
 81         scanf("%d",&a[i]);
 82 
 83     for (i=1;i<=maxg;i++)
 84         be[i]=++num;
 85 
 86     j=0;
 87     for (i=1;i<=n;i++)
 88     {
 89         l=1,r=j;
 90         while (l<=r)
 91         {
 92             m=(l+r)>>1;
 93             if (a[i]<=b[m])
 94                 r=m-1;
 95             else
 96                 l=m+1;
 97         }
 98         b[l]=a[i];
 99         if (l>j)
100             j++;
101 
102         ///all >0
103         if (l==1)
104             v=1;
105         else
106             v=query(be[l-1],1,maxv,1,b[l]-1);
107         update(be[l],1,maxv,b[l],v);
108         tot[l]=(tot[l]+v)%mod;
109         x[i]=l;
110         y[i]=v;
111     }
112 //    printf("%lld",tot[j]);    ///求强制lis
113 
114 
115     ///reverse
116 
117     for (i=1;i<=num;i++)
118         tr[i].l=0,tr[i].r=0,tr[i].sum=0;
119     num=0;
120 
121     for (i=1;i<=maxg;i++)
122         be[i]=++num;
123 
124     j=0;
125     for (i=n;i>=1;i--)
126     {
127         l=1,r=j;
128         while (l<=r)
129         {
130             m=(l+r)>>1;
131             if (a[i]>=b[m])
132                 r=m-1;
133             else
134                 l=m+1;
135         }
136         b[l]=a[i];
137         if (l>j)
138             j++;
139 
140         ///all >0
141         if (l==1)
142             v=1;
143         else
144             v=query(be[l-1],1,maxv,b[l]+1,maxv);
145         update(be[l],1,maxv,b[l],v);
146 //        tot1[l]=(tot1[l]+v)%mod;
147         x1[i]=l;
148         y11[i]=v;
149     }
150 
151     ll chu=mul(tot[j],mod-2);
152 
153     for (i=1;i<=n;i++)
154     {
155         if (i!=1)
156             printf(" ");
157         if (x[i]+x1[i]==j+1)
158         {
159             y[i]=y[i]*y11[i]%mod;
160             printf("%lld",y[i]*chu%mod);
161         }
162         else
163             printf("0");
164     }
165     return 0;
166 }
167 /*
168 8
169 6 5 6 7 1 2 2 3
170 */

way2.

study from solution&群友

树状数组。

对于树状数组的f[x]，它统计若干个数(加lowbit到达x的所有数)作为结尾的子序列为最大时的值和对应的数量，

对于数字x是否会被f[x]一同统计的其它数(xx=x-lowbit(x),xxx=xx-lowbit(xx),...)覆盖，影响数字x作为最长子序列的一员，答案是不会。因为f[x]一同统计的其它数小于x，若以x为结尾的子序列为最大时的值小于这些数为结尾的子序列为最大时的值时，对于大于x的数，它选择衔接f[x]一同统计的某个其它数，子序列的数目必优于衔接x时的子序列的数目。

e.g. 8 1 7 9

对于f[x]一同统计的其它数是否会被数字x覆盖，影响f[x]一同统计的其它数作为最长子序列的一员，答案是不会。数字x是最新出现的，它衔接之前以小于x的数为结尾的子序列，f[x]一同统计的其它数(它们都小于x)为结尾的子序列必然不再是最长子序列，它们的结果被覆盖。对于位置在数字x之后的数，只有小于等于x的数y，衔接f[x]一同统计的其它数为结尾的子序列，才有可能与当前最长子序列的长度齐平，而对于y，它统计以[1,y-1]为结尾的子序列为最大时的值和对应的数量，x>=y-1，必然不会用到f[x]。

e.g. 7 8 8

感觉好拗口，实在是想不明白大佬们怎么想到会用树状数组做的。

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <string>
  6 #include <algorithm>
  7 #include <iostream>
  8 using namespace std;
  9 #define ll long long
 10 
 11 const double eps=1e-8;
 12 const ll inf=1e9;
 13 const ll mod=998244353;
 14 const int maxn=5e5+10;
 15 
 16 struct node
 17 {
 18     int x;
 19     ll y;
 20 }f[maxn],f1[maxn],be[maxn],en[maxn];
 21 
 22 struct rec
 23 {
 24     int x,y;
 25     bool operator<(const rec &b) const
 26     {
 27         return x<b.x;
 28     }
 29 }b[maxn];
 30 
 31 int a[maxn];
 32 
 33 ll mul(ll a,ll b)
 34 {
 35     ll y=1;
 36     while (b)
 37     {
 38         if (b & 1)
 39             y=y*a%mod;
 40         a=a*a%mod;
 41         b>>=1;
 42     }
 43     return y;
 44 }
 45 
 46 int main()
 47 {
 48     int n,m=0,i,j,k,maxsiz=0;
 49     ll l,tot=0;
 50     scanf("%d",&n);
 51     for (i=1;i<=n;i++)
 52     {
 53         scanf("%d",&b[i].x);
 54         b[i].y=i;
 55     }
 56     sort(b+1,b+n+1);
 57     b[0].x=b[1].x-1;
 58     for (i=1;i<=n;i++)
 59     {
 60         if (b[i].x!=b[i-1].x)
 61             m++;
 62         a[b[i].y]=m;
 63     }
 64 
 65     for (i=1;i<=n;i++)
 66     {
 67         j=a[i]-1;
 68         k=0,l=0;
 69         while (j>=1)
 70         {
 71             if (k<f[j].x)
 72                 k=f[j].x,l=f[j].y;
 73             else if (k==f[j].x)
 74                 (l+=f[j].y)%=mod;
 75             j-=j&-j;
 76         }
 77         if (k==0)
 78             l++;
 79         k++;
 80         be[i]={k,l};
 81 
 82         if (k==maxsiz)
 83             (tot+=l)%=mod;
 84         else if (k>maxsiz)
 85             maxsiz=max(maxsiz,k),tot=l;
 86         j=a[i];
 87         while (j<=m)
 88         {
 89             if (k>f[j].x)
 90                 f[j].x=k,f[j].y=l;
 91             else if (k==f[j].x)
 92                 (f[j].y+=l)%=mod;
 93             j+=j&-j;
 94         }
 95     }
 96 
 97     for (i=n;i>=1;i--)
 98     {
 99         a[i]=m+1-a[i];
100         j=a[i]-1;
101         k=0,l=0;
102         while (j>=1)
103         {
104             if (k<f1[j].x)
105                 k=f1[j].x,l=f1[j].y;
106             else if (k==f1[j].x)
107                 (l+=f1[j].y)%=mod;
108             j-=j&-j;
109         }
110         if (k==0)
111             l++;
112         k++;
113         en[i]={k,l};
114 
115         j=a[i];
116         while (j<=m)
117         {
118             if (k>f1[j].x)
119                 f1[j].x=k,f1[j].y=l;
120             else if (k==f1[j].x)
121                 (f1[j].y+=l)%=mod;
122             j+=j&-j;
123         }
124     }
125 
126     for (i=1;i<=n;i++)
127         if (be[i].x+en[i].x==maxsiz+1)
128             printf("%lld%c",be[i].y*en[i].y%mod*mul(tot,mod-2)%mod,(i==n)?'
':' ');
129         else
130             printf("0%c",(i==n)?'
':' ');
131     return 0;
132 }
133 /*
134 6
135 1 4 3 2 1 2
136 
137 8
138 6 5 6 7 1 2 2 3
139 
140 5
141 2 5 4 1 3
142 */

“星云系统”

https://nanti.jisuanke.com/t/39614

way1.单调栈

每个字符最多被加入和删除一次

119ms

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <string>
 5 #include <cmath>
 6 #include <algorithm>
 7 #include <iostream>
 8 using namespace std;
 9 #define ll long long
10 
11 const int maxn=5e6+10;
12 
13 char str[maxn],p[maxn];
14 int st[maxn];
15 
16 int main()
17 {
18     int g,len,i,j,k;
19     scanf("%s%d",str,&g);
20     len=strlen(str);
21     j=0;
22     for (i=0;i<len;i++)
23     {
24         k=max(g-len+i,0);
25         while (j>k && str[i]<p[j-1])
26             j--;
27         p[j++]=str[i];
28     }
29     p[g]=0;
30     printf("%s",p);
31     return 0;
32 }

way2. 二分

一个数插入到s[i]-s[j]的哪个位置

时间复杂度为log(1)+log(2)+...+log(5e5)，远没想象中大，大概一千万。

213ms

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <string>
 5 #include <cmath>
 6 #include <algorithm>
 7 #include <iostream>
 8 using namespace std;
 9 #define ll long long
10 
11 const int maxn=5e6+10;
12 
13 char str[maxn],p[maxn],c;
14 
15 int main()
16 {
17     int g,len,x=1,y=0,l,r,m,i;
18     scanf("%s%d",str,&g);
19     len=strlen(str);
20     for (i=0;i<len;i++)
21     {
22         if (len-i<g)
23             x++;
24         c=str[i];
25         l=x,r=y;
26         while (l<=r)
27         {
28             m=(l+r)>>1;
29             if (c>=p[m])
30                 l=m+1;
31             else
32                 r=m-1;
33         }
34         if (r==g+1)
35             continue;
36 
37         if (x>y)
38             r=x;
39         else if (r<x || c>=p[r])
40             r++;
41         y=r;
42         p[r]=str[i];
43     }
44     p[g+1]=0;
45     printf("%s",p+1);
46     return 0;
47 }
48 /*
49 abcdef
50 5
51 
52 bbcaaew
53 5
54 
55 fffffaf
56 5
57 
58 dbccca
59 5
60 
61 azzz
62 4
63 
64 d
65 1
66 
67 dc
68 2
69 
70 aaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbb
71 25
72 
73 zddddddddddddddadfasf
74 10
75 */

way3.序列自动机

study from 群友

对于目标子序列的每一位，找一个满足后续操作的最小的字符

O(26N) 1.3e8

但实际上，

579ms，说明要么测试数据规模小，要么评测机快。。。

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <string>
 6 #include <algorithm>
 7 #include <iostream>
 8 using namespace std;
 9 #define ll long long
10 
11 const double eps=1e-8;
12 const ll inf=1e9;
13 const ll mod=1e9+7;
14 const int maxn=5e6+10;
15 
16 char str[maxn];
17 int w[26],g[26];
18 vector<int> nex[26];
19 
20 int main()
21 {
22     int len,G,i,j,pos;
23     scanf("%s",str);
24     len=strlen(str);
25     for (i=0;i<len;i++)
26     {
27         j=str[i]-97;
28         g[j]++;
29         nex[j].push_back(i);
30     }
31     scanf("%d",&G);
32     for (i=0;i<26;i++)
33         w[i]=0;///
34 
35     pos=0;
36     while (G--)
37     {
38         for (i=0;i<26;i++)
39         {
40             while (w[i]!=g[i] && nex[i][w[i]]<pos)
41                 w[i]++;
42             if (w[i]!=g[i] && len-nex[i][w[i]]>=G+1)
43                 break;
44         }
45         pos=nex[i][w[i]]+1;
46         w[i]++;
47         printf("%c",i+97);
48     }
49     return 0;
50 }

其中可以写成nex的形式，就可以不用vector了。

一个优化的方法，却跑了更长的时间(估计跟获取vector数据慢有关)

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <string>
 6 #include <algorithm>
 7 #include <iostream>
 8 using namespace std;
 9 #define ll long long
10 
11 const double eps=1e-8;
12 const ll inf=1e9;
13 const ll mod=1e9+7;
14 const int maxn=5e6+10;
15 
16 char str[maxn];
17 int w[26],g[26];
18 vector<int> nex[26];
19 
20 int main()
21 {
22     int len,G,i,j,pos,v;
23     bool vis;
24     scanf("%s",str);
25     len=strlen(str);
26     for (i=0;i<len;i++)
27     {
28         j=str[i]-97;
29         g[j]++;
30         nex[j].push_back(i);
31     }
32     scanf("%d",&G);
33     for (i=0;i<26;i++)
34         w[i]=0;///
35 
36     pos=0;
37     while (G)
38     {
39         v=inf;
40         for (i=0;i<26;i++)
41         {
42             vis=0;
43             while (w[i]!=g[i] && nex[i][w[i]]<pos)
44                 w[i]++;
45             while (w[i]!=g[i] && len-nex[i][w[i]]>=G && nex[i][w[i]]<v)
46             {
47                 G--;
48                 pos=nex[i][w[i]]+1;
49                 w[i]++;
50                 vis=1;
51                 break;
52             }
53             if (vis)
54                 break;
55             if (w[i]!=g[i])
56                 v=min(v,nex[i][w[i]]);
57         }
58         printf("%c",i+97);
59     }
60     return 0;
61 }

内存超限的代码(然后改为用vector)

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <string>
 6 #include <algorithm>
 7 #include <iostream>
 8 using namespace std;
 9 #define ll long long
10 
11 const double eps=1e-8;
12 const ll inf=1e9;
13 const ll mod=1e9+7;
14 const int maxn=5e6+10;
15 
16 char str[maxn];
17 int nex[26][maxn],w[26];
18 
19 int main()
20 {
21     int len,g,i,j,pos;
22     scanf("%s",str);
23     len=strlen(str);
24     for (i=0;i<len;i++)
25     {
26         j=str[i]-97;
27         nex[j][0]++;
28         nex[j][nex[j][0]]=i;
29     }
30     scanf("%d",&g);
31     for (i=0;i<26;i++)
32         w[i]=1;
33 
34     pos=0;
35     while (g--)
36     {
37         for (i=0;i<26;i++)
38         {
39             while (w[i]!=nex[i][0]+1 && nex[i][w[i]]<pos)
40                 w[i]++;
41             if (w[i]!=nex[i][0]+1 && len-nex[i][w[i]]>=g+1)
42                 break;
43         }
44         pos=nex[i][w[i]]+1;
45         w[i]++;
46         printf("%c",i+97);
47     }
48     return 0;
49 }

2019 计蒜之道 复赛

2019 计蒜之道复赛