0%

Solutions of Google's Coding Competitions

Posted on Edited on In Disqus:

待补完

Kick Start

2019 round G

Book Reading (瞎搞)

题意:
一本书有N页, 其中$P_1, P_2,…,P_M(P_i\leq N)$页都损毁了. 有$Q$个人来读它, 第$i$个人自带属性$R_i$,每个人读这本书时只会读$R_i$倍数且没有损毁的页码. 现在统计这本书一共被读了多少次(看一页算一次).
$1\leq M,N, Q\leq1e5$
分析:
如果书没有页码损毁,答案是$\sum_{i=1}^{N}N/R_i$. 接着扣去这Q个人没读损毁的部分, 先把Q个人不读的倍数$R_i$排序(为了看有几个人$R_i$是相同的, 相同的$R_i$只做一次计算,此时最糟糕的输入数据应该是$\{R_i\}=\{1,2,…,1e5\}$,算一下复杂度大概是$\sum_{i=1}^{N}\frac{N}{i}<\int_{1}^{N}\frac{1}{x-1}dx\approx\ln\frac{N}{2}$), 查看$R_i$的倍数是否损毁, 损毁则扣去.

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
#include <stdio.h>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1e5+10;
int prime[maxn];
int P[maxn], R[maxn];
bool torn[maxn];
int main(){
    int n, m, q;
    int T;
    //int pn = init_prime();
    scanf("%d", &T);
    int rnd = 1;
    while(T--){
        scanf("%d%d%d", &n, &m, &q);
        memset(torn, 0, sizeof(torn));
        for(int i=0; i<m; i++){
           scanf("%d", &P[i]);
           torn[P[i]] = true;
        }
        long long ans = 0;
        for(int i=0; i<q; i++){
            scanf("%d", &R[i]);
            ans += (n/R[i]);
        }
        sort(R, R+q);
        int *s=R, *e=R;
        while(s!=R+q){
            e = upper_bound(R, R+q, *s);
            int num = e-s;
            for(int i=1; i*(*s)<=n; i++){
                if(torn[i*(*s)]){
                    ans -= num;
                }
            }
            s = e;
        }
        printf("Case #%d: %lld\n", rnd++, ans);
    }
    return 0;
}

The Equation(贪心, 位运算)

题意:
Given a non-negative integer $M$ and $N$ non-negative integers $\{A_i\}$, find the largest integer $k$ s.t. $\sum_{i=1}^{N}(A_ixork)\leq M$.
分析:
先把给的$M$和$N$个数都转成2进制, 一位一位地来构造$k. k$的位数一定不超过$M$和$N$个数字的最大位数. 显然要从高位开始填, 而且贪心地尽量往高位填1.
先把$k$的每一位填0或者1, 得到该位的异或和算出来. 接下来用一个数组minSum$[i]$来记录到第$i-1$位为止, 能取到的最小异或和的和(每一位异或和,再把这$i-1$个异或和加起来).
搞完这些就可以开始贪心填1惹, 试一试第$i$位填1得到的异或和$+minSum[i]$会不会超出$M$即可.

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
#include <stdio.h>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include<stdlib.h>
#include<time.h>
using namespace std;
const int maxn = 1010;
long long A, m, minSum[maxn], bit1[maxn], bit0[maxn];
int two[maxn][55], res2[55];
int maxx;
void decode(int index, long long n){
    int temp[55];
    int k = 0;
    while(n){
        temp[k++] = n%2;
        n /= 2;
    }
    int p = 0;
    maxx = max(k, maxx);
    for(int i=0; i<k; i++){
        two[index][p++] = temp[i];
    }
}
long long two2ll(int* a, int n){
    long long res = 0, p = 1;
    for(int i=0; i<=maxx; i++){
        res += a[i]*p;
        p *= 2;
    }
    return res;
}
int main(){
    int rnd=1, T, n;
    scanf("%d", &T);
    while(T--){
        maxx = 0;
        memset(two, 0, sizeof(two));
        scanf("%d%lld", &n, &m);
        for(int i=0; i<n; i++){
            scanf("%lld", &A);
            decode(i, A);
        }
        decode(n, m);
        minSum[0] = 0;
        for(int j=0; j<=maxx; j++){
            long long now1=0, now0 = 0;
            for(int i=0; i<n; i++){
                now1 += (two[i][j]^1);
                now0 += (two[i][j]^0);
            }
            bit1[j] = now1*pow(2, j);
            bit0[j] = now0*pow(2, j);
            minSum[j+1] = minSum[j]+min(bit1[j], bit0[j]);
        }
        for(int i=maxx; i>=0; i--){
            if(m-bit1[i] >= minSum[i]){
                res2[i] = 1;
                m -= bit1[i];
            }else{
                res2[i] = 0;
                m -= bit0[i];
            }
        }
        printf("Case #%d: %lld\n", rnd++, m>=0?two2ll(res2, maxx):-1);
    }
    return 0;
}

