抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

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

博客

随笔

朋友

归档

关于

2019 NWRRC 回顾

题解

发布于：2020年5月30日

虽然找到了官方网站，但是并没有找到题解文档或者是 Slide——准确的说是没有找到英文版本的，俄文版本倒是有的，甚至还有标题是英文内容是俄文的…… 下载到的标程也存疑，因为形态比较诡异，也就没有参考；

找到了就会贴出来的找不到的，最后还是依靠校队组织的讲题完成了这篇题解，官方的俄文题解我是不指望了（

下面就是这次的 13 个题目，我也没有做出来几个，没做出来的就先占个坑好了：

A. Accurate Movement

槽里面有一个长条，一个短条，起始位置都在一侧；一次只能移动一个，要保证短条始终在长条内部，问最少需要多少次才能够将两个条都移动到槽的另一端。

签到题。

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

using namespace std;

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

    int a, b, n;
    cin >> a >> b >> n;
    auto xx = n - a;
    auto tt = xx / (b - a) + bool(xx % (b - a));
    cout << tt * 2 - 1 << endl;

    return 0;
}

B. Bad Treap

Treap，树堆，即笛卡尔树；每一个节点包含两个值 (K, V)，K 值满足二叉搜索树的性质（左二子 < 树根 < 右儿子），而 V 值满足堆的性质（根 > 所有儿子）；

现在要构造一颗树堆，它的每个节点定义是 (x, y = sin x)；现在你希望它包含 n 个节点，且平衡性是所有 n-树堆 中最差的；你要构造出这 n 个节点的 x 值，且 x 的类型是 __int32。

数据范围：1 ≤ n ≤ 50000，-2³¹ ≤ x ≤ 2³¹ - 1；

首先，”最不平衡“指的是左右子树的高度差最大；显然，一颗 n 个节点构成的 Treap 能达到的最大的高度差是 n-1：即当整棵树退化成一条链的时候；那么在什么样的情况下，这棵树会退化成一条链呢？一种很简单的情况，就是当 K 和 V 值都是单调的时候，堆的性质一定会满足，所有节点都是其父节点的左二子或是右儿子；

观察节点的函数 (K: x, V: y = sin x)：假设我们想要一个 V 随着 K 增大而增大的区间，那么这个区间可以是 x ∈ [-π/2, π/2]；但是题目要求了键 K 是 __int32 类型，不然我们直接将这个区间平均分配就可以了；但是另注意到，sin x 是一个周期函数，所以对于同一个 V 值，可以对应多个差距为 2kπ 的 K 值，只要这些 K 值递增且为整数，就可以构造出一个整数数列；那么现在我们想要构造一组 K = -π/2 + 2πi / T + 2kπ，使得他们都是整数且数列递增；显然，增量 δ = 2π / T + εkπ；

当然，我们可以使用暴力的方法先行求出这个 ε 的值，进而得到这个增量 δ 的值，使用下面的简单易懂的代码就可以轻松的求出在不同整数精度的情况下的增量值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template <typename number>
class comparable : binary_function<number, number, bool>
{
    number eps = 1e-8;
    int compareTo(number x) const {return x < -eps ? -1 : x > eps;}

public:
    explicit comparable(number eps) : eps(eps) {}
    int compareTo(number a, number b) const {return compareTo(a-b);}
    int operator()(number a, number b) const {return compareTo(a-b);}
};

long double calcDelta(long double precision, unsigned count)
{
    static const long double pi = 3.1415926535897932384626;
    static const long double dpi = 2.0 * pi;
    comparable<long double> cmp(precision);
    const long double delta = pi / count;
    cerr << fixed << setprecision(10) << "delta: " << delta << endl;
    long double xx = delta, ans = xx; int cnt = 0;
    while (cmp(ans, ceil(ans))) ++ cnt, ans = xx + cnt * dpi;   // unsequenced modification and access to "ans"
    return cerr << "found: " << ans << endl, ans;
}

