2015-05-21

解題區/解題區 - 其他題目

ITSA 2015 第四屆桂冠賽

1. Problem A
2. Problem B
3. Problem C
4. Problem D
5. Problem E
6. Problem F
7. Problem G
8. Problem H
9. Problem I
10. Problem J
1. 10.1. Version 1
2. 10.2. Version 2
11. Problem K
12. 後記

有中文題目，那就不多做解釋，咱們直接來坑題解。由於我沒有參與比賽，目前也沒辦法進行 submit 測試我的代碼跟算法正確性。因此以下內容、代碼僅供參考。

題目已經放在 E-tutor，但沒提供測試功能，不能 submit 的 OJ 相當逗趣，再等幾天吧，也許在調數據的時間，或者是根本不打算弄好 … 也許是下一次舉辦比賽才完成。

看過一次題目，大約有下列特徵算法模擬、Bfs、樹形 dp、拓樸排序、最短路徑、dp、二分圖最大匹配、搜索優化、矩形并、掃描線、二分答案。有一題沒看懂，對於那題多維度部分，可能需要的是假解搜索。

有提供中文題目描述呢，不確定自己是否都看得懂，當然程式有點 bug 的話，歡迎大家來 challenge。

感謝各位提供的解法！讓我更了解 BWT $O(n)$ 逆變換。

Problem A

每一輪進行投票，將少數票的那一方留下，直接模擬運行即可，UVa 也有類似的題目。

#include <stdio.h>
#include <vector>
using namespace std;
int A[1024][512];
char s[16];
int main() {
    int testcase;
    int n, m;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf("%s", s);
                A[i][j] = s[0] == 'Y';
            }
        }
        
        vector<int> p;
        for (int i = 0; i < n; i++)
            p.push_back(i);
        for (int i = 0; i < m; i++) {
            int Y = 0;
            for (int j = 0; j < p.size(); j++)
                Y += A[p[j]][i] == 1;
            if (Y == p.size() - Y || Y == 0 || Y == p.size())
                continue;
            vector<int> np;
            for (int  j = 0; j < p.size(); j++) {
                if (Y < p.size() - Y) {
                    if (A[p[j]][i] == 1)
                        np.push_back(p[j]);
                } else {
                    if (A[p[j]][i] == 0)
                        np.push_back(p[j]);
                }
            }
            p = np;
        }
        
        for (int i = 0; i < p.size(); i++) {
            printf("%d%c", p[i]+1, i == p.size()-1 ? '\n' : ' ');
        }
    }
    return 0;
}

Problem B

兩個機器人運行的行動和週期不同，用 timeline 的方式去模擬兩台機器人的狀態，利用 time mod (N + E) 來得到當前屬於前 N 還是後 E。

#include <stdio.h>
#include <vector>
using namespace std;
int main() {
    int testcase;
    int N, M, N1, F1, N2, F2;
    int X1, Y1, E1, X2, Y2, E2;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &M, &N);
        scanf("%d %d %d %d %d", &X1, &Y1, &E1, &N1, &F1);
        scanf("%d %d %d %d %d", &X2, &Y2, &E2, &N2, &F2);
        
        int has = 0;
        for (int i = 0; i <= max(F1, F2); i++) {
            if (X1 == X2 && Y1 == Y2) {
                printf("robots explode at time %d\n", i);
                has = 1;
                break;
            }
            if (i < F1) {
                if (i%(N1 + E1) < N1)
                    Y1 = (Y1 + 1)%N;
                else
                    X1 = (X1 + 1)%M;
            }
            if (i < F2) {
                if (i%(N2 + E2) < E2)
                    X2 = (X2 + 1)%M;
                else
                    Y2 = (Y2 + 1)%N;
            }
        }
        
        if (!has)
            puts("robots will not explode");
    }
    return 0;
}

Problem C

樹中心 (把一點當根，到所有葉節點距離最大值越小越好)，其中一種方法是使用樹形 dp，另外一種方法是拓樸排序。保證樹中心會在最長路徑上的中點，當最長路徑是偶數個頂點構成，則中心會有兩個代表，反之會有一個。只會有這兩種情況。

那麼拓樸排序拔點，順便紀錄拓樸的深度 (分層去看)，看最後一層有一個點、還是兩個點，找字典順序最小的。

