2019.6.24 考试

绝地灬酷狼 2021-12-10 14:15 180阅读 0赞

emmmm。。。。  
还是屈服来写一点东西  
  
**T1 Censoring ac自动机**  
这题有一道同名题，放在字符串基础里，是KMP，但可悲的是，我那道题用hash卡过去的，没有打正解。。。。。。  
导致我读完题之后蒙了，满脑子都是hash，加上ac自动机并没有好好写，也没有理解的特别透彻（更何况板子没背过）。  
于是考试时最后打了个hash叫了上去，骗了87分，再在O（nm）扫的时候加了一个小剪枝，93分。  
然而%%%Yu-shi大佬hashAC，比较难受。（可能我长得丑吧）  
  
说一下正解，把匹配的子串全部tui进自动机后，在单个子串末尾存一下len，正常匹配，和板子一样，不过需要用trie图优化（貌似trie树跑fail指针会T）  
在匹配的时候手动维护栈，一个存字符，一个存之前匹配点指针所指的位置，在匹配成功后暴力弹栈，指针指向弹完栈以后的位置。  
代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 struct node
     4 {
     5     int cnt,l;
     6     node *fail;
     7     node *nxt[26];
     8     node()
     9     {
    10         l=cnt=0;
    11         fail=NULL;
    12         for(int i=0;i<26;i++) nxt[i]=NULL;
    13     }
    14 }*que[100100];
    15 char s[100100];
    16 char st[100100];
    17 char k[100100];
    18 node *root=new node();
    19 node *pos[100100];
    20 int n,top;
    21 void insert(char *k)
    22 {
    23     node *p=new node(),*q=new node();
    24     int len=strlen(k);p=root;
    25     for(int i=0,v;i<len;i++)
    26     {
    27         v=k[i]-'a';
    28         if(p->nxt[v]==NULL)
    29         {
    30             q=(struct node *)malloc(sizeof(node));
    31             q=new node();
    32             p->nxt[v]=q;
    33         }
    34         p=p->nxt[v];
    35     }
    36     p->l=len;
    37     p->cnt++;
    38 }
    39 void build_ac_automation(node *root)
    40 {
    41     int head=0,tail=0;
    42     que[tail++]=root;
    43     while(head!=tail)
    44     {
    45         node* tmp=que[head++];
    46         node* p=NULL;
    47         for(int i=0;i<26;i++)
    48         {
    49             if(tmp->nxt[i]!=NULL)
    50             {
    51                 if(tmp==root) tmp->nxt[i]->fail=root;
    52                 else tmp->nxt[i]->fail=tmp->fail->nxt[i];
    53                 que[tail++]=tmp->nxt[i];
    54             }
    55             else
    56             {
    57                 if(tmp==root) tmp->nxt[i]=tmp;
    58                 else tmp->nxt[i]=tmp->fail->nxt[i];
    59             }
    60         }
    61     }
    62 }
    63 int main()
    64 {
    65     scanf("%s%d",s,&n);
    66     for(int i=1;i<=n;i++)
    67     {
    68         scanf("%s",k);
    69         insert(k);
    70     }
    71     build_ac_automation(root);
    72     int len=strlen(s);
    73     node *p=root,*temp=NULL;
    74     for(int i=0;i<len;i++)
    75     {
    76         int x=s[i]-'a';
    77         st[++top]=s[i],pos[top]=p;
    78         p=p->nxt[x];
    79         if(p==NULL) p=root;
    80         if(p->l)
    81         {
    82             top-=p->l;
    83             p=pos[top+1];
    84         }
    85     }
    86     for(int i=1;i<=top;i++) printf("%c",st[i]);
    87     return 0;
    88 }

代码

**T2 记忆的轮廓 树形期望dp**  
这题考试时看蒙了，样例都手膜不出来，难受啊马飞。（果然我还是太菜了嘤嘤嘤）  
如果教练把50%数据存档点==正确节点可能还能打个暴力。  
接下来是（抄来的）范围题解：  
50%：这一部分分是存档点等于正确节点，显然每个点都存档是最优解。  
这样的话整个问题就转化成了一个普通的树形期望dp。  
在我看来这题应该直接一个dfs就差不多了，不过我并没有自己去码（如果那个大佬写了发现不行请及时提醒我谢谢），而是根据正解码了一个其他的做法。  
我们设d\[i\]为i节点的儿子个数，g\[i\]是对于每一个非叶子错误节点i期望走多少步后会读档。  
可以得到g\[i\]=1+sigma(g\[j\]/d\[i\]) j是i的错误儿子。  
再设s\[i\]代表正确节点的错误儿子的g值和，可以得到s\[i\]=sigma(g\[j\]) j是i的错误儿子。  
期望dp一般倒退，且到达n以后立即停止，所以f\[n\]==0;  
接下来dp转移：f\[i\]=1+1/d\[i\]\*f\[i+1\]+1/d\[i\]\*(g\[i\]+f\[i\])。玄学移项以后是：f\[i\]=d\[i\]+f\[i+1\]+s\[i\]。  
复杂度线性。  
接下来50分代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