因为题目的要求是 50000 数据范围，如果调用上述的 calcDelta(1e-5, 50000) 得到的是 1420，交上去会挂掉；因为 C++ 浮点数有着大家都知道的误差，所以一般来说 T 应该更大的数，比如 60000，求出的增量 710，就可以过了；此外按照 hjl 巨佬的 ppt 上的推法也可以得到相同的结果；最后代码就像下面这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
	int n; cin >> n;
    for (int i = 0; i < n; ++ i)
        cout << 710 * (i - 25000) << endl;
    return 0;
}

C. Cross-Stitch

Cross-Stitch [n] 十字绣给你一个 h 行 w 列的十字绣图案，要求使用一根线将它绣出来，并且消耗线的长度最少；输出这种绣法包含的针数（孔数），并且按照先后顺序输出线经过的点的坐标。

数据规模：1 ≤ w, h ≤ 100；

首先，一根线绣出的意思，就是说存在一条欧拉回路连接这所有的绣边；要消耗线的长度最小，不论怎样的绣边的长度都只能是 1 或者是 √2；最短的消耗，一定是每个十字绣网格，由两条长度为 √2 的表线，和两条长度为 1 的里线组成，且包含起点和终点的网格可以节约一条里线；

因为给的十字绣图案只是表面的走线，里面的走线是可以按照一定的标准来自行连接的，经过草稿纸上的推导其实是我懒得在电脑上画图了，就可以知道起点和终点是可以在同一个方格里的十字上的；这样，当我们连接起点和终点作为里边的时候（这样的连接是合法的），就可以将欧拉路变成欧拉环；

严格按照 表-里-表-里 的方法绣十字绣，当所有的方格的构型是相同（两条里边上下/左右相对）时，一定存在这样的欧拉回路，将所有的绣点连接起来；所以我们可以按照这种思路建图，然后限定 表-里 交错的方法 DFS，就可以找到一个绣十字绣的顺序，它可以确保绣出这个图案并且花费线材最少；特别注意第一针必须绣表线，代码如下：

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

using namespace std;

const int N = 105, M = N * N * 4;
char map[N][N];
int id[N][N], cnt = 0, vis[M];
vector<int> ans;

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

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

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

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

void init(int n, int m)
{
    ans.clear(); cnt = 0;
    for (int i = 0; i <= n; ++ i)
        for (int j = 0; j <= m; ++ j)
            id[i][j] = cnt ++;
    FWS::init(cnt + 5);
}

void addEdge(int u, int v, int color)
{
    FWS::addEdge(u, v, color);
    FWS::addEdge(v, u, color);
}

void dfs(int u, int last_color)
{
    using namespace FWS;
    for (auto cc = head[u]; cc + 1; cc = ee[cc].next)
    {
        if (vis[cc / 2] || ee[cc].w == last_color) continue;
        vis[cc / 2] = true;
        dfs(ee[cc].v, ee[cc].w);
        ans.push_back(ee[cc].v);
    }
}

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

    int m, n;
    cin >> m >> n;
    init(n, m); int sp, div = m + 1;
    for (int i = 1; i <= n; ++ i) cin >> (map[i] + 1);
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j)
            if (map[i][j] == 'X') sp = id[i][j],
                addEdge(id[i - 1][j - 1], id[i][j], 1),
                addEdge(id[i - 1][j], id[i][j - 1], 1),
                addEdge(id[i - 1][j], id[i][j], 0),
                addEdge(id[i - 1][j - 1], id[i][j - 1], 0);
    dfs(sp, 1);
    cout << (ans.size() - 1) << endl;
    for (auto & ii : ans) cout << ii % div << ' ' << ii / div << endl;

    return 0;
}

D. Double Palindrome

定义双回文串：一个字符串是双回文串，当且仅当它是一个回文串或两个回文串的组合；现在询问长度不超过 n 的，由大小为 k 的字符集排列组合构成的所有字符串中回文串的数量，输出答案取模。

