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

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

博客

随笔

朋友

归档

关于

2016 NWERC 回顾

题解

发布于：2020年3月10日

欢乐赛2，既然表现不佳那自然是要认真的补题的。按照惯例，在开始之前首先先码一下官方的题解：

官方网址： https://people.bath.ac.uk/masjhd/2016.NWERC/

在这里你可以下载到题目、官方题解、判题官写的标程以及测试数据。

由于本人实力原因以及各种其他原因，补题仍然有很多不全面的地方，只好先暂时搁置了……（希望Utaha学长教我）目前这个题解仍然存在这些问题：

  • D、G两题我是真的不会写……
  • J题网络流做法还没有写
  • I题的Steiner Tree也没有深入的讨论，直接搬的赛场上的代码
  • 其他我还没能确定的一些小问题

希望看官可以理解。若是我做出来了那些题目，一定会及时更新在这里的.

E – Exam Redistribution

本次签到题，是个人都做出来了。

题目大意

n个房间包含不同数量的学生，收卷子然后发卷子交换批改；先收的卷子先发，求一个安全的顺序，让所有学生都不能改到本房间的试卷。

也就是说给一个序列，求一个满足题目要求的顺序；

分析

暴死的情况有两种：

  1. 要不就是改自己的卷子——一个房间的大小超过了所有其他房间大小的和，那么本身就是不可能的；
  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
38
39
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <utility>

using namespace std;
typedef long long longs;

pair<int,int> s[40];

inline void init()
{
    for(int i=0;i<=30;++i)
        s[i].second = i;
}

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

    int n,sum = 0;
    init();

    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>s[i].first,sum+=s[i].first;
    sort(s+1,s+1+n);
    if(s[n].first > sum>>1)
        cout<<"impossible";
    else
    {
        for(int i=n;i>0;--i)
            cout<<s[i].second<<' ';
        cout<<endl;
    }

    return 0;
}

因为忘记初始化和大于等于忘记=而吃了一发WA也是没谁了……

H – Hamiltonian Hypercube

另一个签到题，是个人都做出来了。

题目大意

n位Gray码可以通过某种申必的方法映射到那个申必n维立方体上，并且还能形成哈密顿路（环）；但是这不重要——只是方便大家理解Gry码的。题目会输入两个Gray码，然后你要输出在这个申必立方体上两个码映射的节点在这个哈密顿路上的区间内包含的节点数。

也就是说求两个Gray码代表的数字的差的绝对值-1.

分析

妹啥好分析的，你会Gray码直接写个转换函数就成；不会的多读几遍题目也该会了。转化方式有好多种，我用的也是最常用的定义法——递归：

$$ ind(x_n) = \begin{cases} ind(x_{n-1}), & x = 0\ x_{n-1} \\ 2^{n} - ind(x_{n-1}) - 1, & x = 1\ x_{n-1} \\ \end{cases} $$

只要注意点别手贱，写出了转换函数之后求差的绝对值-1输出就可以了。和n是没什么关系的，n只是方便了读入以及告诉你转换结果开long long是能存的下而已。

我的代码

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 <cstdio>

using namespace std;
typedef long long longs;

char s1[100],s2[100];

longs gray(char* s, int n)
{
    if(n==1) return s[0]-'0';
    if(s[0]=='0')
        return gray(s+1,n-1);
    else
    {
        longs ret = 1ll<<n;
        return ret-1-gray(s+1,n-1);
    }
}

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

    int n;
    cin>>n;
    for(int i=0;i<n;++i)
        cin>>s1[i];
    for(int i=0;i<n;++i)
        cin>>s2[i];
    longs v1 = gray(s1,n);
    longs v2 = gray(s2,n);
    if(v1>v2) swap(v1,v2);
    longs ans = v2-v1-1;
    cout<<ans<<endl;

    return 0;
}

考试的时候不知道为什么没有写对，但是事后一遍过，就非常的离谱。我寻思该注意的应该都注意到了啊。

C – Careful Ascent

又一个签到题，是个人都做出来了。

题目大意

垂直速度恒定，水平速度理论上恒定：但是会受到不同高度区间的水平风的影响，导致最后实际的速度并不是恒定的。现在在高远的前方有一个目标，你的飞行器要从原点开始升起，要求恰好可以到达这个目标点应该控制的水平速度。

也就是说告诉你目标点的坐标以及不同高度的水平风信息，问你怎么控制水平速度。

分析

初中物理学过吧？那列个方程拿电脑解出来就行。

然后那答案还给了一种比较通用的方法，用于情况稍微复杂一点的状况（但是这个题目一点也不复杂）：二分法，然后模拟验证答案的正确性——偏离目标点左侧就加速，否则减速；直到和目标点的距离差距在eps之内。说不定只要能模拟判断可行性的答案都可以二分的去找。

我的代码

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

using namespace std;
typedef long long longs;
typedef long double longd;
typedef unsigned long long ulong;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cout<<fixed<<setprecision(9);

    longs x,y;
    cin>>x>>y;
    int n;
    cin>>n;
    longd sum = 0, k;
    longs u,l, d = 0;
    while(n--)
    {
        cin>>l>>u>>k;
        d += u-l;
        sum += k*(u-l);
    }
    longd ans = x/(y-d+sum);
    cout<<ans<<endl;

    return 0;
}

F – Free Weights

算是一个比较简单的题目，校队的朋友们都做出来了。

题目大意

一个健身房里有两排哑铃，每种重量的轮盘只有两个。现在我们想要把相同重量的轮盘放在一起；每排的空间是无限的，如果你想要将哑铃轮盘滚到旁边的空位上，这是免费的；否则你挪动任何一个轮盘都会消耗和轮盘等重的费用；问你整理完了这一波哑铃之后单次消耗的最高费用是多少。

也就是说求的是整理好这一波哑铃轮盘必须要挪动的轮盘的最大重量的最小值。

分析

如果要是求总的消费我可真是没太多想法，但是既然都说了“最大xx的最小值”，这一看就是一个二分答案的题目。但是应该怎么来模拟这个行为进行快速判定呢？

因为题目说了只求最高费用，换句话说就是比最高费用低的费用都免费了——随便挪的意思。那我们不如把所有较小的哑铃全部挪到千里之外并且让他们有序——恰好空间也是无限大的；然后再看留下来的轮盘是不是匹配的——不匹配咱也挪不了，说明这个最大重量不行；这样就可以方便的判断答案可行性了。

我的代码

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

using namespace std;
typedef long long longs;
typedef long double longd;
typedef unsigned long long ulong;

const int N = 1e6+5;

int n;
int in[2][N];

