https://ac.nowcoder.com/acm/contest/5666#question

F. Infinite String Comparision

 

题意：给定两个字符串，且可以无限循环，问两个无限的字符串的字典序大小。

如果两个长度不是倍数关系，那么第二次比较一定是每一位向后移动一位，所以如果第一次比不出大小，第二次还是比不出，则一定是两个串都只有一个字符，否则两次内一定有结果。

如果成倍数，比一次长度最大的即可。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 2e6 + 10;
char a[N], b[N];
int ck() {
    int n = max((int)strlen(a), (int)strlen(b));
    int p = (int)strlen(a), q = (int)strlen(b);
    for (int i = 0; i < 2*n; i++) {
        if (a[i%p] != b[i%q]) {
            if (a[i%p] < b[i%q])return -1;
            else return 1;
        }
    }
    return 0;
}
int main() {
    while (scanf("%s%s", a, b) == 2) {
        int ans = ck();
        if (ans == -1)puts("<");
        else if (ans == 0)puts("=");
        else puts(">");
    }
    return 0;
}

 

J. Easy Integration

 

题意：求 ∫01(x−x2)ndx∫_0^1(x−x^2)^ndx。

多次分部积分对 (1−x)n(1-x)^n 降幂。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 2e6 + 10;
ll n;
ll p[N];
ll Pow(ll a, ll b) {
    ll res = 1ll;
    while (b) {
        if (b & 1)res = res * a%mod;
        a = a * a%mod;
        b >>= 1;
    }
    return res;
}
int main() {
    p[0] = 1ll;
    for (ll i = 1; i < N; i++)p[i] = p[i - 1] * i%mod;
    while (~scanf("%lld", &n)) {
        ll a = 1ll, b = 1ll;
        a = p[n] * p[n] % mod;
        b = p[2 * n + 1];
        printf("%lld\n", a*Pow(b, mod - 2) % mod);
    }
    return 0;
}

 

I. 1 or 2

 

题意：给定一张图，要选出一些边作为新图，使得新图上每点的度数为给定的 d[i]d[i]，判断是否有解。

不能用网络流！

拆点，分出入点出点，且之间不连接。但是这样求出的不能保证 1 连向 2 的同时 2 也连向 1，所以不能用于无向图。

正确做法应该是一般图匹配

这题和 HDU3551 一样。

把每个点拆成 d[i] 个点，对于每条边，先新建 2 个点，相连，一个点 连接所有 u 拆出的点，另一个点连接所有 v 拆出的点。

再求一般图最大匹配，如果是完全匹配则YES，否则NO。

如果原图可行，则根据原图的解可以构造出，每个度都与某条边拆出的一个点匹配，而如果某条边没有用到，则它自己的两点匹配。

如果新图有完全匹配，则根据完全匹配也可以在原图构造出对应解。

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 1010;
typedef pair<int, int>pii;
struct Edmond
{
    int pre[N], nxt[N], to[N], n, cnt;
    int mate[N], link[N], vis[N], fa[N];
    int que[N], hd, tl;
    int ss[N], tim;
    void init(int _n) {
        n = _n;
        fill(pre, pre + n + 1, 0);
        fill(nxt, nxt + n + 1, 0);
        fill(to, to + n + 1, 0);
        fill(mate, mate + n + 1, 0);
        fill(link, link + n + 1, 0);
        cnt = hd = tl = 0;
    }
    void addEdge(int x, int y) {
        nxt[cnt] = pre[x];
        to[pre[x] = cnt++] = y;
    }
    int Find(int x) { return fa[x] == x ? x : fa[x] = Find(fa[x]); }
    int LCA(int x, int y) {
        memset(ss, 0, sizeof(ss));
        tim = 0;
        ++tim;
        while (ss[x] != tim) {
            if (x) { ss[x] = tim; x = Find(link[mate[x]]); }
            std::swap(x, y);
        }
        return x;
    }
    void Flower(int x, int y, int p) {
        while (Find(x) != p) {
            link[x] = y;
            fa[y = mate[x]] = fa[x] = p;
            if (vis[y] == 1) vis[que[tl++] = y] = 2;
            x = link[y];
        }
    }
    bool match(int x) {
        hd = tl = 0;
        for (int i = 1; i <= n; ++i) vis[fa[i] = i] = 0;
        vis[que[tl++] = x] = 2;
        while (hd < tl) {
            x = que[hd++];
            for (int i = pre[x]; i; i = nxt[i]) {
                int u = to[i];
                if (!vis[u]) {
                    vis[u] = 1;
                    link[u] = x;
                    if (!mate[u]) {
                        while (x) {
                            x = mate[link[u]];
                            mate[mate[u] = link[u]] = u;
                            u = x;
                        }
                        return true;
                    }
                    else
                        vis[que[tl++] = mate[u]] = 2;
                }
                else if (vis[u] == 2 && Find(u) != Find(x)) {
                    int p = LCA(x, u);
                    Flower(x, u, p);
                    Flower(u, x, p);
                }
            }
        }
        return false;
    }
    int go() {
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (!mate[i] && match(i))ans++;
        }
        return ans;
    }
}ED;
 
