抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

七つの海

今日、海を見た。もう怖くない

博客

随笔

朋友

归档

关于

“科大讯飞杯”第18届上海大学程序设计联赛春季赛暨高校网络友谊赛

七海

题解

发布于：2020年4月18日

次浏览

科大讯飞冠名的上海大学校赛网络赛。一共五个小时，十二个题目。前六个题是简单题，后六个题是麻烦一点的题目；本来还想着能不能挑战一下A七个，然后……然后我就签到完六个题目光荣下岗（

A2B28BE5A2859BE14CE402031844A7D3.jpg

补题链接：https://ac.nowcoder.com/acm/contest/5278

因为官方目前还没有放出官方题解，只有民间题解，所以这里就不贴链接了。如果有了再补

Update：2020 - 4 - 20

官方的题解slide找到了，您可以点击这里下载。

如果上面的CDN链接崩了，您也可以在这个博客的素材仓库中找到这个文件：传送门

日后如果实现了静态博客的pdf展览的页面，那么链接也会在这里更新的。

小声bb：这科大讯飞属实有牌面啊，比起武大校赛就六百多个人，这场比赛报名了四千一百多个人，三千两百多人实际参加，简直不能比（

然后接下来是题解，签到就直接贴码了。部分参考民间题解制作：

A - 组队比赛

真正的签到题。但是我吃了一发罚时，因为我忘记加上绝对值了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int in[4];
    for (int i = 0; i < 4; ++ i)
        cin >> in[i];
    sort(in,in+4);
    cout << abs(in[0]+in[3]-in[1]-in[2]) << endl;

    return 0;
}

第一发就WA给爷整傻了（

B - 每日一报

只要你会使用Arrays.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
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

struct info
{
    int date;
    string id;
    double temp;

    info() = default;
    info(int date, string id, double temp) : date(date), id(id), temp(temp) {}

    bool operator<(const info &rhs) const 
    {
        if (date < rhs.date)
            return true;
        if (rhs.date < date)
            return false;
        if (temp < rhs.temp)
            return true;
        if (rhs.temp < temp)
            return false;
        return id > rhs.id;
    }

    bool operator>(const info &rhs) const 
    {
        return rhs < *this;
    }

    bool operator<=(const info &rhs) const 
    {
        return !(rhs < *this);
    }

    bool operator>=(const info &rhs) const 
    {
        return !(*this < rhs);
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m = 0;
    int x; string y; double z;
    vector<info> v;
    cin >> n;
    for (int i = 0; i < n; ++ i)
    {
        cin >> x >> y >> z;
        if (z < 38.0) continue;
        ++ m;
        v.emplace_back(x,y,z);
    }
    sort(v.begin(), v.end());
    cout << m << endl << fixed << setprecision(1);
    while (m --)
    {
        cout << v[m].date << ' '
             << v[m].id << ' '
             << v[m].temp << endl;
    }

    return 0;
}

如果你愿意，你甚至还可以让CLion帮你自动重载运算符。

C - 最长非公共子序列

首先，题目给了你两个样例：告诉了你，当两个字符串一摸一样的时候答案是-1；然后，显然当两个字符串不一样长的时候，答案是长字符串的长度——因为长字符串自身一定是自己的子序列，而必不可能是短字符串的子序列；

那么，问题就集中在了两个字符串一样长但是不相等的情况了——然而，此时任何一个字符串自身也是满足上面的条件的，所以答案就是字符串长度。没了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>

using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s1, s2;
    cin >> s1 >> s2;
    int l1 = s1.length(), l2 = s2.length();
    if (l1 == l2)
    {
        if (s1 == s2) cout << -1;
        else cout << l1;
    }
    else cout << max(l1, l2);

    return 0;
}

七海的大脑经过快速的思考，发现实际上只有两种情况啊草（

D - 最大字符集

签到题里一个比较有意思的题目。首先想到，n比较大的时候，单字肯定不可取；然后看样例，推测除了特殊情况，k = n - 1；那么问题就变成了如何构造这样的一系列字符串。

啊呀本质上这个题目做了半天就是被样例坑了：有一种万金油的构造方式：n = 2的时候选择"11"，然后n更大的时候向中间插'0'；这样肯定没问题，狂喜，遂敲代码，提交，WA（

