洛谷ACM春季多校训练营：第三场

七海

题解

发布于：2020年3月20日

次浏览

因为是版权原因，这里并不能公开的放题目链接和题目的讲评之类的东西。各位看官就将就着看看我说吧==

又是一场接近爆零的比赛呢（笑

打的很丑，补题不及时罪加一等。题目不多，难度不做评价，但是就英语来说题目都很好懂，读起来都不费劲就是自己做不出来。……所以就不多废话，直接讲题目。

首先是出题人自己对于这次题目难度的评价：

然后，我根据出题人当晚讲评的顺序来说这些题目：

B - Bit fixer

给你一个二进制串，宇宙射线每天会取反一个bit，你很辣鸡，每天只能掰反一个bit；给你一个目标串，问你最少多少天能完成任务。数据规模在1e5之内。

引导

官方讲评在说这个题目之前说了一道下面这样的题目。

这题来源于一道CF题目：

有一条船，速度v1；水速每天都会变，船的方向也可以每天调整，但在一天中方向都不变；而且船每天的航行时间相同。给出两点距离，以及每天的水流大小和方向，问最少需要花多少天？

对于这个题：因为船和水的位移都是矢量，如果把船和水的位移加起来等于起点到终点的向量，就表示船可以到达终点。 又因为矢量相加符合交换律，所以可以先计算水的总位移，与起点->终点的向量相减，就可以得到船要走的位移。

因此，这个题目，只要枚举天数，得到船应走的唯一，判断能不能走完就行了。

所以这个题目，仔细想想也可以用这种思想来解决。

分析

二进制串，每次会被动的变一次；你每次可以修改一位。如果把二进制串也看成向量的话，那么在第x天，你最多只能满足目标串和当前串相差的模≤x的情况。因为每天原串都会变化，所以模也在不断变化；又因为相反一位的值，也就是异或，也是满足交换律的；所以也可以像上面那个题目那样。

为什么反复提到交换律呢？我们的做法，相当于把每个时间片的“外力”和“内力”造成的偏移分离之后统一考虑：然而题目原模型是交错的。只有满足了交换律，我们才能随意挪移一个式子中的不同项，整理组合从而简化。

实现的话，直接枚举然后求差的话，1e10就爆炸了。但是实际上，因为这是一个二进制串，每次只需要更新修改的那一位的状态就可以了（也就是出题人说的曼哈顿法），或者也可以二分答案。

二分单调性：显而易见的，因为外力和内力是可以抵消的。当某个x可以达成目标之后，之后只需不断抵消内外力即可。

总而言之，有了交换性，随便怎么整理（移项）都可以哦。

误区

因为题目只让我们求一个具体的值——也就是能不能在指定天数内达成目标，而不是求一个具体的方案。所以完全可以通过挪移整理来简化模型。最开始我的分析是顺推，分不同的情况，使用队列维护修改的优先级。这样做也许是对的，但是我赛场上没有分析出来（逃），这题就这么死了。事实上只要能想到是只求天数的话，完全没有必要这样麻烦自己。

此外，因为这个题目时求一个最小天数的，且显然具有二分单调性——如果能想到一个二分答案，即使是我那样处理来判别，也是有可能做出来的。总而言之，做不出来就是你傻了。

代码

这是使用优化的枚举的代码：

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

#include <iostream>

using namespace std;
typedef long long longs;

