2014-12-27

UVa 1482 - Playing With Stones

Problem

有 N 堆石頭，每次選一堆，只能不能拿大於一半的石頭總數。

求兩個人都採用最佳策略，請問誰輸誰贏。

Sample Input

Sample Output

NO 
YES 
NO 
YES

Solution

建造 SG 函數進行觀察，接著直接套用 SG 函數的 nim 規則。

關於 SG

让我们再来考虑一下顶点的SG值的意义。当g(x)=k时，表明对于任意一个0<=i<k，都存在x的一个后继y满足g(y)=i。也就是说，当某枚棋子的SG值是k时，我们可以把它变成0、变成1、……、变成k-1，但绝对不能保持k不变。不知道你能不能根据这个联想到Nim游戏， Nim游戏的规则就是：每次选择一堆数量为k的石子，可以把它变成0、变成1、……、变成k-1，但绝对不能保持k不变。这表明，如果将n枚棋子所在的顶点的SG值看作n堆相应数量的石子，那么这个Nim游戏的每个必胜策略都对应于原来这n枚棋子的必胜策略！

http://baike.baidu.com/view/2855458.htm

Sprague-Grundy 圖示演說參考

對於博弈，一直以來盡可能靠記憶化搜索 dp 完成，寫題基本上也還算過得去，在大數據的題目上，除了幾個噁心的數學分析外，利用記憶化搜索進行小數據觀察，真的沒搞頭的題目，大多解法是所謂的 SG 函數 (Sprague-Grundy)。

再不學點新的，就要沒有看得懂的題目可以刷了 … 如果因為看不懂題目，而增加對英文的仇恨值，都不知道溢位幾個世紀去了。

SG 函數簡單而言是對於針對某一類型的博弈遊戲，可以轉換成 Nim 遊戲，每一個 SG 函數的 value 對應 Nim 遊戲中一堆石頭的個數。新世界！

#include <stdio.h>
#include <string.h>
void buildSG() { // observe rule
    int mex[1024] = {}, SG[50];
    SG[0] = 0;
    for (int i = 1; i < 50; i++) {
        memset(mex, 0, sizeof(mex));
        for (int j = 1; j <= i/2; j++)
            mex[SG[i - j]] = 1;
        int sg = 0;
        for (sg = 0; mex[sg]; sg++);
        SG[i] = sg;
        printf("%d : %d\n", i, SG[i]);
    }
}
long long SG(long long x) {
    return x%2 == 1 ? SG(x/2) : x/2; 
}
int main() {
//	buildSG();
    int testcase, n;
    long long x;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        long long ret = 0;
        for (int i = 0; i < n; i++) {
            scanf("%lld", &x);
            ret ^= SG(x);
        }
        puts(ret ? "YES" : "NO");
    }
    return 0;
}

Read More +

2014-12-27

解題區/解題區 - UVa

UVa 1404 - Prime k-tuple

Problem

查找區間內，相鄰 k 個質數中，滿足最大減最小恰好為 s 的情況有多少個。

Sample Input

1 2	1 100 200 4 8

Sample Output

Solution

a, b 大小簡直不可思議，就算能做到全搜索，建表時間是線性，也必須跑上 20 億乘上 20。