前面说了n比较大的时候，那么什么是比较大呢？n = 2？但是按照上面的构造方法，n = 2选"11"的话，似乎并不妨碍n = 1时我构造"0"啊……问题解决了==

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
#include <iostream>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n;
    if (n == 1)
    {
        cout << n << endl;
        cout << 1 << endl;
    }
    else if (n == 2)
    {
        cout << 2 << endl;
        cout << 0 << endl;
        cout << "11" << endl;
    }
    else
    {
        k = n - 1;
        cout << k << endl;
        string s = "";
        int len = 2;
        cout << 1 << s << 1 << endl;
        while (len < n)
        {
            ++ len;
            s.append("0");
            cout << 1 << s << 1 << endl;
        }
    }

    return 0;
}

害，因为这个盲点损失的不仅是+3罚时，还有思考时间和心态啊（

E - 美味的序列

“吃序列，感觉直接贪心模拟就好了啊——然后一边模拟一边开个变量存最大值，完美啊

——我最开始是这么想的。然后就会显然的遇到一个问题：如果两头一样大，就要检查下一位直到可以分辨优劣的程度；但是这么做，最坏每次模拟时间复杂度会退化到O(n)，整个算法会变成平方，不可取；更何况如果整个数列的值一样，那么每次扫描全队列的我岂不是个憨憨。

啊呀不对啊，这不是一小时以内过了一千多个人的签到题吗，不应该有什么高深算法才对啊== 难道不知不觉我已经菜到这么离谱的程度了嘛（卑微

然后，七海的大脑经过了快速（不的思考，发现了题目中有一句话：“把整个序列吃完”

哦，吃完啊，那没事了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>

using namespace std;
using longs = long long;

const int N = 1e5 + 5;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, a[N];
    longs maxx = 0, disc = 0;
    cin >> n;
    for (int i = 0; i < n; ++ i)
        cin >> a[i], maxx += a[i];
    disc = (n + 1ll) * n / 2ll - n;
    cout << maxx - disc;

    return 0;
}

求个和，求个总损失，减一下完事。

F - 日期小助手

给日期，计算最近的父亲节或者母亲节。因为有日期，再加上这两个节日都和星期几有关，很快就想到了fstqwq学长无私分享的板子的 \(Miscellany\) 版块里提到的Zeller日期转换。

所谓Zeller日期转换，就是从公元后的年月日日期到正整数的一个双射。

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
#include <iostream>

using namespace std;

string dateString(int y, int m, int d)
{
    string s;
    if (m == 5) s = "Mother\'s Day: May ";
    else s = "Father\'s Day: June ";
    s.append(to_string(d));
    if (d / 10 == 1) s.append("th, ");
    else if (d % 10 == 1) s.append("st, ");
    else if (d % 10 == 2) s.append("nd, ");
    else if (d % 10 == 3) s.append("rd, ");
    else s.append("th, ");
    s.append(to_string(y));
    return s;
}

namespace Zeller
{
    struct date {int year, month, day; };
    enum weekday {sun = 0, mon, tue, wed, thu, fri, sat};
    typedef int id;

    id getZellerId(int y, int m, int d)
    {
        if (m < 3) -- y, m += 12;
        return 365 *  y + y / 4 - y / 100 + y / 400 + (153 * (m - 3) + 2) / 5 + d - 307;
    }

    date getZellerDate(id zellerId)
    {
        int x = zellerId + 1789995, n, i, j, y, m, d;
        n = 4 * x / 146097; x -= (146097 * n + 3) / 4;
        i = (4000 * (x + 1)) / 1461001; x -= 1461 * i / 4 - 31;
        j = 80 * x / 2447; d = x - 2447 * j / 80; x = j / 11;
        m = j + 2 - 12 * x; y = 100 * (n - 49) + i + x;
        return {y,m,d};
    }