bool check(int m)
{
    int last;
    bool got = false;
    for(int i=0;i<n;++i)
    {
        if(in[0][i]<=m) continue;
        if(!got)
        {
            got = true;
            last = in[0][i];
        }
        else
        {
            if(last!=in[0][i])
                return false;
            got = false;
        }
    }
    if(got) return false;
    for(int i=0;i<n;++i)
    {
        if(in[1][i]<=m) continue;// 上点心吧
        if(!got)
        {
            got = true;
            last = in[1][i];
        }
        else
        {
            if(last!=in[1][i])
                return false;
            got = false;
        }
    }
    return !got;
}

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

    // freopen(R"(D:\shiroha\Downloads\nwerc2016testdata.tar\nwerc2016testdata\free_weights\6-lightly-shuffled.in)","r",stdin);

    cin>>n;
    int max = 0, min = 0x7fffffff;
    for(int i=0;i<n;++i)
    {
        cin>>in[0][i];
        if(in[0][i]>max) max = in[0][i];
        if(in[0][i]<min) min = in[0][i];
    }
    for(int i=0;i<n;++i)
    {
        cin>>in[1][i];
        if(in[1][i]>max) max = in[1][i];
        if(in[1][i]<min) min = in[1][i];
    }

    longs l = 0;
    longs r = max;
    while(l<=r)
    {
        const longs mid = (l+r)>>1;
        if(check(mid)) r = mid-1;
        else l = mid+1;
    }
    cerr<<"check(9589) = "<<check(9589)<<endl;
    cout<<l<<endl;

    return 0;
}

依然是一个不会写代码的玩家因为犯了低级错误而连续WA的结果……

附录

虽然说是一个典型的二分的题目，但是这个模型可以利用的地方还是比较多的：感觉像是降低难度而牵强附会了一些条件。所以还是有别的路子可以走——比如说标程里这位老哥写的sweep法。它非常符合我们的直观感受，且可以解出正确答案，在这里码一下好了：

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
//this solution considers one element after another on the rack
//     A. consider the first two weights next to each other:
//              1. they are equal -> just delete them, nothing to do
//              2. they are different, so I know I have to lift the lighter one, rember the weight of the lighter one and delete it
//     go to A
//
//  Running time: O(n)


#include <bits/stdc++.h>

using namespace std;
typedef vector<int> vi;

int sweep_rack(const vi &rack){
    int res=0;
    int cand=0;
    for(const int &e:rack){ 
        if(e==cand)//found second!
            cand=0;
        else if(e<cand)//I have to be strong enough to lift e (but who knows, maybe also cand)
            res=max(res, e);
        else{// if(e>cand), There is no way out, I have to lift the candidate, but it is not yet clear with e-> make it candidate
            res=max(res, cand);
            cand=e;
        }
    }
    return max(res, cand);
}

vi read_rack(int n){
  vi res(n);
  for (auto &e:res)
    cin >> e;
  return res;
}

int main(){
    
    int n;
    cin >> n;
    
    cout << std::max(sweep_rack(read_rack(n)), sweep_rack(read_rack(n))) <<"\n";
}


相当于扫行的时候做这样的事情：如果已经放在一起了，就直接删除；否则，就挪比较轻的那个（反正没有损失，之后要挪重的话更新答案便是），把另一个比较轻的也给删喽。这样子跑一边下来就能得到题目要的答案。每一步删除的正确性都能保证，稍微想想就知道了。

I – Iron and Coal

一个图论题，可以用搜索来解决。但是其实是一个 Steiner Tree ~~命运石之树（大嘘）~~的问题，有深挖的价值。

按照惯例，先问是不是再问为什么，所以先科普一下：

Steiner Tree

斯坦纳树问题是组合优化学科中的一个问题。将指定点集合中的所有点连通，且边权总和最小的生成树称为最小斯坦纳树（Minimal Steiner Tree）。最小生成树是它的一种特殊情况，而斯坦纳树则是最小斯坦纳树的另有一种情况：只保证指定的点集合联通，但是不保证最小距离。

此外，一般来说，求一个最小斯坦纳树是一个 NP-complete 问题。

此外关于这个有篇博文写的不错，大家可以去看看： https://www.cnblogs.com/ECJTUACM-873284962/p/7643445.html

题目大意

给你一张图，有的点有矿，有的点有煤，你全都要；如果要拥有这个点的资源，你必须要占点才行；从一个点只能到达相邻的点，你最开始只有一号点；题目确保不存在任何一个节点同时拥有两个资源；问你如果能两个都要，最少所需要占的点数；如果不能两个都要就输出"impossible"。

也就是说要求出占领两种资源的最优方法。

分析

最开始做的时候我的队友也没想那么多。首先不能两个都要的情况很简单，就是无路可走。这个判断一下就可以了；两个都要的情况大概分成两种：

  • 一种是一路到头，不仅找到了煤还找到了矿，应有尽有；
  • 另一种是走到某个点然后兵分两路，最后也是两手捧花；

判定最小路径你之前需要先知道怎么求出路径：根据或不根据上面的分析，我们要想判定一个路径（也就这样的树），需要知道三个值：从家到这个点的距离、从这个点到最近的煤的距离、这个点到最近的矿的距离。然而这些距离都是可以通过搜索求出来的，每次搜索复杂度可控制在O(n)，然后遍历所有可能的“三方会谈点”，就可以找到这个最小值了。

不用担心上面的一步到位的情况，它就相当于节点在资源点，然后某条边的长度为0.

然后就是我没有深挖的题解的做法。题解提供了两种做法，一种是类似于我采用的做法，一种是Steiner树归约。先翻一下官方的题解：

解法一： Steiner树归约

  1. 将地图上的每个单元都抽象地看作一个节点
  2. 为每一个可到达的邻居点增加一条权重为0的有向边
  3. 将所有的每种资源都向该资源的超级节点连一条权重为0的边
  4. 以原点作为起点，对每一个超级节点求一个最小Steinner树

458HPW6_1_5NF_ZJ84KS8O8.png

↑这是大概的示意图↑

除了第二条没怎么看懂…… 写了代码在更新这里好了

解法二： 多项式算法

虽然一般来说这是个NPC问题，但是在这种三个节点的特殊情况下，可以设计出多项式的算法来求这个最小Steinner树。我们假设已经建立了解法一所说的超级节点，具体步骤如下：

  1. 使用BFS找出原点到所有其他节点的距离
  2. 使用BFS在反图上求出每种资源的超级节点到所有点的距离
  3. 找到到原点和每种资源的超级节点的距离和最短的点