#include <stdio.h> 
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXN = 32767;
vector<int> g[MAXN];
int deg[MAXN], dist[MAXN];
int main() {
    int testcase, n, u, v;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            g[i].clear(), deg[i] = 0, dist[i] = -1;
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
            deg[u]++, deg[v]++;
        }
        
        queue<int> Q;
        for (int i = 0; i < n; i++)
            if (deg[i] == 1)
                Q.push(i), dist[i] = 1;
        while (!Q.empty()) {
            u = Q.front(), Q.pop();
            for (int i = 0; i < g[u].size(); i++) {
                v = g[u][i];
                if (--deg[v] == 1) {
                    dist[v] = dist[u] + 1;
                    Q.push(v);
                }
            }
        }
        
        int mx = 0, ret;
        for (int i = 0; i < n; i++) {
            if (dist[i] > mx)
                mx = dist[i], ret = i;
        }
        printf("%d\n", ret);
    }
    return 0;
}

Problem D

Bfs 搜索，定義狀態為 dist[x][y][dir] 表示從起點到 (x, y) 時，利用 dir 方向上的門進入的最短路徑，接著按照 Bfs 搜索到目的地。

#include <stdio.h> 
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
const int MAXN = 20;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0}; 
char sg[MAXN][MAXN][4][8];
int dist[MAXN][MAXN][4];
int toDir(char c) {
    switch(c) {
        case 'E': return 0;
        case 'S': return 1;
        case 'W': return 2;
        case 'N': return 3;
    }
    return -1;
}
void bfs(int dir, int sx, int sy, int ex, int ey) {
    queue<int> X, Y, D;
    memset(dist, 0, sizeof(dist));
    X.push(sx), Y.push(sy), D.push(dir);
    dist[sx][sy][dir] = 1;
    while (!X.empty()) {
        sx = X.front(), X.pop();
        sy = Y.front(), Y.pop();
        dir = D.front(), D.pop();
        if (sx == ex && sy == ey) {
            printf("%d\n", dist[sx][sy][dir]);
            return ;
        }
        for (int i = 0; sg[sx][sy][dir][i]; i++) {
            int d = toDir(sg[sx][sy][dir][i]);
            int tx, ty, td;
            tx = sx + dx[d], ty = sy + dy[d];
            td = (d + 2)%4;
            if (dist[tx][ty][td] == 0) {
                dist[tx][ty][td] = dist[sx][sy][dir]+1;
                X.push(tx), Y.push(ty), D.push(td);
            }
        } 
    }
    puts("Are you kidding me?");
}
int main() {
    int testcase;
    int n, m, q, x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf("%d %d", &x, &y);
                for (int k = 0; k < 4; k++)
                    scanf("%s", &sg[x][y][k]);
            }
        }
        
        scanf("%d", &q);
        for (int i = 0; i < q; i++) {
            int ex, ey, sx, sy;
            char s[8];
            scanf("%s %d %d %d %d", &s, &sx, &sy, &ex, &ey);
            bfs(toDir(s[0]), sx, sy, ex, ey);
        }
        puts("----------");
    }
    return 0;
}

Problem E

題目沒看懂，一扯到多維度計算，似乎每年都是同一個出題者嗎？有一種既視感。

Problem F

可以參照 Zerojudge 基因的核，找到多字串的 LCS 長度。但是這一題要求找到所有 LCS，而且還要按照字典順序排好，同時也不能輸出重複的。根據討論，輸出結果可能破百萬，那麼從輸出檔案中得知，這有點不科學大小，光是輸出有可能就會 TLE。

下方的代碼也許只有長度輸出是正確的，在輸出解部分有點問題，假設答案總數並不多，為了加速排序部分以及重複回溯，使用 trie 來輔助完成。若答案總數過多，會使得 trie 記憶體滿溢。

