作为cf上第8个过的人表示很开心..

题意:

给你个逻辑表达式,求一个跟它等价的但每个字母只出现一次的表达式(包含符号: AND(&) OR(|) NOT(~) )

例如[tex](a\&b)|(a\&c)=a|(b\&c)[/tex]

然而..

(a [tex]\&[/tex] b) | (~a[tex]\&[/tex]~b) = a^b,这个表达式并不能成功的表达出来,那么输出No

特别的,常数不能出现,也就是说不允许出现"1"这样的表达式

最多出现11个字母,即a到k

解法:

我们把所拿到的字母进行暴力..

暴力分一部分在左边,一部分在右边,左右用括号括起来

然后中间用一个符号连接

这样分治下去..没了

注意:

判定一种分法是否合法会很麻烦..

你要判定的东西不少..

包括但不限于:左边的值是否只和右边为0或者1有关,还是有别的关系(比如右边某些值取不一样的时候值会有变化)

是否有些字母根本不存在

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
char a[1005];
bool b[205];
int ans[3005];
int another[1005];
bool get_ans(int l,int r)
{
    if (l==r-1)
    {
        return b[(int)a[l]];
    }
    int i;
    for (i=l;;)
    {
        if (a[i]=='(')
        {
            i=another[i];
        }
        i++;
        if (i>=r) break; 
        if (a[i]=='|')
        {
            return get_ans(l,i)||get_ans(i+1,r);
        }
    }
    for (i=l;;)
    {
        if (a[i]=='(')
        {
            i=another[i];
        }
        i++;
        if (i>=r) break; 
        if (a[i]=='&')
        {
            return get_ans(l,i)&&get_ans(i+1,r);
        }
    }
    if (a[l]=='~')
    {
        int flag=0;
        for (;a[l]=='~';l++) flag^=1;
        return flag^get_ans(l,r);
    }
    if (a[l]=='(') return get_ans(l+1,r-1);
    puts("Error : find_something wrong in location :");
    printf("%d %d\n",l,r);
    return false;
}
int datas[3005][2];
int exact[3005][2];
void update(int x,int y,int z)
{
    if (datas[x][z]==-1)
    {
        datas[x][z]=y;
        return;
    }
    if (datas[x][z]==y)
    {
        return;
    }
    datas[x][z]=2;
}
void dfs(int x,int value_from)
{
    if (x==((-x)&x))
    {
        if (ans[value_from]==ans[value_from^x])
        {
            freopen("formula.out","w",stdout);
            puts("No");
            exit(0);
        }
        if (ans[value_from]==1)
        {
            printf("~");
        }
        int i;
        for (i=0;i<11;i++)
        {
            if ((1<<i)==x) printf("%c",(char)(i+'a'));
        }
        return;
    }
    int i;
    for (i=1;i<x;i++)
    {
        if ((i|x)!=x) continue;
        int j;
        for (j=0;j<=x;j++)
        {
            if ((j|x)!=x) continue;
            datas[j][0]=-1;
            datas[j][1]=-1;
            exact[j][0]=-1;
            exact[j][1]=-1;
        }
        int t=i^x;
        for (j=0;j<=x;j++)
        {
            if ((j|x)!=x) continue;
            update(j&i,ans[j^value_from],0);
            update(j&t,ans[j^value_from],1);
        }
        int ans1=-1;
        int data2_i=-1;
        for (j=0;j<=x;j++)
        {
            if ((j|i)!=i) continue;
            if (datas[j][0]==2)
            {
                data2_i=j;
                continue;
            }
            if (ans1==-1)
            {
                ans1=datas[j][0];
            }
            else if (ans1!=datas[j][0])
            {
                ans1=2;
            }
        }
        int ans2=-1;
        int data2_t=-1;
        for (j=0;j<=x;j++)
        {
            if ((j|t)!=t) continue;
            if (datas[j][1]==2)
            {
                data2_t=j;
                continue;
            }
            if (ans2==-1)
            {
                ans2=datas[j][1];
            }
            else if (ans2!=datas[j][1])
            {
                ans2=2;
            }
        }
        if ((ans1==2)&&(data2_i==-1))
        {
            dfs(i,value_from);
            return;
        }
        if ((ans2==2)&&(data2_t==-1))
        {
            dfs(t,value_from);
            return;
        }
        if (ans1!=ans2) continue;
        if (ans1==-1) continue;
        if (ans1==2) continue;
        for (j=0;j<=x;j++)
        {
            if ((j|x)!=x) continue;
            if (datas[j&i][0]==2)
            {
                if (exact[j&t][0]==-1)
                {
                    exact[j&t][0]=ans[j^value_from];
                }
                else if (exact[j&t][0]!=ans[j^value_from])
                {
                    break;
                }
            }
            if (datas[j&t][1]==2)
            {
                if (exact[j&i][1]==-1)
                {
                    exact[j&i][1]=ans[j^value_from];
                }
                else if (exact[j&i][1]!=ans[j^value_from])
                {
                    break;
                }
            }
        }
        if (j<=x) continue;
        printf(" (");
        dfs(i,value_from^data2_t);
        printf(") ");
        if (ans1==0) printf("&"); else printf("|");
        printf(" (");
        dfs(t,value_from^data2_i);
        printf(") ");
        return;
    }
    freopen("formula.out","w",stdout);
    puts("No");
    exit(0);
}
int main()
{
    freopen("formula.in","r",stdin);
    freopen("formula.out","w",stdout);
    gets(a);
    int i;
    static int que[1005];
    int rail=0;
    int x=0;
    for (i=0;a[i]!='\0';i++)
    {
        if (a[i]==' ')
        {
            x++;
            continue;
        }
        a[i-x]=a[i];
        if (a[i]=='(')
        {
            que[rail++]=i-x;
        }
        else if (a[i]==')')
        {
            rail--;
            another[i-x]=que[rail];
            another[que[rail]]=i-x;
        }
    }
    int n=i-x;
    for (i=0;i<(1<<11);i++)
    {
        int j;
        for (j=0;j<11;j++)
        {
            if ((1<<j)&i) b[j+'a']=1; else b[j+'a']=0;
        }
        ans[i]=get_ans(0,n);
    }
    puts("Yes");
    dfs(2047,0);
    return 0;
}