2018.7.31 Noip2018模拟测试赛（十六）

日期：	七月最后一天	总分：	300分
难度：	提高 ~ 省选	得分：	30分（少的可怜）

我太弱了：（题目目录）

T1：Mushroom追妹纸

T2：抵制克苏恩

T3：美味

失分分析：（QAQ）

开始全部题目看了一遍，第二题期望dp，果断放弃……

看到T3，感觉像是线性基，但是要修改，似乎不可做……（QAQ）

只剩下T1，想到正解——后缀数组+KMP，结果忘记怎么打，耗了整个比赛……

最后T1打炸了，成功炸成屎……

剩下的二十分钟，赶紧打一个T3线性基暴力，但样例竟然过不了……

定睛一看，[○･｀Д´･ ○]，我TM竟然理解错题意了！！MMPPP！！

最后T3暴力30分………………

题解：

T1：Mushroom追妹纸

字符串题，前两个条件后缀数组求最长公共字串。

第三个条件，用 KMP 求出$s_3$在前两个串出现的位置，在统计答案的时候，不要选到$s_3$就好了

CODE:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 int n,n1,n2,n3,m,ans=0;
 7 int nxt[100005],pos[100005],f[100005];
 8 int tp[100005],rak[100005],tax[100005];
 9 char s[100005],s1[50005],s2[50005],s3[10005];
10 int height[100005],sa[100005];
11 
12 void get_next(){
13     int i=1,j=0;
14     for(int i=1;i<=n3;i++)nxt[i]=1;
15     nxt[1]=0;
16     while(i<=n3){
17         if(j==0||s3[i]==s3[j])
18             if(s3[++i]!=s3[++j])nxt[i]=j;
19             else nxt[i]=nxt[j];
20         else j=nxt[j];
21     }
22 }
23 
24 void solve(){
25     int i=1,j=1;
26     while(i<=n){
27         if(j==0||s[i]==s3[j])i++,j++;
28         else j=nxt[j];
29         if(j>n3){
30             pos[++pos[0]]=i-1;
31             j=nxt[j];
32         }
33     }
34 }
35 
36 void sort(int a[],int b[]){
37     for(int i=1;i<=m;i++)tax[i]=0;
38     for(int i=1;i<=n;i++)tax[a[i]]++;
39     for(int i=1;i<=m;i++)tax[i]+=tax[i-1];
40     for(int i=n;i>=1;i--)sa[tax[a[b[i]]]--]=b[i];
41 }
42 
43 bool comp(int r[],int a,int b,int k){
44     return r[a]==r[b]&&r[a+k]==r[b+k];
45 }
46 
47 void get_sa(int a[],int b[]){
48     for(int i=1;i<=n1;i++)s[i]=s1[i];
49     s[n1+1]='$';
50     for(int i=1;i<=n2;i++)s[n1+i+1]=s2[i];
51     n=n1+n2+1;
52     for(int i=1;i<=n;i++)a[i]=s[i],b[i]=i;
53     m=256,sort(a,b);
54     for(int j=1,p=0;p<n;j<<=1,m=p){
55         p=0;
56         for(int i=1;i<=j;i++)b[++p]=n-j+i;
57         for(int i=1;i<=n;i++)if(sa[i]>j)b[++p]=sa[i]-j;
58         sort(a,b);
59         int *t=a;a=b;b=t;
60         a[sa[1]]=p=1;
61         for(int i=2;i<=n;i++)
62         a[sa[i]]=comp(b,sa[i],sa[i-1],j)?p:++p;
63     }
64     for(int i=1;i<=n;i++)rak[sa[i]]=i;
65 }
66 
67 void get_height(){
68     int i=1,j=1,k=0;
69     for(i=1;i<=n;height[rak[i++]]=k){
70         j=sa[rak[i]-1];
71         if(k)k--;
72         while(s[i+k]==s[j+k])k++;
73     }
74 }
75 
76 int main(){
77     scanf("%s%s%s",s1+1,s2+1,s3+1);
78     n1=strlen(s1+1),n2=strlen(s2+1),n3=strlen(s3+1);
79     get_sa(rak,tp),get_height();
80     get_next(),solve();
81     for(int i=1;i<=n;i++){
82         int *k=pos,s;
83         do{
84             k=lower_bound(k+1,pos+pos[0]+1,i);
85             s=*k;
86             if(k-pos>pos[0]){s=2e9;break;}
87         }while(*k-n3+1<i);
88         f[i]=s-i;
89     }
90     for(int i=3;i<=n;i++)
91         if((sa[i]<=n1&&sa[i-1]>n1)||(sa[i]>n1&&sa[i-1]<=n1))
92             ans=max(ans,min(height[i],min(f[sa[i]],f[sa[i-1]])));
93     printf("%d",ans);
94 }

