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

七海

题解

发布于：2020年3月31日

次浏览

这一波还是只有八个题目。简单题基本上算是真正的简单题，套模板或者自己认真写一写就出来了；但是麻烦的题就总是感觉还差一把火的样子——倒不如说这应该是水平不足的通常表现吧。还是因为版权原因，并不能把题目挂出来，所以只能看我空讲了：

根据出题人的定义，题目的难度分配大概是下面这样的：

既然给了难度定义，那就根据出题人的思路来补这套题。部分题就直接使用赛场上的代码了。

C - Change

给n个题，每个题有一些可用的名字，问能否让第i个题以第i个字母开头；可以改变题目的顺序。

说白了就是二分图匹配：每个题有的名字的头文字就是连边，表示这个题可以和这些头文字匹配；二分图两侧都有n个元素，问是否存在满匹配；这种问题有多个模板解法，比如匈牙利DFS和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
57
58
59
60
61
62

#include <iostream>
#include <string>
#include <cstring>

using namespace std;
typedef long long longs;

int n,q,m;
bool li[30][30];    // =>[n][m]
bool visit[30];     // => m(首字母)
int match[30];      // =>match[m]=n

bool nextMatch(int i)
{
    for(int j=0;j<m;++j)   // 不要从中途开始
        if(li[i][j]&&!visit[j])
        {
            visit[j] = true;
            if(!~match[j]||nextMatch(match[j]))
            {
                match[j] = i;
                return true;
            }
        }
    return false;
}

inline int maxMatch()
{
    int ans = 0;
    for(int i=0;i<n;++i)   // 要重置visit
    {
        memset(visit,0,sizeof(bool)*(m+1));
        if(nextMatch(i)) ++ans;
    }
    return ans;
}

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

    cin>>n; m = n;
    string s;
    memset(li,0,sizeof li);
    memset(match,-1,sizeof match);
    for (int i = 0; i < n; ++ i)
    {
        cin >> q;
        while (q--)
        {
            cin >> s;
            li[i][s[0]-'a'] = true;
        }
    }
    const int matches = maxMatch();
    cerr <<matches<<endl;
    cout<<(matches == n ? "Yes" : "No")<<endl;

    return 0;
}

需要注意的是，一般来说都使用0表示未匹配状态；但是这里因为每个待匹配元素是char-'a'，所以0本身也是一个匹配元素，应该使用其他方便的数字比如-1作为未匹配状态；或者也可以修正字符的值。虽然是很细节的东西但是吃了罚时所以还是要注意一下。不如之后的模板都使用-1作为未匹配状态，更加健壮。

F - Flaw

给定一个不等式，问在自然溢出的意义下成立的方案数

这里的溢出指的是int溢出。出题人也说少考虑了好多种情况；对于不等式a+n1</>n2来说，左侧的a+n1是分成多个区间的：一个区间是未溢出时正常运算，还有一部分是溢出后的部分；分别讨论处理一下就可以了——具体地说，可以是下面这样：

对于a+n1<n2： 未溢出的部分是[-2³¹, n2-n1)，溢出的部分是[2³¹-n1,INTMAX]；

对于a+n1>n2： 未溢出的部分是(n2-n1, INTMAX-n1]，溢出的部分是[INTMAX+n2-n1,INTMAX]；

处理一下读入的字符串然后进行对应的计算就可以了。但是本题更为经济的做法是观察题目样例，找到规律。比如下面的代码：

代码

进行一些线性组合的猜测后发现这个答案似乎只和n2有关，因此可以这么写：

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

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long longs;

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

    int n1,n2;
    char ch;

    cin>>ch>>ch>>n1>>ch>>n2;
    longs ans;
    if (ch == '>')
    {
        ans = 2147483647ll-n2;
    } else
    {
        ans = 2147483648ll+n2;
    }
    cout<<ans<<endl;

    return 0;
}

说是int范围，但是答案还是会爆int的。

G - Gene

给定两个大写字符串进行匹配：其中匹配是alpha分，失配是-beta分，gap是-gamma分；问最大匹配得分

看题目样例给的图，真的像极了LCS——其实它就是一个LCS：只是转移的规则不太一样——失配有减益效果，使用空格也需要费用。那么简单修改LCS的模板就可以了：转移不再仅通过判等来转移，而是直接通过成本转移；因为空挡有损失，所以dp[0,i]和dp[i,0]都需要预先填入i个空挡的消费。

最后算法的时间复杂度是O(nm)的。

代码

这是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

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long longs;

const int N = 5050, M = 5050;

inline longs max3(longs a, longs b, longs c)
{
    return max(max(a,b),c);
}

int n,m,a,b,y;
char s1[N],s2[N];
longs dp[N][M];

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

    cin>>n>>m>>a>>b>>y;
    for (int i = 1; i <= n; ++ i)
        cin >> s1[i];
    for (int i = 1; i <= m; ++ i)
        cin >> s2[i];
    dp[0][0] = 0;
    for (longs i = 1; i <= n; ++ i)
        dp[i][0] = -y*i;
    for (longs i = 1; i <= m; ++ i)
        dp[0][i] = -y*i;
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 1; j <= m; ++ j)
        {
            dp[i][j] = max3(
                    dp[i-1][j-1]+(s1[i]==s2[j]?a:-b),
                    dp[i-1][j]-y, dp[i][j-1]-y
            );
        }
    }
    cout << dp[n][m] <<endl;

    return 0;
}

然后这题评测机闹了个乌龙：我连续两发WA的莫名其妙，最后队友一交就过了=== 唯一的区别是我是C++14 O2，他直接交的C++(11)；后来我尝试关掉O2优化也通过了，他把我的cin.tie(nullptr)搞成0，开O2也过了，就比较的玄学。

