首页 > 专题系列 > Java解POJ > POJ 2513 Colored Sticks [解题报告] Java
2013
11-11

POJ 2513 Colored Sticks [解题报告] Java

Colored Sticks

问题描述 :

You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color. Is it possible to align the sticks in a straight line such that the colors of the endpoints that touch are of the same color?

输入:

Input is a sequence of lines, each line contains two words, separated by spaces, giving the colors of the endpoints of one stick. A word is a sequence of lowercase letters no longer than 10 characters. There is no more than 250000 sticks.

输出:

If the sticks can be aligned in the desired way, output a single line saying Possible, otherwise output Impossible.

样例输入:

blue red
red violet
cyan blue
blue magenta
magenta cyan

样例输出:

Possible

温馨提示:

Huge input,scanf is recommended.

解题代码:

//* @author:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
 int sum = 0;
 int time[] = new int[500000];
 int parent[] = new int[500000];
 int rank[] = new int[500000];
 trieT root;

 void ini() {
  root = new trieT();
  for (int i = 0; i < 500000; i++)
	parent[i] = i;
 }

public static void main(String[] args) throws IOException {
  BufferedReader re = new BufferedReader(new InputStreamReader(System.in));
  Main p = new Main();
  p.ini();
  int a = 0;
  int b = 0;
  int qtime = 0;

  String tmp = re.readLine();
  while (tmp!=null) {

	a = p.insert(tmp.split(" ")[0].toCharArray(), p.root);
	b = p.insert(tmp.split(" ")[1].toCharArray(), p.root);
	p.time[a]++;
	p.time[b]++;
	tmp = re.readLine();
	if (a != b)
		p.union(a, b);
    }
	
  for (int i = 0; i < p.sum; i++)
	if (p.time[i] % 2 != 0)
		qtime++;
  int k = p.find(0);
  for (int i = 1; i < p.sum; i++)
	if (k != p.find(i)) {
         System.out.println("Impossible");
	  return;
	}
  if (qtime <= 2)
	System.out.println("Possible");
  else
	System.out.println("Impossible");

 }


 int find(int x) {
   if (parent[x] != x) {
	parent[x] = find(parent[x]);
   }
  return parent[x];
 }

 void union(int a, int b) {
   int fa = find(a);
   int fb = find(b);
   if (fa == fb)
	return;
   if (rank[fa] > rank[fb])
	parent[fb] = fa;
   else if (rank[fa] < rank[fb])
	parent[fa] = fb;
   else {
	parent[fa] = fb;
	rank[fb]++;
   }
  }

  int insert(char[] key, trieT trie) {
   for (int i = 0; i < key.length; i++) {
	int index = key[i] - 'a';
	if (trie.child[index] == null) {
         trie.child[index] = new trieT();
	}
	trie = trie.child[index];
    }
    if (trie.count == -1)
	trie.count = sum++;
    return trie.count;
  }
}
class trieT {
	int count = -1;
	trieT child[] = new trieT[26];

	public trieT() {
         for (int i = 0; i < 26; i++)
		child[i] = null;

	}

}

  1. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

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

  5. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的