#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <set>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAXP = 1<<21;
const int MAXN = 4;
const int MAXL = 64;
char pwd[MAXN][MAXL];
int pwdLen[MAXN], A[MAXN], n, sumA;
char dp[MAXP];
int arg_dp[MAXP][2];
void dfs(int dep, int idx[], int v) {
    if (dep == n) {
        int same = 1;
        for (int i = 1; i < n; i++)
            same &= pwd[i][idx[i]] == pwd[0][idx[0]];
        if (same) {
            int s = 0;
            arg_dp[v][0] = -1, arg_dp[v][1] = pwd[0][idx[0]];
            for (int i = 0; i < n; i++) {
                if (idx[i] == 0) {
                    dp[v] = 1;
                    return ;
                }
                s = s + (idx[i]-1) * A[i];
            }
            dp[v] = dp[s] + 1, arg_dp[v][0] = s;
        } else {
            arg_dp[v][0] = -2;
            for (int i = 0; i < n; i++) {
                if (idx[i] == 0)
                    continue;
                if (dp[v - A[i]] > dp[v])
                    dp[v] = dp[v - A[i]];
            }
        }
        return ;
    }
    for (int i = 0; i < pwdLen[dep]; i++) {
        idx[dep] = i;
        dfs(dep+1, idx, v + A[dep] * i);
    }
}
// 
#define MAXCHAR (52 + 10)
#define MAXNODE (131072)
class Trie {
public:
    struct Node {
        Node *next[MAXCHAR];
        int cnt;
        set<int> S;
        void init() {
            cnt = 0, S.clear();
            memset(next, 0, sizeof(next));
        }
    } nodes[MAXNODE];
    Node *root;
    int size, cases;
    Node* getNode() {
    	assert(size < MAXNODE);
        Node *p = &nodes[size++];
        p->init();
        return p;
    }
    void init() {
        size = cases = 0;
        root = getNode();
    }
    inline int toIndex(char c) {
    	if (c <= '9')	return c - '0';
    	if (c <= 'Z')	return 10 + c - 'A';
    	if (c <= 'z')	return 36 + c - 'a';
        assert(false);
    }
    inline int toChar(int i) {
    	if (i < 10)		return i + '0';
    	if (i < 36)		return i - 10 + 'A';
    	if (i < 62)		return i - 36 + 'a';
    	assert(false);
    }
    // basis operation
    void insert(const char str[], int w) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        p->cnt += w;
    }
    int find(const char str[]) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        return p->cnt;
    }
        
    void free() {
        return ;
    }
} tool;
char s[MAXL];
void dfsLCS(int idx[], int v, Trie::Node *u) {
    if (v < 0)
        return ;
    
    if (arg_dp[v][0] >= -1) {
        int vidx = tool.toIndex(arg_dp[v][1]);
        if (u->next[vidx] == NULL)	
            u->next[vidx] = tool.getNode();
        u = u->next[vidx];
        if (u->S.count(v))
            return;
        u->S.insert(v);
        if (dp[v] == 1)
            return ;
        if (arg_dp[v][0] != -1) {
            for (int i = 0; i < n; i++)
                idx[i]--;
            dfsLCS(idx, arg_dp[v][0], u);
            for (int i = 0; i < n; i++)
                idx[i]++;
        }
    } else {
        if (u->S.count(v))
            return;
        u->S.insert(v);
        for (int i = 0; i < n; i++) {
            if (idx[i] == 0)
                continue;
            if (dp[v - A[i]] == dp[v]) {
                idx[i]--;
                dfsLCS(idx, v - A[i], u);
                idx[i]++;
            }
        }
    }
}
void printLCS(int dep, Trie::Node *u, char *s, vector<string> &ret) {
    if (u == NULL)	return;
    if (dep == -1) {
        ret.push_back(s+1);
        return;
    }
    for (int i = 0; i < MAXCHAR; i++) {
        *s = tool.toChar(i);
        printLCS(dep-1, u->next[i], s-1, ret);
    }
}
int countLCS(int dep, Trie::Node *u, char *s) {
    if (u == NULL)	return 0;
    if (dep == -1)
        return 1;
    int ret = 0;
    for (int i = 0; i < MAXCHAR; i++) {
        *s = tool.toChar(i);
        ret += countLCS(dep-1, u->next[i], s-1);
    }
    return ret;
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%s", pwd[i]);
            pwdLen[i] = strlen(pwd[i]);
        }
        A[0] = 1;
        for (int i = 1; i < n; i++)
            A[i] = A[i-1] * pwdLen[i-1];
        
        memset(dp, 0, sizeof(char) * A[n-1] * pwdLen[n-1]);
        
        int idx[MAXN], f = A[n-1] * pwdLen[n-1] - 1;
        dfs(0, idx, 0);
        
//		printf("%d\n", (int) dp[f]);
        
        tool.init();
        memset(s, 0, sizeof(s));
        for (int i = 0; i < n; i++)
            idx[i] = pwdLen[i]-1;
        dfsLCS(idx, f, tool.root);
        printf("%d\n", countLCS(dp[f]-1, tool.root, s + dp[f]-1));
        vector<string> ret;
        printLCS(dp[f]-1, tool.root, s + dp[f]-1, ret);
        sort(ret.begin(), ret.end());
        for (int i = 0; i < ret.size(); i++)
            printf("%s\n", ret[i].c_str());
    }
    return 0;
}
/*
999
2
abcdabcdabcdabcdefghefghefghefgh
dcbadcbadcbadcbahgfehgfehgfehgfe
2
abcdabcdabcdabcd
dcbadcbadcbadcba
999
2
abcabcaa
acbacba
2
abcdfgh
abccfdsg
3
3124158592654359
3173415926581359
763141578926536359 
*/

Problem G

