http://codeforces.com/contest/1137
A. Skyscrapers
题意:n*m的网格每格一个数,在一个交叉点的格子里,要尽量减小横向纵向的数字,保持大小关系不变。
要大小关系不变容易想到最小为行或列的不同数个数。
但是看样例2又发现还要折线方向不同。所以分四种。
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
| #include<bits/stdc++.h> using namespace std; #define ll long long const int INF = 0x3f3f3f3f; const ll inf = 0x3f3f3f3f3f3f3f3f; const int N = 2e5 + 10; int n, m; int a[1010][1010]; vector<int>r[1010], c[1010]; int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf("%d", &a[i][j]); r[i].push_back(a[i][j]); c[j].push_back(a[i][j]); } } for (int i = 1; i <= n; i++) { sort(r[i].begin(), r[i].end()); r[i].erase(unique(r[i].begin(), r[i].end()), r[i].end()); } for (int j = 1; j <= m; j++) { sort(c[j].begin(), c[j].end()); c[j].erase(unique(c[j].begin(), c[j].end()), c[j].end()); } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { int r1 = lower_bound(r[i].begin(), r[i].end(), a[i][j]) - r[i].begin(); int r2 = (int)r[i].size() - r1; int c1 = lower_bound(c[j].begin(), c[j].end(), a[i][j]) - c[j].begin(); int c2 = (int)c[j].size() - c1; printf("%d%c", max(max((int)r[i].size(), (int)c[j].size()), max(r1 + c2, r2 + c1)), " \n"[j == m]); } } return 0; }
|
B. Camp Schedule
题意:给定01串s和t,要求重新排列s,使得t作为子串在s中出现次数尽量多。
既然重排,就没必要考虑s原来什么样子了,只要按照t串放01即可,要重复利用t串相同的前缀和后缀,也就是next数组。
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
| #include<bits/stdc++.h> using namespace std; #define ll long long const int INF = 0x3f3f3f3f; const ll inf = 0x3f3f3f3f3f3f3f3f; const int N = 1e6 + 10; int n, m; char s[N], t[N]; int nxt[N]; void getNextVal(char* p) { int n = strlen(p); nxt[0] = -1; nxt[1] = 0; for (int i = 2; i <= n; i++) { int j = nxt[i - 1]; while (j != -1 && p[i - 1] != p[j]) j = nxt[j]; nxt[i] = j + 1; } } int cnt[2]; char ans[N]; int tot; bool sol(int l, int r) { for (int i = l; i <= r; i++) { if (cnt[0] + cnt[1] == 0)return false; int c = t[i] - '0'; if (cnt[c] > 0) { ans[tot++] = t[i]; cnt[c]--; } else { ans[tot++] = '0' + (c ^ 1); cnt[c ^ 1]--; } } return true; } int main() { scanf("%s%s", &s, &t); n = strlen(s); m = strlen(t); getNextVal(t); for (int i = 0; i < n; i++)cnt[s[i] - '0']++; if (n < m) { printf("%s\n", s); return 0; } sol(0, nxt[m] - 1); while (sol(nxt[m], m - 1)); for (int i = 0; i < tot; i++)printf("%c", ans[i]); puts(""); return 0; }
|
C. Museums Tour
题意:给定一个有向图,每周有d天,每天每个点已知开或不开门,要求第一天从1号点出发,不限走几天,要求经过的不同的开门的点数最多。
强连通分量缩点+拓扑序DAG上dp
把一个点拆成d个点,代表每周的d天,从(u,i)向(v,i+1)连边。
然后求强连通分量,分量内部互相可达,所以求不同点个数。
在分量间同一点拆出来的两个新点一定不可达,否则(u,i)能到(u,j),则(u,j)一定也能到(u,i)。那它们就应该是一个分量里的。
所以在缩点后dp,一定不会出现重复计算。
vector占内存大,用前向星。
tarjan可能会爆栈,把tarjan定义成inline的就好了???
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 69 70 71 72 73 74 75 76
| #include<bits/stdc++.h> using namespace std; #define ll long long const int INF = 0x3f3f3f3f; const ll inf = 0x3f3f3f3f3f3f3f3f; const int N = 1e5 + 10; int n, m, d, w[N*50], dp[N*50]; char s[N][55]; int tot, to[N*50], nx[N*50], st[N*50]; int tot2, to2[N*50], nx2[N*50], st2[N*50]; void add(int u, int v) { to[++tot] = v; nx[tot] = st[u]; st[u] = tot; } void add2(int u, int v) { to2[++tot2] = v; nx2[tot2] = st2[u]; st2[u] = tot2; } int ID(int x, int y) { return (x - 1)*d + y; } int low[N*50], dfn[N*50], clk, scc, bl[N*50], S[N*50], p, vis[N]; bool in[N*50]; inline void tarjan(int u) { dfn[u] = low[u] = ++clk; S[p++] = u; in[u] = true; for (int i = st[u]; i; i = nx[i]) { int v = to[i]; if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else if (in[v])low[u] = min(low[u], dfn[v]); } if (dfn[u] == low[u]) { scc++; while (1) { int x = S[--p]; in[x] = false; bl[x] = scc; int id = (x - 1) / d + 1; if (vis[id] != scc && s[id][(x - 1) % d + 1] == '1') { w[scc]++; vis[id] = scc; } if (x == u)break; } } } int main() { scanf("%d%d%d", &n, &m, &d); for (int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); for (int j = 1; j <= d; j++) add(ID(u, j), ID(v, j%d + 1)); } for (int i = 1; i <= n; i++)scanf("%s", s[i] + 1); for (int i = 1; i <= n * d; i++)if (!dfn[i])tarjan(i); for (int i = 1; i <= n * d; i++) { for (int j = st[i]; j; j = nx[j]) { int v = to[j]; if (bl[v] != bl[i]) add2(bl[i], bl[v]); } } for (int i = 1; i <= scc; i++) { for (int j = st2[i]; j; j = nx2[j]) { dp[i] = max(dp[i], dp[to2[j]]); } dp[i] += w[i]; } printf("%d\n", dp[bl[1]]); return 0; }
|