50%

70%：可以设a\[i\]\[j\]（i<j）表示从正确节点i走到正确节点j的期望步数，中间不存档。  
可以得到：a\[i\]\[j\]=a\[i\]\[j-1\]+1+1/d\[j-1\]\*0+1/d\[j-1\]\*sigma(g\[k\]+a\[i\]\[j\]) k是j-1的错误儿子。  
玄学移项：a\[i\]\[j\]=a\[i\]\[j-1\]\*d\[j-1\]+d\[j-1\]+s\[j-1\]。（不得不说玄学移项可真是个好东西）  
接下来dp转移 f\[i\]\[j\]代表走到第i个点共存j次档。  
首先根据题干，那么肯定存档存到满是最优情况，sof\[n\]\[p\]=0,目标状态f\[1\]\[1\]。  
f\[i\]\[j\]=min(f\[k\]\[j+1\]+a\[i\]\[k\]) n<=k<i。  
接下来70分代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<iostream>
     2 #include<cstring>
     3 #include<cstdio>
     4 #define db double
     5 using namespace std;
     6 struct node{
         int to,nxt;}l[3010];
     7 int n,m,tot,p,head[1510];
     8 db g[1510],s[1510],f[1510][1510],d[1510],a[1510][1510];
     9 void add(int x,int y)
    10 {
    11     l[++tot].to=y;
    12     l[tot].nxt=head[x];
    13     head[x]=tot;
    14 }
    15 void dfs(int x)
    16 {
    17     if(x>n)
    18     {
    19         if(!d[x])
    20         {
    21             g[x]=1;
    22             return ;
    23         }
    24         else
    25         {
    26             for(int i=head[x];i;i=l[i].nxt)
    27             {
    28                 int y=l[i].to;
    29                 dfs(y);
    30                 g[x]+=1.0/d[x]*(g[y]+1.0);
    31             }
    32         }
    33     }
    34     else
    35     {
    36         for(int i=head[x];i;i=l[i].nxt)
    37         {
    38             int y=l[i].to;
    39             dfs(y);
    40             if(y>n) s[x]+=g[y];
    41         }
    42     }
    43 }
    44 void init()
    45 {
    46     tot=0;
    47     memset(d,0,sizeof(d));
    48     memset(s,0,sizeof(s));
    49     memset(g,0,sizeof(g));
    50     memset(f,0x7f,sizeof(f));
    51     memset(a,0x7f,sizeof(a));
    52     memset(l,0,sizeof(l));
    53     memset(head,0,sizeof(head));
    54 }
    55 int main()
    56 {
    57     int QwQ;
    58     scanf("%d",&QwQ);
    59     while(QwQ--)
    60     {
    61         init();
    62         scanf("%d%d%d",&n,&m,&p);
    63         for(int i=1;i<n;i++)
    64             add(i,i+1),d[i]++;
    65         for(int i=1,x,y;i<=m-n;i++)
    66         {
    67             scanf("%d%d",&x,&y);
    68             add(x,y),d[x]++;
    69         }
    70         dfs(1);
    71         for(int i=1;i<=n;i++)
    72         {
    73             a[i][i]=0;
    74             for(int j=i+1;j<=n;j++) a[i][j]=a[i][j-1]*d[j-1]+d[j-1]+s[j-1];
    75         }
    76         f[n][p]=0;
    77         for(int i=n-1;i>=1;i--)
    78             for(int j=p-1;j>=1;j--)
    79                 for(int k=i;k<=n;k++)
    80                     f[i][j]=min(f[i][j],f[k][j+1]+a[i][k]);
    81         for(int i=n-1;i>0;i--) f[i]=f[i+1]+d[i]+s[i];
    82         printf("%.4lf\n",f[1][1]);
    83     }
    84     return 0;
    85 }

70%