看起來是一題二分圖找最大匹配數，可以利用 maxflow 或者是匈牙利算法得到。

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <assert.h>
#include <set>
using namespace std;
const int MAXV = 1024;
const int MAXE = MAXV * 200 * 2;
const int INF = 1<<29;
typedef struct Edge {
    int v, cap, flow;
    Edge *next, *re;
} Edge;
class MaxFlow {
    public:
    Edge edge[MAXE], *adj[MAXV], *pre[MAXV], *arc[MAXV];
    int e, n, level[MAXV], lvCnt[MAXV], Q[MAXV];
    void Init(int x) {
        n = x, e = 0;
        for (int i = 0; i < n; ++i) adj[i] = NULL;
    }
    void Addedge(int x, int y, int flow){
        edge[e].v = y, edge[e].cap = flow, edge[e].next = adj[x];
        edge[e].re = &edge[e+1], adj[x] = &edge[e++];
        edge[e].v = x, edge[e].cap = 0, edge[e].next = adj[y];
        edge[e].re = &edge[e-1], adj[y] = &edge[e++];
    }
    void Bfs(int v){
        int front = 0, rear = 0, r = 0, dis = 0;
        for (int i = 0; i < n; ++i) level[i] = n, lvCnt[i] = 0;
        level[v] = 0, ++lvCnt[0];
        Q[rear++] = v;
        while (front != rear){
            if (front == r) ++dis, r = rear;
            v = Q[front++];
            for (Edge *i = adj[v]; i != NULL; i = i->next) {
                int t = i->v;
                if (level[t] == n) level[t] = dis, Q[rear++] = t, ++lvCnt[dis];
            }
        }
    }
    int Maxflow(int s, int t){
        int ret = 0, i, j;
        Bfs(t);
        for (i = 0; i < n; ++i) pre[i] = NULL, arc[i] = adj[i];
        for (i = 0; i < e; ++i) edge[i].flow = edge[i].cap;
        i = s;
        while (level[s] < n){
            while (arc[i] && (level[i] != level[arc[i]->v]+1 || !arc[i]->flow)) 
                arc[i] = arc[i]->next;
            if (arc[i]){
                j = arc[i]->v;
                pre[j] = arc[i];
                i = j;
                if (i == t){
                    int update = INF;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        if (update > p->flow) update = p->flow;
                    ret += update;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        p->flow -= update, p->re->flow += update;
                    i = s;
                }
            }
            else{
                int depth = n-1;
                for (Edge *p = adj[i]; p != NULL; p = p->next)
                    if (p->flow && depth > level[p->v]) depth = level[p->v];
                if (--lvCnt[level[i]] == 0) return ret;
                level[i] = depth+1;
                ++lvCnt[level[i]];
                arc[i] = adj[i];
                if (i != s) i = pre[i]->re->v;
            }
        }
        return ret;
    }
} g;
int main() {
    int testcase;
    int n, m;
    int nx[128], ny[128], mx[128], my[128];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++)
            scanf("%d %d", &nx[i], &ny[i]);
        for (int i = 0; i < m; i++)
            scanf("%d %d", &mx[i], &my[i]);
            
        int source = n+m, sink = n+m+1;
        g.Init(n+m+2);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (abs(nx[i]-mx[j]) + abs(ny[i]-my[j]) <= 5)
                    g.Addedge(i, j+n, 1);
            }
        }
        for (int i = 0; i < n; i++)
            g.Addedge(source, i, 1);
        for (int i = 0 ; i < m; i++)
            g.Addedge(i+n, sink, 1);
            
        int flow = g.Maxflow(source, sink);
        printf("%d\n", flow);
    }
    return 0;
}

Problem H

如果摩擦力和位能動能互換是連續的，那這一題的作法可能就會有問題。很明顯地為了要求出起點到終點的最少能量需求，必然希望最後到終點的能量恰好為 0，因此逆推最少能量消耗，從終點推論到起點。

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXN = 8192;
int n, m, st, ed, h[MAXN];
vector< pair<int, int> > g[MAXN];
int dist[MAXN], inq[MAXN];
void spfa(int st, int ed, int n) {
    for (int i = 0; i < n; i++)
        dist[i] = 0x3f3f3f3f, inq[i] = 0;
    queue<int> Q;
    int u, v, w;
    dist[ed] = 0, Q.push(ed);
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        inq[u] = 0;
        for (int i = 0; i < g[u].size(); i++)  {
            v = g[u][i].first, w = g[u][i].second;
            if (h[v] > h[u]) {
                if (dist[v] > max(dist[u] - (h[v] - h[u]) + w, 0)) {
                    dist[v] = max(dist[u] - (h[v] - h[u]) + w, 0);
                    if (inq[v] == 0) {
                        inq[v] = 1;
                        Q.push(v);
                    }
                }
            } else {
                if (dist[v] > dist[u] + (h[u] - h[v]) + w) {
                    dist[v] = dist[u] + (h[u] - h[v]) + w;
                    if (inq[v] == 0) {
                        inq[v] = 1;
                        Q.push(v);
                    }
                } 
            }
            
        }
    }
    printf("%d\n", dist[st]);
}
int main() {
    int testcase;
    int u, v, w;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d %d", &n, &m, &st, &ed);
        st--, ed--;
        for (int i = 0; i < n; i++)
            g[i].clear();
        for (int i = 0; i < n; i++)
            scanf("%d", &h[i]);
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &u, &v, &w);
            u--, v--;
            g[u].push_back(make_pair(v, w));
            g[v].push_back(make_pair(u, w));
        }
        
        spfa(st, ed, n);
    }
    return 0;
}