数据规模：1 ≤ k ≤ 26 并且 1 ≤ n ≤ 1e5。

占坑

E. Equidistant

有 n 个城市连成一棵树，每两个相邻的城市连接的边的长为 1；现在这些城市中的一部分（或者全部）都有人要参加区域赛，问比赛场地设置在哪座城市，才可以保证所有城市的参赛者到达比赛场所需要走的路径长度一致，不存在这样的城市时输出 Impossible。

没有什么特别优秀的做法，考虑暴力，但是并不是直接就暴力了——n²给卡到死；仔细思考一波，发现最多只要扫描所有的节点就一定可以找到这个点，那么就可以考虑多起点 BFS：每当一个节点到达一个节点的时候，如果深度和当前深度一致就增加一次访问次数，这样最终只需要遍历所有节点，找到是否存在被访问了 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
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
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 2e5 + 5, M = N;
int n, m, c[N];

struct edge
{
    int u, v, w, next;
    edge() = default;
    edge(int u, int v, int 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, int w)
    {
        ee[tot] = edge(u,v,w,head[u]);
        head[u] = tot ++;
        ee[tot] = edge(v,u,w,head[v]);
        head[v] = tot ++;
    }
}

int BFS()
{
    if (n == 1) return 1;
    queue<int> q;
    int visit[N] {0}, depth[N] {0};
    bool used[N] {false};
    for (int i = 1; i <= m; ++ i)
    {
        q.push(c[i]);
        visit[c[i]] = 1;
        depth[c[i]] = 1;
        used[c[i]] = true;
    }
    int found = -1;
    using namespace FWS;
    while (!q.empty())
    {
        auto top = q.front(); q.pop();
        for (auto ii = head[top]; ~ii; ii = ee[ii].next)
        {
            auto &e = ee[ii];
            if (!depth[e.v] || depth[e.v] == depth[e.u] + e.w)
            {
                visit[e.v] += visit[e.u];
                depth[e.v] = depth[e.u] + e.w;
                if (visit[e.v] == m)
                {found = e.v; break;}
                if (!used[e.v])
                {
                    q.push(e.v);
                    used[e.v] = true;
                }
            }
        }
        if (found > 0) break;
    }
    return found;
}

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

    cin >> n >> m;
    int u, v;
    FWS::init(n);
    for (int i = 1; i < n; ++ i)
    {
        cin >> u >> v;
        FWS::addEdge(u, v, 1);
    }
    for (int i = 1; i <= m; ++ i)
        cin >> c[i];
    int found = BFS();
    if (found < 0) cout << "NO" << endl;
    else cout << "YES" << endl << found << endl;

    return 0;
}

但是这个题目，ECNU 的带佬们有他们独特的想法：首先对于两个“相邻”的特殊点使用倍增 LCA 求中点，且没有终点，一定无解；之后按照 DFS 标号后，就将子树问题转化为了区间问题；虽然到头来，他也没有提供这么做的代码，但是想必也是很有趣的思路吧。

F. Foreach

PHP 的 foreach 模拟器因为题目太长所以下面直接说意思：

有一个 PHP 数组 $a，你可以使用 foreach 遍历所有的变量，并且使用 break 中断循环；为了简单起见，你只能操作变量 $x：你可以使用两种 foreach 语句进行操作：

  • 带引用版本：将变量设置为数组中某元素的引用，你只可以使用如下的形式获得元素的引用

    1
    foreach ($a as &$x) if ($x == <some integer value>) break;

  • 值版本：将变量（引用的元素）设置为一个数组元素的值；同样只能使用如下形式

    1
    foreach ($a as $x) if ($x == <some integer value>) break;

接下来题目会给你一个长度为 n 的数组 $a，并且指定目标状态；要求你生成将原数组转化为目标状态的代码（仅由上述两个语句构成），并在第一行输出代码行数；如果不可能生成这样的代码。输出 -1；