长啊！！（别人都是10几20毫秒，我竟然500ms+ MMP (▼ヘ▼#)）

T2：抵制克苏恩

期望dp，$f[k][a][b][c]$ 表示攻击$k$次后，还剩$a$个 1 血，$b$个2血，$c$个3血，英雄受伤害的期望，直接递推！

CODE：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 int T,n,m,K,A,B,C;
 7 double f[55][10][10][10];
 8 
 9 double dp(int k,int a,int b,int c){
10     if(k==0)return 0;
11     c=min(c,7-a-b);
12     if(f[k][a][b][c])return f[k][a][b][c];
13     f[k][a][b][c]+=1.0/(a+b+c+1)*(dp(k-1,a,b,c)+1);
14     if(a)f[k][a][b][c]+=1.0*a/(a+b+c+1)*dp(k-1,a-1,b,c);
15     if(b)f[k][a][b][c]+=1.0*b/(a+b+c+1)*dp(k-1,a+1,b-1,c+1);
16     if(c)f[k][a][b][c]+=1.0*c/(a+b+c+1)*dp(k-1,a,b+1,c);
17     return f[k][a][b][c];
18 }
19 
20 int main(){
21     scanf("%d",&T);
22     while(T--){
23         scanf("%d%d%d%d",&K,&A,&B,&C);
24         printf("%.2f
",dp(K,A,B,C));
25     }
26 }

T3：美味

主席树，类似 Trie 树的思想，按位贪心；

用一个变量$a$从高位走，0就走1,1就走0；

主席树维护值域和区间，判断，具体看代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 
 5 int n,m,b,x,l,r,y,tot=0,root[200005];
 6 int sum[4000005],lch[4000005],rch[4000005];
 7 
 8 int read(){
 9     int x=0;char ch=0;
10     while(ch<'0'||ch>'9'){ch=getchar();}
11     while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
12     return x;
13 }
14 
15 void update(int &o,int last,int l,int r,int x){
16     o=++tot;
17     lch[o]=lch[last],rch[o]=rch[last],sum[o]=sum[last]+1;
18     if(r-l==1)return;
19     else{
20         int mid=l+r>>1;
21         if(x<mid)update(lch[o],lch[last],l,mid,x);
22         else update(rch[o],rch[last],mid,r,x);
23     }
24 }
25 
26 int query(int o1,int o2,int l,int r,int x,int y){
27     if(l>=y||r<=x)return 0;
28     if(l>=x&&r<=y)return sum[o2]>sum[o1];
29     int mid=l+r>>1;
30     int ans=0;
31     if(x<mid)ans|=query(lch[o1],lch[o2],l,mid,x,y);
32     if(y>mid)ans|=query(rch[o1],rch[o2],mid,r,x,y);
33     return ans;
34 }
35 
36 int main(){
37     n=read(),m=read();
38     for(int i=1;i<=n;i+=2){
39         x=read();
40         update(root[i],root[i-1],0,300000,x);
41         x=read();
42         update(root[i+1],root[i],0,300000,x);
43     }
44     register int i,j,a;
45     for(i=1,a=0;i<=m;++i,a=0){
46         b=read(),x=read(),l=read(),r=read();
47         for(register int j=17;~j;--j){
48             if(b&(1<<j)){
49                 int L=max(a-x,0),R=a+(1<<j)-1-x;    
50                 if(!query(root[l-1],root[r],0,300000,L,R+1))a^=(1<<j);//没法走0就走1 
51             }else{
52                 int L=max(a+(1<<j)-x,0),R=a+(1<<j+1)-1-x;
53                 if(query(root[l-1],root[r],0,300000,L,R+1))a^=(1<<j);//能走1就走1 
54             }
55         }
56         printf("%d
",a^b);
57     }
58 }

成功 1960ms 卡过！！呵呵…… ┐(´∇｀)┌