首页 > 代码库 > google Round D APAC Test 2017 题解

google Round D APAC Test 2017 题解

首先说明一下:我只是用暴力过了4道题的小数据,就是简单的枚举,大数据都不会做!下面的题解,是我从网上搜到的解答以及查看排行榜上大神的答案得出来的。

首先贴一下主要的题解来源:http://codeforces.com/blog/entry/47796,基本上解题思路都是从这里看到的,你可以直接查看这个链接,或者看下面的题解。

还有排行榜大神们的答案,https://code.google.com/codejam/contest/5264486/scoreboard?c=5264486#vf=1,你可以下载所有的答案,进行查看。

当然,首先你得看懂题意,题目从官网上查看,这里就不介绍了。

第一题

1.看完题,怎么感觉这道这么难,难道不是第一道题最简单的套路了么?其实,如果你知道那个问题的话,答案非常简单。

简单的想法,就是枚举合法的序列,长度为(n + m),枚举过程中保证合法性,最后把所有的结果加起来,就是最后的答案,注意,这里求的是概率,所有可能的个数是(n + m)!,而且最后串的长度也是n+m,可以考虑每一次枚举除以因子,从1到n+m,这样算出来就是概率。这里小数据很容易就过了,小数据的数据范围是20,2^20 = 1e6,可以满足要求。大数据是4000,2^4000,根本不行,所以考虑其他途径。

2. 那就是动态规划,枚举当前a和b得票的个数,记dp[a][b],考虑最后一次是投给谁的票,然后可以从dp[a - 1][b]和dp[a][b-1]进行转移,注意这个过程中转移的条件,以及a>b必须满足,其他的dp[a][b] = 0;最后的结果是dp[n][m].这个计算过程也要考虑上面的分母因子。

技术分享
 1 void solve() { 2     int x, y; 3     cin >> x >> y; 4     memset(dp, 0, sizeof dp); 5     dp[0][0] = 1; 6     for (int i = 1; i <= x; i++) { 7         for (int j = 0; j <= y; j++) { 8             if(i <= j) continue; 9             dp[i][j] = dp[i - 1][j] * (x - i + 1) / (x + y - i - j + 1);10             if(i >= j + 1 && j > 0)11                 dp[i][j] += dp[i][j - 1] * (y - j + 1) / (x + y - i - j + 1);12         }13     }14     printf("%.10f\n", dp[x][y]);15 }
View Code

第一名比较巧妙的递推:

技术分享
 1 void init() { 2     for (int i = 1; i <= 2000; i++) dp[i][0] = 1; 3     for (int i = 1; i <= 2000; i++) { 4         for (int j = 1; j < 2000; j++) { 5             if(i <= j) continue; 6             double p1 = 1.0 * i / (i + j); 7             double p2 = 1 - p1; 8             dp[i][j] = dp[i - 1][j] * p1 + dp[i][j - 1] * p2; 9         }10     }11 }
View Code

3. 其实答案就是(n - m)/(n + m), https://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem,可以看一下证明过程

 第二题

1. 小数据5*5,一共有2^25 = 32000000种方式,然后检查一下是否满足条件,最后找到满足要求的最大值。注意这里的情况可能有25种输入,而小数据的测试数据是100,也就是每种情况可以重复4次,可以提前算出所有答案,进行查表。

2. 大数据是100,100,无法进行枚举,然后就观察情况,找规律。可以发现下面的规律。

3. (r,c)和(c,r)的答案是一样的,所以只考虑r<=c的情况。r = 1的时候,答案是 c - c / 3, 例如110110110110这样。r = 2的时候,ans= 2*(c - c / 3),答案是r=1的时候重复2行。下面考虑其他情况。

4. r >= 3.观察

110110110110

101101101101

011011011011

可以发现每三行这样重复,一定是满足要求的,而且这样摆放是最多的,因为每三个至少有一个空白,上面的摆法就是没3个一个空白。然后根据r%3的情况考虑那一行应该放前面。

