ZOJ Monthly, January 2015 (B、E、G、H)

ZOJ Monthly, January 2015 (B、E、G、H)

B題：

先處理出已有卡牌，然後進行dfs，dfs有個很大的剪枝，就是當前位置如果字典序小於了，那麼後面就不用繼續放了，直接用組合數學進行計算即可，如果大於就不用考慮了，如果等於才繼續往後搜，這樣的話，搜等於只要在字典序相等的一條路上搜，時間可以接受

E題：模擬即可，不存在無解情況

G題：先全部數字GCD一遍，如果不為1，就是無解，如果為1，那麼構造答案，其實只要拿第一個數字，可以其他每個數字做一次gcd，第一個數字就是1了，然後再拿第一個數字和後面數字做gcd，就全部都是1了，一共進行n - 2次

H題：這題有個大坑啊，字符串居然只要滿足是子串就可以了- -，感覺題目說的不是那麼清楚，於是只要把已有字符串構造一棵字典樹，然後dp[x][y][u],表示當前在x，y這個位置，在字典樹中位置為u的狀態需要的最小步樹，然後進行最短路即可，遇到單詞結點的時候，可以記錄一下答案的最小值

代碼：

B：

#include 
#include 

typedef long long ll;
const int MOD = 1000000007;
char str[105];

int st[52], have[14], stn, hn, C[105][105];

int cal(int tot) {
    int ans = 1;
    for (int i = 1; i <= 13; i++) {
	if (have[i]) {
	    ans = (int)((ll)ans * C[tot][have[i]] % MOD);
	    tot -= have[i];
	}
    }
    return ans;
}

int dfs(int u) {
    int ans = 0;
    if (u == stn) return 0;
    if (hn - u == 0) return 1;
    for (int i = 1; i <= st[u]; i++) {
	if (!have[i]) continue;
	have[i]--;
	if (i == st[u]) {
	    ans = (ans + dfs(u + 1)) % MOD;
	}
	else if (i < st[u]) {
	    ans = (ans + cal(hn - u - 1)) % MOD;
	}
	have[i]++;
    }
    return ans;
}

int main() {
    for (int i = 0; i < 105; i++) {
	C[i][0] = C[i][i] = 1;
	for (int j = 1; j < i; j++) {
	    C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
	}
    }
    while (gets(str) != NULL) {
	stn = 0;
	hn = 0;
	int len = strlen(str);
	memset(have, 0, sizeof(have));
	for (int i = 0; i < len; i++) {
	    if (str[i] == 'A') st[stn++] = 1;
	    else if (str[i] == '1') {
		st[stn++] = 10;
		i++;
	    }
	    else if (str[i] >= '2' && str[i] <= '9')
		st[stn++] = str[i] - '2' + 2;
	    else if (str[i] == 'J') st[stn++] = 11;
	    else if (str[i] == 'Q') st[stn++] = 12;
	    else if (str[i] == 'K') st[stn++] = 13;
	    have[st[stn - 1]]++;
	}
	for (int i = 1; i <= 13; i++) {
	    have[i] = 4 - have[i];
	    hn += have[i];
	}
	printf("%d\n", dfs(0));
    }
    return 0;
}

#include 
#include 
#include 
using namespace std;

const int N = 15;
const int INF = 0x3f3f3f3f;

int t, n, a[N];

void gao() {
    while (1) {
	int Min = INF, Max = -INF;
	int Minv, Maxv;
	for (int i = 0; i < n; i++) {
	    if (Min > a[i]) {
		Min = a[i];
		Minv = i;
	    }
	    if (Max < a[i]) {
		Max = a[i];
		Maxv = i;
	    }
	}
	if (Min == Max) break;
	a[Minv] = a[Maxv] = Max - Min;
    }
}

int main() {
    scanf("%d", &t);
    while (t--) {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	    scanf("%d", &a[i]);
	gao();
	printf("%d\n", a[0]);
    }
    return 0;
}