Problem I

快速找到多少對的漢明距離恰好相差 P，保證任兩個字串不同，暴力法是直接 $O(N^2)$ 進行比較。由於字串長度不長，可以考慮一下到底要怎麼優化。這一題突然可以想到 UVa 1462 - Fuzzy Google Suggest，但是那一題考慮到字符串長度會比較長，而且還有編輯距離的搜索，跟漢明距離有點差別，也是值得思考的題目。

由於字串長度為 4，只使用大寫字母和數字，下面測試想法 5 組 50000 個的字串，大約跑了 4 秒，不曉得能不能通過正式比賽的數據。想法很簡單，窮舉相同的位置後，利用排容原理找完全不同的字串數量。

例如給定 ABCD，此時 $P = 2$，那麼找到符合 A_C_ 所有的情況，符合配對的字串保證有相似程度有 2 個，但是這些情況可能會出現 ABC_、A_CD、ABCD，也就是說為了找到符合 A_C_，__ 不能填入 BD 的任何相似，計算排容得到完全不相似 (有一個相同的位置) 的個數。

Version 1

直接用字串進行檢索。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
#include <iostream>
using namespace std;
int main() {
    int testcase, n, m;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        map< string, map<string, int> > FUZZY[1<<4];
        map< string, int > CNT[1<<4];
        int ret = 0;
        char s[8], s1[8], s2[8], s3[8];
        int same = 4 - m, diff = m;
        for (int i = 0; i < n; i++) {
            scanf("%s", s);
            
            // find pair
            for (int j = 0; j < (1<<4); j++) {
                if (__builtin_popcount(j) == same) {
                    int sidx1 = 0, sidx2 = 0;
                    for (int k = 0; k < 4; k++) {
                        if ((j>>k)&1)
                            s1[sidx1++] = s[k];
                        else 
                            s2[sidx2++] = s[k];
                    }
                    
                    s1[sidx1] = '\0', s2[sidx2] = '\0', s3[sidx2] = '\0';
                    
                    map<string, int> &tfuzzy = FUZZY[j][s1];
                    int tot = CNT[j][s1], similar = 0;
                    if (tot == 0)	continue;
                    for(int k = (1<<diff)-1; k > 0; k--) {
                        for (int p = 0; p < diff; p++) {
                            if ((k>>p)&1)
                                s3[p] = s2[p];
                            else
                                s3[p] = '_';
                        }
//						cout << s3 << endl; 
                        if (__builtin_popcount(k)%2 == 0)
                            similar -= tfuzzy[s3];
                        else
                            similar += tfuzzy[s3];
                    }
                    
                    ret += tot - similar;
//					printf("%d -- %d %d\n", tot - similar, tot, similar);
                }
            }
            
            // add
            for (int j = 0; j < (1<<4); j++) {
                if (__builtin_popcount(j) == same) {
                    int sidx1 = 0, sidx2 = 0, sidx3 = 0;
                    for (int k = 0; k < 4; k++) {
                        if ((j>>k)&1)
                            s1[sidx1++] = s[k];
                        else 
                            s2[sidx2++] = s[k];
                    }
                    s1[sidx1] = '\0', s2[sidx2] = '\0', s3[sidx2] = '\0';
                    map<string, int> &tfuzzy = FUZZY[j][s1];
                    CNT[j][s1]++;
                    for(int k = (1<<diff)-1; k > 0; k--) {
                        for (int p = 0; p < diff; p++) {
                            if ((k>>p)&1)
                                s3[p] = s2[p];
                            else
                                s3[p] = '_';
                        }
                        tfuzzy[s3]++;
                    }
                }
            }
        }
        
        printf("%d\n", ret);
    }
    return 0;
}

Version 2