    weekday getWeekday(id zellerId)
    {
        return static_cast<weekday>((zellerId + 1) % 7);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    using Zeller::getZellerId;
    using Zeller::getWeekday;
    using Zeller::getZellerDate;

    auto getMotherDayId = [](int y)
    {
        Zeller::id xx = getZellerId(y, 5, 1);
        int yy = getWeekday(xx);
        if (!yy) xx += 7;
        else
        {
            int dd = 7 - yy;
            xx += dd + 7;
        }
        return xx;
    };

    auto getFatherDayId = [](int y)
    {
        Zeller::id xx = getZellerId(y, 6, 1);
        int yy = getWeekday(xx);
        if (!yy) xx += 14;
        else
        {
            int dd = 7 - yy;
            xx += dd + 14;
        }
        return xx;
    };

    int t; cin >> t;
    int y, m, d;
    while (t --)
    {
        cin >> y >> m >> d;
        if (m < 5)
        {
            auto id = getMotherDayId(y);
            auto dd = getZellerDate(id);
            cout << dateString(dd.year, dd.month, dd.day) << endl;
        }
        else if (m > 6)
        {
            auto id = getMotherDayId(y + 1);
            auto dd = getZellerDate(id);
            cout << dateString(dd.year, dd.month, dd.day) << endl;
        }
        else
        {
            auto ll = getMotherDayId(y);
            auto rr = getFatherDayId(y);
            auto mm = getZellerId(y,m,d);
            Zeller::date dd;
            if (mm < ll) dd = getZellerDate(ll);
            else if (mm < rr) dd = getZellerDate(rr);
            else
            {
                auto id = getMotherDayId(y + 1);
                dd = getZellerDate(id);
            }
            cout << dateString(dd.year, dd.month, dd.day) << endl;
        }
    }

    return 0;
}

于是这个题目就变成了愉快的板子题。

看了官方题解，采用的是打表找规律：因为每年365天满足 365 ≡ 1 mod 7，第x个星期日每次的日期偏移是1——所以某月第确定个个星期日一定是出现在一个确定的范围内；找规律可以发现出了闰年之外，每年变化一天；这样我们就可以先打表预处理本就不大的范围内的父亲解母亲节日期，然后再根据输入二分查找。

小声bb：出题人为了照顾大家的英语水平，甚至事后补充了十二个月的单词拼写和 st/nd/rd/th……

G - 血压游戏

一棵树上n个点，每个点有一些松鼠。有一个根节点，这些松鼠都会朝根节点跑，最后在根节点被救出。单位时间内，这些松鼠会按顺序做下面这些事情：

  • 如果这个节点上有多只松鼠，那么先打架，导致一只松鼠去世
  • 剩下来的松鼠跑到当前节点的父节点上；如果当前在根节点，那么被救出

问，所有的松鼠都被从树中救出后，一共还剩下多少只松鼠。

一些想法

暴力做法就是多次DFS更新树节点，统计答案，平均O(nh)；但是显然当树退化成一条链的时候，这样做就变成平方的了，也就是说没了（

想过分层统计每一层树高上的松鼠数量然后……好像和上面没什么区别啊== 但是不同深度的松鼠确实是互不影响的，如果使用某种方法分层处理就好了（

解题思路

虽然不是很懂，但是读完题之后就产生了这题要使用树剖的预感；虽然最后没做出来== 看了民间的题解，确实需要使用树剖的知识。在开始补题之前，先简单介绍一下这些前置知识：

DSU on tree

官方题解思路一：对于每一种深度的点分块建虚树，对于每一棵虚树统计答案；总复杂度O(n log n)。

补题代码

H - 纸牌游戏

扑克，有n张牌，每张代表0~9的数字；要求从手牌中选出k张，组成一个能被3整除的k位非负整数，且不能有前导零；问最大能组成多少。

不超过1000组数据，不超过1e5张牌；这些数字用一个字符串给出；如果无解，输出-1.

I - 古老的打字机

有n个小写字母构成的字符串si，每个字符串的价值是vi；有一个只有一个键的打字机，你的输入有50%的概率变成backspace，剩下的50%是输入一个随机小写字母；你按下了这个按键m次，得到了字符串t；这个字符串的价值可以这样计算：设字符串si在t中出现了ci次，那么价值是

\[ \sum_{i=1}^n c_i v_i \] 求随机字符串t的价值的数学期望，并且输出这个值的\(21^m\)倍数关于1e9+7的模。

J - 能到达吗

n × m的地图中有k个障碍物，给定了障碍物的坐标；玩家最开始在左上角(1,1)，可以四方向在地图内无障碍物的地方移动；求地图中可以互相连通的点对的数量，关于1e9+7取模；这里的点对的两个点可以是一致的，但是颠倒的点对将被算作和原点对同一个。

K - 迷宫

n × m的迷宫，有障碍；给定起点和终点，玩家可以四方向移动，还可以使用一次穿越：无视连通性，在一步的时间内转移到切比雪夫/曼哈顿距离不超过d的另一片空地上；求到达终点所需要的最少步数，如果无解，输出-1.

一些想法

切比雪夫距离，扩展开来是一个

L - 动物森友会

你需要参加n个活动c次数，但这些活动每周只会在固定的m天开放；此外，你每天最多只能参加e次活动；问从一周的周一开始，你最少要几天后才能参加完这些活动。

一些想法

像极了二分图匹配模型，但是因为每天可以干多项活动，每天也有数量限制，那么就用具有通用性的网络流，应该就好可以了。于是，网络流建模完了然后呢？

解题思路

这题目确实应该就是要用网络流的了。那么我们首先来建个模：