const int N = 1e5 + 5;
int len,lim,cnt,pos;
char str[N], ch;
bool dis[N];

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

    cin>>len>>lim;
    cnt = 0;
    for (int i=0;i<len;++i) cin>>str[i];
    for (int i=0;i<len;++i)
    {
        cin>>ch;
        if (str[i] != ch)
        {
            ++ cnt;
            dis[i] = false;
        }
        else dis[i] = true;
    }
    for (int i=1;i<=lim;++i)
    {
        cin>>pos;
        pos = len-1-pos;
        if (dis[pos])
        {
            dis[pos] = false;
            ++ cnt;
        }
        else
        {
            dis[pos] = true;
            -- cnt;
        }
        if (cnt <= i)
        {
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<"icu"<<endl;

    return 0;
}

有一个需要注意的就是，输入中的这个index实际上是从右到左的，所以需要进行处理之后才可以使用。当然也可以输入的时候就从后向前存储。

C - Coprime

给你一个整数序列，再给你一个操作：每次你可以把某个数变成任意的另一个数；问最少经过多少次操作，使得序列中任意相邻两个数互质。数据规模1e5。

分析

首先，互质也就是说 gcd(a, b) =1. 如果a b中有一个数是1，那这就是板上钉钉的了；所以要改，肯定就是改成1.

然后对于具体的数列来说，可以使用贪心处理：假设从左向右处理，如果a b相邻但是不互质，最好肯定还是修改b：因为改a只能保证和b互质，而改b还可以保证和未来的c也一定互质。

代码

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

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long longs;

const int N = 1e5 + 5;
int a[N];

int gcd(int a, int b)
{
    if (b > a) return gcd(b,a);
    else if (!b) return a;
    else return gcd(b, a%b);
}

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

    int n, cnt = 0;
    cin>>n;
    for (int i=0;i<n;++i) cin>>a[i];
    for (int i=1;i<n;++i)
        if (gcd(a[i-1],a[i])-1)
            a[i] = 1, ++ cnt;
    cout<<cnt<<endl;

    return 0;
}

豆知识（模外挂）：其实比起a%b取模，加上判断地使用a-s/b*b来的更快哦。

D - Dodo bird painting

有一根绳子，每次往绳子上滴一滴墨水，墨水会一固定速度扩散；给出滴墨水的时间和位置，问最早什么时候， 绳子完全被墨水覆盖。绳子长度是1e9，墨水数量1e5.

分析

这其实是一个二分套路题。

虽然不是大家都喜欢的经典最大求最小或者最小求最大的问题，但是依然是可以用二分求解：

• 二分单调性：如果某个时间t恰好可以给整条绳子染色，那么小于t的时间一定不能全部染色，且大于t的时间一定也可以给整条绳子染色。
• 问题特性：直接求解（比如DP？），至少需要O(n²)的时间；而确认一个答案可不可以全部染色，只需要O(n)的时间。符合二分答案问题的特点

综上所述，采用二分答案的方法，把最优化问题转化为可行性问题。 这个题目就可以做了，复杂度大约是O(nlogk)，k和墨水的传输速度和绳子长度相关。

具体的说，对于具体的时间，求解这个时间下每滴墨水可以染色的区间，再按顺序合并：如果出现无法合并的情况，就说明不可全部染色。

误区

其实不想话太多笔墨来说自己是怎么错的。但是既然蠢了，就要挂起来婊着。我最开始想着是DP每两滴墨水之间的绳子长度被墨水染色需要的时间，再考虑墨水“跨界点染色”的事情，也就是说DP。这确实是模拟的思路，但是会TLE。并且只要是这种DP，就必须要确认每滴墨水的可能性。可以说就是没什么太大的优化空间，复杂度O(n²)，对于这个题目的1e5的数据规模，那是死的透透的。

其次是实现方面的一些事情：合并区间并不可以贪心！除非经过稳健的排序。否则，位置处在后方的区间仍然可以覆盖前面并未合并的区间，如果贪心退出就判断错误了。

代码

理清思路的情况下还能吃一发WA也是没谁了。只能说不愧是我==

写代码的时候还是不能太过于自以为是了。这里的check要做的事是合并区间，而这个行为并不能通过贪心来节约时间——原因上面也提到了。

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

#include <iostream>
#include <utility>
#include <algorithm>
#include <iomanip>
#include <cmath>

#define pos first
#define spd second
#define npos (q+1)

using namespace std;
typedef long long longs;
typedef pair<double,double> ink;
struct range {double left,right;};