整个算法是一个O(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
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>

#define norm 0
#define iron 1
#define coal 2

using namespace std;
typedef long long longs;
typedef long double longd;
typedef unsigned long long ulong;

struct edge
{
    int to,next;
};

const int N = 2e5+5;
const int INF = 0x1f1f1f1f;     // 因为会出现3*INF，所以不能是0x3f3f3f3f
const char cannot[] = "impossible";

int n,m,k;
int o[N],c[N];
int a,b;
int dis[3][N];  // dis[!norm]代表了从某点能到达的最近的矿源的距离

int head[N];
edge e[(N<<1)+(N<<3)];
int tot = -1;
int tail[N];
edge re[(N<<1)+(N<<3)];

inline void init()
{
    tot = -1;
    memset(head,-1,sizeof(int)*(n+1));
    memset(tail,-1,sizeof(int)*(n+1));
    memset(dis[0],0x1f,sizeof(int)*(n+1));
    memset(dis[1],0x1f,sizeof(int)*(n+1));
    memset(dis[2],0x1f,sizeof(int)*(n+1));
}

inline void addedge(int u, int v)
{
    ++tot;
    e[tot] = {v,head[u]};
    head[u] = tot;
    re[tot] = {u,tail[v]};
    tail[v] = tot;
}

void BFS(int typ)
{
    queue<int> q;
    if(typ)
    {
        if(typ==iron)
            for(int i=1;i<=m;++i)
                q.push(o[i]), dis[iron][o[i]] = 0;
        else for(int i=1;i<=k;++i)
                q.push(c[i]), dis[coal][c[i]] = 0;
        while(!q.empty())
        {
            int top = q.front();
            q.pop();
            int c = tail[top];
            while(~c)
            {
                if(dis[typ][re[c].to] > dis[typ][top]+1)
                {
                    dis[typ][re[c].to] = dis[typ][top]+1;
                    q.push(re[c].to);       // 有可能更新距离时再更新
                }
                c = re[c].next;
            }
        }
    }
    else
    {
        q.push(1);
        dis[norm][1] = 0;
        while(!q.empty())
        {
            int top = q.front();
            q.pop();
            int c = head[top];
            while(~c)
            {
                if(dis[norm][e[c].to] > dis[norm][top]+1)
                {
                    dis[norm][e[c].to] = dis[norm][top]+1;
                    q.push(e[c].to);
                }
                c = e[c].next;
            }
        }
    }
}

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

//    freopen(R"(D:\shiroha\Downloads\nwerc2016testdata.tar\nwerc2016testdata\iron_and_coal\022_one_ore_of_many.in)","r",stdin);

    cin>>n>>m>>k;
    init();
    dis[norm][1] = 0;
    for(int i=1;i<=m;++i)
        cin>>o[i];
    for(int i=1;i<=k;++i)
        cin>>c[i];
    for(int i=1;i<=n;++i)
    {
        cin>>a;
        while(a--)
            cin>>b, addedge(i,b);
    }

    BFS(norm);
    BFS(iron);
    BFS(coal);

    int ans = INF;
    for(int i=1;i<=n;++i)
        ans = min(ans,dis[norm][i]+dis[iron][i]+dis[coal][i]);
    if(ans-INF) cout<<ans<<endl;
    else cout<<cannot<<endl;

    return 0;
}

特别需要注意的地方也就是我代码里注释提到的地方：因为最终我们会把三个值加起来，INF就算开了0x3f3f3f3f，加起来也是会暴毙的。所以应该采用一个更小的INF。我的代码种使用0x1f1f1f1f就可以通过了。啊理论上你开long long或者是开unsigned int都是可以的。

A – Arranging Hat

血麻烦、代码极其难写的一个题目。虽然很快的有了思路但是代码不知道写了多久……

题目大意

会输入一列n数字，每个数字有m位，且包含前缀0；你可以花费1并且改动任何一个数字的任何一位的数字；问最少需要改动多少次才能将原数列改成一个升序的数列，并且输出任何一个结果；

也就是说给一写字符串型的数字，输出一个符合字典序的新序列，它花费了最少的费用。

分析

这题有两种思路。一种是显而易见但是难写的二维DP，另一种是不那么显而易见但是同样难写的递归。两种做法官方的题解里都有提到。

有一个需要注意到的事情：因为n的上限是不超过100的。最坏情况下我们只需要把整个序列的数字的前两位的数字改成递增的，就可以保证整个数列是递增的。也就是说改动次数的上限是2n。如果只是输出一个数值的话似乎只需要看一下前几位就可以了，但是因为还要输出任何一种方案，所以代码瞬间变得难写了起来。（不过似乎本来也就不是多少好写）

在开始前我先翻译一下官方的题解：

解法一： 递归

  1. 对于所有数量X，将前X个数字将第一个数字修改位0
  2. 现在，原问题被拆解为两个规模更小的子问题
  • 对于前X个数字，处理他们除了第一位的部分
  • 对于接下来的数字，修改第一位成为 ≥0 的数字
  1. 查找序列的每一个子区间，每一个起始索引和数字
  2. 利用记忆化搜索，可以控制时间复杂度在 O(N³·M)

不要使用缓慢的Python递归，会死的！

解法一是比较的直观的一种方法。维护这个序列字典序可以简单的划分为这几部：

  • 将前X个数的第一位改成0；并且保证前X个数除了第一位的部分是有序的
  • 将剩下的数字的第一位改成大于0的某个数，并且保证它们是有序的

尾递归是当区间、数字、数位无效或者必然有序（比如只有一个）时返回。但是因为我们没有什么好的办法方便的确定这个X的具体的值，所以就需要尝试所有的X。当更优的时候更新分页标签（split数组存储的就是对于每一个子问题的最优划分位置X），就可以在找到最小费用的桶式得到一种具体的方案。

解法二： 动态规划

  1. 首先我们把一个数字字符串看成一个整体
  2. 令dp[i,j]是我们对前i个数字修改j次可以得到的最小的第i数字
  3. 对于每一种状态，尝试修改第i+1个数字
  4. 从现有的状态贪心地在O(M)的时间内得到最小的数字
  5. 如果转移得到的数字比原状态大，该次转移有效
  6. 这样的状态复杂度是O(N²·M)，转移的复杂度是O(M²)
  7. 但是可以推导出答案的复杂度不会大于O(N·log₁₀N)
  8. 所以最终实际复杂度是：状态O(N²·log₁₀N)，转移O(N·log₁₀N·M)

网上的题解多半也是这样做的，这也确实更加符合一般的思维。只是代码会比较的难写。在之前已经说到了改动次数是由上限的，所以可以用在这里。而且因为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
#include <iostream>
#include <cstdio>
#include <cstring>