r%3 == 0, 随意都可以,观察,答案就是 r / 3 * c * 2, 3行一组, 每一组每一列刚好2个1.

r%3 == 1, 只需要考虑最后一行,使得左边的1尽可能的多,循环的3行里面满足要求的只有第一行,110110110,这样左边,然后答案也很明显,就是 r / 3 * c * 2 + c - c / 3;

r%3 == 2,也是考虑最后2行,使得左边的1尽可能的多,然后就有2种组合:

110110110110

101101101101

或者:

110110110110

011011011011

显然,上面那种情况比较优, 答案就是 r / 3 * c * 2 + c + (c + 2) / 3.

然后,就是这样。

第三题

1. 遇到这题,很容易想到的一个解法就是在当前位置,枚举接下来可能出现的单词,从前往后枚举,如果所有字符都是单词,则结果+1,可以把每个字符出现过的单词链接起来,加速枚举过程,小数据,就这样很容过了,但是大数据,通过 一个一个数的方式,大数据是过不了的,还得想其他的办法。

2.还是动态规划,以单词长度为一维,考虑到该位置的所有可能数,考虑这个数怎么计算。我的想法是依次枚举每个单词,看这个单词能不能出现,然后结果就是dp[i] = dp[i] + dp[i - size(word)]。这里每一个word都要判断。最后的结果就是dp[size(sentence)]。计算一下复杂度,4000 * 400 * 20 = 32000000,可以在时限内完成。

贴一下代码:

技术分享
 1 const int mod = 1e9 + 7; 2 vector<string> s; 3 int dp[4010]; 4 int n, m; 5 void solve() { 6     cin >> n >> m; 7     s.clear(); string t; 8     for (int i = 0; i < n; i++) { 9         cin >> t; s.pb(t);10     }11     while(m--) {12         cin >> t;13         int len = t.size();14         memset(dp, 0, sizeof dp);15         dp[0] = 1;16         for (int i = 1; i <= len; i++) {17             for (int j = 0; j < n; j++) {18                 vector<int> v(26, 0);19                 if(i >= s[j].size()) {20                     for (int x = 0; x < s[j].size(); x++) {21                         v[t[i - x - 1] - a]++;22                         v[s[j][x] - a ]--;23                     }24                     bool f = 1;25                     for (int x = 0; x < 26; x++) {26                         if(v[x] != 0) {f = 0;27                             break;28                         }29                     }30                     if(f) {31                         dp[i] = (dp[i] + dp[i - s[j].size() ]) % mod;32                     }33                 }34             }35         }36         cout <<   << dp[len];37     }38 }
View Code

这里可以考虑加速过程,2个单词,如果他们含有的字母以及个数相同,虽然顺序不同,但是可以算作一个单词,可以通过长度26的数组,算出一个值,统计每个字符的个数,算作这个word的hash值,这样复杂度就可以缩小一个因子,通过map来统计这样处理后相同的单词的个数来做,由于每个单词长度最多是20,所以复杂度就是4000 * 20,map查找的过程可以认为是O(1),下面贴一下第一名大神的代码。

技术分享
 1 #include <cstdio> 2 #include <map> 3 #include <vector> 4  5 using namespace std; 6  7 const int N = 4001; 8 const int mod = 1000000007; 9 10 map<vector<int>, int> c;11 char s[N];12 int dp[N];13 int n, m;14 15 inline void update(int &a, long long b) {16     a = (a + b) % mod;17 }18 19 int main() {20     int t, tt;21     scanf("%d", &t);22     for (tt = 1; tt <= t; tt++) {23         scanf("%d%d", &n, &m);24         c.clear();25         for (int i = 0; i < n; i++) {26             vector<int> a(26);27             scanf("%s", s);28             for (int j = 0; s[j] != \0; j++) a[s[j] - a]++;29             c[a]++;30         }31         printf("Case #%d:", tt);32         for (int i = 0; i < m; i++) {33             scanf("%s", s);34             int ls = strlen(s);35             dp[0] = 1;36             for (int j = 0; j < ls; j++) {37                 dp[j + 1] = 0;38                 vector<int> a(26);39                 for (int k = 0; k < 20 && j - k >= 0; k++) {40                     a[s[j - k] - a]++;41                     map<vector<int>, int>::iterator it = c.find(a);42                     if (it != c.end()) update(dp[j + 1], (long long)dp[j - k] * it->second);43                 }44             }45             printf(" %d", dp[ls]);46         }47         printf("\n");48     }49     return 0;50 }