纯　氧　杀　人 （大嘘）

A - Ammunition

有三个物品，第一种值是a，第二种值是b，第三种值在[0,b/2]中任选，物品的值是整数，现在拿了n个物品，问值的和是否可能是m，保证a<b。

就是说，你有a，b和[0,b>>1]的整数，能否可以从中选取n个整数，使得他们的和为m。

因为自己的一些考虑炸了，所以直接按照标准答案的方法：首先排除不可能的情况——比如超过了max(a,b)*n的话，是无论如何都不可能解决的；话说题目里保证了a<b，那就不用max了；在接下来的讨论中，我们将[0,b>>1]记为c。

然后就是先只考虑b：如果只选b，那显然就是{kb}，k∈[0,n]；换一个b成c，可以达成[kb, kb+(b>>1)]，k∈[0,n)；换两个，那就可达成[kb, kb+(b>>1<<1)]，k∈[0,n-1)；综合考虑，就是说可以选到[0,(n-1)b+(b>>1)] ∪ {nb}范围内的所有数字。这已经是一个很稳健的范围了；

接下来在上面的基础上再考虑a：如果a ≤ (b>>1)，那没事了，要你何用；否则，绝大多数的可能性也都被上面的很大的范围包含了，只需要考虑处于((n-1)b+(b>>1), nb)范围内的值就可以了，而这样的值是有限个的；虽然得出这样的值也是有一定的策略的：

理论上，a可以由b或c变过来，但是如果遍历的话就比较蠢了；我们可以反向考虑：这个值之所以还需要a，是因为它大于上述的连续区间——也就是容不得b>>1存在；如果这个只有ab构成的值要变成上界nb，那只能把它的a全部换成b——也就是它和max的差必须是b-a的倍数；这样就可以做出来这个题目了。

出题人的标程使用了__int128这种标准库不支持且仅可以在Linux环境下使用的类型，实际上用unsigned long long也可以刚过去。

做题记录

这个题目，我最开始想着是解不等式：首先设选了x个a和y个b，满足下面不等式的情况： \[ \begin{cases} f(x,y) = m-ax-by>0 \\ g(x,y) = x+y<n \end{cases} \] 并且两个函数的值都尽可能的小。然后再根据剩余的值进行判断；但是最后因为情况实在是太多了于是作罢。也许这种做法需要gcd等一些东西？看起来又有点像是线性规划……

最后尝试写出来的代码也没有考虑f大于0的情况，最后就导致一些本不可能的情况变得可能了起来== 如果再乱搞一波说不定还是可以的，但是实在管不了这么多特殊情况的乱搞了。但是果然还是没有上述标准做法来的简单轻松——不是没有想过换两个b，但是对于b换a考虑多了。

代码

使用出题人标程的策略完成的判断

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

#include <iostream>

using namespace std;
typedef long long longs;
typedef unsigned long long ulongs;

const char ok[] = "Yes";
const char no[] = "No";

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

    ulongs t, n, m, a, b;
    cin >> t;
    while (t --)
    {
        cin >> n >> m >> a >> b;
        if (!n) cout << (!m ? ok : no) << endl;
        else 
        {
            ulongs max = n*b;
            ulongs maxx = max - b + (b>>1);
            ulongs diff = max - m;
            ulongs dis = b - a;
            if (m > max) cout << no << endl;
            else if (m == max || m <= maxx) cout << ok << endl;
            else if (diff % dis == 0) cout <<
                (diff / dis <= n ? ok : no) << endl;
            else cout << no << endl;    
        }
    }

    return 0;
}

这么分析一波之后真实简单……

D - Duliu

定义maxpre和maxsuf（以下简称函数P和S）为参数区间的最大前缀/后缀和，要求求出： \[ \sum^n_{l=1}\sum^n_{r=l+1}\sum^{r-1}_{i=l}P(l,i)S(i+1,r) \] 并且输出答案对指定质数取模后的值。

题如其名，看起来毒瘤的不行== 但是考虑上一次多校的那个A题，这种“全子串状态”考虑的问题——而且还是求和——更是要从考虑每个元素的贡献的角度入手；姑且大方向是确定的。

B - Bolshevik

有n个人，第i个人有ai元，钱包里有bi元，问第x个人想成为最有钱的人至少偷几个钱包

在这个题里，偷钱包有两种策略：一种是偷最有钱的人的钱包，降低成为最有钱的人的门槛；还有一种是偷钱包最有钱的人的钱包，获得最大收益。但是这两种策略不能等量齐观，都得视情况而定——这是显然的。

做题记录

感觉像极了贪心，但是又不知道应该怎么偷；毕竟偷最有钱的人还是最大方的人带来的收益并不能直观的表示出来…… 感觉和之前做过的两个人抢占目标点完全不一样== 虽然这是废话。

尝试了使用两个堆来维护钱包里钱的数量和总钱数，但是总是谜之挂在#7……就不是很能理解；感觉就凭自己还是不太能看出问题了……解决了这个问题再贴代码。

E - Earthquake

给定长度为n的序列，初值为0；给定两种操作：1：区间对x取max，然后这里从区间两端开始向两边传播，传播的过程中每传播一格就-1；2：区间max。

H - Heartfelt Fancy

给一个图，已经给定了部分边的边权；你可以加一条u和v之间的边，边权为 (u-v)²，以最小化s到t的最短路。

这是一个比较经典的问题：和上一次校内训练的添加节点是一样的思路——正向扫一遍反向扫一遍最短路，然后再遍历节点求出 (u-v)² 最优解；但是在这个题目里这样做会超时——不论最短路怎么求，最后遍历是O(n²)的，对于2e5的数据规模来说无论怎么也不可能过；因此可能需要考虑一些优化。

后记

更新于：2020年3月31日

算法

ACM

Luogu