#define toChar(x) ('0' + x)
#define cur [st][ed][pos][x]   // 当前函数处理的位置

using namespace std;
typedef long long longs;
typedef long double longd;
typedef unsigned long long ulong;

const int N = 45;
const int M = 405;
const int INF = 0x3f3f3f3f;

int n,m;
char s[N][M];
int best[N][N][M][10];          // 最优修改次数，初值INF
int split[N][N][M][10];         // 修改标签，初值是0

int recurse(int st, int ed, int pos, int x)     // 将第[st,ed)个数字的第pos位改为x后，生成有效答案的最少步数
{
    if (pos >= m || st == ed) return 0;         // 参数无效：无贡献
    if (x >= 10) return INF;                    // 不可能的情况：返回INF
    int & that = best cur;
    if (that < INF) return that;                // 记忆化搜索

    int cost = 0;                               
    for (int k = st; k <= ed; ++k)              // 尝试修改区间内所有分界点为 x
    {
        int now = cost                          // 当前的费用 = 修改当前位的费用 + 维护两个区间的有效性的费用
                  + recurse(st, k, pos+1, 0)    
                  + recurse(k, ed, pos, x+1);   
        if (now < that)                         // 更新最小费用和分界标签
        {
            split cur = k;          
            that = now;
        }
        if (k < ed)                             
            cost += (s[k][pos] != toChar(x));   // 这次的修改在区间内且是有效更改，累加步数
    }
    return that;
}

void remake(int st, int ed, int pos, int x)     // 利用split还原最优方案，以修改原数组     
{
    if (x >= 10 || pos >= m || st == ed)        // 无效参数
        return;
    int & val = split cur;

    for (int i = st; i < val; ++ i)             
        s[i][pos] = toChar(x);                  // 根据标签的指示修改
    remake(st, val, pos+1, 0);                  
    remake(val, ed, pos, x+1);
}

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

    cin>>n>>m;
    for (int i=0;i<n;++i)
        cin>>s[i];
    memset(best,0x3f,sizeof(best));

    cerr<<"COST: "<<recurse(0,n,0,0)<<endl;     // cerr输出最优步数
    remake(0,n,0,0);

    for (int i=0;i<n;++i)
        cout<<s[i]<<endl;
    return 0;
}

首先，一个答案是可以通过一个方案来导出来的。所以先寻找更优的方案存储起来，这样最终利用存储的方案就可以得到最优解。寻找最优解需要尝试，每次尝试修改时更新最优方案的存储。代码中利用了尝试函数recurse完成了尝试和记录的工作。

对于尝试函数，整列数字分为三个部分：前X个数字的第一位，前X个数字的剩余部分（子问题1），后面的数字（子问题2）。每次都尝试修改第一部分，并统计这些修改中的有效修改（显然，0→0并不是有效的修改），最后递归统计剩余两部分的消费，就可以找到最小的修改次数和修改方案。使用数组split存储在这个参数的状态下最优的X。最后利用它还原修改的结果就可以了。

因为这种递归是可能出现多种相同的状态的。而因为这个函数的结果只会和状态相关，所以可以使用记忆化搜索来减少这部分不必要的开支。

然后是二维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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <bits/stdc++.h>

using namespace std;
const int N = 45, M = 405;
const int N2 = N<<1;

int n, m;
char in[N][M];
char tmp[M];            // findNext的返回值
char dp[N][N2][M];
bool flag[N][N2];       // 转移是否有效
int pre[N][N2];         // 前导状态表
char* ans[N];

/**
 * 当前dp值now，下一个原数字Next，长度为m，k次修改机会
 * 能否构造出有效转移；能则将转移结果存入tmp
 */
bool findNext(char *now, char *Next, int m, int k)
{
    int num = k, pos;
    strcpy(tmp, Next);
    if(!k)                              // 无修改次数
        return strcmp(tmp, now) >= 0;   // 下一个数有效则找到
    for(pos = 0; pos < m && num > 0; ++pos)
        if(tmp[pos] != now[pos])
        {
            tmp[pos] = now[pos];        // 贪心修改高位
            --num;
        }
    if(strcmp(tmp, now) >= 0)   
        return true;
    // 若未返回，说明未修改部分[pos,m]不够大
    for(--pos; pos >= 0 && now[pos] == '9';)
        --pos;          // 找到可以修改的高位部分中最低的一位
    if(pos < 0)         // 如果不可能将已修改的位改的更大，就不可能
        return false;
    num = k;
    strcpy(tmp, Next);  // 重新开始

    for(int i = 0; i < pos; ++i)
    {
        if(tmp[i] != now[i])
        {
            tmp[i] = now[i];
            --num;
        }
    }

    if(tmp[pos] != now[pos] + 1)  // 尝试可修改的最低位改为+1
    {
        tmp[pos] = now[pos] + 1;
        --num;
    }

    for(++pos; pos < m && num > 0; ++pos)
    {
        if(tmp[pos] != '0')       // 用尽所有的修改次数尽可能减小答案
        {
            tmp[pos] = '0';
            --num;
        }
    }
    return true;                  // 这样的修改一定是有效的
}

inline void init()
{
    memset(flag, false, sizeof(flag));
    for(int i = 0; i < m; ++i)
        dp[0][0][i] = '0';
    dp[0][0][m] = '\0';
    flag[0][0] = true;
}

int main()
{
    scanf("%d%d%*c", &n, &m);
    const int n2 = n << 1;

    for(int i = 1; i <= n; ++i)
        scanf("%s", in[i]);
    init();

    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n2; ++j)
    {
        if(!flag[i][j]) continue;                     // 跳过无效状态
        for(int k = 0; k <= m && j + k < n2; ++k)     // 尝试所有可能的转移
        {
            if(findNext(dp[i][j], in[i + 1], m, k)
                && ( !flag[i + 1][j + k]
                || strcmp(tmp, dp[i + 1][j + k]) < 0  // 找到有效的转移
            ))
            {
                flag[i + 1][j + k] = true;
                strcpy(dp[i+1][j+k], tmp);
                pre[i+1][j+k] = j;          // 做标记，存储字符串，记录前导
            }
        }
    }

    int ptr;
    for(ptr = 0; ptr < n2; ++ptr)
        if(flag[n][ptr]) break;             // 找到次数最少的有效转移
    cerr<<"COST: "<<ptr<<endl;
    for(int i = n; i > 0; ptr = pre[i][ptr], --i)
        ans[i] = dp[i][ptr];             
    for(int i = 1; i <= n; ++i)
        puts(ans[i]);
    return 0;
}