const int N = 1e5 + 5;
int n,q;
const double EPS = 1e-6;
ink li[N];
range r[N];

bool operator<(range& a, range& b)
{
    if (fabs(a.left - b.left) < EPS)
        return a.right < b.right;
    else return a.left < b.left;
}

bool check(int q, double t)
{
    double tmp;
    for (int i=1;i<=q;++i)
    {
        auto &ii = li[i];
        tmp = t*ii.spd;
        r[i] = {ii.pos-tmp, ii.pos+tmp};
    }
    sort(r+1,r+q+1);
    range rr = {r[1].left, r[1].right};
    for (int i=2;i<=q;++i)
    {
        if (r[i].left > rr.right) return false;
        else rr.right = max(r[i].right,rr.right);
    }
    return !(rr.left > 0 || rr.right < (double)n);
}

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

    cin>>n>>q;
    li[0] = make_pair(0,0);
    li[npos] = make_pair(n,0);
    double maxv = 0;
    double x,v;
    for (int i=1;i<=q;++i)
    {
        cin>>x>>v;
        li[i] = make_pair(x,v);
        maxv = max(maxv,v);
    }

    double left = 0, right = n/maxv;
    int times = 100;
    while (times --)
    {
        double mid = (left + right) / 2;
        (check(q,mid) ? right : left) = mid;
    }
    const double ans = (left + right) / 2;
    cout<<fixed<<setprecision(7)<<ans<<endl;

    return 0;
}

有几个比较坑的地方：首先输入的墨水的位置和速度都是浮点数——这我还是查了标程才知道的；然后，关于check函数里面的rr.right的问题：看起来这里的max判断是非必要的，因为我已经排序了；但是因为eps的存在以及一些其他的原因，这里必须要强制保证才可以AC。

另一件事情：如果你不想要使用std::pair<T1,T2>的默认大小判断的话，就干脆的建立一个新类，而不是重命名一个pair——即使你显式的重写了operator<，它用的是什么也不为人知——其实这可实验验证。

H - Huaji robot

有一个n*n的网格图，坐标范围为[(1,1),(n,n)]；横纵坐标互质的地方不能通行；每次移动都是八个方向的移动；给定起点和终点，问能否到达。地图大小n的数据规模是1e9.

引导

出题人讲评的幻灯片上，有下面这段文字：

◦ 推公式？我菜得一比，不会推公式！

◦ 此题更可行的办法是打表+猜结论。

◦ 打表小技巧：当打出的表只有0和1时，就不需要用空格隔开，进一步地，把1换成空格，这样每一个数字和它周围的 关系就更清楚。

这个题目的障碍物非常的奇特——横坐标和纵坐标互质则不能通行。看起来没什么规律，可以打个表来看看特点。这里就直接写打表可以得到的信息：

• x=y对角线除了x=1时均可以通行：正确性显然
• 对于质数行列，会有长段连续的不可通行区域
• 连通块被质数的行列等切成了比较规则的区域

综上所述，可以猜想：除了与整张图的主对角线相连的，所有的连通块都不会太大。因为会被编号时质数行列的直线切开。虽然质数直线并不是连续的，但是还是可以证明每个连通块不大：

因为每个数的质因子数是 log 级别的，所以在 x=p1 和 x=p2 之间，至多会有 log n×(p2-p1) 个点，把相邻的联通块连接起来。所以每个块的大小是 log n×max(pi-pj) 级别，其中 pi 和 pj 是相邻的两个质数。

又因为，1e9的范围内两个质数的差不会太大——实际上1e9内，最大的质数间距为282。这真的不大，这样就可以有一种思路：

• 从起点和终点开始搜索，只要到达 y=x≠1 的点即视为联通

• 使用 map、哈希、偏移量数组来做这次搜索

这样这个题目就可以做了，

分析

其实也并不需要打表，稍微想想也可以得到上面看出来的两点结论：对角线联通，质数直线阻塞。然而这种题目似乎除了搜索别无他法，只要能够简化搜索就可以做了。也可以得出双向搜索，使用 map 存储遍历情况来做。

