Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

用c++实现 一次ac (暴力实现)注意栈的实现

Posted by STEVENCHEN123 at 2015-10-08 21:26:32 on Problem 3295
#include<iostream>
#include <sstream>
#include<string>
#include<cstdlib>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<stack>
#include<fstream>
#include<cassert>
#include<map>
#include<set>
#include<vector>
#include<cstring>
#include<algorithm>
#include"limits.h"
using namespace std;
//#define debug
bool Judge(char op,bool a,bool b=false)
{
    switch(op){
        case 'K':
            return a&&b;
            break;
        case 'A':
            return a||b;
            break;
        case 'N':
            return !a;
            break;
        case 'C':
            return !(a&&!b);
            break;
        case 'E':
            return a==b;
            break;
    }
    assert(1);
    return 1;
}
bool isSymbol(char k)
{
    return k=='K'||k=='A'||k=='N'||k=='C'||k=='E';
}
struct Char
{
    char c;
    int t;
    Char(char cc,int tt):c(cc),t(tt){
    }
};
struct Bool
{
    bool b;
    int t;
    Bool(bool bb,int tt):b(bb),t(tt){
    }
};
bool solve(const string & s)
{
    vector<Char> sym;
    vector<Bool> var;
    int cnt=0;
    for (int i = 0; i < s.size(); ++i)
    {
        if (isSymbol(s[i]))
        {
            sym.push_back(Char(s[i],cnt++));
        }
        else{
            var.push_back(Bool(s[i]-'0',cnt++));
        }
        while(1){
            if (var.size()&&sym.size()&&sym.back().c=='N'&&var.back().t>sym.back().t)
            {
                char cc=sym.back().c;
                bool bb=var.back().b;
                sym.pop_back();
                var.pop_back();
                var.push_back(Bool(Judge(cc, bb),cnt++));
                continue;
            }
            if (var.size()>=2&&sym.size()&&sym.back().t<var.back().t&&sym.back().t<var[var.size()-2].t)
            {
                char cc=sym.back().c;
                bool bb=var.back().b;
                sym.pop_back();
                var.pop_back();
                bool aa=var.back().b;
                var.pop_back();
                var.push_back(Bool(Judge(cc, aa,bb),cnt++));
                continue;
            }
            break;
        }
    }
    assert(var.size()==1&&sym.size()==0);
    return var.back().b;
}
void replaceAll(string & s,char  c,char re)
{
    long p=s.find(string(1,c));
    while (p!=string::npos) {
        s.replace(p, 1, string(1,re));
        p=s.find(string(1,c));
    }
}
void preProcess(string & s,int p)
{
    int vec[5]={0};
    int k=0;
    while (p>0) {
        vec[k++]=p%2;
        p/=2;
    }
    replaceAll(s,'p', (char)vec[0]+'0');
    replaceAll(s,'q', (char)vec[1]+'0');
    replaceAll(s,'r', (char)vec[2]+'0');
    replaceAll(s,'s', (char)vec[3]+'0');
    replaceAll(s,'t', (char)vec[4]+'0');
}
int main()
{
#ifdef debug
    freopen("/Users/steven/Desktop/tmp.txt","r",stdin);
    clock_t a=clock();
#endif
    string s;
    while (cin>>s&&s!="0") {
        bool ans=1;
        for (int i=0; i<32; i++) {
            string tmp=s;
            preProcess(tmp, i);
            if (!solve(tmp)) {
                ans=0;
                break;
            }
        }
        if (ans) {
            cout<<"tautology"<<endl;
        }
        else
            cout<<"not"<<endl;
        
    }
    
#ifdef debug
    clock_t b=clock();
    cout<<"running time:"<<(b-a)/(double)CLOCKS_PER_SEC<<endl;
#endif
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator