题目在这里啊
A.最长上升子序列，范围很小所以写了简单的O(n^2)算法
#include <iostream> #define rep(i, j, k) for(int i = j;i <= k;i ++) #define rev(i, j, k) for(int i = j;i >= k;i --) using namespace std; typedef long long ll; int n, m, a[1111], f[1111]; int main() { ios::sync_with_stdio(false); cin >> n; rep(i, 1, n) cin >> a[i]; rep(i, 1, n) { f[i] = 1; rep(j, 1, i - 1) { if(a[j] < a[i]) f[i] = max(f[i], f[j] + 1); } } rep(i, 1, n) m = max(m, f[i]); cout << m; return 0; }
B.Sum( C[i] * G[i] ) = 0 的方案数嘛
就是个分组背包问题嘛，O(n^2 * m^2 * max_weight)
#include <iostream> #include <cstdio> using namespace std; int n, m, x, y, s, t, a[23], f[23][23333]; int main() { ios::sync_with_stdio(false); cin >> n >> m, f[0][0] = 1; for(int i = 1;i <= n;i ++) cin >> a[i], a[i] += 15; for(int i = 1;i <= m;i ++) { cin >> x, s += x; for(int j = 1;j <= n;j ++) { y = x * a[j]; for(int k = 15000;k >= y;k --) { f[i][k] += f[i - 1][k - y]; } } } printf("%d ", f[m][s * 15]); return 0; }
C.就是个阶乘+组合数，合在一起或者分开算都是ok的
不到30其实就能爆掉longlong了...题目保证不爆了就不管了
对，初始化请不要忘记有 k = 0
#include <bits/stdc++.h> #define rep(i, j, k) for(int i = j;i <= k;i ++) #define rev(i, j, k) for(int i = j;i >= k;i --) using namespace std; typedef long long ll; ll b[1000], a[31][901]; int t, n, k; int main() { ios::sync_with_stdio(false); a[1][1] = b[0] = b[1] = 1; rep(i, 1, 30) a[i][0] = 1; rep(i, 2, 30) { b[i] = b[i - 1] * i; rep(j, 1, i) a[i][j] = a[i - 1][j - 1] + a[i - 1][j]; } cin >> t; rep(i, 1, t) { cout << "Case "<< i <<": "; cin >> n >> k; cout << a[n][k] * a[n][k] * b[k] << endl; } return 0; }
D.回文串好多都是区间DP
f[i][j]代表从 i 到j 这段区间能弄出多少种回文串
其实我的DP转移方程是对着样例数据YY出来的...
if(s[i] == s[j]) f[i][j] = f[i + 1][j] + f[i][j - 1] + 1
else f[i][j] = f[i + 1][j] + f[i][j - 1] - f[i + 1][j - 1]
因为不满足 s[i] == s[j] 的话，那样子加就会重复计算，所以需要减去重复部分
否则的话，因为这段区间两边字母相同
所以就可以在它们中间夹上f[i + 1][j - 1]种回文串(所以不用减重复
另外也可以什么都不加，所以还要 +1
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); int t; ll f[70][70]; string s; cin >> t; for(int i = 1;i <= t;i ++) { cin >> s; memset(f, 0, sizeof f); for(int j = 0;j < s.size();j ++) f[j][j] = 1; for(int d = 1;d < s.size();d ++) for(int j = 0;j + d < s.size();j ++) { int k = j + d; if(s[j] == s[k]) f[j][k] = f[j + 1][k] + f[j][k - 1] + 1; else f[j][k] = f[j + 1][k] + f[j][k - 1] - f[j + 1][k - 1]; } cout << "Case " << i << ": " << f[0][s.size() - 1] << endl; } return 0; }
E.我说Floyed你就会了吧，这就很有灵性！
#include <iostream> #include <cstring> #include <cstdio> #define rep(i, j, k) for(int i = j;i <= k;i ++) #define rev(i, j, k) for(int i = j;i >= k;i --) using namespace std; typedef long long ll; string s; bool f[26][26]; int main() { ios::sync_with_stdio(false); while(cin >> s) { if(s[0] == '0') { rep(k, 0, 25) rep(i, 0, 25) rep(j, 0, 25) f[i][j] |= f[i][k] & f[k][j]; puts(f[1][12] ? "Yes." : "No."); memset(f, 0, sizeof f); } else f[s[0] - 'a'][*(s.end() - 1) - 'a'] = 1; } return 0; }
F.不存在任何一条路径上有两点颜色相同...
n*m的矩阵，路径固定长度为n + m - 1，所以n + m - 1 > k 就不存在方案
...所以n , m <= 1000完全开玩笑的
直观来看最坏情况就是在5 * 6的矩阵里
我们考虑爆搜+检验，O(10 ^ 30 * n * m)
1. 优化一下，压位来记录前 [ i * j ] 矩阵（不含a[i][j]）里用过的颜色
来确定a[i][j]的可选颜色，然后这样大概在O(10 ^ 20)
2.再优化一下，如果前 [ i * j ] 矩阵（不含a[i][j]）里用过的颜色数为 C
那么剩下部分（含a[i][j]）最少需要颜色数 D = n - i + m - j - 1 + 2
如果 C + D > k 那么当前方案是不可能有解的， 这样大概 O(玄学)
当然仍过不了5 * 6 矩阵初始全空的情况
3.再优化一下，当前位置如果染色为 p 或 q
这两种颜色都是第一次被使用
即之前的dfs中染过色的以及初始就被染色的部分都没使用过这两种颜色
那么我们可以认为这两种颜色是等价的
换句话说就是当前位置染色为 p 再dfs下去
和当前位置染色为 q 再dfs下去对答案的贡献是一样的
所以可以只算一个，另一个直接加上就可以了
这时候效率O(玄学 --), 5 * 6 矩阵初始全空的情况已经能过了...
大力交一发能过了...15ms很快乐
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int Mod = 1e9 + 7; int n, m, k, a[12][12]; int used[11], g[12][12], f[12][12]; ll dfs(int x, int y) { if(y > m) x ++, y = 1; if(x > n) return 1; int z = __builtin_popcount(g[x][y] = g[x - 1][y] | g[x][y - 1]); if(z + n - x + m - y + 1 > k) return 0; ll ret = 0, tmp = -1; if(!a[x][y]) { for(int i = 1;i <= k;i ++) { if((g[x][y] | f[x][y]) & (1 << i)) continue; used[i] ++, g[x][y] |= (1 << i); if(used[i] == 1) { if(tmp == -1) tmp = dfs(x, y + 1); ret += tmp; } else { ret += dfs(x, y + 1); } used[i] --, g[x][y] ^= (1 << i); } } else { g[x][y] |= (1 << a[x][y]); ret = dfs(x, y + 1); } return ret % Mod; } int main() { ios::sync_with_stdio(false); cin >> n >> m >> k; if(n + m - 1 > k) { puts("0"); return 0; } for(int i = 1;i <= n;i ++) for(int j = 1;j <= m;j ++) { cin >> a[i][j]; if(a[i][j]) used[a[i][j]] ++; } for(int i = n;i;i --) for(int j = m;j;j --) { if(a[i][j] && ((f[i + 1][j] | f[i][j + 1]) & (1 << a[i][j]))) { puts("0"); return 0; } f[i][j] = f[i + 1][j] | f[i][j + 1] | (1 << a[i][j]); } cout << dfs(1, 1) % Mod << endl; return 0; }
G.结论题啦
3次bfs找到一条树的直径两个端点 s t
然后ans[i] = max( dis(i, s) , dis(i, t) )
#include <bits/stdc++.h> #define rep(i, j, k) for(int i = j;i < (k + 1);i ++) #define rev(i, j, k) for(int i = j;i >= k;i --) using namespace std; typedef long long ll; int n, st, en, vis[11111], dis[3][11111]; vector <pair<int, int> > e[11111]; queue <int> q; void bfs(int s, int t) { static int u;en = 0; memset(dis[t], 0, sizeof dis[t]); memset(vis, -1, sizeof vis); q.push(s), vis[s] = t; while(!q.empty()) { u = q.front(), q.pop(); rep(i, 0, e[u].size() - 1) if(t != vis[e[u][i].first] && dis[t][e[u][i].first] < dis[t][u] + e[u][i].second) { dis[t][e[u][i].first] = dis[t][u] + e[u][i].second; q.push(e[u][i].first), vis[e[u][i].first] = t; } } rep(i, 1, n) if(dis[t][i] > en) en = dis[t][i], st = i; } int main() { int u, v; ios::sync_with_stdio(false); while(cin >> n) { rep(i, 1, n) e[i].clear(); rep(i, 2, n) cin >> u >> v, e[i].push_back(make_pair(u, v)), e[u].push_back(make_pair(i, v)); bfs(1, 0), bfs(st, 1), bfs(st, 2); rep(i, 1, n) cout << max(dis[1][i], dis[2][i]) << endl; } return 0; }
H.显然所有环都需要1次变成树
然后再数出树的数量，再并到一棵树上
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 200010; vector <int> e[maxn]; int n, m, f[maxn], v[maxn], root[maxn]; void dfs1(int x) { v[x] = 1; for(int i = 0;i < e[x].size();i ++) if(e[x][i] != x) dfs1(e[x][i]); } int dfs2(int x, int t, int y = 0) { if(v[x] == t) return 1; else if(v[x] != 0 && v[x] != t) return 0; v[x] = t; for(int i = 0;i < e[x].size();i ++) y |= dfs2(e[x][i], t); return y; } int main() { ios::sync_with_stdio(false); cin >> n; for(int i = 1;i <= n;i ++) cin >> f[i], e[f[i]].push_back(i); for(int i = 1;i <= n;i ++) if(f[i] == i) dfs1(i), root[++ root[0]] = i, m = 1; for(int i = 1;i <= n;i ++) if(!v[i] && dfs2(i, i)) root[++ root[0]] = i; if(m) { cout << root[0] - 1 << endl; for(int i = 2;i <= root[0];i ++) f[root[i]] = root[1]; for(int i = 1;i <= n;i ++) cout << f[i] << " "; } else { cout << root[0] << endl; for(int i = 1;i <= root[0];i ++) f[root[i]] = root[1]; for(int i = 1;i <= n;i ++) cout << f[i] << " "; } return 0; }
I.转一下能不能转好，一共就只有12种转法...
除去顺时针和逆时针就是6种，枚举一下再验证吧
#include <iostream> #include <cstdio> #define rep(i, j, k) for(int i = j;i <= k;i ++) using namespace std; int f[6][8] = { 1, 3, 5, 7, 9, 11, 13, 15, 2, 4, 6, 8, 10, 12, 14, 16, 1, 2, 21, 22, 12, 11, 17, 18, 3, 4, 23, 24, 10, 9, 19, 20, 5, 6, 23, 21, 16, 15, 18, 20, 7, 8, 24, 22, 14, 13, 17, 19 }; bool judge(int *a) { for(int i = 1;i < 24;i += 4) if(!(a[i] == a[i + 1] && a[i] == a[i + 2] && a[i] == a[i + 3])) return 0; return 1; } bool ok(int *a, int *b, int ret = 0) { static int c[16]; rep(i, 0, 7) c[i] = c[i + 8] = a[b[i]]; rep(i, 0, 7) a[b[i]] = c[i + 2]; ret |= judge(a); rep(i, 0, 7) a[b[i]] = c[i + 6]; ret |= judge(a); rep(i, 0, 7) a[b[i]] = c[i]; return ret; } int main() { ios::sync_with_stdio(false); int n, m, a[30]; cin >> n; rep(i, 1, n) { rep(i, 1, 24) cin >> a[i];m = judge(a); rep(i, 0, 5) if(ok(a, f[i])) m = 1; puts(m ? "YES" : "NO"); } return 0; }
J.一个简单的剪枝暴搜...
因为要满足同一行同一列同一区域只出现一次...
所以预处理一下就行了，压不压位随意吧...
WA了1h发现是dfs函数最后忘记写return 0...
很多地方会默认return 1所以不报编译错误...
这个时候vs大法就很舒服了...
虽然给你带个安全套，但是提醒肯定会提醒的！
#include <iostream> #include <algorithm> using namespace std; int k, a[9][9], b[9], c[9], d[9]; pair<int, int> p[100]; bool dfs(int n) { if(n > k) { for(int i = 0;i < 9;i ++) { for(int j = 0;j < 8;j ++) printf("%d ", a[i][j]); printf("%d ", a[i][8]); } return 1; } int x = p[n].first, y = p[n].second, z = x / 3 * 3 + y / 3; for(int i = 1;i <= 9;i ++) { if((b[x] | c[y] | d[z]) & (1 << i)) continue; a[x][y] = i; b[x] ^= 1 << i; c[y] ^= 1 << i; d[z] ^= 1 << i; if(dfs(n + 1)) return 1; b[x] ^= 1 << i; c[y] ^= 1 << i; d[z] ^= 1 << i; } return 0; } int main() { ios::sync_with_stdio(false); int i, j, flag = 0; char str[10]; while(cin >> str) { if(flag ++) puts(""); for(i = 0;i < 9;i ++) b[i] = c[i] = d[i] = 0; i = 0, j = 0, k = 0; if(str[0] == '?') a[i][j] = -1, p[++ k] = make_pair(i, j); else a[i][j] = str[0] - '0', b[0] |= 1 << a[i][j], c[0] |= 1 << a[i][j], d[0] |= 1 << a[i][j]; for(j ++;i < 9;i ++) { for(;j < 9;j ++) { cin >> str; if(str[0] == '?') a[i][j] = -1, p[++ k] = make_pair(i, j); else a[i][j] = str[0] - '0', b[i] |= 1 << a[i][j], c[j] |= 1 << a[i][j], d[i / 3 * 3 + j / 3] |= 1 << a[i][j]; } j = 0; } dfs(1); } return 0; }
题外话:
日常被自己的ios::sync_with_stdio坑...
会取消cin和scanf，cout和printf的同步
所以一旦开了这玩意儿就绝对不能混用了！
当然开了这玩意儿后，cin几乎是绝对比scanf好用的
因为我们很少需要格式化读入的骚操作
而cout和printf各有利弊吧
简单输出cout仍然是比printf方便的
而格式化输出的话，printf更舒服
至于puts似乎是跟printf一路的吧...
不好好训练脑子就要锈死了...