將字串轉數字當作索引值加快速度。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
#include <iostream>
using namespace std;
int toIndex(int x) { // [0...36]
    if ('0' <= x && x <= '9')
        return x - '0';
    if ('A' <= x && x <= 'Z')
        return x + 10 - 'A';
    return 36;
}
int main() {
    int testcase, n, m;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        map< int, map<int, int> > FUZZY[1<<4];
        map< int, int > CNT[1<<4];
        int ret = 0;
        char s[8], s2[8], s3[8];
        int same = 4 - m, diff = m;
        for (int i = 0; i < n; i++) {
            scanf("%s", s);
            
            // find pair
            for (int j = 0; j < (1<<4); j++) {
                if (__builtin_popcount(j) == same) {
                    int sidx1 = 0, sidx2 = 0;
                    int s1 = 0, s3 = 0;
                    for (int k = 0; k < 4; k++) {
                        if ((j>>k)&1)
                            s1 = s1 * 37 + toIndex(s[k]);
                        else 
                            s2[sidx2++] = s[k];
                    }
                                        
                    map<int, int> &tfuzzy = FUZZY[j][s1];
                    int tot = CNT[j][s1], similar = 0;
                    CNT[j][s1]++;
                    
                    for(int k = (1<<diff)-1; k > 0; k--) {
                        s3 = 0;
                        for (int p = 0; p < diff; p++) {
                            if ((k>>p)&1)
                                s3 = s3 * 37 + toIndex(s2[p]);
                            else
                                s3 = s3 * 37 + toIndex('_');
                        }
                        if (__builtin_popcount(k)%2 == 0)
                            similar -= tfuzzy[s3];
                        else
                            similar += tfuzzy[s3];
                        
                        tfuzzy[s3]++;
                    }
                    
                    ret += tot - similar;
//					printf("%d -- %d %d\n", tot - similar, tot, similar);
                }
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}

Version 3

發現排容地方寫得不恰當，善用排容原理的組合計算，類似 N 不排 N 的組合數 (錯排)。map 查找會慢很多，就算用分堆的 map 效率仍然提升不高，那麼直接開一個陣列空間 $O(37^4) = O(1874161)$，所有字串轉數字，雖然清空會慢很多，但是查找速度夠快。

感謝蚯蚓、卡車告知這問題。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
#include <iostream>
using namespace std;
inline int toIndex(int x) { // [0...36]
    if ('0' <= x && x <= '9')
        return x - '0';
    if ('A' <= x && x <= 'Z')
        return x + 10 - 'A';
    return 36;
}
const int MOD = 1874161; // 37^4
int FUZZY[MOD];
int main() {
    int C[16][16] = {};
    for (int i = 0; i < 16; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = C[i-1][j-1] + C[i-1][j];
    }
    
    int testcase, n, m;	
    
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < MOD; i++)
            FUZZY[i] = 0;
        int ret = 0;
        int same = 4 - m, diff = m;
        char s[8];
        for (int i = 0; i < n; i++) {
            scanf("%s", s);
            
            // find pair
            for (int j = 0; j < (1<<4); j++) {
                if (__builtin_popcount(j) >= same) {
                    int s1 = 0;
                    for (int k = 0; k < 4; k++) {
                        if ((j>>k)&1)
                            s1 = s1 * 37 + toIndex(s[k]);
                        else 
                            s1 = s1 * 37 + toIndex('_');
                    }
                    int &r = FUZZY[s1];
                    int v = __builtin_popcount(j);
                    if ((v - same)%2 == 0)
                        ret += r * C[v][same];
                    else
                        ret -= r * C[v][same];
                    r++;
                }
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}

Problem J

考了一題 BWT 壓縮的逆轉換，從簡單的思路至少要 $O(N^2 log N)$ 吧？沒想到的是利用特性可以達到 $O(N)$。這裡需要研究一下 為什麼相同字母順序在壓縮和解壓縮會相同 ，百思不解的就是這個地方，若是能解決，就直接利用輔助數組達到 $O(N)$ 逆推上一個元素是什麼，最後輸出一個反向的結果。

這裡解釋一下順序性問題

BANANA          ABANAN            (1)A----N(9)
ANANAB    sort  ANABAN   view A   (2)A----N(10)
NANABA  ------> ANANAB  --------> (3)A----B(12)
ANABAN          BANANA           (11)B----A(4)
NABANA          NABANA            (7)NAB--A(5)
ABANAN          NANABA            (8)NAN--A(6)

明顯地左側的 A 順序會跟右側的 A 順序相同，原因是 B----A < NAB--A < NAN--A，那麼保證 AB----, ANAB--, ANAN-- 一定也會出現 (根據 $O(N^2 log N)$ 的做法得到，因為他們是循環的！)，既然後綴順序已經排序 (B----A, NAB--A, NAN--A)，那麼右側中，相同的字母順序，肯定跟左側一樣 (由小到大)。

藉此可以推導下一個字母到底是何物！例如結尾字母是 A(4)，那麼前一個一定是 B(11)，而 B(11) 對應右側的 B(12)，B(12) 的前一個是 A(3)，A(3) 對應右側 A(6) …

1
2
3

R:      B(11)    A(3)     N(8)   A(2)    N(7)   A(1)   <---- inverse result
       /  \    /    \    /  \   /   \   /   \   /
L:  A(4)  B(12)      A(6)   N(10)   A(5)     N(9)

Version 1

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
// O(n), BWT compress inverse
const int MAXN = 2048;
char s[MAXN];
int K[MAXN], M[MAXN], C[MAXN], N;
int main() {
    int testcase, e_pos;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s %d", s, &e_pos), e_pos--;
        
        string L(s), F(s);
        N = L.length();
        
        memset(K, 0, sizeof(K));
        memset(M, 0, sizeof(M));
        memset(C, 0, sizeof(C));
        
        for (int i = 0; i < N; i++) {
            C[i] = K[L[i]];
            K[L[i]]++;
        }
        
        sort(F.begin(), F.end());
        for (int i = 0; i < N; i++) {
            if (i == 0 || F[i] != F[i-1])
                M[F[i]] = i;
        }
        
        string T(N, '?');
        for (int i = 0; i < N; i++) {
            T[N-1-i] = L[e_pos];
            e_pos = C[e_pos] + M[L[e_pos]];
        }
        puts(T.c_str());
    }
    return 0;
}
/*
2
CGA
3
NNBAAA
4 
*/

Version 2

蚯蚓的寫法順推。

#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
static const int MXN = 514514;
int main() {
    int t;
    std::cin >> t;
    
    while (t--) {	
        int p;
        std::string str;
        std::cin >> str >> p;
        
        std::vector<std::pair<char, int>> vec;
        for (size_t i = 0; i < str.length(); i++)
            vec.push_back(std::make_pair(str[i], i));
        std::sort(vec.begin(), vec.end());
        
        std::string ans;
        for (int i = p - 1; ans.length() < str.length(); i = vec[i].second)
            ans += vec[i].first;
        std::cout << ans << std::endl;
    }
}

Problem K

二分答案 + 掃描線，來找到是否矩形并的面積等於所求的整個面積。算法的複雜度是 $O(N \log^2{N} )$，如果太慢的話就懇求各位幫忙。

掃描線部分，將每個平行兩軸的矩形保留垂直的邊，水平的邊不影響運算結果。接著按照 X 軸方向由左往右掃描，將矩形左側的垂直邊當作入邊 +1、右側的垂直邊當作出邊 -1，維護 Y 值的區間覆蓋。

假設 Y 可能是實數，需要針對 Y 進行離散化處理，接著懶操作標記，對於線段樹的某個區間，若覆蓋數 cover = 0 則表示該區間無法提供，相反地提供整個區間。

註記邪惡的 $\text{round}(\sqrt{k} \times c)$ ，不小心看成 $\text{round}(\sqrt{k}) \times c$

感謝蚯蚓告知這問題。

#include <stdio.h> 
#include <string.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
const int MAXN = 131072;
class SegmentTree {
public:
    struct Node {
        int cover;				// #cover
        int L, R;			// value in real line, cover [L, R]
        int clen;			// cover length
        void init(int a = 0, int b = 0, int c = 0, int d = 0) {
            cover = a, L = b, R = c, clen = d;
        }
    } nodes[MAXN];
    int Y[MAXN];
    void pushDown(int k, int l, int r) {
    }
    void pushUp(int k, int l, int r) {
        if (nodes[k].cover > 0) {
            nodes[k].clen = nodes[k].R - nodes[k].L;
        } else {
            if (l == r)
                nodes[k].clen = 0;
            else
                nodes[k].clen = nodes[k<<1].clen + nodes[k<<1|1].clen;
        }
    }
    void build(int k, int l, int r) { 
        nodes[k].init(0, Y[l], Y[r+1], 0);
        if (l == r)
            return ;
        int mid = (l + r)/2;
        build(k<<1, l, mid);
        build(k<<1|1, mid+1, r);
        pushUp(k, l, r);
    } 
    // operator, add
    void addUpdate(int k, int l, int r, int val) {
        nodes[k].cover += val;
        if (nodes[k].cover > 0) {
            nodes[k].clen = nodes[k].R - nodes[k].L;
        } else {
            if (l == r)
                nodes[k].clen = 0;
            else
                nodes[k].clen = nodes[k<<1].clen + nodes[k<<1|1].clen;
        }
    }
    void add(int k, int l, int r, int x, int y, int val) {
        if (x <= l && r <= y) {
            addUpdate(k, l, r, val);
            return;
        }
        pushDown(k, l, r);
        int mid = (l + r)/2;
        if (x <= mid)
            add(k<<1, l, mid, x, y, val);
        if (y > mid)
            add(k<<1|1, mid+1, r, x, y, val);
        pushUp(k, l, r);
    }
    // query 
    long long r_sum;
    void qinit() {
        r_sum = 0;
    }
    void query(int k, int l, int r, int x, int y) {
        if (x <= l && r <= y) {
            r_sum += nodes[k].clen;
            return ;
        }
        pushDown(k, l, r);
        int mid = (l + r)/2;
        if (x <= mid)
            query(k<<1, l, mid, x, y);
        if (y > mid)
            query(k<<1|1, mid+1, r, x, y);
        pushUp(k, l, r);
    }
} tree;
struct Event {
    long long x, yl, yr;
    int val;
    Event(long long a = 0, long long b = 0, long long c = 0, int d = 0):
    x(a), yl(b), yr(c), val(d) {}
    bool operator<(const Event &a) const {
        return x < a.x;
    }
};
const int MAXD = 32767;
int Lx[MAXD], Ly[MAXD], Rx[MAXD], Ry[MAXD];
long long X[MAXD], Y[MAXD];
double K[MAXD];
long long areaCoverAll(int N, int Lx[], int Ly[], int Rx[], int Ry[]) {
    vector<Event> events;
    vector<int> VY;
    map<int, int> RY;
    for (int i = 0; i < N; i++) {
        int x1, x2, y1, y2;
        x1 = Lx[i], x2 = Rx[i];
        y1 = Ly[i], y2 = Ry[i];
        if (x1 < x2 && y1 < y2) {
            events.push_back(Event(x1, y1, y2,  1));
            events.push_back(Event(x2, y1, y2, -1));
            VY.push_back(y1), VY.push_back(y2);
        }
    }
    
    sort(VY.begin(), VY.end());	
    VY.resize(unique(VY.begin(), VY.end()) - VY.begin());
    
    for (int i = 0; i < VY.size(); i++) {
        tree.Y[i] = VY[i];
        RY[VY[i]] = i;
    }
                
    if (VY.size() < 2)	
        return 0;
    tree.build(1, 0, VY.size()-2);
    
    sort(events.begin(), events.end());
    long long area = 0, prevX = 0;
    for (int i = 0, j; i < events.size(); ) {		
        if (i > 0) {
            tree.qinit();
            tree.query(1, 0, VY.size()-2, 0, VY.size()-2);
            area += (events[i].x - prevX) * tree.r_sum;
        }
        j = i;
        while (j < events.size() && events[j].x <= events[i].x) {
            tree.add(1, 0, VY.size()-2, RY[events[j].yl], RY[events[j].yr] - 1, events[j].val);
            j++;
        }
        prevX = events[i].x;
        i = j;
    }
    return area;
}
int main() {
    int testcase, cases = 0;
    long long W, H;
    int N;
    double sqrtK[128];
    for (int i = 0; i < 128; i++)
        sqrtK[i] = sqrt(i);
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lld %lld", &W, &H);
        scanf("%d", &N);
                
        for (int i = 0; i < N; i++) {
            int x, y, k;
            scanf("%d %d %d", &k, &x, &y);
            if (k < 1 || k > 100)
                return 0;
            X[i] = x, Y[i] = y, K[i] = sqrtK[k];
        }
                
        if (N < 1 || N > 20000 || W <= 0 || H <= 0 || W > 1e+7 || H > 1e+7)
            return 0;
            
        double l = 0.4, r = max(W, H), mid;
        int ret = -1;
        while (fabs(l - r) > 0.1) {
            mid = (l + r)/2;
            
            for (int i = 0; i < N; i++) {
                Lx[i] = min(max(round(X[i] - K[i] * mid), 0.0), (double) W);
                Rx[i] = min(max(round(X[i] + K[i] * mid), 0.0), (double) W);
                Ly[i] = min(max(round(Y[i] - K[i] * mid), 0.0), (double) H);
                Ry[i] = min(max(round(Y[i] + K[i] * mid), 0.0), (double) H);
            }
            
            long long area = areaCoverAll(N, Lx, Ly, Rx, Ry);
            if (area == W*H)
                r = mid, ret = ceil(mid*2);
            else
                l = mid;
        }
        
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}
/*
9999
9 9
1
1 0 0
1 1
1
4 0 0
2
12 8
3
4 2 2
16 8 4
4 2 6
12 8
3
4 2 2
10 8 4
4 2 6 
*/

後記

如有錯誤，多多包涵。

Morris' Blog

ITSA 2015 第四屆桂冠賽

contents

Problem A

Problem B

Problem C

Problem D

Problem E

Problem F

Problem G

Problem H

Problem I

Version 1

Version 2

Version 3

Problem J

Version 1

Version 2

Problem K

後記