北屿

北屿小智障

0%

CodeJam 2020 Qualification Round

Posted on Edited on In

嗝，感谢Google给我发的邮件让我在404不再寂寞。
就做了3道题，30pts就能拿到资格
但前面的很简单，随便水水..后面的题自然是最喜欢的口胡
——20200404

Vestigium 7pts

Description

计算矩阵对角线左上到右下的和，计算出现重复元素的行数和列数

Solution

…没啥好说的$O(n^4)$似乎都能过

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

const int N = 205;

int a[N][N];
int num[N];

int main() {
    int T, n, k, r, c;
    scanf("%d", &T);
    for(int t=1; t<=T; t++) {
        scanf("%d", &n);
        for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) scanf("%d", &a[i][j]);
        k = r = c = 0;
        
        for(int i=1; i<=n; i++) k+=a[i][i];
        for(int i=1; i<=n; i++) {
            memset(num, 0, sizeof(num));
            for(int j=1; j<=n; j++) num[a[i][j]]++;
            int fl = 0;
            for(int j=1; j<=n; j++) if(num[j]>1) fl=1;
            if(fl) r++;
        }
        for(int j=1; j<=n; j++) {
            memset(num, 0, sizeof(num));
            for(int i=1; i<=n; i++) num[a[i][j]]++;
            int fl = 0;
            for(int i=1; i<=n; i++) if(num[i]>1) fl=1;
            if(fl) c++;
        }
        printf("Case #%d: %d %d %d\n", t, k, r, c);
    } return 0;
}

Nesting Depth 5pts 11pts

Description

一个序列，让你添加括号，使得每个数被嵌套的括号数量恰好是他这个数。

Solution

就很简单的构造-，-

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;

const int N = 150;

int a[N];

int main() {
    int T, n; string s, res;
    cin >> T; getline(cin, s);
    for(int t=1; t<=T; t++) {
        res="";
        getline(cin, s);
        n = s.length();
        for(int i=1; i<=n; i++) a[i]=s[i-1]-'0';
        n; a[n+1]=0;
        for(int i=0; i<=n; i++) {
            if(i) res+=a[i]+'0';
            if(a[i]>a[i+1]) {
                for(int j=1; j<=a[i]-a[i+1]; j++) res+=')';
            } else if(a[i]<a[i+1]) {
                for(int j=1; j<=a[i+1]-a[i]; j++) res+='(';
            }
        }
        cout << "Case #" << t << ": " << res << endl;
    } return 0;
}

Parenting Partnering Returns 7pts 12pts

Description

两个人干活，有每个活的起始和结束时间，让你分配个方案，判断一下可不可能

Solution

排序一下直接贪心就好了…
简单想一下，如果两个人都有空那么随便安排一个就可以；如果只有一个人有空，那么只能让另一个人；如果都没空自然不可以。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

#define xx first
#define yy second

const int N = 1050;

struct mypr { int x, y, id; } a[N];
int b[N];

int cmp(const mypr &a, const mypr &b) { return a.x==b.x?a.y<b.y:a.x<b.x; } 

int main() {
    int T, n;
    cin >> T;
    for(int t=1; t<=T; t++) {
        cin >> n;
        for(int i=1; i<=n; i++) {
            cin >> a[i].x >> a[i].y; a[i].id = i;
        }
        memset(b, 0, sizeof(b));
        sort(a+1, a+n+1, cmp);
        int avj=0, avc=0, fl=0;
        for(int i=1; i<=n; i++) {
            if(avj<=a[i].x) {
                b[a[i].id]=1;
                avj = a[i].y;
            } else if(avc<=a[i].x) {
                b[a[i].id]=0;
                avc = a[i].y;
            } else {
                fl=1;
            }
        }
        if(fl) cout << "Case #" << t << ": IMPOSSIBLE" << endl;
        else {
            string aa = "";
            for(int i=1; i<=n; i++) if(b[i]) aa+="J"; else aa+="C";
            cout << "Case #" << t << ": " << aa << endl;
        }
    }
    return 0;
}

ESAb ATAd 1pts 9pts 16pts

Description