100%（真正神仙）：emmmm。。。。  
分析一下a数组的大小，可以看到是爆炸式增长。  
所以进行一波神仙分析：我们来估计答案的上界。考虑一种可行方案，每n/p个正确节点就设立一次存档位置，考虑最坏情况，观察a的转移，应该每变换一次存档点，大约需要3^(n/p)s\[i\]+3(n/p-1)\*s\[i+1\]+3^(n/p-2)\*s\[i+2\]+……因为最多m个节点，s的上限是1500（实际上也远远达不到），把所有s都视为这个上限，提取公因数，计算一下那个等比数列求和，由于p是有下界的，因此n/p有上界14，发现最后也就是个12位数的样子，而至于a会爆炸的问题，double是可以存很多位的，而且太大的a肯定不可能被用上。  
由此观之，答案并没有那么大，所以我们可以设一个常数进行转移，这个常数大概在40多一点，因为a的下界已经是2^40了，而答案的上界远远没有达到，经过精确计算还可以再把step调小一点。  
所以最终复杂度（nplogans）  
代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<iostream>
     2 #include<cstring>
     3 #include<cstdio>
     4 #define db double
     5 using namespace std;
     6 struct node{
         int to,nxt;}l[3010];
     7 int n,m,tot,p,head[1510];
     8 db g[1510],s[1510],f[1510][1510],d[1510],a[1510][1510];
     9 void add(int x,int y)
    10 {
    11     l[++tot].to=y;
    12     l[tot].nxt=head[x];
    13     head[x]=tot;
    14 }
    15 void dfs(int x)
    16 {
    17     if(x>n)
    18     {
    19         if(!d[x])
    20         {
    21             g[x]=1;
    22             return ;
    23         }
    24         else
    25         {
    26             for(int i=head[x];i;i=l[i].nxt)
    27             {
    28                 int y=l[i].to;
    29                 dfs(y);
    30                 g[x]+=1.0/d[x]*(g[y]+1.0);
    31             }
    32         }
    33     }
    34     else
    35     {
    36         for(int i=head[x];i;i=l[i].nxt)
    37         {
    38             int y=l[i].to;
    39             dfs(y);
    40             if(y>n) s[x]+=g[y];
    41         }
    42     }
    43 }
    44 void init()
    45 {
    46     tot=0;
    47     memset(d,0,sizeof(d));
    48     memset(s,0,sizeof(s));
    49     memset(g,0,sizeof(g));
    50     memset(f,0x7f,sizeof(f));
    51     memset(a,0x7f,sizeof(a));
    52     memset(l,0,sizeof(l));
    53     memset(head,0,sizeof(head));
    54 }
    55 int main()
    56 {
    57     int QwQ;
    58     scanf("%d",&QwQ);
    59     while(QwQ--)
    60     {
    61         init();
    62         scanf("%d%d%d",&n,&m,&p);
    63         for(int i=1;i<n;i++)
    64             add(i,i+1),d[i]++;
    65         for(int i=1,x,y;i<=m-n;i++)
    66         {
    67             scanf("%d%d",&x,&y);
    68             add(x,y),d[x]++;
    69         }
    70         dfs(1);
    71         for(int i=1;i<=n;i++)
    72         {
    73             a[i][i]=0;
    74             for(int j=i+1;j<=n;j++) a[i][j]=a[i][j-1]*d[j-1]+d[j-1]+s[j-1];
    75         }
    76         f[n][p]=0;
    77         for(int i=n-1;i>=1;i--)
    78             for(int j=p-1;j>=1;j--)
    79                 for(int k=i;k<=min(n,i+45);k++)
    80                     f[i][j]=min(f[i][j],f[k][j+1]+a[i][k]);
    81         printf("%.4lf\n",f[1][1]);
    82     }
    83     return 0;
    84 }

100%