#include 
#include 

const int N = 100005;

int gcd(int a, int b) {
    if (!b) return a;
    return gcd(b, a % b);
}

int n, a;

int main() {
    int cas = 0;
    while (~scanf("%d", &n)) {
	int s = 0;
	for (int i = 0; i < n; i++) {
	    scanf("%d", &a);
	    s = gcd(s, a);
	}
	printf("Case %d: ", ++cas);
	if (s != 1) {
	    printf("-1\n");
	} else {
	    printf("%d\n", 2 * n - 2);
	    for (int i = 2; i <= n; i++)
		printf("1 %d\n", i);
	    for (int i = 2; i <= n; i++)
		printf("1 %d\n", i);
	}
	printf("\n");
    }
    return 0;
}

#include 
#include 
#include 
#include 
using namespace std;

const int N = 25;
const int MAXN = 20005;
const int INF = 0x3f3f3f3f;

int t, n, m;
char str[N][N], s[105];

int ch[MAXN][26], sz, dp[N][N][MAXN];
bool val[MAXN];

void init() {
    sz = 0;
    memset(val, 0, sizeof(val));
    memset(ch[0], 0, sizeof(ch[0]));
}

int idx(char c) {
    return c - 'A';
}

void insert(char *str) {
    int len = strlen(str);
    int u = 0;
    for (int i = 0; i < len; i++) {
	int c = idx(str[i]);
	if (!ch[u][c]) {
	    ch[u][c] = ++sz;
	    memset(ch[sz], 0, sizeof(ch[sz]));
	}
	u = ch[u][c];
    }
    val[u] = true;
}

struct State {
    int x, y, u, val;
    State() {}
    State(int x, int y, int u, int val) {
	this->x = x;
	this->y = y;
	this->u = u;
	this->val = val;
    }
    bool operator < (const State& c) const {
	return val > c.val;
    }
};

const int d[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};

int main() {
    scanf("%d", &t);
    while (t--) {
	priority_queue Q;
	scanf("%d%d", &n, &m);
	memset(dp, INF, sizeof(dp));
	for (int i = 0; i < n; i++) {
	    scanf("%s", str[i]);
	    for (int j = 0; j < m; j++) {
		if (str[i][j] == '@') {
		    Q.push(State(i, j, 0, 0));
		    dp[i][j][0] = 0;
		}
	    }
	}
	int q;
	int ans = INF;
	scanf("%d", &q);
	init();
	while (q--) {
	    scanf("%s", s);
	    insert(s);
	}
	while (!Q.empty()) {
	    State now = Q.top();
	    Q.pop();
	    if (val[now.u])
		ans = min(ans, now.val);
	    if (now.val >= ans) continue;
	    for (int i = 0; i < 4; i++) {
		int x = now.x + d[i][0];
		int y = now.y + d[i][1];
		if (x < 0 || x >= n || y < 0 || y >= m || str[x][y] == '#') continue;
		if (dp[x][y][0] > now.val + 1) {
		    dp[x][y][0] = now.val + 1;
		    Q.push(State(x, y, 0, now.val + 1));
		}
		if (str[x][y] >= 'A' && str[x][y] <= 'Z') {
		    int u = now.u;
		    int c = idx(str[x][y]);
		    while (1) {
			u = ch[u][c];
			if (u == 0) break;
			if (dp[x][y][u] > now.val + 1) {
			    dp[x][y][u] = now.val + 1;
			    Q.push(State(x, y, u, now.val + 1));
			}
		    }
		} else {
		    int u = now.u;
		    if (dp[x][y][u] > now.val + 1) {
			dp[x][y][u] = now.val + 1;
			Q.push(State(x, y, u, now.val + 1));
		    }
		}
	    }
	}
	if (ans == INF) ans = -1;
	printf("%d\n", ans);
    }
    return 0;
}