数据规模：数组长度 1 ≤ n ≤ 50，元素（包括原始状态和目标状态）的值 1 ≤ si, ti ≤ 100；

使用谷歌生草机来学习共产主义唯一指定语言——俄语

G. Golf Time

有一个宽为 w，高为 h 的球场，定义坐标系：+x 向右，+y 向上；球场内有一个 n 边形池塘，如果球到达了池塘位置就会立即下沉，输入将按照顺时针方向描述池塘边缘所有的格点；球总是朝东北方向发出，并保持匀速直线运动 (1, 1)；当球撞到了边缘，球会被无能量损失的反弹（仅改变运动方向）；现在告诉你 t 个发球点，问这个球是否可以永远的运动下去，或在落水之前运动的时间以及落水时的准确位置。

数据规模：4 ≤ w, h ≤ 5e8，4 ≤ n ≤ 1000，1 ≤ t ≤ 100；

占坑

H. High Load Database

有一个数据库，里面有 n 块数据，每一块数据的大小是 ai；接下来尝试将这个大数据库分库成多个单个存储了不超过 t 数据的数据库：要求数据块的顺序保持和原数据库一致，且每一块数据一定要放在一个数据库中；进行 q 次询问，每次询问 ti，要求求出分成的数据库的数量，或者不能够实现目标。

数据规模：1 ≤ n ≤ 2e6，1 ≤ Σai ≤ 1e6，1 ≤ q ≤ 1e6，1 ≤ t ≤ Σai；

不能分库的情况很显然，就是存在单块数据大于这个要求的数据库最大容量 t，做一下特殊处理就好了；接下来对于单次询问 t，也很容易有这样的思路：从第一块数据开始贪心的向右边数，当空间超过 t 的时候就取出最后一块数据，并且统计次数自增即可；这样对于单次询问是 O(n) 的。

但是问题是这题询问次数很多，这样复杂度就是 O(nq) 的，就会炸了；所以需要想方设法进行一些优化：注意到了询问从左向右的过程是再不断累加求和，这个过程显然可以使用前缀和优化掉；接下来得到的前缀和序列就是一个递增序列：我们每一次寻找到的当前分库存储的数据量 x’ 也可以表示为 Σx + x’ 的前缀和形式，这样就可以使用二分查找了；

还是应当注意一些实现细节；整体复杂度是 O(qlogn)。

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>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 2e5 + 5;

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

    int n, a[N], q, t, inm = 0, sum[N] {0};
    cin >> n;
    for (int i = 1; i <= n; ++ i)
        cin >> a[i], inm = max(inm, a[i]),
                     sum[i] = sum[i - 1] + a[i];
    unordered_map<int, int> mem;
    const auto end = sum + n + 1;
    cin >> q; while (q --)
    {
        cin >> t;
        if (t < inm) cout << "Impossible" << endl;
        else if (mem.count(t)) cout << mem[t] << endl;
        else
        {
            int ans = 0;
            for (int cur = 0; cur < n; -- cur)
            {
                ++ ans;
                cur = upper_bound(sum + cur, end, sum[cur] + t) - sum;
            }
            cout << (mem[t] = ans) << endl;
        }
    }

    return 0;
}

虽然这样前缀和二分就已经可以做出这个题目了：但是听了校队的 sac 巨佬的讲解之后，了解到了这种情况下还可以使用倍增来搜索前缀和数组，以快速找到下一个合理的位置；先上代码：

1
2
3
4
5
6
7
8
9
while (++ cnt) 
{
    int tol = 0, bin = 1;
    while (bin)
    	if (l + tol + bin > n || a[l + tol + bin] - a[l] > t) bin >>= 1;
    	else tol += bin, bin <<= 1;
    if (l + tol == n) break;
    l += tol;
}

