北屿

北屿小智障

0%

KickStart2020 Round A

Posted on Edited on In

好不容易记得一次比赛2333，希望还能记得codejam
题比较简单，100min我差不多做完rk400+，T3T4各提交错误了一次
最后rk429

T1 Allocation

Description

有$N$个房子要销售，有$B$块钱，每个房子价格$A_i$，问最多买多少套房子
$T\leqslant 100, N\leqslant 10^5, B\leqslant 10^5, A_i\leqslant 1000$

Solution

一开始被$B,A_i$的范围骗了233，以为是背包优化什么的
wdnmd排序贪心就完事了

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
#include <bits/stdc++.h>
using namespace std;

const int N = 100050;

int a[N];

int main() {
    int T, n, B, ans, tmp;
    scanf("%d", &T); 
    for(int t=1; t<=T; t++) {
        scanf("%d%d", &n, &B);
        for(int i=1; i<=n; i++) scanf("%d", &a[i]);
        ans = 0, tmp=0;
        
        sort(a+1, a+n+1);
        for(int i=1; i<=n; i++) {
            if(tmp+a[i]<=B) {
                tmp += a[i];
                ans++;
            } else break;
        }
        printf("Case #%d: %d\n", t, ans);
    }
    return 0;
}

T2 Plates

Description

$N$摞碟子，每摞$K$个碟子，每个碟子有一个权值，选一个碟子要选以上的所有碟子，选$P$个碟子问最多的权值
$T\leqslant 100, N\leqslant 50, K\leqslant 30, P\leqslant N\times K$

Solution

就dp咯
f[i][j]表示前i摞碟子选j个获得的最大权值，转移就是枚举这摞碟子选几个f[i][j]=max{f[i][j], f[i-1][j-k]}，枚举k
简单背包，复杂度就是$O(NKP)$

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
#include <bits/stdc++.h>
using namespace std;

const int N = 55;
const int K = 33;

int a[N][K];
int f[N][N*K];

int main() {
    int T, n, k, p;
    scanf("%d", &T);
    for(int t=1; t<=T; t++) {
        scanf("%d%d%d", &n, &k, &p);
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=k; j++) {
                scanf("%d", &a[i][j]);
                a[i][j]+=a[i][j-1];
            }
        }
        
        memset(f, 0, sizeof(f));
        for(int i=1; i<=n; i++) {
            for(int j=0; j<=k; j++) {
                for(int u=j; u<=p; u++) {
                    f[i][u]=max(f[i][u], f[i-1][u-j]+a[i][j]);
                }
            }
        }
        printf("Case #%d: %d\n", t, f[n][p]);
    }
    return 0;
}

T3 Workout

Description

一个长度为$N$的序列，中间可以插入$K$个元素，让相邻的差最小，问最小多少。

Solution

一开始想到的是贪心，写了一个堆，发现并不对233
例如10 20中间插入4个的时候，应该是10 12 14 16 18 20，但如果每次选最多的再插入一开始就会出现15，然后出现小数，不妥
贪心也确实是正确的，再每次强行截断就可以，这就需要二分答案了，然后贪心判断就可以了。复杂度就是$O(N\log N)$

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
#include <bits/stdc++.h>
using namespace std;

const int N = 100050;
typedef long long ll;

int n;
int a[N];

int check(int x) {
    int ans=0;
    for(int i=2; i<=n; i++) {
        double t=1.0*(a[i]-a[i-1])/x;
        ans+=ceil(t)-1;
    } return ans;
}
int main() {
    int T, k;
    scanf("%d", &T);
    for(int t=1; t<=T; t++) {
        scanf("%d%d", &n, &k);
        for(int i=1; i<=n; i++) {
            scanf("%d", &a[i]);
        }
        ll l=1, r=1e9, mid;
        while(l<=r) {
            mid=(l+r)>>1;
            if(check(mid)<=k) r=mid-1;
            else l=mid+1;
        } printf("Case #%d: %lld\n", t, l);
    }
    return 0;
}

T4 Bundling

Description

$N$个字符串，分成每组$K$个，$N$能被$K$整除，每组的贡献是最长公共前缀的长度，问最多贡献。
$T\leqslant 100, K\leqslant N\leqslant 10^5, \text{the total number of characters} \leqslant 2\times 10^6$

Solution

首先想到的还是贪心，直接sort然后选相邻的。
但这样是不对的，举个例子这样会破坏后面的高贡献

1
2
3
4
5
4 2
AAA
OOOOOOOO
OOOOOOOO
ZZZZ

这种情况显然让A和Z去配对，留下较长的。
一般最长公共前缀都会想到Trie树吧，Trie树上的最近公共祖先的深度就是最长公共前缀，那就想想怎么用Trie树做
感觉应该是一个树形DP的样子
最后也比较简单咯，还是用到了一个贪心的想法，如果一个子树中数量大于$K$个，那么显然不可能让这些去和别的子树组成一组，而是让多余的组成一组。那么去除子树中整个组的元素，剩下的具体是那些我们其实是并不关心的，因为他们一定和其他子树组成一组，最长公共前缀一定在当前节点或者更网上的节点。如果剩下的所有的元素可以组成一个新组，那么一定在这个节点的地方组。
说白了，就是从下往上选组，够$K$个就在当前节点合并，不够就继续往上传。
复杂度就是节点个数，遍历了一遍，再乘上26的常量。
ps.这题的样例有点弱，自己造一下试试

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
#include <bits/stdc++.h>
using namespace std;

const int N = 2000500;

int T, n, k;

struct Trie {
    int rt, cnt;
    int ch[N][26];
    int sz[N], tsz[N];
    
    int newnode() {
        cnt++;
        memset(ch[cnt], 0, sizeof(ch[cnt]));
        sz[cnt]=0, tsz[cnt]=0;
        return cnt;
    }
    void init() {
        cnt=0;
        rt=newnode();
    }
    
    void insert(string a) {
        int x=rt;
        for(int i=0; i<a.length(); i++) {
            int v=a[i]-'A'; sz[x]++;
            if(!ch[x][v]) ch[x][v]=newnode();
            x=ch[x][v];
        } sz[x]++, tsz[x]++;
    }
    
    int dp(int x, int d) {
        int t=tsz[x], res=0;
        for(int i=0; i<26; i++) if(ch[x][i]) {
            if(sz[ch[x][i]]>=k) res+=dp(ch[x][i], d+1);
            t+=sz[ch[x][i]]%k;
        } res+=int(t/k)*d;
//		cout << x << " " << d << " " << sz[x] << " " << tsz[x] << " " << res << endl; 
        return res;
    }
} tr;

int main() {
    scanf("%d", &T);
    for(int t=1; t<=T; t++) {
        scanf("%d%d", &n, &k);
        tr.init();
        for(int i=1; i<=n; i++) {
            string s; cin >> s;
            tr.insert(s);
        }
        printf("Case #%d: %d\n", t, tr.dp(tr.rt, 0));
    }
    return 0;
}
/*
1
8 2
GOO
GO
ART
ART
GOOO
AT
PPPP
OOO
*/
Related Posts
Have fun.