先做一次 sieve，接著對 [a, b] 進行 local sieve，題目雖然沒說明 b - a 的大小，實際看來是非常小的。

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
using namespace std;
#define maxL (50000>>5)+1
#define MAXN (2000000000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
#define GET2(x) (mark2[x>>5]>>(x&31)&1)
#define SET2(x) (mark2[x>>5] |= 1<<(x&31))
int mark[maxL], mark2[MAXN];
int P[5500], Pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 50000;
    for(i = 2; i <= n; i++) {
            if(!GET(i)) {
            for (k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
int local_sieve(int a, int b, int k, int s) {	
    int sqr = sqrt(b), gap = b - a;
    memset(mark2, 0, ((gap>>5) + 1) * 4);
    
    for (int i = 0; i < Pt && P[i] <= sqr; i++) {
        int p = P[i], base = a / p * p;
        while (base <= p)	base += p;
        for (int j = base; j <= b; j += p)
            SET2(j - a);
    }
    if (a == 1)	SET2(0);
    queue<int> Q;
    int ret = 0;
    for (int i = 0; i <= gap; i++) {
        if (!GET2(i)) {
            if (Q.size() == k - 1) {
                if (k == 0)
                    ret += s == 0;
                else if ((a + i) - Q.front() == s)
                    ret++;
            }
            Q.push(a + i);
            while (Q.size() >= k)	Q.pop();
        }
    }
    return ret;
}
int main() {
    sieve();
    
    int testcase;
    int a, b, k, s;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d %d", &a, &b, &k, &s);
        printf("%d\n", local_sieve(a, b, k, s));
    }
    return 0;
}

Read More +

2014-12-27

解題區/解題區 - UVa

UVa 1291 - Dance Dance Revolution

Problem

跳舞機共有四個方向，兩隻腳必須在某一個時刻按到該按鈕。

1
2
3

#1#
204
#3#

一開始雙腳站立於 0 的位置，每一個時刻只能移動一隻腳。

每一次移動的花費，0 到任何位置都是消耗體力 2、其餘數字移動到相鄰格子消耗體力 3、其餘數字移動到相面格子消耗體力 4，腳不動消耗體力 1。

過程中雙腳不能站立於同一個格子。

Sample Input

1
2
3

1 2 2 4 0 
1 2 3 4 1 2 3 3 4 2 0 
0

Sample Output

1
2

8 
22

Solution

dp[i][j][k] 分別記錄時刻 i，左腳所在位置 j，右腳所在位置 k。分別進行轉移即可。

#include <stdio.h>
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
int A[32767];
int cg[5][5] = {
    {0, 2, 2, 2, 2},
    {INF, 1, 3, 4, 3},
    {INF, 3, 1, 3, 4},
    {INF, 4, 3, 1, 3},
    {INF, 3, 4, 3, 1}
};
int main() {
    while (scanf("%d", &A[0]) == 1 && A[0]) {
        int n = 1;
        for (; scanf("%d", &A[n]) && A[n]; n++);
        int dp[2][5][5]; // [][left][right]
        memset(dp, 0x3f, sizeof(dp));
        int p = 0, q = 1;
        dp[p][0][0] = 0;
        for (int i = 0; i < n; i++) {
            p = !p, q = !q;
            memset(dp[p], 0x3f, sizeof(dp[p]));
            for (int j = 0; j < 5; j++) {
                for (int k = 0; k < 5; k++) {
                    int l = A[i];
                    if (j != l) {
                        dp[p][j][l] = min(dp[p][j][l], dp[q][j][k] + cg[k][l]);
                    }
                    if (k != l) {
                        dp[p][l][k] = min(dp[p][l][k], dp[q][j][k] + cg[j][l]);
                    }
                    if (j == l || k == l) {
                        dp[p][j][k] = min(dp[p][j][k], dp[q][j][k] + 1);
                    }
                }
            }
        }
        
        int ret = INF;
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                ret = min(ret, dp[p][i][j]);
            }
        }
        
        printf("%d\n", ret);
    }
    return 0;
}
/*
 1 2 2 4 0
 1 2 3 4 1 2 3 3 4 2 0
 0
 */

Read More +

2014-12-27

解題區/解題區 - UVa

UVa 1267 - Network

Problem

有一個 N 節點的樹，要架設服務的 server，必須滿足所有葉節點到最近的 server 距離小於等於 M。一開始會給定一個架好的 server。

求最少的放置個數。

Sample Input

Sample Output

1
2

1 
0

Solution

針對加好的 server，將這個 server 當作 root，將 tree 轉換成 rooted tree，接著使用貪心。

盡可能放置越遠越好，根據 dfs 搜索的順序，查看內部節點 u，其子樹最遠的葉節點深度為何，以及子樹內部距離最近的 server 所在。

共計三種可能

節點 u 逼不得已情況下放置 server
節點 u 無須 server，其子樹的葉節點都已經符合標準
節點 u 無須 server，其子樹的葉節點必須靠另外一個子樹的最近 server 服務。

#include <stdio.h> 
#include <vector>
#include <algorithm>
using namespace std;
vector<int> g[1024];
int n, m, s, x, y;
int ret = 0;
int dfs(int u, int p, int dep, int &place) {
    int leaf = 0, pp = 0x3f3f3f3f;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (v == p)
            continue;
        int p;
        int tmp = dfs(v, u, dep + 1, p);
        pp = min(p, pp);
        leaf = max(leaf, tmp);
    }
    place = pp;
    if (leaf - dep + pp - dep <= m)
        leaf = 0;
    if (leaf == dep + m) {
        place = dep;
        ret += (u != s), leaf = 0/*, printf("place %d, %d\n", u, place)*/;
    }
    if (g[u].size() == 1)
        return dep;
    else
        return leaf;
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &n, &s, &m);
        for (int i = 0; i <= n; i++)
            g[i].clear();
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &x, &y);
            g[x].push_back(y);
            g[y].push_back(x);
        }
        
        ret = 0;
        int foo;
        dfs(s, -1, 0, foo);
        printf("%d\n", ret);
    }
    return 0;
}
/*
2 
14 12 2 
1 2 
2 3 
3 4 
4 5 
5 6 
7 5 
8 5 
4 9 
10 3 
2 12 
12 14 
13 14 
14 11 
14 3 4 
1 2 
2 3 
3 4 
4 5 
5 6 
7 5 
8 5 
4 9 
10 3 
2 12 
12 14 
13 14 
14 11
*/