这里主要来说一下最麻烦的构造有效转移，也就是findNext函数（也是我不知道写暴毙多少次的一个地方）。这里我们使用贪心的策略：尽可能的修改高位，并且尽可能的让高位小，同时也要保证字典序。这样，对于每一位数字只有两种可能：

  • 因为从高位向低位修改，每次修改都按照上面的规则，所以可以认为前半部分是一致的。
  • 这一位的后面部分足够给力，比前一个数字的同位部分大；那么这一位只需和前一个数字的这一位一样就行；
  • 否则，这一位必须领头，修改成比前一个数字同位的数字大一；且这一定是最后一次修改。

简单的说，就是要不改成和前一个数字同位值相等，要不改成大1；因为尽可能构造小的满足字典序的数字，所以大1的这次修改一定只会出现在最后一次。……不仅说起来绕口，写起来也很麻烦。我采用的方法是这样的：

  • 首先贪心的用完所有次数，从高位向低位修改：一律改成和同位值相等
  • 如果这样已经满足了字典序，那必然是最小的有效转移
  • 否则，向高位遍历，寻找可以再大1的位置；它可以不是刚才已经修改过的位置，因为它一定比最后一次贪心修改的位置靠前
  • 重新修改，将找到的这一位之前所有数字改成相等，这一位改成大1. 此时字典序可以保证
  • 若还有未用尽的次数，可以贪心地修改这一位后的高位来尽可能降低返回值

这样就完成了基于有效状态的有效转移的构造。再将构造结果传给DP用来进行状态转移即可。

J – Jupiter Orbiter

这是一个好题目，但是不难做。标准解法是最大流问题，但是可以简单的贪心出答案。不过俗话说得好，最大流不过是套在网络流模型上的贪心罢了，从这题来看就非常的正确。

题目大意

一个探测器有s个传感器和q个FIFO的存储卡。这些存储卡有一定的容量；每个传感器都会将它收集到的数据存储到属于该传感器的唯一的存储卡中；现在这台探测仪要进行n轮探测，每次探测过程分为收集阶段和传输阶段；收集阶段每个传感器都会收集到ai的数据存储到它的存储卡中；传输阶段可以将总量不超过d的信息从存储卡发送回地球。告诉你上面的这些所有的量，问你会不会有数据因为装不进存储卡而丢失。

换句话说，就是有Q和容量为C的FIFO队列，有n个从这些队列中删除数据的机会，且每次最多的删除总量为d。并且每次删除前队列都会获得a的数据，但是存不下的部分会丢失。请问能不能做到在最后一次删除数据之后，所有的队列为空。

分析

我的队友并没有考虑的很复杂。虽然说是先接受数据在传输数据，但是这题并不一定这样做：我们可以先接受数据，静等下一轮的情况，然后选择性的传输容量最紧缺的地方的数据。倒是也可以顺风顺水的做出来。但是还是先说比较常规的网络流做法：

说之前依然先看题解：

解法一： 网络流最大流

  1. 将本题根据网络流模型建模
  2. 确认最大流是否和产生的数据总量相等

M7DIIU_S_T_A_@GL0OPWR@4.png

↑建模大概是这样的↑

题解说的非常简单，然后给了一个图。我自己又根据第一组测试样例画了一个：

WD2Z4_Y_FKF~3_P.png

简单的总结一下我自己的建模方法，和题解画图略有不同但是本质是一样的；大概就是这样：

  • 对于每一轮的探测，将每个传感器和队列都建立一个节点；对于每次传输数据也建立一个节点
  • 从原点出发，向每轮的所有传感器连边，容量是它们这一轮获得的数据数量
  • 对于每一轮的每个传感器，向它对应的本轮的队列连边，容量是队列的流量
  • 从本轮的队列节点出发，向本轮的传输节点连边，容量是无限大；向可能存在的下一轮的对应探测器连边，容量是无限大
  • 对于所有的传输数据节点，则可以向汇点连边，容量是本轮可以发送数据量的最大值

完成了这样的建模，就可以套板子来一遍最大流，轻松而愉快的解出这个题目了。

此外，题解也提供了贪心的做法：

解法二： 模拟贪心

  1. 模拟接受数据的全过程
  2. 只要队列满了，就记录多出去的部分：这是必须要在上一轮处理掉的数据
  3. 再模拟一次数据接受的全过程
  4. 使用第一轮得到的经验进行数据处理：处理不了时就失败了
  5. 因为要尽可能避免失败，所以要尽早的回避记录的限制
  6. 可以在排序后的记录表的指导下贪婪的传输数据

感觉有点怪怪的…… 不知道是我翻译的问题还是思维上的不同。但是总体的指导思想就是在知道下一轮的情况下科学安排本轮数据传输的侧重点。这其实并不需要扫两遍模拟，一次模拟就可以实现目的。我简单介绍下我的队友实现的思路：

  • 对于每一轮的数据：如果可以完全传输，那么就今日事今日毕，清空队列
  • 对于任何一组数据：如果当局获得的数据总量比容量大，那必然是会丢失数据
  • 如果本轮数据不能完全传输，那就先不处理；可传输容量带到下一轮
  • 模拟接受下一轮的数据时，如果有的队列溢出了，那这部分就是上一轮必须要处理的部分
  • 如果最后一轮结束时队列仍然不能清零，那么失败；否则成功

应该还是非常清晰的，具体可以看我的代码。

我的代码

因为我想要偷懒，所以就先把比赛时候的代码搬上来了。这个代码并没有使用最大流：

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

using namespace std;
typedef long long longs;
typedef long double longd;
typedef unsigned long long ulong;

const char can[] = "possible";
const char cannot[] = "impossible";
const int N = 35;
const int M = 105;

int n,q,s;
int uq[M], c[N];
int d, a;
int tmp[N];
bool state = true;

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

    longs todo = 0;
    longs cando = 0;

    cin>>n>>q>>s;
    for(int i=1;i<=s;++i) cin>>uq[i];
    for(int i=1;i<=q;++i) cin>>c[i];
    for(int i=1;i<=n;++i)
    {
        cin>>d;                 // 本回合的资金
        for(int j=1;j<=s;++j) 
        {
            cin>>a;
            if(a > c[uq[j]]) state = false; // 不可能装下：直接暴毙
            tmp[uq[j]] += a;                
            if(tmp[uq[j]] > c[uq[j]])       // 用上回合的资金处理危险部分
            {
                cando -= tmp[uq[j]] - c[uq[j]];
                if(cando < 0) state = false;
                tmp[uq[j]] = c[uq[j]];
            }
            if(!state) break;
        }
        if(!state) break;
        cando += d;             // 使用本回合资金
        todo = 0;
        for(int i=1;i<=q;++i)
            todo += tmp[i];     
        if(todo <= cando)       // 可以全部处理完：清零
        {
            cando = todo = 0;
            memset(tmp,0,sizeof(int)*(q+1));
        }                       // 否则看下回合情况
    }
    if(todo > cando) state = false;

    if(state) cout<<can<<endl;
    else cout<<cannot<<endl;
    return 0;
}