**T3 雨天的尾巴 树上差分+lca+权值线段树+线段树合并**  
考试时的沙雕MouDing：  
第一眼：树上差分？？？  
第二眼：喵的lca又忘了。。。  
第三眼：树套树？？？  
第四眼：树套树也不会。。。  
异常真实。。。。无颜面对hzoi父老乡亲。  
所以又打了一个纯暴力交上去了，骗到50。。。。  
当初在想树上差分的时候感觉没有办法O（1）修改，总是感觉要O(n),也想着用权值线段树，可总是没有正经思路。  
考完时候pa大神讲题，最终用到了线段树合并。（顺便揭穿pa大猪蹄子的丑恶嘴脸）  
方法是dfs下去，在递归回来的时候进行合并，就可以了。  
果然还是不能够灵活运用，或者说思路有问题。  
代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<iostream>
      2 #include<cstdio>
      3 #include<cstring>
      4 #include<algorithm>
      5 #include<cmath>
      6 #define N 100010
      7 using namespace std;
      8 struct node{
         int to,nxt;}l[N*2];
      9 struct no{
         int l,r,num;}q[N*2];
     10 int t,n,m,tot,head[N],a[N],b[N],ch[N],fa[N][21],d[N],imax=-1,sz;
     11 int s[N*50],ls[N*50],rs[N*50],num[N*50],ans[N],rt[N*50];
     12 void add(int x,int y)
     13 {
     14     l[++tot].to=y;
     15     l[tot].nxt=head[x];
     16     head[x]=tot;
     17 }
     18 void Dfs(int x,int dep)
     19 {
     20     d[x]=dep;
     21     for(int i=1;i<=t;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
     22     for(int i=head[x];i;i=l[i].nxt)
     23     {
     24         int y=l[i].to;
     25         if(!d[y])
     26         {
     27             fa[y][0]=x;
     28             Dfs(y,dep+1);
     29         }
     30     }
     31 }
     32 int lca(int x,int y)
     33 {
     34     if(d[x]>d[y]) swap(x,y);
     35     for(int i=t;i>=0;i--)
     36         if(d[fa[y][i]]>=d[x]) y=fa[y][i];
     37     if(x==y) return x;
     38     for(int i=t;i>=0;i--)
     39     {
     40         if(fa[y][i]!=fa[x][i])
     41         {
     42             y=fa[y][i];
     43             x=fa[x][i];
     44         }
     45     }
     46     return fa[x][0];
     47 }
     48 void change(int &k,int pos,int data,int l,int r)
     49 {
     50     if(!k) k=++sz;
     51     if(l==r)
     52     {
     53         s[k]=pos;
     54         num[k]+=data;
     55         return ;
     56     }
     57     int mid=l+r>>1;
     58     if(pos<=mid) change(ls[k],pos,data,l,mid);
     59     else change(rs[k],pos,data,mid+1,r);
     60     if(num[ls[k]]==num[rs[k]])
     61     {
     62         num[k]=num[ls[k]];
     63         s[k]=min(s[ls[k]],s[rs[k]]);
     64     }
     65     else
     66     {
     67         num[k]=max(num[ls[k]],num[rs[k]]);
     68         s[k]=(num[ls[k]]>num[rs[k]])?s[ls[k]]:s[rs[k]];
     69     }
     70 }
     71 int merge(int x,int y,int l,int r)
     72 {
     73     if(!x||!y) return x+y;
     74     if(l==r)
     75     {
     76         num[x]+=num[y];
     77         return x;
     78     }
     79     int mid=l+r>>1;
     80     ls[x]=merge(ls[x],ls[y],l,mid);
     81     rs[x]=merge(rs[x],rs[y],mid+1,r);
     82     num[x]=max(num[ls[x]],num[rs[x]]);
     83     if(num[ls[x]]==num[rs[x]])
     84     {
     85         num[x]=num[ls[x]];
     86         s[x]=min(s[ls[x]],s[rs[x]]);
     87     }
     88     else
     89     {
     90         num[x]=max(num[ls[x]],num[rs[x]]);
     91         s[x]=(num[ls[x]]>num[rs[x]])?s[ls[x]]:s[rs[x]];
     92     }
     93     return x;
     94 }
     95 void dfs(int x)
     96 {
     97     for(int i=head[x];i;i=l[i].nxt)
     98     {
     99         int y=l[i].to;
    100         if(d[y]>d[x])
    101         {
    102             dfs(y);
    103             rt[x]=merge(rt[x],rt[y],1,imax);
    104         }
    105     }
    106     ans[x]=ch[s[rt[x]]];
    107 }
    108 int main()
    109 {
    110     scanf("%d%d",&n,&m);
    111     t=log2(n)+1;
    112     for(int i=1,x,y;i<n;i++)
    113     {
    114         scanf("%d%d",&x,&y);
    115         add(x,y),add(y,x);
    116     }
    117     Dfs(1,1);
    118     for(int i=1;i<=m;i++)
    119     {
    120         scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].num);
    121         a[i]=b[i]=q[i].num;
    122     }
    123     sort(b+1,b+m+1);
    124     int p=unique(b+1,b+m+1)-b-1;
    125     for(int i=1;i<=m;i++)
    126     {
    127         a[i]=lower_bound(b+1,b+p+1,a[i])-b;
    128         imax=max(imax,a[i]);
    129         ch[a[i]]=q[i].num;
    130     }
    131     for(int i=1;i<=m;i++)
    132     {
    133         int Lca=lca(q[i].l,q[i].r);
    134         change(rt[q[i].l],a[i],1,1,imax);
    135         change(rt[q[i].r],a[i],1,1,imax);
    136         change(rt[Lca],a[i],-1,1,imax);
    137         change(rt[fa[Lca][0]],a[i],-1,1,imax);
    138     }
    139     dfs(1);
    140     for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
    141     return 0;
    142 }

代码

转载于:https://www.cnblogs.com/MouDing/p/11115912.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211210/5a2c6212ce154c6886c67ac4c3ee0bf1.png