Shifts(状压dp, 位运算)

题意:
两保安要排n天的班, 这两个保安a,
b在第$i$天如果上班的话会分别收获$A[i],B[i]$快乐值. 每一天至少要有一个人上班. 最后两人的快乐值总和应不小于$h$. 问有多少排班方案.
$0\leq N\leq 20$
分析:
暴搜的话$3^{20}\approx3.5\times1e9$,不太行. 使用$[0,2^n-1]$之间的整数来表示A的排班表, 第n位为0表示不上班, 1表示上班. 用$f[i]$表示, 在A的排班表为$i$时, 能够使B的快乐达到$h$的方案数.
先计算一天只有一个人上班的情况, 枚举$2^n$种A的排班方案$\{i
\}$. 由于只有一个人上班,所以$i$的二进制某位为1时,A上班B不上班. 把这$2^n$种排版方案中使B的快乐值达到h的方案挑出来, 即令$f[i]=1$;
接下来把A,B都上班的情况算进去. 某天A不上班, 比如9=1001的第二天,默认B的排班不变, 这个状态下的方案数应该贡献到13=1101的方案数中去. 即$(A,B)=(1101, 0110)\leftarrow(1001, 0110)$, 因为如果对B来说0110能使他快乐达到h,那么A在第二天上不上班无所谓.
最后对$2^n$排班确认此时A的快乐值是否会达到h, 若达到则将该状态下的方案数加到答案里.

代码: 
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
#include <stdio.h>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1e7+10;
long long A[30], B[30], f[maxn];
int main(){
    int T, rnd=1, n;
    long long h;
    scanf("%d", &T);
    while(T--){
        scanf("%d%lld", &n, &h);
        for(int i=0; i<n; i++){
            scanf("%lld", A+i);
        }
        for(int i=0; i<n; i++){
            scanf("%lld", B+i);
        }
        int up = 1<<n;
        memset(f, 0, sizeof(f));
        for(int i=0; i<up; i++){
            long long sumB = 0;
            int now = 1;
            //assume that there are only one guy works per day.
            //when the bit is 1, A works, then B does not work
            //get all plans where sumB can reach h
            for(int j=0; j<n; j++){
                if(!(i&now)) sumB += B[j];
                now = now<<1;
            }
            if(sumB>=h){
                f[i]++;
            }
        }
        for(int i=0; i<n; i++){
            for(int j=0; j<up; j++){
                if(j&(1<<i)){//if A works today
                    f[j] += f[j^(1<<i)];
                    //plans should add plans where if today does not work
                    //0xor0/1 does not make changes, 1xor1 makes 1 turn to 0
                }
            }
        }
        long long ans = 0;
        for(int i=0; i<up; i++){
            long long sumA = 0;
            int now = 1;
            for(int j=0; j<n; j++){
                if(i&now) sumA += A[j];
                now = now<<1;
            }
            if(sumA>=h){
                ans += f[i];
            }
        }
        printf("Case #%d: %lld\n", rnd++, ans);
    }
    return 0;
}

Code Jam

Code Jam to I/O for Women

2020

Interleaved Output: Part 1(贪心)

贪就对了