思路就是上面分析里提到的那样，简单解决。

K – Kiwi Trees

计算几何的题目。因为没有板子（理由！）和忘掉了很多非常非常基础的几何知识最后没有做出来。但是其实是一个比较好写的题目，不会写属实有些吃亏。

题目大意

隔壁老王有一个形状是简单多边形的院子。这个多边形有一些特点：每条边的长度大于30m；任何的一个角的大小在18°~144°之间，但是不保证多边形是凸多边形；现在老王想在这个院子里种两棵一模一样的果树，于是它买来了两棵树。老板告诉他这两棵树长大了之后会占用以种树点为圆心的，半径为3.999m的圆的区域；而且两棵树如果树冠长在一起是NG的。种的时候邻居也来抗议，称如果老王的树冠长出了他自家的院子，他们就向居委会举报。问老王应该把这两棵树中在哪里才能避免树的死亡以及居委会的整改？

换句话说，就是告诉你一个有点特殊的多边形，能不能在这个多边形内摆两个不相交的圆。能的话就算出两个圆心坐标。

特别提示：输入的多边形的顶点对于多边形而言是顺时针的。

分析

因为这个多边形的边有保底长度，所以不用想太多：就算是一个极端的情况下，一般来说一个凸角塞一个圆就没什么问题了。塞完之后再遍历所有可以塞的地方，找到一对满足要求的输出就可以了。

但是实现的时候要更加的注意细节。因为即使你将这个圆塞进了某个凸角里，它仍然有可能和一切不是这个角的边相交。所以为了保险起见还要扫一遍所有的边判断确保没有这种情况的发生。

然后就是具体实现了。有了几何板子和几何知识就是顺理成章的事情。但是为了照顾一下没有这些东西的看客比如我，这里简单的进行一下知识的科普。如果之后有时间的话会整理专题的：

二维向量叉乘的作用：

  • 求两个向量的夹角，因为可以由定义式求出sinθ
  • 求两个向量为两条边形成的平行四边形的面积
  • 在顺/逆时针下判断多边形角的凹凸性
    比如对于顺时针多边形，叉乘为正的时候，这个角是一个凹角

高等数学白学力（大悲）

然后题目给了一个官方题解。大体类似但是也有不同，姑且给翻译了一波：

  1. 任何大于四个顶点的简单多边形至少会有两个凸角
  2. 由题意可知，多边形的角度是18~144度，边长至少30m
  3. 这样的一个凸角割成三角形，一定能容纳一个半径不超过4.008m的圆
  4. 特判：当输入是一个三角形的时候，可以直接判定不可以

怎么说呢，这样做的话题目的代码大概会变的更加地好写。数学论证凸角一定可以塞下，然后只需要随便找两个凸角算一下圆心就可以了——这个也可以通过角平分线算出来。但是关于三角形的特判我是不太苟同：因为如果三角形的边足够大，它还是可以塞下符合标准的两个圆的。所以我觉得这一步还是应该进行尝试。

我的代码

因为没有板子，所以补题的时候基本计算的板子抄了校队另一个同学的。

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

#define THIS (*this)

using namespace std;
typedef long long longs;
typedef long double longd;
typedef unsigned long long ulong;

class point
{
public:
    longd x, y;

    point operator +(const point& rhs) const;
    point operator -(const point& rhs) const;
    longd operator *(const point& rhs) const;   // 点乘
    point operator *(longd rhs) const;          // 数乘
    point operator *(double rhs) const;
    point& operator +=(const point& rhs);
    point& operator -=(const point& rhs);
    point& operator *=(longd rhs);
    point& operator *=(double rhs);

    longd cross(const point& rhs) const;        // 叉乘模：平行四边形面积
    longd length() const;                       // 向量的模
    point normal() const;                       // 单位化向量
    longd distance(const point& b) const;       // 到某点的距离
    longd distance(const point& ls,const point& rs) const;  // 到直线ls-rs的距离
    void println();                             // 一行输出坐标
};

const int R = 4000;
const double r = 4000;
const double eps = 1e-3;
const double r2 = 2*r - eps;
const int N = 2060;
int n;
point p[N];
vector<point> v;

point calculate(point a,point b)
{
    a = a.normal();
    b = b.normal();
    longd angle = acos(a*b) / 2;    // 计算夹角的1/2
    point k = (a+b).normal();       // 角平分线的单位向量
    return k * (R / sin(angle));    // 返回满足垂直距离≥R的相对坐标
}

bool intersect(point& x,point& ls,point& rs)    // 相交（距离不足）返回false
{
    if ((ls-x)*(rs-ls) > 0) return x.distance(ls) >= r-eps; // x在ls的远端
    if ((rs-x)*(ls-rs) > 0) return x.distance(rs) >= r-eps;
    return x.distance(ls,rs) >= r-eps;          // x在直线ls-rs的正上方
}

bool test(point& x)     // 遍历检查点到所有边的距离
{
    for (int i = 1; i <= n; ++ i)
        if (!intersect(x,p[i-1],p[i])) return false;
    return true;
}

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

    cin>>n;
    for (int i = 1; i <= n; ++ i)
        cin >> p[i].x >> p[i].y;
    p[0] = p[n]; p[n+1] = p[1];

    for (int i = 1; i <= n; ++ i)
    {
        if ((p[i]-p[i-1]).cross(p[i+1]-p[i]) > 0)   // 跳过多边形的凹角
            continue;
        auto tmp = p[i] + calculate(p[i-1]-p[i],p[i+1]-p[i]);   // 得到绝对位置
        if (test(tmp)) v.push_back(tmp);
    }

    bool found = false;
    for (auto& p1 : v) for (auto& p2 : v)
        if (p1.distance(p2) >= r2)          // 判断两个点之间的距离
        {
            cout<<fixed<<setprecision(10);
            p1.println();
            p2.println();
            found = true; goto END;
        }

    END:
    if(!found) cout<<"impossible"<<endl;
    return 0;
}