  • 从源点向一周的七天连边，边的流量是这个日子经历的次数*e
  • 每周天向当天可以举行的活动连边，边的流量是无穷大
  • 从每个活动向汇点连边，第i个活动的边的流量是ci

非常的合理：从源点流出的是我们可以执行活动的总次数，流向汇点的是有效的次数；如果最后满流了，那么也就成了。但是这并不能帮助我们直观的求出来答案天数。

进一步分析，求的是满足条件的最小天数：显然这是一个具有二分单调性的经典模型；然后，这个网络流模型从源点流出的边的流量恰好需要一个确定的天数来确定，然后判断一个答案的可行性——那么一个使用二分+网络流模型来解题的思路就有了。

曾经某一次比赛中，可能有这么一个同学说过了这样一句话：“网络流的本质还是贪心”；那么这个题目（确实，七天不算是特别复杂）可不可以直接裸贪心来解决呢？

693EA78014F78D5CE246D2818BCC3E4E.jpg

那等我想到了再补好了（

补题代码

补题的时候这个题目总是过不了，一度让我认为我的板子出锅了== 然而经过多轮检查，发现它并没有什么问题（

这是网络流最大流的dinic算法+当前弧的板子：

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
namespace FlowNetwork
{
    int dis[N], cur[N];
    int S, T, cnt = 0;

    auto __addedge = [](int u, int v, longs w)
    {
        FWS::addedge(u, v, w);
        FWS::addedge(v, u, 0);
    };

    bool bfs()
    {
        using namespace FWS;
        static queue<int> q;
        memset(dis, 0x3f, sizeof(int)*(cnt + 1));
        q.push(S); dis[S] = 0;
        while (!q.empty())
        {
            int u = q.front(); q.pop();
            for (int cc = head[u]; ~cc; cc = ee[cc].next)
            {
                edge& e = ee[cc]; int v = e.v, w = e.w;
                cur[u] = head[u];
                if (!w || dis[v] <= dis[u] + 1) continue;
                dis[v] = dis[u] + 1; q.push(v);
            }
        }
        return dis[T] != inf;
    }

    longs dfs(int u, longs inflow)
    {
        using namespace FWS;
        if (u == T) return inflow;
        longs outflow = 0, rest = inflow;
        for (int &cc = cur[u]; ~cc; cc = ee[cc].next)
        {
            edge &e = ee[cc]; int v = e.v; longs w = e.w;
            edge &r = ee[cc ^ 1];
            if (!w || dis[v] != dis[u] + 1) continue;
            longs t = dfs(v, min(w, rest));
            outflow += t; e.w -= t; r.w += t; rest -= t;
            if (!rest) break;
        }
        if (!outflow) dis[u] = 0;
        return outflow;
    }