代码: 
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
#include <stdio.h>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 110;
char str[maxn];
int main(){
    int t, rnd=1;
    scanf("%d", &t);
    while(t--){
        int i=0, I=0, o=0, O=0;
        scanf("%s", str);
        int len = strlen(str), ans = 0;
        for(int k=0; k<len; k++){
            if(str[k] == 'I') I++;
            else if(str[k] == 'i') i++;
            else if(str[k] == 'O' ){
                if(I){
                    --I;
                    ans++;
                }else{
                    --i;
                }
            }else if(str[k] == 'o'){
                if(i){
                    --i;
                }else{
                    --I;
                }
            }
        }
        printf("Case #%d: %d\n", rnd++, ans);
        
    }
    return 0;
}

Imbalance Obviation(图染色graph coloring, 图遍历)

题意:
We have a balance scale and $N$ identical 1-gram marbles numbered from $1$ to $N$. If the difference of the weight between the left pan and the right pan is more than 1, the scale will lose its balance. Now we play a game, we put marbles into the scale in order from $1$ to $N$, each time we put a marble, we can choose whether left or right pan to put into. After we put all marbles into the scale, we start to take them from it: the problem’s input will be a permutation of $\{1,2,…,N\}=\{A_1,A_2,…,A_N\}$, which means the number order of marbles we take out of the scale. Now we need to determine a method to put marbles into the scales(for the number $i$-th marble, choose left or right pan to put). The scale should never lose its balance during the processing above.
The permutation of taking out is always legal.
$1\leq N\leq 1000$
分析:
Divide this problem into 2 situations: $N$ is odd or even.
The easier case is when $N$ is even. When we start to put marbles, we must put a marble on one side then put the next mable on the other side to keep the balance, which means for a odd-numered marble $2i-1$, it must be in a different side of $2i$‘s. For example we can put 1 in left then must put 2 in right. Then we can choose either side to put 3, say right, then we must put 4 in left.
Then consider taking out, we can know after putting on, the number of left pan must equal to the right pan’s. So $A_1$ and $A_2$ must in different sides and so do $A_{2i-1}$ and ${A_{2i}}$. 可恶英文写得好麻烦
所以这里面可以得到$N$个对立个关系,我们由此建一张图, 图中的点为石头的编号, 两点连边的则表示两石头不在同一盘子上. 接下来对图染色, 染两个颜色表示放左盘/右盘. 由于题目输入保证合法因此只要遍历一遍图即可染色.
若$N$为基数, 我们知道放石头的时候, 第$N$个放的盘肯定比另一边多一. 取走时, 第一个取走的石子必须从多的那个盘子上取走, 即$N$和$A_1$在同一个盘上. 把这和这两者不在同一盘子内的石子添加到对方边里即可. 剩下的工作和偶数没区别,染色就vans了. 特判一下$N=A_1$的情况, 爱放哪放哪. 这题解写得我好暴躁

代码: 
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
80
81
82
83
#include <stdio.h>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 1010;
int save[maxn];
vector<int> mp[maxn];
int color[maxn];
void init(int n){
    for(int i=1; i<=n; i++){
        mp[i].clear();
    }
    memset(color, 0, sizeof(color));
}
void dfs(int index, int flag){
    color[index]  = flag;
    for(int i=0; i<mp[index].size(); i++){
        if(color[mp[index][i]]==0){//not been visited
            dfs(mp[index][i], -flag);
        }
    }
}
int main(){
    int t, rnd=1;
    scanf("%d", &t);
    while(t--){
        int n;
        scanf("%d", &n);
        init(n);
        bool flag = false;
        for(int i=1; i<=n; i++){
            scanf("%d", &save[i]);
            if(n%2 && i==1) continue;
            if(flag){
                mp[save[i]].push_back(save[i-1]);
                mp[save[i-1]].push_back(save[i]);
            }
            flag = ! flag;
        }
        
        for(int i=1; i<=n; i++){
            if(i%2==0){
                mp[i].push_back(i-1);
                mp[i-1].push_back(i);
            }
        }
        if(n%2 && save[1]!=n){
            for(int i=0; i<mp[n].size(); i++){
                mp[save[1]].push_back(mp[n][i]);
            }
            for(int i=0; i<mp[save[1]].size(); i++){
                mp[n].push_back(mp[save[1]][i]);
            }
        }
        for(int i=1; i<=n; i++){
            if(color[i]==0) dfs(i, 1);
        }
        printf("Case #%d: ", rnd++);
        for(int i=1; i<n; i++){
            if(color[i] == 1){
                printf("L");
            }else{
                printf("R");
            }
        }
        if(n%2 && (color[save[1]]==0 && color[n]==0) ){
            printf("L");
        }else{
            if(color[n] == 1){
                printf("L");
            }else{
                printf("R");
            }
        }
        printf("\n");
        
    }
    return 0;
}

