注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3200/2106]表达式  

2015-06-20 15:06:26|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3200: 表达式

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 19  Solved: 15
[Submit][Status][Discuss]

Description

Tar的第一项家庭作业是一大堆中缀表达式。他要把这些表达式写成后缀形式之后交给老师。Tar不会做这个作业,所以他找同学要了一份答案来抄。Tar的老师是一个近视眼,分不清连续一串的相同字符和一个字符的区别。Tar今天感觉非常累,于是他决定偷懒,少抄几个字糊弄一下老师。请你帮他完成这个任务。
我们来做几个必要的定义。
表达式由a-z的小写字母和一些二元运算符构成,运算符可以是a-z以外的任意可见字符。
中缀表达式就是一般情况下使用的表达式,比如((a+h)/b)*(c+d),将运算符置于两个运算数中间(注意运算数本身可以是变量或者一个表达式,因此这是一个递归定义)。一般可以利用括号指定运算顺序。
后缀表达式的特点是把运算符置于两个运算数之后,比如和上式等价的后缀表达式是ah+b/cd+*。后缀表达式不需要括号,严格从左到右进行计算。
另外我们假定这个表达式系统内,相同的运算符号满足结合律和交换律,具体来说:
结合律:A*(B*C) = (A*B)*C 写成后缀时,ABC** = AB*C*。
交换律:A*B = B*A 写成后缀时,AB* = BA*

Input

一行字符,表示Tar同学的答案。以后缀表达式的形式给出。

Output

输出一个数字,表示Tar能够蒙混过关至少要写几个字。

Sample Input

样例输入1 af+b*cd**
样例输入2 xy*x*y*x*y*

Sample Output

样例输出1 7 样例输出2 3

HINT

样例解释2
xy*x*y*x*y* = xxxyyy***** = (xy*) 长度为3 
100%的数据满足:输入长度<=2500

Solution

两条运算定律实际上讲的是这么一件事情:对于中缀为 A1 ? A2 ? A3 ?... ? An 形式的表达式,我们可以任意交换这些表达式的顺序。

在处理中缀表达式的时候会用到表达式树这个工具(有表达式 A ? B,那么以 ? 为根,A 与 B 为左右子树建树),对于后缀表达式,可以类似构造。由于这题的特性,我们把树中相邻的同运算符节点收缩,二叉树变为多叉树。

对每个树节点定义 ans[i] 表示这个节点上的最小存储空间。另外,对每个节点,定义 avl[i, x],x 是一个字符,表示是否存在一个最优解,使x这个字符出现在该节点后缀表达式的开头。对于一个叶子节点,ans[i] = 1,avl[i, x] = 1 当且仅当这个叶子节点的字符是 x。

对于非叶子节点,先递归处理其所有子节点,再考虑表达式顺序。首先可以知道最后的表达式形式一定是 Ai1 Ai2 Ai3 ....Ain ? ?... ? ? 的形式。先考虑节点 i 的所有子节点,分为叶子节点和非叶子节点。对于叶子节点 x,有相同字符的节点一定放在一起,因此可以将它们合并。这时候节点 i 的最小存储空间是 |X| +∑(i !∈X)ans[i] + 1,X 表示合并后 i 的子节点中叶子的集合。

我们注意到所有非叶子节点的后缀表达式一定以变量开头,以操作符结尾。因此,将两个这样的节点相邻放置不会降低答案,唯一的优化途径是将一个叶子节点 x 置于这个非叶子节点 j 之前,在 avl[j, x] = 1 的情况下,答案可以降低 1。显然每个节点只能使用一次,因此我们需要在叶子节点和非叶节点之间找一个最大匹配,最大匹配的大小就是答案可以降低的数量。

这样就可以得到了 ans[i]。要得到 avl[i, x],继续观察匹配过程。i 的子节点中,显然所有叶子节点上的字母都可以放在开头。对于非叶子节点j,它可以放在开头,当且仅当之前的匹配里有一个最大匹配不包含它。如果我们之前求出的最大匹配里的确不包含 j,那么 j 可以作为开头。否则,从 j 的匹配点开始找一次增广路,找到则表示 j 可以不在最大匹配中。在这两种情况下,如果 avl[j, x] = 1,那么 avl[i, x] 也应当为 1。

Code