Read More +

2014-12-27

解題區/解題區 - UVa

UVa 1125 - Sherlock Holmes

Problem

有 N 個箱子，每個箱子都有 M 顆球，每一個箱子的黑、白球分配的個數不同，希望分成兩堆，每一堆必須有 N/2 個箱子，並且要符合黑球、或白球必須在兩堆佔有多數 (> 50%) 的情況。

假設佔有的比例分別為 m1, m2，最大化 min(m1, m2)。

Sample Input

Sample Output

W 51.67

Solution

N 很大，M 也很大。一開始就目測需要 random 的隨機交換法，這樣湊出答案的機率是挺高的。

當然這有點不靠譜，使用 dp 背包問題，由於狀態數量太多，必須使用 set 壓縮。

dp[i][j] 表示放置前 i 個箱子，存在 j 個數的球。

統計兩色的球總個數，個數多的必然是最後佔有多數，決定球顏色後，針對個數進行背包問題的計算，由於每個箱子的球總數一樣，分成兩堆時，分母是固定的，因此可以無視另一個顏色的存在。

#include <stdio.h>
#include <stdlib.h> 
#include <set>
#include <algorithm>
using namespace std;
int main() {
    int n, m, A[32767];
    while (scanf("%d %d", &n, &m) == 2) {
        int w, b, wsum = 0, bsum = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &w, &b);
            wsum += w, bsum += b;
            A[i] = w;
        }
        if (wsum == bsum || n%2 != 0) {
            puts("No solution");
            continue;
        }
        char major = 'W';
        if (wsum < bsum) {
            major = 'B';
            wsum = bsum;
            for (int i = 0; i < n; i++)
                A[i] = m - A[i];
        }
        set<int> dp[32767];
        set<int>::iterator it;
        dp[0].insert(0);
        for (int i = 0; i < n; i++) {
            int w = A[i];
            for (int j = min(i, n/2 - 1); j >= 0; j--) {
                for (it = dp[j].begin(); it != dp[j].end(); it++)
                    dp[j+1].insert((*it) + w);
            }
        }
        
        int ret = -1;
        int half = n/2 * m / 2;
        for (it = dp[n/2].begin(); it != dp[n/2].end(); it++) {
            if (*it <= wsum/2 && *it > half)
                ret = max(ret, *it);
        }
        if (ret < 0) {
            puts("No solution");
        } else {
            printf("%c %.2lf\n", major, ret * 100.0 / (n/2 * m));
        }
    }
    return 0;
}

Read More +

2014-12-27

解題區/解題區 - UVa

UVa 881 - Points, Polygons and Containers

Problem

有數個不相交的簡單多變形，構成類似等高線的地勢圖，每一個簡單多邊形都有其代碼編號，接著有數個不按照順序的詢問點，請問所在的位置是在哪一塊。

Sample Input

1
4
3 18 16 1 16 1 1 18 1
1 2 15 2 2 14 2
4 15 2 15 15 3 15
2 10 4 4 10 4 4
4
2 20 4
4 3 11
3 5 6
1 12 11

Sample Output

Solution

首先用射線法，找到所有的簡單多邊形關係，O(n^2) 找到 DAG 圖。

接著將 DAG 圖縮成一個 rooted tree 圖，挑選深度最深的節點，外圍的深度是 0，越靠近裡面深度越高。

接著對於每一組詢問，從 root 開始走訪，直到沒有可以包含住這個點。

