[数据结构与算法]Codeforces Round #745 (Div. 2)部分题解(A ~ C，E的题意与想法)

前言

这场div2的时间就很离谱，也是怪博主自己没好好看，最后也是错过了。
但是补完题之后有一种庆幸自己没打的喜悦，否则又得掉大fen。

闲话不多说了，上主菜。

A - CQXYM Count Permutations(数学+思维)

比赛链接：https://codeforces.com/contest/1581/problem/A

题目大意

1~2n的数字序列的排列组合一共会有 $(2n)!$ 种不同的结果。

请问，在这些结果中，正序下标的数量不少于n的有多少个？
结果对10⁹+7取模。

正序下标：如果有下标 i 使得a[i]<a[i+1]，则称 i 为正序下标。

思路

这其实是一个结论题：会有一半的结果满足条件。也就是 $\frac{1}{2}$$(2n)!$ 。
这个是可以证明的：
假设{$c_1$，$c_2$，$c_3$，$c_4$，…，$c$_$2n$ }存在k个正序下标。
那么我们可以推得：{$2n?c_1$，$2n?c_2$，$2n?c_3$，$2n?c_4$，…，$2n?c$_$2n$ }有$2n?k$个正序下标。

剩下的只需要注意一个点：
$\frac{1}{2}$不要最后处理，我们可以把$(2n)!$的第一个$2$和$\frac{1}{2}$自爆，这样就不会出现精度问题了。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int main()
{
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        ll ans=1;
        for(int i=3;i<=2*n;i++)
            ans=(ans%mod)*(i%mod)%mod;
        cout<<ans<<endl;
    }
}

B - Diameter of Graph (数据结构+思维)

比赛链接：https://codeforces.com/contest/1581/problem/B

题目大意

CQXYM想要用$n$个结点与$m$条边来构造一张无向连通图。
他觉得这很简单，于是决定加一点难度：
构造出来的无向连通图中的每两个结点之间的最短距离必须严格小于$k?1$。

请问CQXYM是在痴人说梦吗？
是则输出$YES$，不是则输出$NO$。

思路

这明显是抽查各位基础知识学得踏不踏实，博主我看到的时候当时就不乐意了。

这不是在蔑视我[○･｀Д′･ ○]？

在我把我手上所有的数据结构书都翻了一遍之后也是胸有成竹的把它给AC了。
这叫什么？这就叫专业，这就叫 胸 有 成 竹。

首先我们先处理最简单的情况：

• $n$个结点与$m$条边无法构成一张图 （$m>(n?n?n)/2或m<n?1$）

if(m>(n*n-n)/2||m<n-1)
      cout<<"NO"<<endl;

接下来，我们考虑$k$的取值。

如果$k<2$，此时条件会变得不合法，所以特判掉。

else if(k<2)
	cout<<"NO"<<endl;

如果$k==2$，也就是说点与点之间的最大距离为$0$，那也就是说这张图上只能有$1$个点，$0$条边才满足条件。

else if(k==2)
{
    if(n==1&&m==0)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
}

如果$k==3$，也就是说点与点之间的最大距离为$1$，此时我们可以采用完全图的方式构图。
在完全图中，点与点之间的距离都是1，满足题意。（下图为结点数为5的完全无向图）

else if(k==3){
    if(m==(n*n-n)/2)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
}

如果$k>3$，此时我们就可以构建一张星型图，把剩下的边找地方画，这样就可以保证所有点之间的最小距离的最大值为$2$，这种情况一定可以成立。(下图为由6个结点形成的星型图)

最后就是把上面的内容整合在一起。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        ll n,m,k;
        cin>>n>>m>>k;
        if(m>(n*n-n)/2||m<n-1)
            cout<<"NO"<<endl;
        else if(k<2)
            cout<<"NO"<<endl;
        else if(k==2)
        {
            if(n==1&&m==0)
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }
        else if(k==3)
        {
            if(m==(n*n-n)/2)
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }
        else
            cout<<"YES"<<endl;
    }
}