简单的说就是固定左侧端点，然后使用倍增的方法（其实也就是变相的二分）来枚举段的大小；理论上的时间复杂度仍然和二分方法一样，是 O(log 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
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
#define USING_STDIO 0
#if USING_STDIO
#include <cstdio>
#include <cctype>

inline int nextInt()
{
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
    return x*f;
}
#else
#include <iostream>
#include <iomanip>
#endif
#include <unordered_map>

using namespace std;

constexpr long double eps = 1e-8;
template <typename number>
int compareTo(number x) {return x < -eps ? -1 : x > eps;}
template <typename number>
int compareTo(number a, number b) {return compareTo(a-b);}

const int N = 2e5 + 5;
int n, a[N], q, t;
long long sum[N];

int main()
{
#if !USING_STDIO
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
#endif

    cin >> n; int top = sum[0] = 0;
    sum[n + 1] = 0x7fffffffffffffff;
    for (int i = 1; i <= n; ++ i)
        cin >> a[i], top = max(top, a[i]),
        sum[i] = sum[i - 1] + a[i];
    unordered_map<int, int> memo;
    cin >> q; while (q --)
    {
        cin >> t;
        if (t < top) cout << "Impossible" << endl;
        else if (memo[t]) cout << memo[t] << endl;
        else
        {
            int cnt = 0, l = 0, r;
            while (++ cnt)
            {
                int off = 0, bin = 1;
                while (bin)
                    if ((r = l + off + bin) > n ||
                        sum[r] - sum[l] > t) bin >>= 1;
                    else off += bin, bin <<= 1;
                if (l + off == n) break;
                l += off;
            }
            cout << (memo[t] = cnt) << endl;
        }
    }

    return 0;
}

虽然不知道在其他的二分题目里面这有没有什么应用，但是在这里他就这么用上了。

I. Ideal Pyramid

二维坐标系中有 n 个柱子，使用 (x, y, h) 来描述它们：xy 即平面坐标系中代表位置的坐标，h 代表这些柱子的高度；现在法老想要修金字塔：金字塔是一个四棱方锥，四个三角面和坐标系平面的夹角是 45°；法老希望这个金字塔覆盖了所有的柱子，同时尽可能的小，并且金字塔尖一定要是整数坐标的；要求输出 (x, y, h) 描述这个金字塔：xy 是金字塔尖的位置坐标，h 是这个金字塔的高度。

一开始看还以为是平面二分，甚至搬出了我那丑陋的平面几何板子== 最后发现这彻头彻尾是一个超有趣的思维题（也不算吧，主要还是自己太蠢了）：我们假设在每一个柱子处建造小型金字塔，那么符合题意的金字塔一定会把这些金字塔都包含在其中，这样的话金字塔投影的正方形一定会把这些小金字塔的正方形包含在其中——大正方形包含小正方形还是很好计算的；所以我们只要把柱子转化成金字塔投影方形，然后求可以覆盖这些投影的最小正方形，然后求出这个正方形的中心坐标并且计算高度就可以了（草

特别提示：这个金字塔的投影就是边都在网格上的正方形，而不是格点菱形；就算是格点菱形依然是这个思路，只不过求包覆的大菱形的难度变大了==

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

using namespace std;

struct triple
{
    int x, y, h;
    triple(int x, int y, int h) : x(x), y(y), h(h) {}
};

vector<triple> p;
int n;

triple solution()
{
    int uu = p[0].y - p[0].h,
            dd = p[0].y + p[0].h,
            ll = p[0].x - p[0].h,
            rr = p[0].x + p[0].h;
    for (auto &ii : p)
    {
        int uuu = ii.y - ii.h,
                ddd = ii.y + ii.h,
                lll = ii.x - ii.h,
                rrr = ii.x + ii.h;
        uu = min(uu, uuu);
        dd = max(dd, ddd);
        ll = min(ll, lll);
        rr = max(rr, rrr);
    }
    auto xx = rr - ll, yy = dd - uu;
    unsigned length = max(xx, yy);
    if (length & 1u) ++ length;
    int height = length >> 1u;
    return {ll + height, uu + height, height};
}

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

    cin >> n; int x, y, h;
    for (int i = 0; i < n; ++ i)
    {
        cin >> x >> y >> h;
        p.emplace_back(x, y, h);
    }
    auto ans = n == 1 ? p.front() : solution();
    cout << ans.x << ' ' << ans.y << ' '
         << ans.h << endl;
    return 0;
}

