首页 > 专题系列 > Java解POJ > POJ 3295 Tautology [解题报告] Java
2013
11-12

POJ 3295 Tautology [解题报告] Java

Tautology

问题描述 :

WFF ‘N PROOF is a logic game played with dice. Each die has six faces representing some subset of the possible symbols K, A, N, C, E, p, q, r, s, t. A Well-formed formula (WFF) is any string of these symbols obeying the following rules:

  • p, q, r, s, and t are WFFs
  • if w is a WFF, Nw is a WFF
  • if w and x are WFFs, Kwx, Awx, Cwx, and Ewx are WFFs.

The meaning of a WFF is defined as follows:

  • p, q, r, s, and t are logical variables that may take on the value 0 (false) or 1 (true).
  • K, A, N, C, E mean and, or, not, implies, and equals as defined in the truth table below.


Definitions of K, A, N, C, and E
     w  x   Kwx   Awx    Nw   Cwx   Ewx
  1  1   1   1    0   1   1
  1  0   0   1    0   0   0
  0  1   0   1    1   1   0
  0  0   0   0    1   1   1

A tautology is a WFF that has value 1 (true) regardless of the values of its variables. For example, ApNp is a tautology because it is true regardless of the value of p. On the other hand, ApNq is not, because it has the value 0 for p=0, q=1.

You must determine whether or not a WFF is a tautology.

输入:

Input consists of several test cases. Each test case is a single line containing a WFF with no more than 100 symbols. A line containing 0 follows the last case.

输出:

For each test case, output a line containing tautology or not as appropriate.

样例输入:

ApNp
ApNq
0

样例输出:

tautology
not

解题代码:

//* @author: 
import java.util.Scanner;
import java.util.Stack;

public class Main {
 public static void main(String[] args) {
  new Main().init();
 }

 public void init() {
  Scanner sc = new Scanner(System.in);
  char[] s;
  boolean flag;
  while (!sc.hasNextInt()) {
	flag = true;
	s = sc.next().toCharArray();
	for (int i = 0; i < 32; i++) {
		if (!check(i, s)) {
			flag = false;
			break;
		}
	}
	if (flag)
		System.out.println("tautology");
	else
		System.out.println("not");
   }
 }

  public boolean check(int i, char[] s) {
   Stack< Integer> stack = new Stack< Integer>();
   for (char c : s) {
	if (c >= 'p' && c <= 't') {
		int d = c - 'p';
		d = (1 <<  d & i) >> d;
		boolean flag = true;
		while (flag) {
			if (stack.isEmpty()) {
				stack.push(d);
				flag = false;
			} else if (isoperate(stack.peek())) {
				stack.push(d);
				flag = false;
			} else if (stack.peek() == 'N') {
				d = 1 - d;
				stack.pop();
			} else {
				int dd = stack.pop();
				int oper = stack.pop();
				switch (oper) {
				case 'K':
					d &= dd;
					break;
				case 'A':
					d |= dd;
					break;
				case 'C':
					d = dd - d > 0 ? 0 : 1;
					break;
				case 'E':
					d = 1 - (d ^ dd);
					break;
				default:
					break;
				}
			}
		}
	} else {
		stack.push((int) c); 
	}
   }

   return stack.pop() == 1;
  }


  private boolean isoperate(Integer peek) {
    switch (peek.intValue()) {
	case 'K':
	case 'A':
	case 'C':
	case 'E':
		return true;
	default:
		return false;
	}
  }

}

  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  3. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  4. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }