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;
}