    longs dinic()
    {
        longs maxflow = 0;
        while (bfs()) maxflow += dfs(S, inf);
        return maxflow;
    }
}

日……loj的代码编辑器也太好看了吧== 个人觉得某些方面超过Monaco Editor了。如果我知道了这是哪个前端轮子的话我也去整一个——不过整哪里呢（

然后就是本题的代码：

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <bitset>

#define FN FlowNetwork

using namespace std;
using longs = long long;

const signed inf = 0x3f3f3f3f;
const longs INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1050, M = N * 8;

int n, e, c[N], sum;
bitset<8> a[N];

struct edge
{
    int u, v, next;
    longs w;
    edge() = default;
    edge(int u, int v, longs w, int next)
            : u(u), v(v), w(w), next(next) {}
};

namespace FWS
{
    int head[N];
    int tot;
    edge ee[M * 2];

    void init(int n = N-1)
    {
        memset(head, -1, sizeof(int)*(n+1));
        tot = 0;
    }

    void addedge(int u, int v, longs w)
    {
        ee[tot] = edge(u,v,w,head[u]);
        head[u] = tot ++;
    }
}

namespace FlowNetwork
{
    int dis[N], cur[N];
    int S, T, cnt = 0;

    const int __event = 9, __day = 2;
    auto event = [](int i){return __event+i;};
    auto day = [](int i){return __day+i;};

    auto __addedge = [](int u, int v, longs w)
    {
        FWS::addedge(u, v, w);
        FWS::addedge(v, u, 0);
    };

    auto __build = [](int t)
    {
        cnt = 0; FWS::init(n+9);
        S = ++ cnt; T = ++ cnt;
        for (int i = 1; i <= 7; ++ i)
            __addedge(S, ++ cnt, (t/7+(t%7>=i))*e);
        for (int i = 1; i <= n; ++ i)
        {
            __addedge(++ cnt, T, c[i]);
            for (int j = 1; j <= 7; ++ j)
                if (a[i][j]) __addedge(day(j), cnt, INF);
        }
    };

    bool bfs()
    {
        using namespace FWS;
        static queue<int> q;
        memset(dis, 0x3f, sizeof(int)*(cnt + 1));
        q.push(S); dis[S] = 0;
        while (!q.empty())
        {
            int u = q.front(); q.pop();
            for (int cc = head[u]; ~cc; cc = ee[cc].next)
            {
                edge& e = ee[cc]; int v = e.v, w = e.w;
                cur[u] = head[u];
                if (!w || dis[v] <= dis[u] + 1) continue;
                dis[v] = dis[u] + 1; q.push(v);
            }
        }
        return dis[T] != inf;
    }

    longs dfs(int u, longs inflow)
    {
        using namespace FWS;
        if (u == T) return inflow;
        longs outflow = 0, rest = inflow;
        for (int &cc = cur[u]; ~cc; cc = ee[cc].next)
        {
            edge &e = ee[cc]; int v = e.v; longs w = e.w;
            edge &r = ee[cc ^ 1];
            if (!w || dis[v] != dis[u] + 1) continue;
            longs t = dfs(v, min(w, rest));
            outflow += t; e.w -= t; r.w += t; rest -= t;
            if (!rest) break;
        }
        if (!outflow) dis[u] = 0;
        return outflow;
    }

    longs dinic()
    {
        longs maxflow = 0;
        while (bfs()) maxflow += dfs(S, INF);
        return maxflow;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> e;
    int m, x; sum = 0;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> c[i] >> m;
        sum += c[i];
        while (m --)
        {
            cin >> x;
            a[i][x] = true;
        }
    }

    auto check = [&](int mid)
    {
        if (e * mid < sum) return false;        
        FN::__build(mid);
        return FN::dinic() == sum;
    };

    int ll = 0, rr = inf / e, ans = 0;      
    while (ll <= rr)
    {
        int mm = ll + rr >> 1;
        if (check(mm)) ans = mm, rr = -- mm;
        else ll = ++ mm;
    }
    cout << ans << endl;

    return 0;
}

真的离谱：验完板子，还是那个板子重新敲一遍就一遍过了可还行（

后记

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://shiraha.cn/2020/SHU-iflytek-cup-18th-spring-contest/

更新于：2020年4月18日

算法

ACM

Nowcoder

评论