point point::operator +(const point& rhs) const {return (point){x + rhs.x, y + rhs.y};}
point point::operator -(const point& rhs) const {return (point){x - rhs.x, y - rhs.y};}
longd point::operator *(const point& rhs) const {return x * rhs.x + y * rhs.y;}
point point::operator *(const longd rhs) const {return (point){rhs * x, rhs * y};}
point point::operator *(const double rhs) const {return (point){rhs * x, rhs * y};}
point& point::operator +=(const point& rhs) {x += rhs.x; y += rhs.y; return THIS;}
point& point::operator -=(const point& rhs) {x -= rhs.x; y -= rhs.y; return THIS;}
point& point::operator *=(longd rhs) {x *= rhs; y *= rhs; return THIS;}
point& point::operator *=(double rhs) {x *= rhs; y *= rhs; return THIS;}

longd point::cross(const point& rhs) const {return rhs.y * x - rhs.x * y;}

longd point::length() const {return sqrtl(THIS*THIS);}

point point::normal() const
{
    longd l = this->length();
    return (point){x/l,y/l};
}

longd point::distance(const point& b) const {return (THIS-b).length();}

longd point::distance(const point& ls,const point& rs) const
{
    return fabsl((ls-THIS).cross(rs-THIS))/ls.distance(rs);
}

void point::println() {cout << x << ' ' << y << endl;}

想清楚了，套板子出答案也是相对简单的事情；不过就是要想清楚才行。实际赛场上A了这个题目的两支队伍都吃了那么两三发罚时才A的，这个和事后套板子应该还是有很大的差距吧。有一个可能要注意的地方就是：在把圆塞进某个具体的角的时候也要去判断它和其他边的情况——而判断这个实际上还要分情况讨论。细节就是有点多啊==

B – British Menu

一个比较典型的SCC缩点+DAGdp的题目。如果有板子并且打的比较熟练的话应该能很快的做出来吧，但是可惜我两者都不是。

题目大意

你去英国旅行，想吃英国菜，但是酒店只给了你一张自助餐餐券；所以你打算今晚往死里吃，尽可能多吃几种菜。但是有的菜连着吃可能会出问题比如温两碗酒，要一份头孢，但是如果把它们分开吃就没毛病。旅游指南告诉了你你可以在吃完一种菜之后吃哪些菜，但是这样的话就难免重复：你发现如果有一种菜可以吃两次，那么它们之间一定不会有超过四种的不同的菜。但是你并不想吃两次一样的菜，所以今晚你应该怎么吃，才能尽可能多的吃到不同的菜？

换句话说，就是给你一个有向图，途中的每个环最多包含五个不同的节点。然后你要计算出图中不经过相同节点的最长路。

特别提示：这道题的时空限制是10000ms，512MB。

分析

有向有环图，它有环；求最长路，一般要求无环图。怎么样才能做这个题目？有环缩环成点不就有无环图了嘛。怎么缩点呢？那必然是Tarjan法。因为还要求最长路，所以要求出每个SCC内的路的长度——反正最多五个点，怎么玩都行。至于缩成的DAG可以怎么求最长路？拓扑排序啊！……才不是咧，SCC缩成的点可不能和一般的点等量齐观，所以需要DAGdp。那这个题目大概的思路就有了。

然后就是抄板子→手抖抄错了→WA了然后肉眼扫描→……的死循环（悲）

官方依然给了题解，所以还是翻译一下：

  1. 这个问题一般来说是 NP-complete 的。但是这个问题可通过在DAG中使用DP，在O(n+m)的时间内求解
  2. 由题意可得，图中的每个SCC最多只有五个节点
  3. 所以可以暴力地求出每个SCC内任何两个顶点之间的最长路。O(n!)已经够快了
  4. 将所有的SCC缩成一个点
  5. 现在图变成DAG了，可以DP；需要读取刚才对每个SCC计算的最长路。

大概写代码实现的思路就是这样。因为给了10s，这个算法基本上只要敲对了都能过。

我的代码

真正的模板题，事后重写也差不多要了我的老命，是时候准备一份优秀的板子了

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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>

#define same(u,v) (sccId[u]==sccId[v])
#define cleanDis() memset(dis,0,sizeof dis)
#define V e[c].to

using namespace std;
typedef vector<int> arrays;
struct edge {int to,next;};

const int N = 1e5 + 5;
const int M = 1e6 + 5;
int n,m;

namespace FrontStar
{
    int head[N];
    edge e[M];
    int tot = -1;
}

namespace Tarjan
{
    int dfn[N], low[N];
    int nextDfn = 1;
    bool instack[N];
    stack<int> s;
}

namespace SCCcomponent
{
    int cnt;
    int sccId[N];       // 顶点属于的SCC分量
    int id[N];          // 顶点在分量内的编号
    arrays group[N];    // SCC分量包含的点
    int dis[6][6];
    bool visit[N];
    arrays inEdge[N];   // 分量内的边
}

namespace DAGgraph
{
    int in[N];
    queue<int> q;
    int tmp[N], dp[N];
}

inline void init()
{
    using namespace Tarjan;
    using namespace FrontStar;
    using namespace SCCcomponent;
    using namespace DAGgraph;
    memset(head, -1, sizeof(int) * (n + 1));
    memset(dfn,0,sizeof(int)*(n+1));
    memset(low,0,sizeof(int)*(n+1));
    memset(sccId, 0, sizeof(int) * (n + 1));
    memset(id,0,sizeof(int)*(n+1));
    memset(tmp,0,sizeof(int)*(n+1));
    memset(dp,0,sizeof(int)*(n+1));
    memset(in, 0, sizeof(int) * (n + 1));
    memset(instack,0,sizeof(bool)*(n+1));
    memset(visit,0,sizeof(bool)*(n+1));
    tot = -1; cnt = 0; nextDfn = 1;
}

inline void addedge(int u, int v)
{
    using namespace FrontStar;
    e[++tot] = {v,head[u]};
    head[u] = tot;
}

void tarjan(int U)
{
    using namespace Tarjan;
    using namespace SCCcomponent;
    using namespace FrontStar;
    
    dfn[U] = low[U] = nextDfn++;
    s.push(U);
    instack[U] = true;

    int c = head[U];
    while (~c)
    {
        if (!dfn[V])
        {
            tarjan(V);
            low[U] = min(low[U], low[V]);
        }
        else if (instack[V])
            low[U] = min(low[U], low[V]);
        c = e[c].next;
    }

    if (dfn[U] == low[U])
    {
        int cur, tagId = 0;
        ++cnt;
        do
        {
            cur = s.top(); s.pop();
            instack[cur] = false;
            sccId[cur] = cnt;
            group[cnt].push_back(cur);
            id[cur] = ++tagId;
        } while (cur != U);
    }
}