但是在实现的过程中还要注意，可能两个点都连接到

当然，这种奇怪的题目也有可能是一个结论，这个时候就别无他法只能当场去世了。

代码

使用 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
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 <map>
#include <queue>

#define bound(x,y) (x<=n&&x>=1&&y<=n&&y>=1)

using namespace std;
typedef long long longs;
struct pos{int x,y;};

const int dx[] = {1,1,0,-1,-1,-1,0,1};
const int dy[] = {0,1,1,1,0,-1,-1,-1};

int n,sx,sy,ex,ey;
map<int,map<int,short>> m;
bool found = false;

int gcd(int a, int b)
{
    if (b > a) return gcd(b,a);
    else if (!b) return a;
    else return gcd(b, a%b);
}

bool check(int x, int y, short flag)
{
    queue<pos> q; pos top;
    m[x][y] = flag; q.push({x,y});
    while(!q.empty())
    {
        top = q.front(); q.pop();
        for (int i = 0; i < 8; ++ i)
        {
            int xx = top.x + dx[i];
            int yy = top.y + dy[i];
            if (bound(xx,yy) && gcd(xx,yy) != 1)
            {
                if (!m[xx][yy])
                {
                    if (xx == yy && xx != 1)
                        return true;
                    m[xx][yy] = flag;
                    q.push({xx,yy});
                }
                else if (m[xx][yy] != flag)
                    return found = true;
            }
        }
    }
    return false;
}

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

    cin>>n>>sx>>sy>>ex>>ey;
    bool c1 = check(sx,sy,1);
    bool c2 = check(ex,ey,2);
    bool checked = c1 && c2;
    cout<<((checked||found)?"gl":"gg")<<endl;

    return 0;
}

第一次写的时候不知道犯了什么浑，结果按照标程的方法布局代码就过了，不是很懂…… 也许两头搜索就应该使用 vis 数组记录具体哪一次搜索到达的信息吧。

E - Eluos blocks

给了一个由三种俄罗斯方块拼成的图形，记为ABC；A类俄罗斯方块只有一个，而其他的有无数个；求出这唯一的A类方块的位置。整个图形的规模小于500。求出解的数量。并且按照指定的顺序输出所有的解。

引导

这种一看就是考智商的思维题。这道题再加大难度之前是这样的：

弱化版的条件有这样的区别：无B类方块，依然是一个A类和若干C类方块

这种情况下，只有两种不同的图形，图形之间的差距挺容易被对比出来的，这里直接说：

• 显然，A是斜杠的对角线的两个方块缺失，C是反斜杠的对角线。
• 即使这些方块不断的堆积，这种特性也会得以保留。
• A图形跨三行：首尾两行只有一个方块，中间一行有两个；C跨两行，每行两个。

那么这题的解法就有眉目了：可以利用最后一条特性，确定A所在的水平位置，再搜索垂直方向，找到满足条件的情况输出即可；也可以利用前两条特性，找到最左上角的“孤立”方块，若右侧无方块那就可以肯定是A，否则是C，删去。这种做法的正确性也可以比较容易的讨论证明。

现在的情况是不仅有AC，还有B类方块；这样的话上面的方法就不行了，我们需要去找新的规律：

分析

虽然对角线上的两个方块的独特性已经消失了，但是参考上面的特性，我们还是可以找出新的特性：从反对角线方向观察方块的“厚度”，也可以观察到这样的特点：

• A类方块占有斜杠方向对角线的四列，每列有一个方块；
• B类、C类方块占有斜对角线方向的两列，每列有两个方块；

这样就和上面简单版题目的第三条特性相似，可以使用同样的方法来做了：通过统计对角线的方块数量，找到数量是奇数的四列方块，然后再遍历某对角线上的所有方块，检查它们是A的一部分时的正确性，就可以在O(n³)的时间内求解。所有的解都会出现在这个范围内。