交互题。有一个01序列，每10问会发生一次变化，可能是01翻转，可能是序列翻转，可能01翻转然后序列翻转，可能不变，每次询问告诉你那个位的数是多少

Solution

我觉得只需要记4个数，（第1个和第2个）（0和1），然后先花两次询问来查看变化，然后在询问剩下的就ok
（当然这是口胡的，我没写

Code

None

Indicium 7pts 25pts

Description

第一题差不多的定义，就是构造一个自然拉丁方让对角线的值是$k$，$n\leqslant 50$

Solution

首先就想到了一个式子$\sum a_i=n, \sum ia_i=k$，其中$a_i\geqslant 2 \text{ or } a_i=0$，有这个自然数解，也就有解
有两个问题…一个是这个复杂度好像很玄学..
还有就是构造的时候遇到了问题..优先级似乎是分开的…不是很懂了，有空再做吧我去写实验了..

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;

const int N = 55;

int a[N][N], row[N][N], col[N][N];
int b[N], inq[N];
int q1[N], q2[N];
int T, n, k;

int getans(int k, int n) {
    if(n==0) return k==0?1:-1;
    if(n==1) return -1;
    if(k%n==0) { q1[++q1[0]]=k/n; q2[q1[0]]=n; return 1; }
    if(k<n) return -1;
    for(int i=k/n; i>0; i--) {
        q1[++q1[0]]=i;
        for(int j=min(n, k/i); j>=2; j--) {
            q2[q1[0]]=j;
            int t=getans(k-i*j, n-j);
            if(t==1) return 1;
        }
        --q1[0];
    } return -1;
}

int main() {
    cin >> T;
    for(int t=1; t<=T; t++) {
        cin >> n >> k;
        memset(a, 0, sizeof(a)); memset(row, 0, sizeof(row)); memset(col, 0, sizeof(col));
        memset(b, 0, sizeof(b)); memset(inq, 0, sizeof(inq));
        q1[0]=q2[0]=0;
        
        printf("Case #%d: ", t);
        if(getans(k, n)==-1) puts("IMPOSSIBLE");
        else {
            puts("POSSIBLE");
//			for(int i=1; i<=q1[0]; i++) cout << q1[i] << " x " << q2[i] << endl;
            int cnt=0;
            for(int i=1; i<=q1[0]; i++) {
                for(int j=1; j<=q2[i]; j++) {
                    cnt++;
                    a[cnt][cnt]=q1[i];
                    row[cnt][q1[i]]=1, col[cnt][q1[i]]=1;
                }
            }
            for(int i=1; i<=q1[0]; i++) inq[q1[i]]=1;
            for(int i=1; i<=q1[0]; i++) b[i]=q1[i];
            for(int i=q1[0]+1, tt=1; i<=n; i++, tt++) { while(inq[tt]) tt++; b[i]=tt; }
            
            
            for(int i=1; i<=n; i++) {
                for(int j=1; j<=n; j++) if(inq[b[j]] && col[j][b[j]]) {
                    int ff=0;
                    for(int tt=j; tt<=n; tt++) if(!col[tt][b[j]]) { ff=tt; break; }
                    if(!ff) for(int tt=1; tt<=j; tt++) if(!col[tt][b[j]]) { ff=tt; break; }
                    if(!ff) continue;
                    if(ff>j) for(int tt=j; tt<ff; tt++) swap(b[tt], b[tt+1]);
                    else for(int tt=j; tt>ff; tt--) swap(b[tt], b[tt-1]);
                }
                for(int j=1; j<=n; j++) cout << b[j] << " "; cout << endl;
                for(int j=1; j<=n; j++) {
                    if(!a[i][j]) {
                        for(int u=1; u<=n; u++) if(!row[i][b[u]] && !col[j][b[u]]) {
                            a[i][j]=b[u]; row[i][b[u]]=col[j][b[u]]=1; break;
                        }
                    }
                }
                
                for(int j=n; j>1; j--) swap(b[j], b[j-1]);
            }
            for(int i=1; i<=n; i++) 
                for(int j=1; j<=n; j++) 
                    printf("%d%c", a[i][j], " \n"[j==n]);
        }
    }
    return 0;
}
Related Posts
Have fun.