C - Portal(暴力+思维)

比赛链接：https://codeforces.com/contest/1581/problem/C

题目大意

在游戏Minecraft之中存在着下界这一维度。

玩家想要进入下界，就必须使用黑曜石搭建出有效的下界传送门框架，然后点火激活。


一个有效的下界传送门框架需要满足的条件为：

1>如果框架大小为$n\times m$，则$n$ 与 $m$需要满足$n>=4$ $and$ $m>=5$；
2>框架的四个角可以不是黑曜石，中间包围的区域需要是空气方块；

现在给出一个$n\times m$的矩阵，矩阵中$0$代表空气方块，$1$代表黑曜石。
你可以把任意一个黑曜石替换成空气($1\to 0$)，也可以把空气替换成黑曜石($0\to 1$)。

请问最少需要替换多少个方块才能造出一个有效的下界传送门框架？

思路

博主作为$MC$十年老玩家，不说别的，光下界传送门博主也是至少搭过上千个了，去下界就跟回家一样。
所以一发AC掉这个题根本不在话下。

额，这个题它不讲武德，它没有实力，它搞偷袭，呜呜呜┭┮﹏┭┮

不瞎扯了，我们来看一下这个题。

首先我们要知道$4?5$是传送门的最小限制而已，也就是说最小的传送门形式应该是下面的这个：

0110
1001
1001
1001
0110

注意，四个角可以是$1$也可以不是$1$，即使是下面的形式也是有效的框架形式：

1110
1001
1001
1001
0111

了解到这一点之后我们就需要想一想，如果我们指定了一片区域，想知道它需要替换多少个方块才可以变得有效，我们该怎么办。

我们用二维前缀和数组存储整个矩阵，可以利用这个矩阵与前缀和的特点，快速地获取到指定区域的具体情况。

接下来我们就暴力枚举出每次的起始行、起始列、终止行与终止列，由于数据比较水，使得O(n³)就能过。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int a[450][450];
int sum[450][450];

int query(int cx, int cy, int zx, int zy)
{
    return sum[zx][zy] - sum[cx-1][zy] - sum[zx][cy-1] + sum[cx-1][cy-1];
}

int main()
{
    int t;
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        for(int i=1; i<=n; i++)
        {
            string ss;
            cin>>ss;
            for(int j=1; j<=m; j++)
                a[i][j]=ss[j-1]-'0';
        }

        memset(sum,0,sizeof(sum));
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
                sum[i][j]=sum[i-1][j]+sum[i][j-1]+a[i][j]-sum[i-1][j-1];
        }
        int ans=inf;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                for(int x=i+4; x<=n; x++)
                {
                    int sleft=x-i-1-query(i+1,j,x-1,j);
                    for(int y=j+3; y<=m; y++)
                    {
                        int kong=query(i+1,j+1,x-1,y-1);
                        int htop=y-j-1-query(i,j+1,i,y-1);
                        int hbottom=y-j-1-query(x,j+1,x,y-1);
                        int sright=x-i-1-query(i+1,y,x-1,y);
                        int weight=kong+htop+hbottom+sleft+sright;
                        if(weight>=ans) break;
                        ans=min(ans,weight);
                    }
                }

        cout<<ans<<endl;
    }
}

你以为到这就结束了？

虽然是O(n³)就能水过，但目前还是一个O(n⁴)的代码，会在第三个样例 $T$ 掉的。
所以我们需要再做一些剪枝。

我们想一想，在我们不断去枚举传送门的右下角的位置的时候，横着的两排黑曜石所需要的消费与中间空白区域所需要的消费是不递减的，竖着的左面一列的黑曜石所需要的消费是不会改变的，而竖着的右面一列的黑曜石所需要的消费的改变是无法确定的。

此时我们可以利用 左+中+上+下 一定不递减的性质进行一次剪枝，这样就可以水过去了。

AC代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int a[450][450];
int sum[450][450];