#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <iostream>
#include <assert.h>
using namespace std;
#define eps 1e-8
#define MAXN 1024
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
    bool operator==(const Pt &a) const {
        return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    } 
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
int inPolygon(Pt p[], int n, Pt q) {
    int i, j, cnt = 0;
    for(i = 0, j = n-1; i < n; j = i++) {
        if(onSeg(p[i], p[j], q))
            return 1;
        if(p[i].y > q.y != p[j].y > q.y &&
            q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
            cnt++;
    }
    return cnt&1;
}
const double pi = acos(-1);
Pt polygon[MAXN][512];
int pn[MAXN], parent[MAXN], visited[MAXN], depth[MAXN];
int pid[MAXN];
vector<int> g[MAXN], tree[MAXN];
void dfs(int u) {
    visited[u] = 1, depth[u] = 0, parent[u] = -1;
    int d = -1;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (visited[v] == 0)	dfs(v);
        if (depth[v] > d)
            d = depth[v], parent[u] = v;
    }
    depth[u] = d + 1;
}
int query(int u, Pt q) {
    for (int i = 0; i < tree[u].size(); i++) {
        int v = tree[u][i];
        if (inPolygon(polygon[v], pn[v], q)) {
            return query(v, q);
        }
    }
    return u;
}
int main() {
    int testcase, n, m;
    string line;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        assert(n < MAXN);
        while (getchar() != '\n');
        for (int i = 0; i < n; i++) {
            getline(cin, line);
            stringstream sin(line);
            int m = 0;
            sin >> pid[i];
            while (sin >> polygon[i][m].x >> polygon[i][m].y) {
                m++;
                assert(m < 512);
            }
            pn[i] = m;
        }
        pid[n] = 0;
        for (int i = 0; i <= n; i++)
            g[i].clear(), visited[i] = 0, tree[i].clear();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j)	continue;
                if (inPolygon(polygon[i], pn[i], polygon[j][0]))
                    g[j].push_back(i);
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (visited[i] == 0)
                dfs(i);
        }
        for (int i = 0; i < n; i++)
            if (parent[i] == -1)
                tree[n].push_back(i);
            else
                tree[parent[i]].push_back(i);
//		for (int i = 0; i < n; i++)
//			printf("%d: %d\n", pid[i], parent[i]);
        scanf("%d", &m);
        assert(m < 32767);
        int out[32767] = {};
        for (int i = 0; i < m; i++) {
            Pt q;
            int id;
            scanf("%d %lf %lf", &id, &q.x, &q.y);
            assert(id <= m);
            out[id] = query(n, q);
        }
        for (int i = 1; i <= m; i++)
            printf("%d %d\n", i, pid[out[i]]);
        if (testcase)
            puts("");
    }
    return 0;
}
/*
5
0 0
50 50
100 0
100 100
0 100
2
49 50
50 51
7
0 5
5 0
10 7
15 0
20 5
15 10
5 10
7
0 5
5 0
10 7
15 0
20 5
15 10
5 10
*/

Read More +

2014-12-27

解題區/解題區 - UVa

UVa 879 - Circuit Nets

Problem

給定一組電路的連接，請問有多少個電網個數。

Sample Input

1
14
 1 11 7 11 2 12 12 8 11 12 3 13 4 13 13 14
14  9 5 14 6 10

Sample Output

Solution

單純查找連通子圖的個數，使用并查集完成。

#include <stdio.h>
#include <sstream>
using namespace std;
int parent[65536], weight[65536];
int findp(int x) {
    return parent[x] == x ? x : parent[x] = findp(parent[x]);
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if (x == y)	return 0;
    if (weight[x] > weight[y])
        parent[y] = x, weight[x] += weight[y];
    else
        parent[x] = y, weight[y] += weight[x];
    return 1;
}
int main() {
    int testcase, n;
    char line[1024];
    scanf("%d", &testcase);
    while (getchar() != '\n');
    while (getchar() != '\n');
    while (testcase--) {
        scanf("%d", &n);
        while (getchar() != '\n');
        for (int i = 0; i < n; i++)
            parent[i] = i, weight[i] = 1;
        int ret = n, x, y;
        while (gets(line) && line[0] != '\0') {
            stringstream sin(line);
            while (sin >> x >> y) {
                x--, y--;
                ret -= joint(x, y);
            }
        }
        printf("%d\n", ret);
        if (testcase)
            puts("");
    }
    return 0;
}
/*
1
14
 1 11 7 11 2 12 12 8 11 12 3 13 4 13 13 14
14  9 5 14 6 10 
*/

Read More +

2014-12-27

解題區/解題區 - UVa

UVa 844 - Pousse

Problem

模擬一款推硬幣的遊戲，在一個 N x N 的盤面，可以從上下左右四個方向塞入自己的硬幣。