Interleaved Output: Part 2

题意:
There are 4 printer work independently and print “IO,Io,iO,io” respectively. 然鹅四台打印机的结果混在了一起, 像这样:
index: 1 2 3 4 5 6 7 8
IO: . . . . . I . O
Io: I . . . o . . .
iO: . i O . . . . .
io: . . . i . . o .
string: I i O i o I o O
现在我们拿到的是最终混在一起的打印结果, 需要猜IO这台打印机最多打了多少个IO.
分析:
把四台一起工作的过程看成一个NFA, 不记打印机打了几次的话, 每台打印机要么就是处于打完两个字母(准备打下一个字母)的状态0, 要么就处于打完第一个字母的状态1, 这个nfa就有2^4=16种状态. 一开始四台打印机(IO,Io,iO,io)处在0=0000, 接受一个I时转移到1100=3(左低右高). 在状态转移时再带一个额外的数字k, 记录当前打了多少个IO.
最后由于只有一个终态0000, 把在此状态下的k取最大值即可

代码: 
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <stdio.h>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
const int maxn = 110;
char str[maxn];
queue< pair<int, int> > que[2];//first->which state, second->number of IO matched
map< pair<int,int>, bool>mp;
void init(){
    while(!que[0].empty()){
        que[0].pop();
    }
    while(!que[1].empty()){
        que[1].pop();
    }
    mp.clear();
}
int main(){
    int t, rnd=1;
    scanf("%d", &t);
    while(t--){
        scanf("%s", str);
        int ans = 0, len=strlen(str);
        init();
        bool flag = false;
        que[flag].push(make_pair(0, 0));
        for(int i=0; i<len; i++){
            char now = str[i];
            mp.clear();
            while(!que[flag].empty()){
                pair<int, int> q = que[flag].front(), temp;
                que[flag].pop();
                if(now=='I'){
                    if( (q.first&(1<<0)) == 0){//machine IO not print yet
                        temp = make_pair(q.first+1, q.second);
                        if(!mp[temp]){
                            que[!flag].push(temp);
                            mp[temp] = true;
                        }
                    }
                    if( (q.first&(1<<1)) == 0){//machine Io not print yet
                        temp = make_pair(q.first+2, q.second);
                        if(!mp[temp]){
                            que[!flag].push(temp);
                            mp[temp] = true;
                        }
                    }
                }else if(now == 'i'){
                    if( (q.first&(1<<2)) == 0){//machine iO not print yet
                        temp = make_pair(q.first+4, q.second);
                        if(!mp[temp]){
                            que[!flag].push(temp);
                            mp[temp] = true;
                        }
                    }
                    if( (q.first&(1<<3)) == 0){//machine io not print yet
                        temp = make_pair(q.first+8, q.second);
                        if(!mp[temp]){
                            que[!flag].push(temp);
                            mp[temp] = true;
                        }
                    }
                }else if(now == 'O'){
                    if( (q.first&(1<<0)) != 0){//machine IO has printed I
                        temp = make_pair(q.first-1, q.second+1);
                        if(!mp[temp]){
                            que[!flag].push(temp);
                            mp[temp] = true;
                        }
                    }
                    if( (q.first&(1<<2)) != 0){//machine iO has printed i
                        temp = make_pair(q.first-4, q.second);
                        if(!mp[temp]){
                            que[!flag].push(temp);
                            mp[temp] = true;
                        }
                    }
                }else{//now is 'o'
                    if( (q.first&(1<<1)) != 0){//machine Io has printed I
                        temp = make_pair(q.first-2, q.second);
                        if(!mp[temp]){
                            que[!flag].push(temp);
                            mp[temp] = true;
                        }
                    }
                    if( (q.first&(1<<3)) != 0){//machine io has printed i
                        temp = make_pair(q.first-8, q.second);
                        if(!mp[temp]){
                            que[!flag].push(temp);
                            mp[temp] = true;
                        }
                    }
                }
            }
            flag = !flag;
        }
        while(!que[flag].empty()){
            pair<int, int> q = que[flag].front();
            que[flag].pop();
            ans = max(ans, q.second);
        }
        printf("Case #%d: %d\n", rnd++, ans);
    }
    return 0;
}