void dfs(int now, int raw, int length)
{
    using namespace SCCcomponent;
    dis[id[raw]][id[now]] = max(dis[id[raw]][id[now]], length);
    visit[now] = true;
    for (auto that : inEdge[now])
        if (!visit[that]) dfs(that, raw, length + 1);
    visit[now] = false;
}

inline void topsort()
{
    using namespace DAGgraph;
    using namespace SCCcomponent;
    using namespace FrontStar;

    for (int i=1; i <= cnt; ++i)
        if (!in[i]) q.push(i);
    while (!q.empty())
    {
        int now = q.front(); q.pop();
        cleanDis();
        for (auto node : group[now])
            dfs(node,node,0);
        for (auto i : group[now])
            for (auto j : group[now])
                tmp[i] = max(tmp[i],dp[j]+dis[id[j]][id[i]]);
        for (auto node : group[now])
            dp[node] = tmp[node];
        for (auto U : group[now])
        {
            int c = head[U];
            while (~c)
            {
                if (!same(U, V))
                {
                    dp[V] = max(dp[V], dp[U] + 1);
                    --in[sccId[V]];
                    if (!in[sccId[V]])
                        q.push(sccId[V]);
                }
                c = e[c].next;
            }
        }
    }
}

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

    cin>>n>>m;
    init();
    int u,v;
    while (m--)
    {
        cin>>u>>v;
        addedge(u,v);
    }

    using namespace Tarjan;
    using namespace SCCcomponent;
    using namespace DAGgraph;
    using namespace FrontStar;

    for (int i=1;i<=n;++i)
        if (!dfn[i]) tarjan(i);
    cerr << "SCC component count: " << cnt << endl;
    for (int i=1;i<=n;++i)
    {
        int c = FrontStar::head[i];
        while (~c)
        {
            if (same(i, e[c].to))
                inEdge[i].push_back(e[c].to);
            else ++in[sccId[e[c].to]];
            c = e[c].next;
        }
    }
    topsort();

    int ans = 0;
    for (int i=1;i<=n;++i)
        ans = max(ans,dp[i]);
    cout<<ans+1<<endl;

    return 0;
}

小　心　全　局　变　量（警觉.jpg）

好像在ACM里，前向星比起开着氧气的vector并没有太大的优势，写起来还容易出错…… 了解，下次还敢==

D – Driving in Optimistan

光是读题都读了很久才大概看明白的一个题目，比赛时没有做出来。

意外地，这个题和G题都没有查到好心CSDN博主的解析。

题目大意

奥普提米斯坦国有很多个港口城镇组成；为了省钱，它们只修了能连接所有港口城镇的必要道路，因此从一处到另一处只有一条路；路上每公里都有一个牌子，包含了当前位置到所有城市的最短距离。这个国家的旅游指南上有一张表，记录了任意两个城市之间的最短距离；问能不能通过这些信息，计算出所有的路牌上的数字的平均值。

也就是说，给定一棵树所有叶子节点之间的距离，求出每1公里道路上都会放置的路标上写着的距离的平均数。

分析

贴一下官方题解的翻译：

  • 直接考虑整个树上的所有标志太难了，只考虑叶节点和交叉点
    1. 把每个城市作为一个孤立的节点
    2. 按照距离排序所有的城市点对
    3. 给这两个节点加一个树根，合并两棵子树
  • 对于以r为树根的每个子树T，在以下两种情况下计算穿过r的最短路的平均长度：
    • 两个端点都在子树T内时，记为 Ar²
    • 仅一个端点在子树T内时，记为 Ar¹
  • 这两个值可以通过r的所有孩子的 A¹ 和它们到r的距离来计算

也就是说是一个树上DP…… 且慢，这种讨论方式，之前是不是做过差不多的题目……

我的代码

还没呢，写完了就给补上（

G – Gotta Nudge ’Em All

宝可梦GO模拟器一道非常恶毒的题目：恶毒就恶毒在它那巨长的题目以及乱七八糟的规则，光是都题目都能让人觉得恶心的一个题目。校队的朋友应该是没有一个人去尝试这个题目的——我们队也不例外；甚至整个vjudge上只有两年前和三年前有两发AC的提交，当年区域赛似乎也没几个队伍A了这题目…… 直说了，我不想做这个题目==

估计是为了防止阿克的，但是比赛的时候还是有一支队伍阿克了（

题目大意

这是一个宝可梦GO模拟器：给你若干条宝可梦的进化链；糖果是游戏中的货币：捉一只宝可梦可得3颗糖果，放一只宝可梦可得1颗糖果，糖果和进化链相关。进化宝可梦花费糖果，且进化高级的宝可梦的花费不低于低级宝可梦的花费；捉一只宝可梦可得100经验，进化一只宝可梦可得500经验；开局有一个道具幸运蛋，在使用它后的1800s内获得的经验翻倍；题目规定只在它生效期间内进化宝可梦；现在给你捕捉宝可梦的时间序列，求可以获得经验的最大值。

也就是说，给你一个你抓到宝可梦的时间表，然后求出可以最大化你获得的XP的翻倍道具的使用时刻。

分析

本体最大的难点：英语阅读

别的就不知道啦，刚读完题，还没分析呢// 题解又臭又长也不想翻译== 完事了会贴在这里的

我的代码

还没呢，写完了就给补上（

后记

一些感想

就比赛而言，如果真的是简单的签到题就快快委托给代码手，早交早仏== 虽然前期开题确实重要，但是真正比赛应该更加的灵活多变一些；虽然最后我们A了8个题（一般是学弟A的，悲），但是前一个小时只签到了一个题目。这是非常的吃亏的==

就写代码而言，主要还是准备板子吧。一个题目有成熟的板子和没有成熟的板子差距还是很大的== 然后就是代码手多辛苦，你不行你就别上（指自己WA了签到题），老老实实叫队友来写。真要是心有不甘课后补题，自己多练练啊（）

就个人而言，写代码能力实在是过于欠缺。下次练习专题也整成私人比赛好了。但是就目前情况来看，三人云练习还是水分很多的，不要被蒙蔽了双眼。

小 心 全 局 变 量

参考资料

http://clatisus.com/NWERC 2016?tdsourcetag=s_pctim_aiomsg

2016 NWERC 回顾
https://shiraha.cn/2020/2016-nwerc/
本文作者
七海
发布于
2020年3月10日
许可协议
CC BY-NC-SA 4.0

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

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

更新于：2020年3月10日

算法

ACM

Codeforces

Gym

评论