現在有兩個人輪流玩，一開始由 ‘X’ 作為先手，塞入硬幣的過程中，會將同行或同列的硬幣往前推，如果同一個的硬幣個數大於 N，則末端的硬幣將會掉出盤面。

模擬遊戲，直到其中一個玩家的連線個數大於另一名玩家，連線個數只看行、列皆具有相同硬幣的情況。

Sample Input

2
4
L2
T2
L2
B2
R2
QUIT
4
L2
T2
L2
B2
R2
T1
L2
QUIT

Sample Output

1
2
3

TIE GAME
X WINS

Solution

#include <stdio.h> 
#include <string.h>
char cmd[32767][64];
char g[128][128];
int n;
int isCompleted() {
    int Oline = 0, Xline = 0, cnt;
    char c;
    for (int i = 0; i < n; i++) {
        c = g[i][0], cnt = 0;
        for (int j = 0; g[i][0] == g[i][j] && j < n; cnt++, j++);
        if (cnt == n && c != ' ') {
            Oline += c == 'O';
            Xline += c == 'X';
        }
        c = g[0][i], cnt = 0;
        for (int j = 0; g[0][i] == g[j][i] && j < n; cnt++, j++);
        if (cnt == n && c != ' ') {
            Oline += c == 'O';
            Xline += c == 'X';
        }
    }
    return Oline == Xline ? 0 : (Oline < Xline ? -1 : 1);
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        int m = 0;
        while (scanf("%s", cmd[m]) == 1) {
            if (!strcmp(cmd[m], "QUIT"))
                break;
            m++;
        }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                g[i][j] = ' ';
        int ret = 0, turn = 0;
        for (int i = 0; i < m; i++, turn = !turn) {
            int x;
            sscanf(cmd[i]+1, "%d", &x);
            x--;
            if (cmd[i][0] == 'L') {
                int idx = 0;
                while (idx < n && g[x][idx] != ' ')	idx++;
                for (int i = idx; i > 0; i--)
                    g[x][i] = g[x][i-1];
                g[x][0] = turn ? 'O' : 'X';
            }
            if (cmd[i][0] == 'R') {
                int idx = n-1;
                while (idx > 0 && g[x][idx] != ' ')	idx--;
                for (int i = idx; i < n-1; i++)
                    g[x][i] = g[x][i+1];
                g[x][n-1] = turn ? 'O' : 'X';
            }
            if (cmd[i][0] == 'T') {
                int idx = 0;
                while (idx < n && g[idx][x] != ' ')	idx++;
                for (int i = idx; i > 0; i--)
                    g[i][x] = g[i-1][x];
                g[0][x] = turn ? 'O' : 'X';
            }			
            if (cmd[i][0] == 'B') {
                int idx = n-1;
                while (idx > 0 && g[idx][x] != ' ')	idx--;
                for (int i = idx; i < n-1; i++)
                    g[i][x] = g[i+1][x];
                g[n-1][x] = turn ? 'O' : 'X';
            }
//			for (int i = 0; i < n; i++, puts(""))
//				for (int j = 0; j < n; j++)
//					putchar(g[i][j]);
//			puts("---");
            if (ret = isCompleted())
                break;
        }
        if (ret)
            puts(ret < 0 ? "X WINS" : "O WINS");
        else
            puts("TIE GAME");
        if (testcase)
            puts("");
    }
    return 0;
}
/*
2
4
L2
T2
L2
B2
R2
QUIT
4
L2
T2
L2
B2
R2
T1
L2
QUIT
*/

Read More +

2014-12-27

解題區/解題區 - UVa

UVa 828 - Deciphering Messages

Problem

給一加密原則，現在要求解密，並且在只有一組文本情況下輸出正解。

一開始給定一字串 L，接著加密時，每一組訊息的 word，由左而右加密。

如果字符 c 存在於 L，使用凱薩加密 shift N 位。
如果字符 c 不存在於 L，輸出三個字浮，分別是 L[m]、c 使用凱薩加密 shift N 位、L[m+1]。每一次使用這一條 m 就 +1，假想 L 是環狀的。

Sample Input

1
RSAEIO
2
5
RTSSKAEAGE
GRSCAV
RGSSCAV
RUSIQO
RUSSGAACEV JEGIITOOGR

Sample Output

RICE
error in encryption
EAT
error in encryption
SEAT HERE

Solution