J. Just the Last Digit

现在有一个 n 个节点的图，它的每个节点的高度都是唯一的，且是 [1, n] 中的一个整数：数字越大高度越低；现在你只能从高的点到达低的点，你最开始站在最高点处；接下来给你的数据包括一组数据：记载了从每一个点（高度）到达其他点的方法数的最后一位，要求你根据这些数据还原出这个图的可达信息。

数据范围：2 ≤ n ≤ 500.

输入数据看起来有点像入度，但其实不是；只给最后一位的数字也非常的吓人，啊这那我不会做了==

仔细观察样例一定可以发现：对于ai,ja_{i,j} ，就是从 i 点出发到达 j 点的方式数字，当 i ≤ j 的时候的数字必然是 0：这很好理解，因为我比不可能到达比我当前位置高的地方；那我们对于第 i 组数据，只需要从第 i+1 个位置开始考虑就可以了：首先就是 i+1 位置，它只可能是两个值——1 表示该点和当前点是直接连接的，0 则表示没有直接通路；因为这两个点高度差距之间不允许出现间接到达的可能，所以就可以直接得出准确信息；

接下来考虑 [i+2, n] 位置的值：根本没有办法考虑，你能得到的信息就是它定义说的那样；但是从定义出发，就这样：当我们确认 i - i+1 的路径是存在的，那么对于 x ∈ [i+2, n]，一定会有 cnt(i, x) ≥ cnt(i+1, x) ——因为 i 一定可以通过 i+1 到达这些位置，这是确定的间接到达，可以从现在的第 i 组数据中减去；

我们继续向右扫描，如果还能遇到没有被消除的，存在的 j ∈ [i+2, n]，那么它一定是 1，并且代表它和 i 是直接连接的：因为间接连接的可能性都在前面的扫描中被排除了；我们可以再如法炮制，将通过 j 间接到达的可能性全部排除；这样循环就可以填完整个数组，求出所有可能建立直接连接的边，也就是还原了图。

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;

const int N = 550;

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

    int n, map[N][N], ans[N][N];
    char ch;
    cin >> n;
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
        {
            cin >> ch;
            map[i][j] = ch - '0';
        }
    for (int i = 1; i < n; ++ i)
        for (int j = i + 1; j <= n; ++ j)
        {
            ans[i][j] = map[i][j];
            if (map[i][j]) for (int k = 1; k <= n; ++ k)
            {
                map[i][k] -= map[j][k];
                while (map[i][k] < 0) map[i][k] += 10;
            }
        }
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 1; j <= n; ++ j)
            cout << ans[i][j];
        cout << endl;
    }

    return 0;
}

K. King’s Children

国王有一个 n × m 矩阵的地图，每一个方格是地盘的最小单位；王有不超过 26 个儿子，用字母表示；每一个儿子有一个城堡，位于地图中的某个方格上：这个方格使用这个字母的大写形式标识，其他方格用 . 表示；现在国王要将地盘分给儿子们，分给儿子们的地盘用字母的小写形式表示；分地图有要求：所有领土必须全部分给儿子，且每个儿子得到的领土是严格的网格矩阵；此外，国王希望 A 儿子分到的领土尽可能的大；现在要求你将分割后的矩阵计算出来并输出。

数据范围：1 ≤ n, m ≤ 1000

