某岛

… : "…アッカリ~ン . .. . " .. .
April 5, 2020

Google Code Jam 2020 Qualification Round

我感觉我下一轮就要被淘汰了。。。赶紧写一发题解。。。
ABC 略。

因为最近在教 家主 写 python。。虽然没有教会。。。但是我也可以用 python 切水题了。。。

T = list(map(int, input().split()))[0]
for case in range(1, T+1):
    n = list(map(int, input().split()))[0]
    A = []
    for i in range(n):
        A.append(list(map(int, input().split())))

    k = 0
    r = 0
    c = 0
    for i in range(n):
        k += A[i][i]

    for i in range(n):
        C = [0] * (n+1)
        for j in range(n):
            if (C[A[i][j]] == 1):
                r += 1
                break
            C[A[i][j]] = 1

    for j in range(n):
        C = [0] * (n+1)
        for i in range(n):
            if (C[A[i][j]] == 1):
                c += 1
                break
            C[A[i][j]] = 1

    print("Case #%d: %d %d %d" % (case, k,r,c))

T = list(map(int, input().split()))[0]
for case in range(1, T+1):
    s = input()
    z = ""
    k = 0
    for c in s:
        while (k < int(c)):
            z += '('
            k += 1
        while (k > int(c)):
            z += ')'
            k -= 1
        z += c
    while (k > 0):
        z += ')'
        k -= 1

    print("Case #%d: %s" % (case, z))

T = list(map(int, input().split()))[0]
for case in range(1, T+1):
    n = list(map(int, input().split()))[0]
    e = []
    z = ['-'] * n
    o = list(range(n))
    for i in range(n):
        e.append(list(map(int, input().split())))

    o.sort(key=lambda x: e[x])
    t = 0
    for _i in range(n):
        i = o[_i]
        if (z[i] == '-' and e[i][0] >= t):
            z[i] = 'C'
            t = e[i][1]
    t = 0
    for _i in range(n):
        i = o[_i]
        if (z[i] == '-' and e[i][0] >= t):
            z[i] = 'J'
            t = e[i][1]
            
    res = ""
    for i in range(n):
        res += z[i]
    for i in range(n):
        if (z[i] == '-'):
            res = "IMPOSSIBLE"
            break
    print("Case #%d: %s" % (case, res))

D 交互题。
考虑大数据。注意 10 个询问变化一次,我们必须在最后的 10 个询问中得到所有 100 个状态。
所以最后必须 1 个询问,得到 10 个状态。这需要我们用前面的询问预处理各种信息。
—– xxxxx xxxxx —–
显然我们可以 10 个 10 个分组,每次取前面 5 个和后面 5 个,那么考虑对称的位置,不失一般性,只有两种可能。
– 相同的话,取反 和 取反加交换,会改变这两个元素的状态。
– 不同的话,取反 和 交换,会改变这两个元素的状态。

所以我们每次用 10 个询问,把成对的元素进行分组,再补充一个询问,判断相同和不同的变换方式是否相同。
就可以最后一次扫出来了。

int A[N], B[N];
VI t00[N], t01[N]; int same[N];

void query(int A[], int x) {
    cout << x << endl;  cout.flush();
    cin >> A[x];
}

int main() {
    
#ifndef ONLINE_JUDGE
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
    
#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
#endif
    
    // 0 0 ,       rev, swap rev
    // 0 1 , swap, rev
    
    // 100
    // 20
    
    
    int t, n; RD(t, n); REP(ii, t) {
        
        REP(i, n/10) {
            t00[i].clear(); t01[i].clear();
            REP_1(j, 5) {
                int a = i*10+j;
                int b = n+1-a;
                query(A, a);
                query(A, b);
                if (A[a] == A[b]) {
                    t00[i].PB(a);
                } else {
                    t01[i].PB(a);
                }
            }
        }
        
        
        REP(i, n/10) {
            //if (t00[i].empty() || t01[i].empty()) continue;
            int a0 = t00[i].empty() ? t01[i].front() : t00[i].front();
            int a1 = t01[i].empty() ? t00[i].front() : t01[i].front();
            query(B, a0);
            query(B, a1);
            
            same[i] = (A[a0]==B[a0]) == (A[a1]==B[a1]);
        }
        
        REP(i, n/10) {
            
            if (!t00[i].empty()) {
                int a = t00[i].front();
                query(B, a);
                if (A[a] != B[a]) {
                    for (auto a: t00[i]) {
                          int b = n+1 - a;
                          A[a] ^= 1;
                          A[b] ^= 1;
                    }
                    
                    if (same[i]) {
                        for (auto a: t01[i]) {
                            int b = n+1 - a;
                            A[a] ^= 1;
                            A[b] ^= 1;
                        }
                    }
                } else {
                    if (!same[i]) {
                        for (auto a: t01[i]) {
                            int b = n+1 - a;
                            A[a] ^= 1;
                            A[b] ^= 1;
                        }
                    }
                }
            } else {
                int a = t01[i].front();
                query(B, a);
                if (A[a] != B[a]) {
                    for (auto a: t01[i]) {
                        int b = n+1 - a;
                        A[a] ^= 1;
                        A[b] ^= 1;
                    }
                }
            }
        }
        
        string s;
        REP_1(i, n) {
            s += char('0' + A[i]);
        }
        
        cout << s << endl; cout.flush(); cin >> s;
    }
}

构造主对角线和为 k 的拉丁方。
据说可以用二分图匹配?


const int N = (1e2) + 9;
int A[N][N];
int n, k;

bool dfs(int x = 0, int y = 0) {
    if (x == n) {
        int s = 0;
        REP(i, n) s += A[i][i];
        if (s == k) {
            puts("POSSIBLE");
            REP(i, n) {
                REP(j, n) printf("%d ", A[i][j]);
                cout << endl;
            }
            return 1;
        }
        return 0;
    }
    if (y == n) {
        return dfs(x+1, 0);
    }
    
    VI t; REP(i, n+1) t.PB(1);
    REP(i, x) t[A[i][y]] = 0;
    REP(i, y) t[A[x][i]] = 0;
    REP_1(i, n) if (t[i]) {
        A[x][y] = i;
        if (dfs(x, y+1)) {
            return 1;
        }
    }
    return 0;
}

int main() {
    
#ifndef ONLINE_JUDGE
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
    
#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
#endif
    
    // 0 0 ,       rev, swap rev
    // 0 1 , swap, rev
    
    // 100
    // 20
    
    
    int T; RD(T); REP_1(Case, T) {

        printf("Case #%d: ", Case);
        RD(n,k);
        
        if (!dfs()) {
                        puts("IMPOSSIBLE");
        }
    }
}