学步园

                   这个题基本思路是枚举各个事件的真值，枚举的思路有两个：

1.利用离散数学主合取范式的01表达方式，如果事件有3种，真值取法有000，001，010，011，100，101，110，111转化为10进制是0，1，2，3，4，5，6，7=2^3-1

2 dfs(),

#include<cstdio>
#include<iostream>
#include<cstring>
#include<stack>
#include<cctype>
using namespace std;
int  sign[26],vis[26],letter[26],count;
char str[120];
int cmp()
{
    // for(int i=0; i<26; i++)
    //if(vis[i])
    //cout<<char(i+'a')<<" "<<sign[i]<<endl;
    stack<int>st;
    for(int i=strlen(str)-1; i>=0; i--)
    {
        if(islower(str[i]))
            st.push(sign[str[i]-'a']);
        else
        {
            int u,v;
            switch (str[i])
            {
            case 'C':
                u=st.top();
                st.pop();
                v=st.top();
                st.pop();
                st.push(u&&v);
                break;
            case 'D':
                u=st.top();
                st.pop();
                v=st.top();
                st.pop();
                st.push(u||v);
                break;
            case 'I':
                u=st.top();
                st.pop();
                v=st.top();
                st.pop();
                st.push(!u||v);
                break;
            case 'E':
                u=st.top();
                st.pop();
                v=st.top();
                st.pop();
                st.push((!u||v)&(!v||u));
                break;
            case 'N':
                u=st.top();
                st.pop();
                st.push(!u);
                break;
            default:
                break;
            }
        }
    }
    return st.top();
}
int main()
{
    //freopen("in.txt","r",stdin);
    int cas,flag;
    scanf("%d",&cas);
    getchar ();
    while(cas--)
    {
        //fgets(str,120,stdin);
        cin>>str;
        memset(vis,0,sizeof(vis));
        count=0;
        for(int i=0; str[i]!='\0'; i++)
            if(islower(str[i]))
            {
                if(!vis[str[i]-'a'])
                    letter[count++]=str[i]-'a';
                vis[str[i]-'a']=1;
            }
        int a;
        a=(1<<(count))-1;
        flag=0;
        while(a>=0)
        {
            int aa=a,temp=0;
            memset(sign,0,sizeof(sign));
            while(aa)
            {
                sign[letter[temp++]]=aa%2;
                aa/=2;
            }
            if(!cmp())
            {
                flag=1;
                break;
            }
            a--;
        }
        if(flag)
            cout<<"NO\n";
        else cout<<"YES\n";
    }
    return 0;
}

#include<cstdio>
#include<iostream>
#include<cstring>
#include<stack>
#include<cctype>
using namespace std;
int  sign[26],vis[26],letter[26],count;
char str[120];
int cmp()
{
    //for(int i=0; i<26; i++)
    //  if(vis[i])
    // cout<<char(i+'a')<<" "<<sign[i]<<endl;
    stack<int>st;
    for(int i=strlen(str)-1; i>=0; i--)
    {
        if(islower(str[i]))
            st.push(sign[str[i]-'a']);
        else
        {
            int u,v;
            switch (str[i])
            {
            case 'C':
                u=st.top();
                st.pop();
                v=st.top();
                st.pop();
                st.push(u&&v);
                break;
            case 'D':
                u=st.top();
                st.pop();
                v=st.top();
                st.pop();
                st.push(u||v);
                break;
            case 'I':
                u=st.top();
                st.pop();
                v=st.top();
                st.pop();
                st.push(!u||v);
                break;
            case 'E':
                u=st.top();
                st.pop();
                v=st.top();
                st.pop();
                st.push((!u||v)&(!v||u));
                break;
            case 'N':
                u=st.top();
                st.pop();
                st.push(!u);
                break;
            default:
                break;
            }
        }
    }
    return st.top();
}
bool dfs(int cur)
{
    sign[cur]=1;
    int next,flag=0;
    for(int i=cur+1; i<=25; i++)
        if(vis[i])
        {
            flag=1;
            next=i;
            break;
        }
    if(flag)
    {
        if(!dfs(next))
            return false;
        else
        {
            sign[cur]=0;
            if(!dfs(next))
                return false;
        }
    }
    else
    {
        int a;
        a=cmp();
        if(!a)  return false;
        else
        {
            sign[cur]=0;
            a=cmp();
            if(!a)
                return false;
        }
    }
    return true;
}
int main()
{
    //freopen("in.txt","r",stdin);
    int cas;
    scanf("%d",&cas);
    getchar ();
    while(cas--)
    {
        //fgets(str,120,stdin);
        cin>>str;
        memset(vis,0,sizeof(vis));
        count=0;
        for(int i=0; str[i]!='\0'; i++)
            if(islower(str[i]))
                vis[str[i]-'a']=1;
        for(int i=0; i<=25; i++)
        {
            if(vis[i])
            {
                if(dfs(i))
                    cout<<"YES\n";
                else cout<<"NO\n";
                break;
            }
        }
    }
    return 0;
}