科大讯飞杯NowCoder5278
/ / 阅读耗时 41 分钟 “科大讯飞杯”第18届上海大学程序设计联赛春季赛暨高校网络友谊赛题解。
共12题，5小时，难度不高的比赛。
A、组队比赛
给定四个整数，两两分组，最小化组间差距。一共就3种情况，算一遍即可。签到题。1
2
3
4
5
6
7
8
9
10
11
12
using namespace std;
int main()
{
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
printf("%d", min(min(abs(a + c - b - d), abs(a + b - c - d)), abs(a + d - b - c)));
// PAUSE;
return 0;
}
B、每日一报
多元排序，写好排序函数，一遍sort即过。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
using namespace std;
struct Node
{
int date;
int num;
double tw;
} op[500];
bool cmp(Node a, Node b)
{
if (a.date != b.date) return a.date > b.date;
if (a.tw != b.tw) return a.tw > b.tw;
return a.num < b.num;
}
int main()
{
int n;
scanf("%d", &n);
int s = 1;
for (int i = 1; i <= n; i++) {
scanf("%d%d%lf", &op[s].date, &op[s].num, &op[s].tw);
if (op[s].tw >= 38.0) ++s;
}
sort(op + 1, op + s, cmp);
printf("%d\n", s - 1);
for (int i = 1; i < s; i++) {
printf("%d %d %.1lf\n", op[i].date, op[i].num, op[i].tw);
}
// PAUSE;
return 0;
}
C、最长非公共子序列
当两者长度不等时，答案就是较长的那一个串。当长度相同时，考虑两个串是否相等，若相等，则不存在符合题意的串，否则就是两者其中之一。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
using namespace std;
char s1[5005], s2[5005];
int l1, l2;
int main()
{
scanf("%s%s", s1, s2);
l1 = strlen(s1), l2 = strlen(s2);
if (l1 != l2) {
printf("%d", max(l1, l2));
} else {
if (strcmp(s1, s2) == 0)
printf("-1");
else
printf("%d", l1);
}
// PAUSE;
return 0;
}
D、最大字符集
按长度讨论。对于$n$为1、2时的情况很容易求出答案，对于$n$更大的情况，考虑形如$01\cdots 10$（或$10\cdots 01$）的串，它们必然不会出现某一个串是另一串子串的问题，并且长度任意选（除了长度为1的），因此其余的答案也容易得到。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main()
{
int n;
scanf("%d", &n);
if (n == 1) {
printf("1\n0");
} else if (n == 2) {
printf("2\n0\n11");
} else {
printf("%d\n", n - 1);
for (int i = 2; i <= n; i++) {
printf("0");
for (int j = 1; j <= i - 2; j++) printf("1");
printf("0\n");
}
}
// PAUSE;
return 0;
}
E、美味的序列
正着反着都来一遍答案就有了，全场第二简单题。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
using namespace std;
int op[100005], n;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", op + i);
long long ans = 0, s = 0;
for (int i = 1; i <= n; i++) {
s += op[i] - i + 1;
}
ans = s;
s = 0;
reverse(op + 1, op + n + 1);
for (int i = 1; i <= n; i++) {
s += op[i] - i + 1;
}
ans = max(ans, s);
printf("%lld", ans);
// PAUSE;
return 0;
}
F、日期小助手
模拟题，需要考虑闰年，还有考虑一些英语问题。总而言之就是没有多少思维性，纯肝向的题目。
最简单的方式是打一个表，然后在里面直接找出日期。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
const char* MQ[] = {"2000514", "2001513", "2002512", "2003511", "2004509", "2005508", "2006514", "2007513", "2008511", "2009510", "2010509", "2011508", "2012513", "2013512", "2014511", "2015510", "2016508", "2017514", "2018513", "2019512", "2020510", "2021509", "2022508", "2023514", "2024512", "2025511", "2026510", "2027509", "2028514", "2029513", "2030512", "2031511", "2032509", "2033508", "2034514", "2035513", "2036511", "2037510", "2038509", "2039508", "2040513", "2041512", "2042511", "2043510", "2044508", "2045514", "2046513", "2047512", "2048510", "2049509", "2050508", "2051514", "2052512", "2053511", "2054510", "2055509", "2056514", "2057513", "2058512", "2059511", "2060509", "2061508", "2062514", "2063513", "2064511", "2065510", "2066509", "2067508", "2068513", "2069512", "2070511", "2071510", "2072508", "2073514", "2074513", "2075512", "2076510", "2077509", "2078508", "2079514", "2080512", "2081511", "2082510", "2083509", "2084514", "2085513", "2086512", "2087511", "2088509", "2089508", "2090514", "2091513", "2092511", "2093510", "2094509", "2095508", "2096513", "2097512", "2098511", "2099510", "2100509", "2101508", "2102514", "2103513", "2104511", "2105510"};
const char* FQ[] = {"2000618", "2001617", "2002616", "2003615", "2004620", "2005619", "2006618", "2007617", "2008615", "2009621", "2010620", "2011619", "2012617", "2013616", "2014615", "2015621", "2016619", "2017618", "2018617", "2019616", "2020621", "2021620", "2022619", "2023618", "2024616", "2025615", "2026621", "2027620", "2028618", "2029617", "2030616", "2031615", "2032620", "2033619", "2034618", "2035617", "2036615", "2037621", "2038620", "2039619", "2040617", "2041616", "2042615", "2043621", "2044619", "2045618", "2046617", "2047616", "2048621", "2049620", "2050619", "2051618", "2052616", "2053615", "2054621", "2055620", "2056618", "2057617", "2058616", "2059615", "2060620", "2061619", "2062618", "2063617", "2064615", "2065621", "2066620", "2067619", "2068617", "2069616", "2070615", "2071621", "2072619", "2073618", "2074617", "2075616", "2076621", "2077620", "2078619", "2079618", "2080616", "2081615", "2082621", "2083620", "2084618", "2085617", "2086616", "2087615", "2088620", "2089619", "2090618", "2091617", "2092615", "2093621", "2094620", "2095619", "2096617", "2097616", "2098615", "2099621", "2100620", "2101619", "2102618", "2103617", "2104615", "2105621"};
struct Date
{
int y, m, d;
bool operator<(Date p)
{
if (p.y != y) return y < p.y;
if (p.m != m) return m < p.m;
return d < p.d;
}
} mq, fq, now;
Date convert(const char* s)
{
Date p;
p.y = (s[0] - '0') * 1000 + (s[1] - '0') * 100 + (s[2] - '0') * 10 + s[3] - '0';
p.m = s[4] - '0';
p.d = (s[5] - '0') * 10 + s[6] - '0';
return p;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &now.y, &now.m, &now.d);
for (int j = 0; j < 106; j++) {
Date s = convert(MQ[j]);
// printf("%d %d %d\n", s.y, s.m, s.d);
if (now < s) {
mq = s;
break;
}
}
for (int j = 0; j < 106; j++) {
Date s = convert(FQ[j]);
if (now < s) {
fq = s;
break;
}
}
Date s;
if (fq < mq) {
printf("Father's Day: June %d", fq.d);
s = fq;
} else {
printf("Mother's Day: May %d", mq.d);
s = mq;
}
if (s.d == 11 || s.d == 12 || s.d == 13)
printf("th");
else if (s.d % 10 == 1)
printf("st");
else if (s.d % 10 == 2)
printf("nd");
else if (s.d % 10 == 3)
printf("rd");
else
printf("th");
printf(", %d\n", s.y);
}
// PAUSE;
return 0;
}
难题分割线（雾
G、血压游戏
有很多做法，一种很优雅的做法是使用虚树配合DP。
显然只有同一个深度的节点会互相干扰，因此我们只需要按深度讨论，找出同一个深度的节点，建立虚树，然后在上面DP，DP方程很好列。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
struct Edge
{
int next, to;
} edge[N << 1], es[N << 1];
using namespace std;
int n, root, num[N], head[N], cnt = 1, gr[N][21], dep[N], sta[N], top, dfn[N], DFN, hs[N], cn = 1;
set<int> tmp;
vector<int> vec[N];
inline void add(int x, int y)
{
edge[cnt].next = head[x], edge[cnt].to = y, head[x] = cnt++;
}
inline void adde(int x, int y)
{
tmp.insert(x), tmp.insert(y), es[cn].next = hs[x], es[cn].to = y, hs[x] = cn++;
}
void DFS(int x)
{
dfn[x] = ++DFN;
for (int i = head[x]; i; i = edge[i].next) {
if (dep[edge[i].to]) continue;
dep[edge[i].to] = dep[x] + 1, gr[edge[i].to][0] = x;
for (int j = 1; j <= 20; j++) gr[edge[i].to][j] = gr[gr[edge[i].to][j - 1]][j - 1];
DFS(edge[i].to);
}
}
inline int LCA(int x, int y)
{
if (dep[x] < dep[y]) swap(x, y);
for (int i = 20; i >= 0; i--) {
if (dep[gr[x][i]] > dep[y]) x = gr[x][i];
}
if (x == y) return x;
for (int i = 20; i >= 0; i--) {
if (gr[x][i] != gr[y][i]) x = gr[x][i], y = gr[y][i];
}
return gr[x][0];
}
inline void insert(int x)
{
if (top <= 1)
sta[++top] = x;
else {
int lca = LCA(sta[top], x);
if (lca == sta[top])
sta[++top] = x;
else {
while (top > 1 && dfn[lca] <= dfn[sta[top - 1]]) adde(sta[top - 1], sta[top]), --top;
if (lca != sta[top]) adde(lca, sta[top]), sta[top] = lca;
sta[++top] = x;
}
}
}
long long DP(int x)
{
if (hs[x] == 0 && x != root) return num[x];
long long dp = 0;
for (int i = hs[x]; i; i = es[i].next) {
long long ch = DP(es[i].to);
if (ch) ch = max(1ll, ch - (dep[es[i].to] - dep[x]));
dp += ch;
}
return dp;
}
inline int cmp(int x, int y)
{
return dfn[x] < dfn[y];
}
int main()
{
long long ans = 0;
scanf("%d%d", &n, &root);
for (int i = 1; i <= n; i++) scanf("%d", num + i);
for (int i = 1, x, y; i < n; i++) scanf("%d%d", &x, &y), add(x, y), add(y, x);
dep[root] = 1, DFS(root);
for (int i = 1; i <= n; i++) vec[dep[i]].push_back(i);
for (int i = 1; i <= n; i++) sort(vec[i].begin(), vec[i].end(), cmp);
ans = num[root] > 1 ? num[root] - 1 : num[root];
for (int i = 2; i <= n; i++) {
sta[top = 1] = root, tmp.insert(root);
for (int j = 0; j < vec[i].size(); j++) insert(vec[i][j]);
while (top > 1) adde(sta[top - 1], sta[top]), --top;
long long dp = DP(root);
ans += dp > 1 ? dp - 1 : dp;
for (set<int>::iterator it = tmp.begin(); it != tmp.end(); it++) hs[*it] = 0;
cn = 1, tmp.clear();
}
printf("%lld", ans);
// PAUSE;
return 0;
}
H、纸牌游戏
首先需要知道十进制整数能被3整除的充要条件是该整数的各个位数字相加的和能被3整除，问题转化为了数字的和。然后考虑贪心。
贪心的方法就是从9到0依次遍历，枚举每一个数字能够取的次数，然后判断剩下的数字能否构造出符合题意的数。现在的问题就是如何进行判定。
由于枚举的复杂度就是$O(n)$的，判定这一步的复杂度不能到$O(n)$。现在假定数字$i$出现的次数为$a_i$，考虑给定的数字能否找出一种方案，使得选$k$个数，它们的和模3为$p$。
事实上，0到9这10个数可以分为3类，一类模3为0，另两类模3为1和2，我们不妨只考虑三类数的数量，记为$b_0,b_1,b_2$，显然$b_0=a_0+a_3+a_6+a_9$，$b_1,b_2$同理可以推得。
假设存在一种方案符合题意，这个方案中三类数分别取了$x,y,z$个，那么可以列出下面的方程：
枚举$y$与$z$模3的性质（共9种情况），对于其中满足方程的数对$(m,n)$，有：
这样可以将$y,z$写成如下形式：
根据$b_1,b_2$，我们很容易推出$k_1,k_2$的取值范围，进而得到$y,z$的取值范围，从而得到$x$的范围。然后判断这一个范围是否满足$b_0$的限制即可。
这样我们就得到了$O(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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
using namespace std;
inline int check(int a, int b, int c, int k, int sv)
{
if (a + b + c < k) return 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if ((i + 2 * j) % 3 != sv) continue;
if (b - i < 0 || c - j < 0) continue;
int k1 = (b - i) / 3, k2 = (c - j) / 3;
double down = (k - i - j - a) / 3.0;
double up = (k - i - j) / 3.0;
int pd = ceil(down), pu = floor(up);
if (pu < pd) continue;
if (k1 + k2 < pd || pu < 0) continue;
return 1;
}
}
return 0;
}
char op[1000005], ans[1000005];
int num[20], k, n0, n1, n2, at;
void DFS(int x, int sv)
{
if (x == -1) return;
for (int i = num[x]; i >= 0; i--) {
if (i > k) continue;
if (x % 3 == 0) {
n0 -= num[x];
} else if (x % 3 == 1) {
n1 -= num[x];
} else {
n2 -= num[x];
}
if (check(n0, n1, n2, k - i, ((sv - x % 3 * i) % 3 + 3) % 3)) {
for (int j = 1; j <= i; j++) ans[at++] = x + '0';
k -= i;
DFS(x - 1, ((sv - x % 3 * i) % 3 + 3) % 3);
return;
}
if (x % 3 == 0) {
n0 += num[x];
} else if (x % 3 == 1) {
n1 += num[x];
} else {
n2 += num[x];
}
}
}
int main()
{
int t;
// printf("%d\n", check(0, 3, 0, 1, 0));
scanf("%d", &t);
for (int i = 1; i <= t; i++) {
scanf("%s%d", op, &k);
for (int j = 0; j < 10; j++) num[j] = 0;
for (int j = 0; op[j]; j++) ++num[op[j] - '0'];
n0 = num[0] + num[3] + num[6] + num[9];
n1 = num[1] + num[4] + num[7];
n2 = num[2] + num[5] + num[8];
at = 0, DFS(9, 0);
if (at == 0 || (ans[0] == '0' && at != 1)) {
printf("-1");
} else {
for (int j = 0; j < at; j++) printf("%c", ans[j]);
}
printf("\n");
}
// PAUSE;
return 0;
}
I、古老的打字机
整场比赛我最喜欢的一道题，比较有思维含量。
要解决本题，需要熟悉AC自动机的相关内容。回想AC自动机中是如何求很多串在一个串内各自的出现次数的：建出AC自动机后，把这一个串丢到AC自动机上跑，记录每一个状态被访问的次数，最后在fail树上一遍DFS统计一波。
由于需要最后再fail树上统计，我们不妨直接一开始就进行一遍DFS，将每一个串的权值下放到其在fail树上的子树节点上，这样遍历一遍AC自动机，串的价值就是走过状态权值之和。
然后本题可以转化为在AC自动机上进行期望DP的问题。DP转移方程还是比较好列的。但是到这一步本题还没有完全解决，这是因为退格操作的存在。退格操作使得我们可能回退一个字符，这样就需要减去权值，对于DP来说需要记额外状态，这显然不可取。
但是可以退一步想：无论退不退格，在哪里退格，最后得到就是一个串，只不过长度不定。凭借这个思路，可以得到一个方法：对于固定长度为$p$的串，禁止使用退格操作（下一步填每一个字母的概率都是$\frac {1}{26}$），得到期望$e_p$，如果再记算上退格操作得到的长度为$p$的串概率为$f_i$，那么答案就是：
问题转化为求$f$，然而这并不是一个简单的二项分布问题，求$f$仍然需要DP，比较常规。
本题同时考察了AC自动机（含fail树），期望概率DP以及一丁点数论（乘法逆元），兼具思维性，给出题人点赞。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
using namespace std;
char str[N], op[N];
int vis[N], to[N], ct = 1, fail[N], tr[N][26], cnt = 1, v[N], n, m, fa[N], head[N], dp[N][N];
int inv26, inv27, f[N][N];
struct Edge
{
int next, to;
} edge[N];
inline void add(int x, int y)
{
edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}
inline int qPow(int x, int y = MOD - 2)
{
int ans = 1, sta = x;
while (y) {
if (y & 1) ans = 1ll * sta * ans % MOD;
sta = 1ll * sta * sta % MOD, y >>= 1;
}
return ans;
}
queue<int> que;
void insert(const char* p, int ps)
{
int i = 0, now = 1;
while (p[i]) {
if (tr[now][p[i] - 'a'] == 0) tr[now][p[i] - 'a'] = ++ct;
now = tr[now][p[i] - 'a'], i++;
}
v[now] += ps;
}
void DFS(int x, int s)
{
v[x] += s;
for (int i = head[x]; i; i = edge[i].next) DFS(edge[i].to, v[x]);
}
int DP(int x, int c)
{
if (c == 0) return dp[x][c] = v[x];
if (~dp[x][c]) return dp[x][c];
dp[x][c] = 0;
for (int i = 0; i < 26; i++) {
dp[x][c] = (dp[x][c] + 1ll * (v[x] + DP(tr[x][i], c - 1)) * inv26 % MOD) % MOD;
}
return dp[x][c];
}
int main()
{
scanf("%d%d", &n, &m), inv26 = qPow(26), inv27 = qPow(27);
for (int i = 1, x; i <= n; i++) scanf("%s%d", op, &x), insert(op, x);
for (int i = 0; i < 26; i++) tr[0][i] = 1;
que.push(1);
while (!que.empty()) {
int p = que.front();
que.pop();
for (int i = 0; i < 26; i++) {
if (tr[p][i])
fail[tr[p][i]] = tr[fail[p]][i], que.push(tr[p][i]);
else
tr[p][i] = tr[fail[p]][i];
}
}
for (int i = 2; i <= ct; i++) add(fail[i], i);
DFS(1, 0), memset(dp, -1, sizeof(dp)), f[0][0] = 1;
for (int i = 1; i <= m; i++) {
f[i][0] = 1ll * (f[i - 1][1] + f[i - 1][0]) * inv27 % MOD;
f[i][m] = 1ll * f[i - 1][m - 1] * (1 - inv27) % MOD;
for (int j = 1; j < m; j++) {
f[i][j] = (1ll * f[i - 1][j - 1] * (1 - inv27) % MOD + 1ll * f[i - 1][j + 1] * inv27 % MOD) % MOD;
}
}
int ans = 0;
for (int i = 0; i <= m; i++) ans = (ans + 1ll * f[m][i] * DP(1, i) % MOD) % MOD;
ans = 1ll * ans * qPow(27, m) % MOD;
printf("%d", (ans + MOD) % MOD);
return 0;
}
J、能到达吗
一个傻搜索，不过数据范围过大。
由于障碍物很少，但是图很大，可以将一大片的点合并，然后用并查集合并求解。
合并节点的方法是对于存在障碍物的一行，将这一行按障碍物分开，对于连续的没有障碍物的若干行，将它们合并成一个。这样做能将块的复杂度降到$O(k)$。
本题细节较多。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
using namespace std;
int n, m, k, fa[N];
vector<int> vec[N >> 2], up, down, l, r;
vector<long long> num;
set<int> ssp;
int inv2 = 500000004;
int ff(int x)
{
return fa[x] == x ? x : fa[x] = ff(fa[x]);
}
inline void merge(int x, int y)
{
if (ff(x) == ff(y)) return;
int f1 = ff(x), f2 = ff(y);
fa[f1] = f2, num[f2] += num[f1], num[f2] %= MOD;
}
inline int les(int x, int y)
{
return up[y] > down[x] + 1 || (up[y] == down[x] + 1 && l[y] > r[x]);
}
inline int ok(int x, int y)
{
return up[y] == down[x] + 1 && l[y] <= r[x] && r[y] >= l[x];
}
int findL(int x, int l, int r) //(,]
{
if (l >= r) return -1;
if (r == l + 1) return ok(x, r) ? r : -1;
int mid = (l + r) >> 1;
if (les(x, mid) || ok(x, mid)) return findL(x, l, mid);
return findL(x, mid, r);
}
int findR(int x, int l, int r) //[,)
{
if (l >= r) return -1;
if (r == l + 1) return ok(x, l) ? l : -1;
int mid = (l + r) >> 1;
if (!les(x, mid)) return findR(x, mid, r);
return findR(x, l, mid);
}
int main()
{
int t;
scanf("%d", &t);
while (t--) {
scanf("%d%d%d", &n, &m, &k);
up.clear(), down.clear(), l.clear(), r.clear(), num.clear();
for (int i = 1, x, y; i <= k; i++) scanf("%d%d", &x, &y), vec[x].push_back(y), ssp.insert(x);
int now = 1;
for (int i : ssp) {
if (i > now) {
num.push_back(1ll * (i - now) * m % MOD);
up.push_back(now), down.push_back(i - 1), l.push_back(1), r.push_back(m);
}
sort(vec[i].begin(), vec[i].end());
int sv = 1;
for (int j = 0; j < vec[i].size(); j++) {
if (vec[i][j] - sv > 0) {
up.push_back(i), down.push_back(i);
l.push_back(sv), r.push_back(vec[i][j] - 1), num.push_back(vec[i][j] - sv);
}
sv = vec[i][j] + 1;
}
if (m - sv + 1 > 0) {
up.push_back(i), down.push_back(i);
l.push_back(sv), r.push_back(m), num.push_back(m - sv + 1);
}
now = i + 1;
}
if (n - now + 1 > 0) {
up.push_back(now), down.push_back(n);
l.push_back(1), r.push_back(m), num.push_back(1ll * (n - now + 1) * m % MOD);
}
long long ans = 0;
for (int i = 0; i < up.size(); i++) fa[i] = i;
for (int i = 0; i < up.size(); i++) {
int l = findL(i, i, up.size() - 1), r = findR(i, i + 1, up.size());
if (l != -1)
for (int j = l; j <= r; j++) merge(i, j);
}
for (int i = 0; i < up.size(); i++) {
if (fa[i] == i) ans += 1ll * num[i] * (num[i] + 1) % MOD * inv2 % MOD, ans %= MOD;
}
printf("%lld\n", ans);
for (int i : ssp) vec[i].clear();
ssp.clear();
}
return 0;
}
K、迷宫
这题出的还是很有技术含量的。
可以预见的是只要$d$不是0，那么合理使用穿越一定不会使答案更差。于是我们对$d=0$特判，对$d>0$的情况默认都使用一次穿越。
下一步从起点来一遍BFS，再从终点来一遍BFS，对于某一个点$p$，前者求出的距离记为$dis(p,1)$，后者记为$dis(p,2)$。
问题转化为找两个点$p,q$（两个点可以互相穿越），使得$dis(p,1)+1+dis(q,2)$尽可能小。
强行遍历显然不可取。考虑一下切比雪夫距离，正好是一个正方形的范围，这样问题转化为在一个正方形区域中求最小值问题，即一个二维RMQ问题。二维RMQ问题有很多方法解决，但是这里不能用二维ST表，因为它空间复杂度是$O(nmlognlogm)$，会炸空间。用阉割版（只能求正方形范围）的ST表（时空复杂度为$O(nmlog(\min(n,m)))$）或许可以，不过不推荐。最好的做法是使用单调队列，可以在时空复杂度$O(nm)$下解决这个问题。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
121
122
123
124
125
126
127
128
129
using namespace std;
int n, m, d, bx, by, ex, ey, dis[N][N][2], minn[N][N], minn2[N][N];
char op[N][N];
const int X[] = {-1, 0, 1, 0}, Y[] = {0, 1, 0, -1};
queue<pair<int, int>> que;
pair<int, int> fr[N][N][2];
deque<int> dq;
inline void BFS(int x, int y, int at)
{
que.push(make_pair(x, y)), dis[x][y][at] = 0;
while (!que.empty()) {
pair<int, int> now = que.front();
que.pop();
for (int i = 0, xx, yy; i < 4; i++) {
xx = now.first + X[i], yy = now.second + Y[i];
if (xx < 0 || xx >= n || yy < 0 || yy >= m || op[xx][yy] == 'X') continue;
if (dis[xx][yy][at] > dis[now.first][now.second][at] + 1) {
dis[xx][yy][at] = dis[now.first][now.second][at] + 1;
fr[xx][yy][at] = now;
que.push(make_pair(xx, yy));
}
}
}
}
void FDFS(int x, int y)
{
if (x == bx && y == by) {
printf("%d %d\n", bx, by);
} else {
FDFS(fr[x][y][0].first, fr[x][y][0].second);
printf("%d %d\n", x, y);
}
}
void DFS(int x, int y)
{
if (x == ex && y == ey) {
printf("%d %d\n", x, y);
} else {
printf("%d %d\n", x, y);
DFS(fr[x][y][1].first, fr[x][y][1].second);
}
}
inline void addX(int x, int y)
{
while (!dq.empty() && dis[x][dq.back()][1] > dis[x][y][1]) dq.pop_back();
dq.push_back(y);
}
inline void addY(int y, int x)
{
while (!dq.empty() && minn[dq.back()][y] > minn[x][y]) dq.pop_back();
dq.push_back(x);
}
inline int getQ(int p)
{
while (!dq.empty() && dq.front() < p) dq.pop_front();
return dq.front();
}
int main()
{
scanf("%d%d%d", &n, &m, &d);
for (int i = 0; i < n; i++) scanf("%s", op + i);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (op[i][j] == 'S') bx = i, by = j;
if (op[i][j] == 'T') ex = i, ey = j;
dis[i][j][0] = dis[i][j][1] = 0x3f3f3f3f;
}
}
BFS(bx, by, 0), BFS(ex, ey, 1);
if (d == 0) {
if (dis[ex][ey][0] >= inf) {
printf("-1");
} else {
printf("%d\n", dis[ex][ey][0]);
FDFS(ex, ey);
}
return 0;
}
for (int i = 0, at; i < n; i++) {
while (!dq.empty()) dq.pop_back();
at = 0;
while (at <= d && at < m) addX(i, at++);
for (int j = 0; j < m; j++) {
while (at <= j + d && at < m) addX(i, at++);
minn[i][j] = dis[i][getQ(max(0, j - d))][1];
}
}
for (int i = 0, at; i < m; i++) {
while (!dq.empty()) dq.pop_back();
at = 0;
while (at <= d && at < n) addY(i, at++);
for (int j = 0; j < n; j++) {
while (at <= j + d && at < n) addY(i, at++);
minn2[j][i] = minn[getQ(max(0, j - d))][i];
}
}
int ans = inf, tx, ty;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int get = minn2[i][j];
if (dis[i][j][0] + 1 + get < ans) {
ans = dis[i][j][0] + 1 + get;
tx = i, ty = j;
}
}
}
if (ans >= inf) {
printf("-1");
} else {
printf("%d\n", ans);
FDFS(tx, ty);
int get = minn2[tx][ty];
for (int i = max(0, tx - d); i <= min(n - 1, tx + d); i++) {
for (int j = max(0, ty - d); j <= min(m - 1, ty + d); j++) {
if (dis[i][j][1] == get) {
DFS(i, j);
return 0;
}
}
}
}
return 0;
}
L、动物森友会
后六道题中最简单的一道，放最后了（毒瘤。方法是二分答案配合网络流。
二分出一个答案，然后建网络流图，答案判定就看最大流看是否满流即可。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
using namespace std;
struct
{
int to, next, v;
} edge[20005];
int head[N], cnt = 0, n, b, e, deep[N], cur[N] = {0};
queue<int> que;
inline void add(int x, int y, int z)
{
edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = z, head[x] = cnt++;
}
int DFS(int x, int limit)
{
if (limit == 0 || x == e) return limit;
int f, flow = 0;
for (int i = cur[x]; ~i; i = edge[i].next) {
cur[x] = i;
if (deep[edge[i].to] == deep[x] + 1 && (f = DFS(edge[i].to, min(limit, edge[i].v)))) {
edge[i].v -= f, edge[i ^ 1].v += f, flow += f, limit -= f;
if (!limit) break;
}
}
return flow;
}
bool BFS()
{
while (!que.empty()) que.pop();
for (int i = 1; i <= n; i++) deep[i] = n, cur[i] = head[i];
deep[b] = 0, que.push(b);
while (!que.empty()) {
int f = que.front();
que.pop();
for (int i = head[f]; ~i; i = edge[i].next) {
if (edge[i].v > 0 && deep[edge[i].to] == n) {
deep[edge[i].to] = deep[f] + 1, que.push(edge[i].to);
if (edge[i].to == e) return true;
}
}
}
return deep[e] != n;
}
int events, li, c[1005], os[7][1005], sum;
inline int check(int x)
{
cnt = 0;
for (int i = 1; i <= n; i++) head[i] = -1;
for (int i = 1; i <= 7; i++) {
add(b, i + 1, min(1ll * x / 7 * li + (i <= x % 7 ? li : 0), 1ll * sum)), add(i + 1, b, 0);
}
for (int i = 0; i < 7; i++) {
for (int j = 1; j <= os[i][0]; j++) {
add(i + 2, 8 + os[i][j], sum);
add(8 + os[i][j], i + 2, 0);
}
}
for (int i = 1; i <= events; i++) add(8 + i, e, c[i]), add(e, 8 + i, 0);
int flow = 0;
while (BFS()) flow += DFS(b, inf);
return flow == sum;
}
int main()
{
scanf("%d%d", &events, &li);
n = 2 + 7 + events, b = 1, e = n;
for (int i = 1, p; i <= events; i++) {
scanf("%d%d", c + i, &p), sum += c[i];
for (int j = 1, x; j <= p; j++) {
scanf("%d", &x);
os[x - 1][++os[x - 1][0]] = i;
}
}
int l = 0, r = 700000000, mid;
while (l < r) {
if (r == l + 1) {
printf("%d", r);
break;
}
mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid;
}
}
// PAUSE;
return 0;
}