搜索，雖然看起來有點可怕，但是條件很多，如果搜索到兩種以上的情況，立即退出。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <sstream>
using namespace std;
int inL[128] = {}, N, Q, Llen;
char L[128], s[1024];
char text[128];
int sol;
void dfs(int idx, int pl, int m) {
    while (s[idx] == ' ')	text[pl++] = ' ', idx++;
    if (sol >= 2)	return;
    if (s[idx] == '\0') {
        sol++;
        text[pl] = '\0';
        puts(text);
        return;
    }
    
    char a, b, c;
    for (int i = 'A'; i <= 'Z'; i++) {
        if (inL[i]) {
            a = L[m%Llen];
            b = (i-'A'+N)%26 + 'A';
            c = L[(m+1)%Llen];
            text[pl] = i;
            if (a == s[idx] && b == s[idx+1] && c == s[idx+2]) {
                dfs(idx+3, pl+1, m+1);
            }
        } else {
            a = (i-'A'+N)%26 + 'A';
            text[pl] = i;
            if (a == s[idx]) {
                dfs(idx+1, pl+1, m);
            }
        } 
    }
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s", L);
        scanf("%d %d", &N, &Q);
        memset(inL, 0, sizeof(inL));
        for (int i = 0; L[i]; i++)
            inL[L[i]] = 1;
        Llen = strlen(L);
        while (getchar() != '\n');
        for (int i = 0; i < Q; i++) {
            gets(s);
            sol = 0;
            dfs(0, 0, 0);
            if (sol != 1)
                puts("error in encryption");
        }
        if (testcase)
            puts("");
    }
    return 0;
}

Read More +

2014-12-27

解題區/解題區 - UVa

UVa 818 - Cutting Chains

Problem

有 n 個鐵環，現在已知鐵環之間緊扣在一起，目標要把鐵環串成一鏈，可以選擇將鐵環剪開，隨後再將其串在一起。

找最少剪開的次數。

Sample Input

5 1 2 2 3 4 5 -1 -1
7 1 2 2 3 3 1 4 5 5 6 6 7 7 4 -1 -1
4 1 2 1 3 1 4 -1 -1
3 1 2 2 3 3 1 -1 -1
3 1 2 2 1 -1 -1
0

Sample Output

Set 1: Minimum links to open is 1
Set 2: Minimum links to open is 2
Set 3: Minimum links to open is 1
Set 4: Minimum links to open is 1
Set 5: Minimum links to open is 1

Solution

n < 15，窮舉哪幾個環需要剪開，接著把這些需要剪開的環先抽出來，查看剩餘的鐵環的情況，必須滿足都是鏈狀，而且連通元件的個數不能大於剪開的個數 + 1，如此一來，在放回剪開的環才能串在一起。

鏈狀的檢查：檢查每一個 node 的 degree 不可大於 2，同時不應該存在環。

#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
int g[16][16], gmask[16];
int visited[16];
int dfs(int u, int p, int open, int n) {
    visited[u] = 1;
    for (int i = 0; i < n; i++) {
        if ((open>>i)&1)
            continue;
        if (g[u][i] == 0 || i == p)
            continue;
        if (visited[i] || dfs(i, u, open, n))
            return 1;
    }
    return 0;
}
int checkChain(int open, int n) {
    for (int i = 0; i < n; i++) {
        if ((open>>i)&1)
            continue;
        int t = gmask[i]^(gmask[i]&open);
        int degree = __builtin_popcount(t);
        if (degree > 2)
            return 0;
    }
    
    int op = __builtin_popcount(open);
    int comp = 0;
    memset(visited, 0, sizeof(visited));
    for (int i = 0; i < n; i++) {
        if ((open>>i)&1)	continue;
        if (visited[i] == 0) {
            if (dfs(i, -1, open, n)) // have cycle
                return 0;
            comp++;
        }
    }
    return op >= comp - 1;
}
int main() {
    int cases = 0;
    int n, x, y;
    while (scanf("%d", &n) == 1 && n) {
        memset(g, 0, sizeof(g));
        memset(gmask, 0, sizeof(gmask));
        while (scanf("%d %d", &x, &y) == 2) {
            if (x == -1)	break;
            x--, y--;
            g[x][y] = g[y][x] = 1;
            gmask[x] |= 1<<y, gmask[y] |= 1<<x;
        }
        
        int ret = 0x3f3f3f3f;
        for (int i = 0; i < (1<<n); i++) { // 1: open.
            int op = __builtin_popcount(i);
            if (op >= ret)	continue;
            if (checkChain(i, n))
                ret = min(ret, op); 
        }
        printf("Set %d: Minimum links to open is %d\n", ++cases, ret);
    }
    return 0;
}

Read More +