好麻烦的 DSU 题目…… 直接翻译题意就可以知道，首先我们要求出整个矩阵中 A 可以拓展的最大子矩阵，然后再拓展其他的字母，将整个矩阵填满；填充最大子矩阵可以使用很多种方法：比如悬线法，或者是单调数据结构等等，求出了 A 的最大子矩阵之后，就将矩阵剩余部分划分成了四个部分；因为其他的字母只需要扩充后填满整个矩形即可，所以不再需要跑一遍最大子矩阵了，随便使用什么乱搞的方法将矩阵填满就可以了。

这里填充其他矩阵的方法，就是对于任何一个字母，先尝试上下拓展，将整列占满，之后再尝试横向拓展；就算这一步暴力也问题不大，之后得到的结果一定是有效的。

先复习关于最大 0, 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
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
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int N = 1050;
char map[N][N], ans[N][N];
int n, m, pos[N][N];

struct node
{
    int x, y; char ch;
    node(int x, int y, char ch) : x(x), y(y), ch(ch) {}
};

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

    int Ax, Ay;           
    vector<node> vec;     
    pair<int, int> seg[N];
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i)
        cin >> (map[i] + 1);
    memset(pos, 0, sizeof pos);
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j)
            if (map[i][j] == 'A')
                pos[i][j] = map[i][j] - 'A' + 1,
                Ax = i, Ay = j;
            else if (map[i][j] != '.')
                pos[i][j] = map[i][j] - 'A' + 1,
                vec.emplace_back(i, j, pos[i][j] - 1 + 'a');
    for (int j = 1; j <= m; ++ j)
    {
        int uu = Ax, dd = Ax;
        if (pos[Ax][j] && j != Ay)
        {
            seg[j] = make_pair(uu, dd - 1);
            continue;
        }
        while (uu > 1 && !pos[uu - 1][j]) -- uu;
        while (dd + 1 <= n && !pos[dd + 1][j]) ++ dd;
        seg[j] = make_pair(uu, dd);
    }
    pair<int, int> outer = seg[Ay], sav;
    int al = Ay, ar = Ay, aa = 0;
    for (int ll = Ay; ll >= 1; -- ll)
    {
        auto inner = outer;
        for (int rr = Ay; rr <= m; ++ rr)
        {
            int area = (rr - ll + 1) * (inner.second - inner.first + 1);
            if (area > aa)
            {
                aa = area, al = ll, ar = rr;
                sav = inner;
            }
            inner.first = max(inner.first, seg[rr + 1].first);
            inner.second = min(inner.second, seg[rr + 1].second);
        }
        outer.first = max(outer.first, seg[ll - 1].first);
        outer.second = min(outer.second, seg[ll - 1].second);
    }
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j)
            ans[i][j] = '.';
    for (int j = al; j <= ar; ++ j)
        for (int i = sav.first; i <= sav.second; ++ i)
            ans[i][j] = 'a';
    ans[Ax][Ay] = 'A';
    for (auto &ii : vec) ans[ii.x][ii.y] = ii.ch - 'a' + 'A';
    for (auto &ii : vec)
    {
        int xx = ii.x, yy = ii.y;
        char now = ii.ch;
        if (xx <= sav.second && xx >= sav.first)
        {
            int ll, rr;
            while (yy < m && (yy > al || yy + 1 < al) && ans[xx][yy + 1] == '.')
                ans[xx][++ yy] = now;
            rr = yy, yy = ii.y;
            while (yy > 1 && (yy < ar || yy - 1 > ar) && ans[xx][yy - 1] == '.')
                ans[xx][-- yy] = now;
            ll = yy;
            while (true)
            {
                ++ xx;
                if (xx > n || xx > sav.second) break;
                bool flag = true;
                for (int j = ll; j <= rr; ++ j) flag &= ans[xx][j] == '.';
                if (flag) for (int j = ll; j <= rr; ++ j) ans[xx][j] = now;
                else break;
            }
            xx = ii.x;
            while (true)
            {
                -- xx;
                if (xx < 1 || xx < sav.first) break;
                bool flag = true;
                for (int j = ll; j <= rr; ++ j) flag &= ans[xx][j] == '.';
                if (flag) for (int j = ll; j <= rr; ++ j) ans[xx][j] = now;
                else break;
            }
        }
        else
        {
            int uu, dd;
            while (xx < n && (xx > sav.second || xx + 1 < sav.first) && ans[xx + 1][yy] == '.')
                ans[++ xx][yy] = now;
            dd = xx, xx = ii.x;
            while (xx > 1 && (xx < sav.first || xx - 1 > sav.second) && ans[xx - 1][yy] == '.')
                ans[-- xx][yy] = now;
            uu = xx;
            while (true)
            {
                ++ yy;
                if (yy > m) break;
                bool flag = true;
                for (int i = uu; i <= dd; ++ i) flag &= ans[i][yy] == '.';
                if (flag) for (int i = uu; i <= dd; ++ i) ans[i][yy] = now;
                else break;
            }
            yy = ii.y;
            while (true)
            {
                -- yy;
                if (yy < 1) break;
                bool flag = true;
                for (int i = uu; i <= dd; ++ i) flag &= ans[i][yy] == '.';
                if (flag) for (int i = uu; i <= dd; ++ i) ans[i][yy] = now;
                else break;
            }
        }
    }
    for (int i = 1; i <= n; ++ i)
        cout << (ans[i] + 1) << endl;

    return 0;
}