int l[N], r[N], tot, n, m;
int main() {
    while (scanf("%d%d", &n, &m) == 2) {
        tot = 0;
        for (int i = 1; i <= n; i++) {
            int d;
            scanf("%d", &d);
            l[i] = ++tot;
            r[i] = tot + d - 1;
            tot += d - 1;
        }
        ED.init(tot + 2 * m);
        for (int i = 0; i < m; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            tot++;
            for (int j = l[u]; j <= r[u]; j++) {
                ED.addEdge(tot, j);
                ED.addEdge(j, tot);
            }
            ED.addEdge(tot, tot + 1);
            ED.addEdge(tot + 1, tot);
            tot++;
            for (int j = l[v]; j <= r[v]; j++) {
                ED.addEdge(tot, j);
                ED.addEdge(j, tot);
            }
        }
 
        if ((tot & 1) || ED.go() != tot / 2)puts("No");
        else puts("Yes");
    }
    return 0;
}

 

H. Minimum-cost Flow

 

题意：给定一个费用流，多次询问，问每条边的容量为 uv,u≤v\frac{u}{v},u\le v 时，从 1 到 n 流 1 单位流量的最小费用。

费用流

直接用分数肯定不行，考虑变成整数。

发现 f(cap,flow)=f(uv,1)=1vf(u,v)f(cap,flow)=f(\frac{u}{v},1)=\frac{1}{v}f(u,v)，但是如果容量变化，就必须要重新跑，因为流过的边可能会变，所以要再变为 uvf(1,vu)\frac{u}{v}f(1,\frac{v}{u})，

很重要的一点在于当容量不变，即网络不变时，流量增加，之前已经流过的流量是不会受到影响的，所以增加一单位流量时新增加的费用完全可以用新的总费用-旧的总费用得到。

所以本题可以从小到大增加流量，由于每条边容量都为 1，所以可以把所有的整数流量时的费用都求出来。但是 vu\frac{v}{u} 可能是分数，所以要看成 一个整数+一个小于1的分数，对于小于1的那部分，由上一行可以知道该流量一定是在一条边里的，并且可以知道这条边流满时这条边里 1 单位流量的费用，那么只要乘上这个分数即可。

由于每条边的容量为 1，而边数最多 100，所以流量最多 100，不会T。

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 1010;
typedef pair<int, int>pii;

int co[N];

struct E
{
	int from, to, cp, v;
	int rev;
	E() {}
	E(int f, int t, int cp, int v, int rev) :from(f), to(t), cp(cp), v(v), rev(rev) {}
};
struct MCMF
{
	int n, m, s, t;
	vector<E> edges;
	vector<int> G[N];
	bool inq[N];     //是否在队列
	int d[N];        //Bellman_ford单源最短路径
	int p[N];        //p[i]表从s到i的最小费用路径上的最后一条弧编号
	int a[N];        //a[i]表示从s到i的最小残量
	void init(int _n, int _s, int _t) {
		n = _n; s = _s; t = _t;
		for (int i = 1; i <= n; i++) G[i].clear();
		edges.clear(); m = 0;
	}

	void addedge(int from, int to, int cap, int cost) {
		edges.push_back(E(from, to, cap, cost, 0));
		edges.push_back(E(to, from, 0, -cost, 1));
		G[from].push_back(m++);
		G[to].push_back(m++);
	}

	bool BellmanFord(int &flow, int &cost) {
		for (int i = 1; i <= n; i++) d[i] = INF;
		memset(inq, 0, sizeof inq);
		d[s] = 0, a[s] = INF, inq[s] = true;
		queue<int> Q; Q.push(s);
		while (!Q.empty()) {
			int u = Q.front(); Q.pop();
			inq[u] = false;
			for (int& idx : G[u]) {
				E &e = edges[idx];
				if (e.cp && d[e.to] > d[u] + e.v) {
					d[e.to] = d[u] + e.v;
					p[e.to] = idx;
					a[e.to] = min(a[u], e.cp);
					if (!inq[e.to]) {
						Q.push(e.to);
						inq[e.to] = true;
					}
				}
			}
		}
		if (d[t] == INF) return false;
		flow += a[t];
		cost += a[t] * d[t];
		int u = t;
		while (u != s) {
			edges[p[u]].cp -= a[t];
			edges[p[u] ^ 1].cp += a[t];
			u = edges[p[u]].from;
		}
		return true;
	}

