kick start 2018 H

最近抽空开始刷算法题了，开始准备一下面试。

/** * 题目：https://codejam.withgoogle.com/codejam/contest/3324486/dashboard * 将字符串送进trie树，然后统计前缀，注意短的前缀确定的集合肯定包含了那些长的前缀的情况。 * 除了前缀，后面的位置可以随意取。 * O(p*n) */ #include <bits/stdc++.h> using namespace std; const int MAXSIGMA = 2; struct Node{ Node *p[MAXSIGMA]; int v; }; map<char, int> mp{ {'B', 0}, {'R', 1} }; Node* newNode(){ Node *res = new Node(); res->v = 0; for(int i = 0; i < MAXSIGMA; i++){ res->p[i] = nullptr; } return res; }; void insert(Node *rt, string s){ int n = s.length(); for(int i = 0; i < n; i++){ int c = mp[s[i]]; if(rt->p[c] == nullptr){ rt->p[c] = newNode(); } rt = rt->p[c]; } rt->v = n; } map<int, int> cnt;//用来计数 int solve(Node *rt){ for(int i = 0; i < MAXSIGMA; i++){ if(rt->p[i]){ if(rt->p[i]->v != 0){ cnt[rt->p[i]->v]++; }else{ solve(rt->p[i]); } } } } void mydel(Node *rt){ for(int i = 0; i < MAXSIGMA; i++){ if(rt->p[i]){ mydel(rt->p[i]); } } delete rt; } int main(){ //freopen("small.in", "r", stdin); //freopen("out.txt", "w", stdout); fstream in, out; in.open("large.in", ios::in); out.open("out.txt", ios::out); int t; in>>t; int n, m; for(int k = 1; k <= t; k++){ in>>n>>m; cnt.clear(); Node *trie = newNode(); string s; for(int i = 0; i < m; i++){ in>>s; auto rt = trie; insert(rt, s); } solve(trie); long long res = 0; for(auto c : cnt){ res += (1LL << (n - c.first)) * c.second; } out<<"Case #"<<k<<": "<<(1LL << n) - res<<endl; mydel(trie); } } /** * 题目：https://codejam.withgoogle.com/codejam/contest/3324486/dashboard#s=p1 * 墙只能从两边倒，而我们需要选连续的一半的墙使得value最大即可， * 其实我们只要选了第一块x，使得x两侧的墙中，不打算涂的数量不少于要涂的数量即可,这样我们总能保证在墙倒之前给它涂色 * 于是转化为求最大连续子串和。 * O(n) */ #include <bits/stdc++.h> using namespace std; int main(){ fstream in, out; in.open("large.in", ios::in); out.open("out.txt", ios::out); int t; in>>t; int n; string s; for(int k = 1; k <= t; k++){ in>>n; in>>s; int res = 0; int m = (n + 1) / 2; int j = 0; for(; j < m; j++){ res += s[j] - '0'; } int ans = res; for(; j < n; j++){ res = res - s[j-m] + s[j]; ans = max(ans, res); } out<<"Case #"<<k<<": "<<ans<<endl; } } /** * 题目：https://codejam.withgoogle.com/codejam/contest/3324486/dashboard#s=p2 * 容斥原理 * res = 全部的排列 - 1对夫妻相邻 + 两对夫妻相邻 - 三对夫妻相邻... * 注意求组合数的时候有除法要求逆元。 * O(n + m) */ #include <bits/stdc++.h> using namespace std; typedef long long LL; const int MOD = 1e9+7; const int MAXN = 200010; LL a[MAXN], b[MAXN]; //阶乘、2的幂 LL quickpow(LL a, LL b){ LL res = 1, temp = a % MOD; while(b){ if(b & 1) res = res * temp % MOD; b >>= 1; temp = temp * temp % MOD; } return res; } int inv(int x){ return quickpow(x, MOD-2); } int main(){ fstream cin, cout; cin.open("large.in", ios::in); cout.open("out.txt", ios::out); int t; a[0] = 1; b[0] = 1; for(int i = 1; i < MAXN; i++){ a[i] = a[i - 1] * i % MOD; b[i] = b[i - 1] * 2 % MOD; } cin>>t; int n, m; for(int k = 1; k <= t; k++){ cin>>n>>m; int nn = n * 2; int res = 0; LL c = m; for(int i = 1; i <= m; i++){ if(i&1){ res = (res + a[nn-i] * b[i] % MOD * c % MOD) % MOD; }else{ res = (res - a[nn-i] * b[i] % MOD * c % MOD + MOD) % MOD; } c = c * (m - i) % MOD * inv(i + 1) % MOD; //c = c * (m - i) / (i + 1); } cout<<"Case #"<<k<<": "<<(a[nn] - res + MOD) % MOD<<endl; } } /** * 题目：https://codejam.wit