因为基本上就是嗯暴力，所以代码也算不上整洁优雅==

L. Lengths and Periods

求字符串的临界指数：字符串 w 的子串 t，是由 t 的某个前缀 p 循环 α 次得到：这里的 α 未必是整数；字符串 w 的临界指数就是最大的 α；

数据范围：|w| ≤ 2e5

参考了一篇博客的介绍，它提到了这个题目不能用HDU6661 Acesrc and String Theory的做法来做；有时间研究研究

M. Managing Difficulties

给一个长度为 n 的数组 a；要求求出这个数组中，满足 i ≤ j ≤ k 并且ak−aj=aj−aia_k - a_j = a_j - a_i 的不同的三元组 (i, j, k) 的数量；有不超过 10 组的测试数据；

数据范围：3 ≤ n ≤ 2000，1 ≤aia_i ≤ 1e9

另一个签到题：一个第一题一个最后一题…… 好小子，真会照顾人（

直接暴力是 n³ 的直接暴毙，所以需要优化；这就是常用的套路：暴力两个下标，寻找满足第三个下标的值是否存在，或者存在几个，然后计算个数就可以了；至于记录下标值的数量，显然可以使用稀疏数组 unordered_map：

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

using namespace std;
typedef long long longs;

const int N = 2060;
int n, t, a[N];
unordered_map<int, int> mmp;

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

    cin >> t; while (t --)
    {
        cin >> n;
        for (int i = 1; i <= n; ++ i)
            cin >> a[i];
        auto n1 = n - 1;
        longs ans = 0;
        for (int i = 1; i <= n; ++ i)
            ++ mmp[a[i]];
        for (int i = 1; i <= n; ++ i)
        {
            -- mmp[a[i]];
            for (int j = 1; j < i; ++ j)
            {
                auto pos = 2 * a[i] - a[j];
                ans += mmp[pos];
            }
        }
        cout << ans << endl;
    }


    return 0;
}

当然，你也可以使用其他的思路进行暴力；大抵复杂度都是平方等级的。

后记

菜的扣脚…… 不会做题就算了，甚至还不会补题 == 我爬我爬（

3dfecf7637dcd426.jpg

你已经是一个成熟的题目了，应该学会自动 AC 了 ==

2019 NWRRC 回顾
https://shiraha.cn/2020/2019-nwrrc/
本文作者
七海
发布于
2020年5月30日
许可协议
CC BY-NC-SA 4.0

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

您可以参见本网站的声明和许可来了解详情

更新于：2020年5月30日

算法

ACM

Codeforces

Gym

评论