	pii go() {
		int flow = 0, cost = 0;
		while (BellmanFord(flow, cost)) {
			co[flow] = cost;
		}
		return pii(flow, cost);
	}
} MM;

ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	return b == 0 ? a : gcd(b, a%b);
}
int n, m, q;
int main() {
	while (scanf("%d%d", &n, &m) == 2) {
		int S = 1, T = n;
		MM.init(n, S, T);
		for (int i = 0; i < m; i++) {
			int a, b, c;
			scanf("%d%d%d", &a, &b, &c);
			MM.addedge(a, b, 1, c);
		}
		int mxf = MM.go().first;
		scanf("%d", &q);
		while (q--) {
			ll u, v;
			scanf("%lld%lld", &u, &v);
			if (mxf*u < v) { puts("NaN"); continue; }
			ll x = u * co[v / u] + (v%u)*(co[v / u + 1] - co[v / u]);
			ll g = gcd(x, v);
			printf("%lld/%lld\n", x / g, v / g);
		}
	}
	return 0;
}

 

A. B-Suffix Array

 

题意：给定一个只有 ‘A’, ‘B’ 的字符串。定义一个字符串的 B 数列的每一位为该位前面最近的和它相同字母的位置和该位置的距离，如果前面没有和它相同的字符，则为 0。对于给定字符串的每一个后缀，求出它的 B 数列，并按照 B 数列的字典序排序，输出。

题解直接标了结论题。也是挺神的。

参考 大佬的博客

结论：定义一个字符串的 C 数列，为每一位后面最近的和它相同的字母的位置的距离，如果没有则为 n，且最后一位规定为 n+1。再求 C 数列的后缀数组，倒序输出。

C 和 B 的不同之处就在于一个是后面一个是前面，可以发现 B 数列把所有同为 ‘A’ 的位置向左移动一位，同为 ‘B’ 的位置的向左移动一位，就得到了对应的 C 数列。

B 数列一定是类似 0111102 的形式，假设有两个字符串S，T，在某一位的 B 数列值第一次不同，则这一位一定一个是 ‘A’，一个是 ’B’，则不同的这一位一定有一个是 1，另一个不是 1，这样向左移动一位后由于原先在不同位的B值这时移动到了相同位，则原先 B 数列字典序小的那个串（即第一个不同位为 1 的那个串）这时 C 数列反而更小。所以求 B 数列递增就是求 C 数列递减。

而由于每个后缀的 B 数列都必须重新求，但 C 数列可以只求一次，所以问题转换为求 C 数列后，只要对整个字符串求一次 C，再对后缀排序即可。

而由于最后一位的 B 值一定是 0，所以最后一位 B 数列一定最小，也就是必须要让它的 C 数列最大，所以最后一位规定为 n+1。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 2e5 + 10;
int n;
char s[N];
int rk[N], sa[N], tmp[N], lcp[N], tk;	//0开始
bool compare_sa(int i, int j) {
	if (rk[i] != rk[j])return rk[i] < rk[j];
	else {
		int ri = i + tk <= n ? rk[i + tk] : -1;
		int rj = j + tk <= n ? rk[j + tk] : -1;
		return ri < rj;
	}
}
void constract_sa(const int* S) {
	for (int i = 0; i <= n; i++) {
		sa[i] = i;
		rk[i] = i < n ? S[i] : -1;
	}
	for (tk = 1; tk <= n; tk *= 2) {
		sort(sa, sa + n + 1, compare_sa);
		tmp[sa[0]] = 0;
		for (int i = 1; i <= n; i++) {
			tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);
		}
		for (int i = 0; i <= n; i++) {
			rk[i] = tmp[i];
		}
	}
}
int C[N];
int main() {
	while (~scanf("%d", &n)) {
		scanf("%s", s);
		for (int i = 0; i < n; i++) {
			C[i] = -1;
			for (int j = i + 1; j < n; j++) {
				if (s[j] == s[i]) {
					C[i] = j - i;
					break;
				}
			}
			if (C[i] == -1)C[i] = n;
		}
		C[n - 1] = n + 1;
		constract_sa(C);
		for (int i = n; i >= 1; i--)printf("%d%s", sa[i] + 1, i == 1 ? "\n" : " ");
	}
	return 0;
}