题意:
平面给$N(N\leq1200)$个点, 从中取4个点组成四边形(可凸可凹), 问能组成的四边形的最小面积2(2是为了保证计算都按整数算吧).
分析:
把四边形看成两个三角形的合成, 枚举所有线段视为对角线, 再从线段两边的找个最距离最小的点构成三角形. 现在问题就是如何$O(1)$地找到这样的点(毕竟枚举线段已经$O(N^2)$). 我先把wa的代码贴着吧, 不知道哪里写挂了,这题有原题bzoj3703.
还有人迷之循环优化$O(N^3)$过了….神奇

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
80
#include <stdio.h>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
const int maxn = 1300;
const long long inf = 9000000000000000000;
pair<long long, long long> save[maxn];
map<pair<long long, long long>, int> mp;
long long getArea(pair<long long,long long> a, pair<long long, long long> b, pair<long long, long long> c){
    long long a11=b.first-a.first, a21=b.second-a.second, a12=c.first-a.first, a22=c.second-a.second;
    long long det = a11*a22-a12*a21;
    return det<0?-det:det;
    return det;
}
struct Line{
    pair<long long, long long> sta, end;
    double slope;
    Line(){
        sta = end = make_pair(0,0);
        slope = 0;
    }
    Line(pair<long long, long long> x, pair<long long, long long> y){
        sta=x, end=y;
        if(x.first == y.first){
            slope = 1e60;
        }else slope = ((y.second-x.second)*1.0f)/((y.first-x.first)*1.0f);
    }
    bool operator<(const Line&n)const{
            return slope < n.slope;
    }
}line[maxn*maxn];
int main(){
    int t, rnd=1;
    scanf("%d", &t);
    while(t--){
        int n;
        scanf("%d", &n);
        mp.clear();
        for(int i=0; i<n; i++){
            scanf("%lld%lld", &save[i].first, &save[i].second);
        }
        sort(save, save+n);
        
        for(int i=0; i<n; i++){
            mp[save[i]] = i;
        }
        long long ans = inf;
        int m = 0;
        for(int i=0; i<n; i++){
            for(int j=i+1; j<n; j++){
                line[m++] = Line(save[i], save[j]);
            }
        }
        sort(line, line+m);
        
        for(int i=0; i<m; i++){
            long long la = inf, ra = inf;
            
            if(mp[line[i].sta] > mp[line[i].end]) swap(line[i].sta, line[i].end);
            
            if(mp[line[i].sta]>0)
                la = getArea(line[i].sta, line[i].end, save[ mp[line[i].sta]-1 ]);
                
            if(mp[line[i].end]<n-1)
                ra = getArea(line[i].sta, line[i].end, save[ mp[line[i].end]+1 ]);
                
            if(la!=inf && ra!=inf)
                ans = min(ans, la+ra);
            swap(mp[line[i].sta], mp[line[i].end]);
            swap(save[mp[line[i].sta]], save[mp[line[i].end]]);
        }
        printf("Case #%d: %lld\n", rnd++, ans);
    }
    return 0;
}