这里说的斜杠方向指的是将整个图逆时针旋转45°。旋转之后可以得到图形的“列”和“厚度”。

这个题目似乎实际上O(n⁴)的算法也可以卡过去。也就是说枚举能过的。

代码

特别注意：输出的坐标是需要排序的。也就是说这题没有SPJ。

1

G - Game

给5个整数，要求使用加减乘除括弧运算符以及前4个数字拼成一个算式，使得算式结构等于第5个数；问是否可以构造出这样的算式。

分析

非常经典的问题：你可以不停枚举，枚举数字排列，枚举运算符，枚举括号位置，然后求解验证；也可以每次选出两个数字和一种运算符计算，将计算结果丢回去，重新选择计算直到只剩下一个数字，都可以。怎么做都可以做出来，暴力只要写对了也可以AC。

误区

这个游戏和常规24点游戏有一个根本上的不同：数字的顺序是可以随机调换的，最后构造的算式中，数字出现在式子中的顺序未必是输入的顺序。如果按照一般24点写死的话就会死。这有可能就是赛场上我和队友没有AC这个题目的原因所在。

代码

首先四选二，再三选二，枚举所有可能的运算方式（包括反向的减法除法）：

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

using namespace std;
typedef long long longs;

const double eps = 1e-6;
const struct{int x,y;} other[4][4] =
        {
                {{},{2,3},{1,3},{1,2}},
                {{3,2},{},{0,3},{0,2}},
                {{3,1},{3,0},{},{0,1}},
                {{2,1},{2,0},{1,0},{}}
        };
int ed;

double operate(double a, double b, int mode)
{
    switch (mode)
    {
        case 0: return a+b;
        case 1: return a*b;
        case 2: return a-b;
        case 3: return b-a;
        case 4: return !a?0:b/a;
        default: return b?a/b:0;
    }
}

bool deepSearch(double a[])
{
    for (int i=0;i<3;++i)
        for (int j=i+1;j<3;++j)
            for (int op1=0;op1<6;++op1)
                for (int op2=0;op2<6;++op2)
                    if (fabs(operate(
                            operate(a[i],a[j],op1),a[3-i-j],op2
                    )-ed)<eps)
                        return true;
    return false;
}

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

    int t,op[4];
    cin>>t;

    auto fun = [&]() -> bool
    {
        double arr[3];
        for (int i=0;i<4;++i)
            for (int j=i+1;j<4;++j)
                for (int k=0;k<6;++k)
                {
                    arr[0] = operate(op[i],op[j],k);
                    arr[1] = op[other[i][j].x];
                    arr[2] = op[other[i][j].y];
                    if (deepSearch(arr)) return true;
                }
        return false;
    };

    while (t--)
    {
        cin>>op[0]>>op[1]>>op[2]>>op[3]>>ed;
        cout<<(fun()?"Yes":"No")<<endl;
    }


    return 0;
}

现在觉得适当的多用用lambda表达式声明一些函数还是蛮好的== 有点香

A - Able was I ere I saw Elba

给一个长度为 n 字符串，以及m个操作；每个操作能让你花 c 个代价把字符 a 变成字符 b；对于串中的所有子串[l,r]，都可以花一个最小的代价来把它变成回文串；问对于所有n*(n-1)/2个子串，最小代价和是多少。

引导

首先题目里是子串，而不是子序列（否则个数也不对了），子串是连续的。

和很多的区间数据结构题目不同，这个题目并不是每次询问一个空间内的子串，而是所有可能的子串。这和随机询问不同，是一种特殊性，可以加以利用；下面我们考虑一对字符 s[i] 和 s[j] 的贡献：

• 设 i j 的对称轴为 k，显然k是中点；显然，所有以k为对称轴的子串都会受到同样来自 i j 的贡献；
• 这样的子串数量是 min(i,n-j+1)，这也是显然的。
• 直接枚举复杂度太大，但是可以简化：若贡献 i 次，那么一定满足 i < n-j+1， j 的取值有范围；
• 假设 j 的最大值为 m，则 i < n-m+1 => m<n-i+1 。