View Code

这里我第一次看见vector也可以作为map键值的代码,真是开阔眼界了。学习一下。其实这道题,就跟普通的dp套路一样,总长度一般作为一维,枚举最后一个单词是什么,然后加上前面的长度的结果,而这些结果已经提前计算出来了,然后就可以递推了,这个套路很一般,如果一眼能看到,应该很容易ac,码代码难度也不是很大。

第四题

1.看题,看到区间,价值,单个区间可能比几个区间加起来的价值还小,所以贪心是不行的,然后我看到小数据范围是10,2^10=1024,简单的可以枚举所有情况,所以小数据就暴力,很简单的就过了!接下来考虑大数据,2^1000,去枚举肯定是不行的,需要寻找其他路径。

2.这也是dp,这次dp的题怎么这么多,(可以总结一下一般的套路,dp(计数,概率),二分(比较难的二分,最大最小),位操作,加上一些stack,queue的题目,还有什么以后再加),看别人的答案,有需要线段树的,其实是维护滑动窗口内的最小值,这个可以通过deque,速度非常快,上次也是apac也做到,专门考这个知识点的,那个题比较水,因为一眼可以看出来是考哪个知识点的,所以很容易想到,这道题目,不仔细分析,想不到用这个吧。

双端队列维护滑动窗口内的最大值或者最小值的题目:https://code.google.com/codejam/contest/4284487/dashboard#s=p3就是这个,维护窗口内最大值,是二维的,可以轻松的转化到一维的情况。

这个题目,其实一开始可以考虑用dp,因为一般最小值,然后是加起来,还有方案数,各种组合,跟具体的组合无关的,一般是dp,这还是最后一题,dp的可能性最大。然后是以输入的区间个数为一维,模仿背包的过程,每来一个区间段,对所有可能的结果进行更新。

3. 然后就想到第二维是结果的可能哪一位,最后求长度L的最小值,然后小于这个长度需要先计算出来,每来一个新的区间段,看这个区间段可以对那些长度进行更新,考虑是0/1背包,可以对长度从大到小更新,从而可以省去线段个数这一维,也是dp的第一维。考虑这样的转移方式,dp[i] = min(dp[i],  min(dp[i - r], dp[i - l]) + c), 当前的输入区间是(l, r), 花费是 c, 接下来需要考虑的就是如何高效的维护min(dp[i - r], dp[i - l]) , 对于从1~L的区间每一个点都需要更新,(这里dp[0] = 0,这是初始化条件,不需要更新,)每一个都需要前面的一个区间的最小值来更新, 这个区间是固定大小的,滑动的,可以通过上面的deque来维护, 或者可以同线段树来维护区间的最小值,复杂度是O(logn),单点更新,(这里不需要区间更新,线段树写起来还是比较简单的)。

下面的过程都很明朗了,直接码代码就可以了!

先是线段树代码,可以使用线段树模板。(下面是排名第二的大神的思路,我用自己熟悉的线段树写的)。

