ring.java

第四届百度杯编程大赛final解题报告+标程

import java.io.*;
import java.util.*;

public class ring {
	static final int max_word = 100;
	static Scanner cin;

	static int n, m;

	static class AC_Automaton {
	    static final int max_set_size = (max_word >> 5) + 1;
	    
	    class node {
	        int g[] = new int[26];
	        int f;
	        int out[] = new int[max_set_size];
	        int value;
	        char ch;
	        node(final char _ch) {
	        	for (int i = 0; i < max_set_size; i++)
	        		out[i] = 0;
	        	for (int i = 0; i < 26; i++)
	        		g[i] = 0;
	            f = 0;
	            value = 0;
	            ch = _ch;
	        }
	    };
	    
	    int dictlen = 0;
	    node dict[] = new node[1010];
	    int w[] = new int[max_word];
	    int cnt_word;
	    
	    void set_bit(final int now, final int p) {
	        dict[now].out[p >>> 5] |= 1 << (p & 31);
	    }
	    
	    int get_bit(final int now, final int p) {
	        return ((dict[now].out[p >>> 5]) >>> (p & 31)) & 1;
	    }
	    
	    void union_out(final int a, final int b) {
	        dict[a].value = 0;
	        for (int i = 0; i < max_set_size; i++) {
	            dict[a].out[i] |= dict[b].out[i];
	            for (int j = 0; j < 32; j++) {
	                if (((dict[a].out[i] >>> j) & 1) != 0) {
	                    dict[a].value += w[(i << 5) + j];
	                }
	            }
	        }
	    }
	    
	    AC_Automaton() {
	        dictlen = 0;
	        dict[dictlen++] = new node('*');
	        cnt_word = 0;
	    }
	    
	    void insert(String word) {
	        int now = 0;
	        int p = 0;
	        while (p < word.length()) {
	            if (dict[now].g[word.charAt(p) - 'a'] == 0) {
	            	dict[now].g[word.charAt(p) - 'a'] = dictlen;
	                now = dictlen;
	                dict[dictlen++] = new node(word.charAt(p));
	            } else {
	                now = dict[now].g[word.charAt(p) - 'a'];
	            }
	            p++;
	        }
	        set_bit(now, cnt_word++);
	    }
	    
	    void read_w() {
	        for (int i = 0; i < m; i++) {
	        	w[i] = cin.nextInt();
	        }
	    }
	    
	    void make_AC() {
	    	int l, r;
	    	int q[] = new int[100000];
	    	l = 0;
	    	r = 0;
	        for (int i = 0; i < 26; i++) {
	            int u = dict[0].g[i];
	            if (u != 0) {
	                q[r++] = u;
	                dict[u].f = 0;
	                union_out(u, u);
	            }
	        }
	        while (l < r) {
	            int now = q[l++];
	            for (int i = 0; i < 26; i++) {
	                int u = dict[now].g[i];
	                if (u != 0) {
	                    q[r++] = u;
	                    int v = dict[now].f;
	                    while (dict[v].g[i] == 0 && v != 0) v = dict[v].f;
	                    dict[u].f = dict[v].g[i];
	                    union_out(u, dict[u].f);
	                }
	            }
	        }
	    }

	    void print() {
	        for (int i = 0; i < dictlen; i++) {
	            System.out.printf("%d(%c): f=%d, value=%d, out=(", i, dict[i].ch, dict[i].f, dict[i].value);
	            for (int j = 0; j < max_word; j++) {
	                if (get_bit(i, j) != 0) {
	                	System.out.printf("%d ", j);
	                }
	            }
	            System.out.printf(")  ");
	            System.out.printf("(");
	            for (int j = 0; j < 26; j++)
	                if (dict[i].g[j] != 0) {
	                	System.out.printf("%d ", dict[i].g[j]);
	                }
	            System.out.printf(")\n");
	        }
	    }
	}

	static final int max_len = 100;
	static final int max_size = 1010;
	static int f[][] = new int[max_len][max_size];
	static int pre[][] = new int[max_len][max_size];

	static AC_Automaton ac;

	static void print(int i, int j) {
	    if (j != 0) {
	    	System.out.printf("%c", ac.dict[j].ch);
	        print(i - 1, pre[i][j]);
	    }
	}

	static boolean better(int flag, int i1, int j1, char last, int add, int i2, int j2) {
	    if (f[i1][j1] + add > f[i2][j2])
	        return true;
	    if (f[i1][j1] + add < f[i2][j2])
	        return false;
	    
	    if (flag != 0) {
	        if (i1 + 1 < i2)
	            return true;
	        if (i1 + 1 > i2)
	            return false;
	        
	        if (last < ac.dict[j2].ch)
	            return true;
	        if (last > ac.dict[j2].ch)
	            return false;
	        j2 = pre[i2--][j2];
	    } else {
	        if (i1 < i2)
	            return true;
	        if (i1 > i2)
	            return false;
	    }
	    
	    while (i2 != 0 || i1 != 0) {
	        char last1 = ac.dict[j1].ch;
	        char last2 = ac.dict[j2].ch;
	        if (last1 < last2)
	            return true;
	        if (last1 > last2)
	            return false;
	        j1 = pre[i1--][j1];
	        j2 = pre[i2--][j2];
	    }
	    return i1 < i2;
	}

	public static void main(String args[]) throws Exception {
		cin = new Scanner(System.in);
	    int ca = cin.nextInt();
	    for (int c = 0; c < ca; c++) {
	        ac = new AC_Automaton();
	        n = cin.nextInt();
	        m = cin.nextInt();
	        for (int i = 0; i < m; i++) {
	            String buf = cin.next();
	            StringBuilder buf1 = new StringBuilder(buf);
	            buf1.reverse();
	            buf = buf1.toString();
	            ac.insert(buf);
	        }
	        ac.read_w();
	        ac.make_AC();

	        for (int i = 0; i < max_len; i++)
	        	for (int j = 0; j < max_size; j++) {
	        		f[i][j] = -1;
	        		pre[i][j] = 0;
	        	}

	        f[0][0] = 0;
	        int ans = 0;
	        int ans_ptr_i = 0, ans_ptr_j = 0;
	        
	        for (int i = 0; i < n; i++) {
	            for (int j = 0; j < ac.dictlen; j++) {
	                if (f[i][j] != -1) {
	                    for (int k = 0; k < 26; k++) {
	                        int next = ac.dict[j].g[k];
	                        for (int xx = 0; xx < 2; xx++) {
	                            if (next != 0) {
	                                if (better(1, i, j, (char)(k + 'a'), ac.dict[next].value, i + 1, next)) {
	                                    f[i + 1][next] = f[i][j] + ac.dict[next].value;
	                                    pre[i + 1][next] = j;
	                                }
	                                if (ac.dict[next].value != 0 && better(0, i + 1, next, (char)(0), 0, ans_ptr_i, ans_ptr_j)) {
	                                    ans = f[i + 1][next];
	                                    ans_ptr_i = i + 1;
	                                    ans_ptr_j = next;
	                                }
	                            }
	                            int p = ac.dict[j].f;
	                            while (ac.dict[p].g[k] == 0 && p != 0)
	                                p = ac.dict[p].f;
	                            next = ac.dict[p].g[k];
	                        }
	                    }
	                }
	            }
	        }
//	        printf("%d\n", ans);
	        print(ans_ptr_i, ans_ptr_j);
	        System.out.printf("\n");
	    }
	}

}