至于让 i j 字符相同，可以修改两者中的一个，也可以同时修改两个字符使他们的值相等，找到最小的花费。又因为它们有不同的贡献度，还要记得加算倍数。事实上，分贡献的倍数讨论就可以了。

根据上面的分析，可以确定这样的实现思路：

• 根据奉献的次数来分别处理：奉献次数为 i 时，也就是a[i]与所有的 a[t] (i<t<n-i+1) 不发生冲突的最少花费的和；奉献 j 次时，就是反向同理；
• 因为字符集只有26，可以处理每个字母数量的前缀和，从而快速得出区间 (i,n-i+1) 内存在的不同字符个数，以累加对答案的总贡献；
• 因为变化字符使得相等有多种方案，需要预先处理任意两个字符的转化代价，再处理消除任意两个冲突字符的代价；这可以使用 Floyd 预处理。

这样，就可以着手实现这个题目了。

分析

首先看懂题目。我们选择样本不大且有代表性的样例2：

字符串"aabaa"一共有十个子串，下面只列出需要修改字符的子串：

• "aaba", "abaa" => "abba"：a -> b，消费1*2
• "aab", "baa" => "bab"：a -> b，消费1*2
• "ab", "ba" => "bb"：a -> b，消费1*2

综上所述，将这个字符串的全部子串变为回文串的总消费是6，也就是要求解输出的值。

首先维护一个字符集的前缀和；然后根据输入的转化成本信息，使用Floyd求出所有可互相转化的字符转化的最低成本；然后考虑解决冲突：当字符 i j 不同时，将它们改成相同的时候所需要的最低成本；随后遍历串中每一个字符，只考虑单个字符的贡献以统计答案。具体地说，统计答案是这样做的：

• 对于下标为 [0,n-1] 的字符串的第 i 个字符：它的左侧有 i 个字符，右侧有 n-i-1 个字符；
• 若字符靠左侧，则 i 较小；这里仅考虑 i 作为对称轴左侧字符的情况，因为右侧的情况会被更小的 i 考虑到；
• 若字符 i 在左侧，那么它的左侧还可能有 [0,i] 个字符；这里仅考虑 i 的情况，因为其他情况会被从右侧对称考虑到；但是仍然要计算所有的可能前缀的回文串；
• 问题转化成：当子串的对称轴左侧最前端有 substr(0,i) 的前缀时，字符 i 可以为回文串奉献的最小修改成本；
• 因为有了长度为 i 的前缀，所以可能在子串中和 i 对称的字符只有下标为 [i+1,n-i-1] 的字符；尝试修改字符 i 使得字符 i 与每个这些字符都相等；
• 因为有可选的长度为 i 的前缀，所以上述计算得到的奉献还需要加算奉献倍数 i+1；
• 当字符 i 在右侧时，需要注意的是：使用全部后缀的情况已经被对应的左侧字符考虑过了，所以考虑的对称字符只有下标为 [n-i, i-1] 的字符。
• 特别注意，字符串长度为奇数的时候，最中间的一个字符单独计算贡献时不能带来任何贡献；

注意上述的所有细节，方可写出这个题目的代码。

代码

1

F - Fake information

空间中有 m 个点，有 n 个粒子在这些点上随机运动；开始时所有粒子处在1号点；每轮运动，粒子都会随机运动到其它另一个点，运动持续无数次；设 d[i,j] 表示第 i 个粒子和第 j 个粒子运动轨迹的最长公共前缀，求 max{d[i,j]} 的期望值。数据规模是100.

引导

分析

后记

菜呢，是真的菜。签到题的思路全部歪了，到最后除了最简单的划水题，一个题目也没有做出来。甚至根本都没有向二分答案的方向上去想。

更新于：2020年3月20日

算法

ACM

Luogu