Code Jam Round 1C 2018

A Whole New Word

暴力

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 char s[11], t[11];
 5 set<string> S;
 6 map<char, int> cnt[11];
 7 int ok, L;
 8 
 9 void dfs(int l){
10     if(l == L + 1){
11         t[l] = 0;
12         if(S.find(string(t + 1)) != S.end()) return;
13         ok = 1;
14         puts(t + 1);
15         return;
16     }
17     for(char c = 'A'; c <= 'Z'; c++){
18         if(ok) return;
19         if(cnt[l].find(c) == cnt[l].end()) continue;
20         t[l] = c;
21         dfs(l + 1);
22     }
23 }
24 
25 int main(){
26     int T;
27     scanf("%d", &T);
28     for(int kase = 1; kase <= T; ++kase){
29         S.clear();
30         int N;
31         scanf("%d %d", &N, &L);
32         for(int i = 1; i <= L; ++i) cnt[i].clear();
33         for(int i = 1; i <= N; ++i){
34             scanf("%s", s + 1);
35             S.insert(string(s + 1));
36             for(int j = 1; j <= L; ++j)
37                 cnt[j][s[j]]++;
38         }
39         ok = 0;
40         printf("Case #%d: ", kase);
41         dfs(1);
42         if(!ok) puts("-");
43     }
44     return 0;
45 }

Aguin

Lollipop Shop

贪心出现次数少的

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 int cnt[222], vis[222];
 5 
 6 int main(){
 7     int T;
 8     scanf("%d", &T);
 9     while(T--){
10         int n;
11         scanf("%d", &n);
12         memset(cnt, 0, sizeof(cnt));
13         memset(vis, 0, sizeof(vis));
14         for(int i = 1; i <= n; ++i){
15             int x, y, m = 222, p = -1;
16             scanf("%d", &x);
17             for(int j = 1; j <= x; ++j){
18                 scanf("%d", &y);
19                 cnt[y]++;
20                 if(vis[y]) continue;
21                 if(cnt[y] < m) m = cnt[y], p = y;
22             }
23             if(p != -1) vis[p] = 1;
24             cout << p << endl;
25         }
26     }
27     return 0;
28 }

Aguin

Ant Stack

暴力一下发现最多一百多层

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const LL INF = 1e18;
 5 LL f[222];
 6 
 7 int main(){
 8     int T;
 9     scanf("%d", &T);
10     for(int kase = 1; kase <= T; ++kase){
11         for(int i = 1; i <= 200; ++i) f[i] = INF;
12         int n, w, ans = 0;
13         scanf("%d", &n);
14         for(int i = 1; i <= n; ++i){
15             scanf("%d", &w);
16             for(int j = 200; j >= 0; j--){
17                 if(6LL * w >= f[j]) f[j+1] = min(f[j+1], f[j] + w);
18             }
19         }
20         for(int i = 1; i <= 200; ++i)
21             if(f[i] != INF) ans = i;
22         printf("Case #%d: %d
", kase, ans);
23     }
24     return 0;
25 }

Aguin