/**************************************************************
    Problem: 3200
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:44 ms
    Memory:1600 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#define isa(c) (c>='a'&&c<='z')
#define N 10010
int n,stk[N],ts,son[N][2],i,j,et,la[N],has[N],f[N],can[N],id[N];char s[N];
struct E{int to,nxt;}e[N];
#define add(x,y) (e[++et]=(E){y,la[x]},la[x]=et)
#define ck(c) (isa(c)&&!(has[x]&(1<<c-'a'))||!isa(c))
#define fb(c) (isa(c)?has[x]|=1<<c-'a':1)
void dfs(int x){
    if(!x)return;
    dfs(son[x][0]),dfs(son[x][1]);
    if(s[son[x][0]]==s[x]){
        for(int&i=la[son[x][0]];i;i=e[i].nxt)
        if(s[x]!=s[e[i].to]&&ck(s[e[i].to]))add(x,e[i].to),fb(s[e[i].to]);
    }
    else if(son[x][0]&&ck(s[son[x][0]]))add(x,son[x][0]),fb(s[son[x][0]]);
    if(s[son[x][1]]==s[x]){
        for(int&i=la[son[x][1]];i;i=e[i].nxt)
        if(s[x]!=s[e[i].to]&&ck(s[e[i].to]))add(x,e[i].to),fb(s[e[i].to]);
    }
    else if(son[x][1]&&ck(s[son[x][1]]))add(x,son[x][1]),fb(s[son[x][1]]);
}
struct NF{
    int s,t,et,la[N],d[N],cur[N],tot,q[N],l,r;
    struct E{int to,flow,nxt;}e[N<<1];
    void init(int tt,int S,int T){
        tot=tt+10;et=1;memset(la,0,tot<<2);s=S,t=T;
    }
    void adde(int x,int y,int f){
        e[++et]=(E){y,f,la[x]},la[x]=et;
        e[++et]=(E){x,0,la[y]},la[y]=et;
    }
    int bfs(int s){
        memset(d,0,tot<<2);
        for(q[l=r=0]=t,d[t]=1;l<=r;l++)
        for(int i=la[q[l]];i;i=e[i].nxt)
        if(e[i^1].flow&&!d[e[i].to])
        d[q[++r]=e[i].to]=d[q[l]]+1;
        return d[s];
    }
#define min(a,b) (a<b?a:b)
    int dfs(int x,int ret){
        if(x==t||ret==0)return ret;
        int tmp,flow=0;
        for(int&i=cur[x];i;i=e[i].nxt)
        if(d[e[i].to]+1==d[x]){
            tmp=dfs(e[i].to,min(e[i].flow,ret-flow));
            e[i].flow-=tmp,e[i^1].flow+=tmp,flow+=tmp;
            if(flow==ret)return flow;
        }
        return flow;
    }
    int maxflow(){
        int flow=0;
        while(bfs(s))memcpy(cur,la,tot<<2),flow+=dfs(s,1<<30);
        return flow;
    }
}nf;
void calc(int x){
    for(int i=la[x];i;i=e[i].nxt)calc(e[i].to);
    if(isa(s[x])){
        can[x]=1<<s[x]-'a';f[x]=1;
        return;
    }
    int cnt=26;
    for(int i=la[x];i;i=e[i].nxt)
    if(isa(s[e[i].to]))id[e[i].to]=s[e[i].to]-'a'+1,can[x]|=1<<s[e[i].to]-'a';
    else id[e[i].to]=++cnt;
    nf.init(cnt+2,cnt+1,cnt+2);
    for(int i=la[x];i;i=e[i].nxt)
    if(isa(s[e[i].to]))nf.adde(cnt+1,id[e[i].to],1);
    else{
        nf.adde(id[e[i].to],cnt+2,1);
        for(int j=0;j<26;j++)
        if(can[e[i].to]&(1<<j))nf.adde(j+1,id[e[i].to],1);
    }
    f[x]=1-nf.maxflow();
    for(int i=la[x];i;i=e[i].nxt){
        f[x]+=f[e[i].to];
        if(!isa(s[e[i].to])&&nf.bfs(id[e[i].to]))can[x]|=can[e[i].to];
    }
}
int main(){
    scanf("%s",s+1);
    for(i=1;s[i];stk[++ts]=i++)
    if(!isa(s[i]))son[i][0]=stk[ts--],son[i][1]=stk[ts--];
    else has[i]=1<<s[i]-'a';
    n=i-1;dfs(n);memset(f,63,sizeof(f));
    calc(n);printf("%d\n",f[n]);
}
  评论这张
 
阅读(26)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018