int query(int cx, int cy, int zx, int zy)
{
    return sum[zx][zy] - sum[cx-1][zy] - sum[zx][cy-1] + sum[cx-1][cy-1];
}

int main()
{
    int t;
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        for(int i=1; i<=n; i++)
        {
            string ss;
            cin>>ss;
            for(int j=1; j<=m; j++)
                a[i][j]=ss[j-1]-'0';
        }

        memset(sum,0,sizeof(sum));
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
                sum[i][j]=sum[i-1][j]+sum[i][j-1]+a[i][j]-sum[i-1][j-1];
        }
        /// 4*5即以上都可以搭成地狱门，最小框架范围为4*5
        ///（实质上是4*5-4==16个，也就是说最少要有16个黑曜石才能搭乘地狱门）
        /// 所以ans的值最大为16，可以不是inf
        int ans=inf;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                for(int x=i+4; x<=n; x++)
                {
                    int sleft=x-i-1-query(i+1,j,x-1,j);  ///算出形成最左面那一列黑曜石所需要的替换的方块数量
                    for(int y=j+3; y<=m; y++)
                    {
                        int kong=query(i+1,j+1,x-1,y-1);    ///算出产生中间围住的空白方块所需要的替换的方块数量
                        int htop=y-j-1-query(i,j+1,i,y-1);  ///算出形成最上面那一行黑曜石所需要的替换的方块数量
                        int hbottom=y-j-1-query(x,j+1,x,y-1);///算出形成最下面那一行黑曜石所需要的替换的方块数量
                        int sright=x-i-1-query(i+1,y,x-1,y); ///算出形成最右面那一列黑曜石所需要的替换的方块数量
                        int weight=kong+htop+hbottom+sleft;
                        ///在逐步模拟右下角的点时，sleft是不会改变的，htop、hbottom与只增不减，sright不一定会怎么样
                        ///因此，我们可以通过前四个的值进行剪枝（一定会变大或者不变的部分）
                        if(weight>=ans) break;
                        ans=min(ans,weight+sright);
                    }
                }

        cout<<ans<<endl;
    }
}

D - Mathematics Curriculum

比赛链接：https://codeforces.com/contest/1581/problem/D

少有的看了一下午题意没看懂，看大佬们AC的代码也看不明白的题。
貌似是个dp，还牵扯到序列，还有杨辉三角。

奇奇怪怪的D，我甚至觉得E题都比这题简单。

只能先放在这，看看有没有大佬可以出篇题解我去悟一悟。

E - Train Maintenance(差分数组+线段树+数学)

比赛链接：https://codeforces.com/contest/1581/problem/E

题目大意

在一个火车站有$n$列火车，每一列火车都有两个属性：工作天数$x_i$和维修天数$y_i$。
当火车$i$在第$t$天的时候开始工作后，它会工作$x_i$天，然后进入$y_i$天的维修，然后再进入$x_i$天的工作，直到火车$i$被停用。

一开始，所有的火车都是停用状态。
在接下来的$m$天里，每天都会有一条指令op k。
$op==1$时，将启用火车$k$；$op==2$时，将停用火车$k$。

现在需要你求出每天有多少列火车正在维修。

想法

自己看完，没啥思路说实话。
于是搜了一下，找到了一篇说是线段树的。
说这个我可就不困了，我当时就研究了40min。

大佬的博客

怎么说呢，有的地方还能看懂，有的地方比较迷惑。

首先为什么是$sqrt(m)$？解释看懂了一些，但又没完全懂。
其次二维数组$cnt$的作用没搞明白，差分数组我倒是明白了。

其他的我基本上都悟了，应该就差这两个点了。
感觉E题要比D题容易，我再下下功夫。
这个地方就先埋个坑，如果博主参悟到了就第一时间发博客。

总的来说这次的div2对于博主这样的菜狗来说是略微有点难度的(doge)。

后续再把DE题看一看补一补，E题必须得出，真的就差一点了我感觉。

这次就到这里，感谢阅读。