技术分享
 1 #include<bits/stdc++.h> 2 #define pb push_back 3 #define FOR(i, n) for (int i = 0; i < (int)n; ++i) 4 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl 5 typedef long long ll; 6 using namespace std; 7 typedef pair<int, int> pii; 8 const int maxn = 1e4 + 10; 9 const ll inf = 1ll << 60;10 ll f[maxn * 4];11 int x, y;12 ll v;13 void bt(int o, int l, int r) {14     if(l == r) {15         f[o] = 1ll << 60;16     } else {17         int mid = (l + r) / 2;18         bt(o * 2, l, mid);19         bt(o * 2 + 1, mid + 1, r);20         f[o] = min(f[o * 2], f[o * 2 + 1]);21     }22 }23 void update(int o, int l, int r) {24     if(l == r && l == x) {25         f[o] = min(f[o], v);26     } else {27         int mid = (l + r) / 2;28         if(x <= mid) update(o * 2, l, mid);29         else update(o * 2 + 1, mid + 1, r);30         f[o] = min(f[o * 2], f[o * 2 + 1]);31     }32 }33 ll ask(int o, int l, int r) {34     if(r < x || l > y) return 1ll << 60;35     if(x <= l && r <= y) return f[o];36     int mid = (l + r) / 2;37     ll res = 1ll << 60;38     if(x <= mid) res = min(res, ask(o * 2, l, mid));39     if(y > mid) res = min(res, ask(o * 2 + 1, mid + 1, r));40     return res;41 }42 int n, m, l;43 void solve() {44     cin >> n >> m >> l;45     bt(1, 0, l);46     x = 0, v = 0;47     update(1, 0, l);48     int tl, tr, p;49     for (int i = 1; i <= n; i++) {50         cin >> tl >> tr >> p;51         for (int j = l; j >= 1; j--) {52             int cl = max(0, j - tr);53             int cr = min(j - 1, j - tl);54             if(cl <= cr) {55                 x = cl, y = cr;56                 ll t = ask(1, 0, l);57                 //cout << i << " " << j << " " << cl << " " << cr << " " << t << endl;58                 x = j; v = t + p;59                 update(1, 0, l);60             }61         }62     }63     x = y = l;64     ll res = ask(1, 0, l);65     if(res <= m) {66         cout << res << endl;67     } else {68         cout << "IMPOSSIBLE" << endl;69     }70 }71 int main() {72     freopen("test.in", "r", stdin);73     freopen("test.out", "w", stdout);74     int _; cin >> _;75     for (int i = 1; i <= _; i++) {76         cout << "Case #" << i << ": ";77         solve();78     }79 80     return 0;81 }
View Code

接着是deque代码,这个是排名第一的大神的代码,写的非常漂亮。

技术分享
 1 #include <cstdio> 2 #include <algorithm> 3  4 using namespace std; 5  6 const int N = 10001; 7 const long long INF = ~0ull >> 2; 8  9 long long dp[N];10 int n, m, l;11 int d[N], p, q;12 13 int main() {14     freopen("test.in", "r", stdin);15     freopen("test.out", "w", stdout);16     int t, tt;17     scanf("%d", &t);18     for (tt = 1; tt <= t; tt++) {19         for (int i = 1; i < N; i++) dp[i] = INF;20         dp[0] = 0;21         scanf("%d%d%d", &n, &m, &l);22         for (int i = 0; i < n; i++) {23             int a, b, c;24             scanf("%d%d%d", &a, &b, &c);25             p = q = 0;26             for (int j = a; l - j >= 0 && j < b; j++) {27                 while (q > p && dp[d[q - 1]] >= dp[l - j]) q--;28                 d[q++] = l - j;29             }30             for (int j = l; j >= 0; j--) {31                 if (j - b >= 0) {32                     while (q > p && dp[d[q - 1]] >= dp[j - b]) q--;33                     d[q++] = j - b;34                 }35                 if (p < q) dp[j] = min(dp[j], dp[d[p]] + c);36                 if (d[p] >= j - a) p++;37             }38         }39         if (dp[l] <= m) printf("Case #%d: %lld\n", tt, dp[l]);40         else printf("Case #%d: IMPOSSIBLE\n", tt);41     }42     return 0;43 }
View Code

总结:

这次4道题,3道dp,一道找规律,如果有一些套路,加上简单思考应该可以做出来吧!看了这些大神的代码,恍然大悟,原来是这样,需要一些小的知识点,比如上面第四题(这些知识通过平时的积累),还有遇到问题怎么分析,怎么分析,就是套路,多做题练习和思考,多掌握一些套路,以后总会有帮助的。

google Round D APAC Test 2017 题解