2021牛客寒假算法基础集训营5（A B D F G）

比赛链接：这里

OP

个人能力有限，有的题目实在知识点欠缺太多，这里是大佬的题解

A 美丽的路径

dfs 二分

思路

在通过dfs确定所有起始点可达点包括目标点后，就要开始判断最大美丽值。

在使用二分求最大美丽值时，对于check部分，我们可以按如下策略处理：

为方便叙述，我们标记大于等于mid的点为1，小于mid的点为0，mid<=答案时，总1数>=总0数；

①要求所有可达边不存在边的两端点均为1；
若存在，则路径可在这两点间反复横跳，使美丽值大于等于此点，此时应向右二分。

②要求起始点与目标点不均为0；
若满足，由于路径中不存在两连续的1，则路径总1数最大的情况即为 01010…1010，此时总0数必大于总1数，此时应向左二分。

③要求存在一条路径满足标记为 01010…101 或 10101…010 或 10101…101，从边的角度看，也可以描述为，存在一条路径，其上每条边的两端不全为0。
若路径上有一条00边，由于没有11边进行补齐，1的数量将永远小于等于0的数量。

代码

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
#include<bits/stdc++.h>
using namespace std;

vector<int> rod[200005];
int n,t,MAX;
int a[200005],vis[200005],f[200005],s;

void dfs1(int x)
{
    vis[x]=1;
    for(int i=0;i<rod[x].size();i++)
    {
        if(!vis[rod[x][i]])
        dfs1(rod[x][i]);
    }
}

void dfs2(int p,int x)
{
    f[p]=1;
    for(int i=0;i<rod[p].size();i++)
    {
        if(!f[rod[p][i]]&&(a[p]>=x||a[rod[p][i]]>=x))
        dfs2(rod[p][i],x);
    }
}

int check(int x)
{
    for(int i=1;i<=n;i++)
        if(vis[i]&&a[i]>=x)//判据一
            for(int j=0;j<rod[i].size();j++)
                if(a[rod[i][j]]>=x)
                    return 1;

    if(a[s]<x&&a[t]<x)//判据二
    return 0;

    memset(f,0,sizeof f);
    dfs2(s,x);
    return f[t];//判据三
}

int main()
{
    int T,m,e,b;
    scanf("%d",&T);
    while(T--)
    {
        MAX=0;
        scanf("%d%d%d%d",&n,&m,&s,&t);
        memset(vis,0,sizeof vis);
        for(int i=1;i<=n;i++)
        rod[i].clear();
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            MAX=max(MAX,a[i]);
        }
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&b,&e);
            rod[e].push_back(b);//建图
            rod[b].push_back(e);
        }
        dfs1(s);//判断可达性
        if(!vis[t])
        {
            printf("NO\n");
            continue;
        }
        int l=0,r=MAX;
        while(l<r)
        {
            int mid=l+r+1 >>1;//右取整二分
            if(check(mid))l=mid;
            else r=mid-1;
        }
        printf("YES\n%d\n",l);
    }
    return 0;
}

B 比武招亲（上）

组合数，递推，多重集（这里和这里）

思路

我们可以先枚举差值 d∈[0,n−1]d\in[0,n-1]，对于每一个差值 dd，都有 n−dn-d 种最小值。

确定了最小值和 d ，便可以确定最大值，下一步我们需要算出对于每一种 d 的一种最小值下有多少种组合：

我们可以讲问题转化成

在网格内，从 ( 0 , 0 ) 点到 ( a , b ) 点的最短路径数。

总共一定有 a + b 步，只需要选取其中 a 步向右走，剩下的便是 b 步向上走；
回到刚才的问题中，向上走便代表+1，向右走便代表处理下一个数，所以对于 d 和 m ，组合种类数为 del[d]=Cd+m−2m−2del[d]=C_{d+m-2}^{m-2}；

再接下来，我们需要获得 del[ i ] 的递推式：
对于 d ，del[d]=∏j=m−1d+m−2(j)d!del[d]=\frac {\prod_{j=m-1}^{d+m-2}(j)} {d!}；
所以 del[d]=del[d−1]∗(d+m−2)/ddel[d]=del[d-1]*(d+m-2)/d；

除法用逆元处理即可。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5e5+5,M=998244353;
static ll del[N]= {0};
ll qm(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)ans=ans*a%M;
        a=a*a%M;
        b>>=1;
    }
    return ans%M;
}
int main()
{
    ll n,m,i,j;
    ll ans=0;
    cin>>n>>m;
    /*if(m==1)ans=0;//经测试，并不需要对 m==1or2 特判
    else if(m==2)
    {
        for(i=1; i<=n-1; i++)
        {
            ans+=i*(n-i)%M;
            ans%=M;
        }
    }
    else*/
    {
        del[0]=1;
        for(i=1;i<=n-1;i++)
            {
                del[i]=(del[i-1]*(m-2+i))%M*qm(i,M-2)%M;
                del[i]%=M;
            }
        for(i=1;i<=n-1;i++)ans+=del[i]*(n-i)%M*i,ans%=M;
    }
    cout<<ans;
    return 0;
}

D 石子游戏

差分

思路

先构建差分数组，a[ i ] 代表第 i 堆比第 i - 1 堆多的石子数。

进行一次从 b 开始的 k 堆石子个数均+1的操作体现在差分数组上就是 a[b]=a[b]+1,a[b+k]=a[b+k]−1a[b]=a[b]+1,a[b+k]=a[b+k]-1；

我们的目标就是通过操作将差分数组变为[x,0,0,...][x,0,0,...]；

由于最左侧的值不是常量（猜想是所有堆的最大石子数），我选择从右向左遍历数组，直至 i - k ==1 ：

如果a[ i ] > 0，通过进行 a[ i ] 步操作，使 a[i−k]=a[i−k]+a[i],a[i]=0a[i-k]=a[ i - k ] + a[ i ],a[i]=0；
如果a[ i ] < 0，此时我们可以看作第 i 堆与其右侧所有堆石子个数相同，并小于第 i - 1 堆的石子数。如果 (n−i+1)%k==0(n - i + 1 )\%k==0，即 i 及其右侧石子堆数为 k 的倍数，此时即可通过 -a[ i ] * (n - i + 1 )/k 次操作补齐；如果不能被 k 整除，则无法凑成所有堆石子数相同的情况。

对于第 2 ~ k 堆，还需要再检查其差分 ，如果某位大于 0，或 某位小于 0 且(n - i + 1 )%k!=0，同样无法实现。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=1e9+7;
 
int main()
{
    int t;
    static ll a[N];
    cin>>t;
    while(t--)
    {
        memset(a,0,sizeof a);
        int n,last=0,now,f=1,i,k;
        cin>>n>>k;
        ll op=0;
        for(i=1;i<=n;i++)scanf("%d",&now),a[i]=now-last,last=now;
        for(i=n;i>=k+1&&f;i--)
        {
            if(a[i]>0)op+=a[i],a[i-k]+=a[i];
            else if(a[i]<0)
            {
                if((n-i+1)%k==0)op+=(n-i+1)/k*(-a[i]);
                else f=0;
            }
        }
        for(i=k;i>=2&&f;i--)
        {
            if(a[i]>0)f=0;
            else if(a[i]<0)
            {
                if((n-i+1)%k==0)op+=(n-i+1)/k*(-a[i]);
                else f=0;
            }
        }
        if(f)printf("%lld\n",op);
        else printf("-1\n");
    }
    return 0;
}

F 我的心是冰冰的

签到题

思路

由于是树，没有环状结构，便可使用如下策略：

第一层填 A 色，第二层填 B 色，第三层填 A 色…

所以结果即为 (n==1)?1:2

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5,M=1e9+7;

int main()
{
    int t,n,i,a,b;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(i=2;i<=n;i++)scanf("%d%d",&a,&b);
        printf("%d\n",(n==1)?1:2);
    }
    return 0;
}

注意要把没用的数据吃掉！

G 模仿游戏

贪心

思路

tim1与tim2代表鸽鸽与妹妹的打怪队列长度；

如果此怪未曾遇到过，则将其加入tim1队列；

如果遇到过：
若是此分钟出现的，能打它的最近时间是下一分钟；
若是非此分钟出现的，则能打它的最近时间是此分钟；

还有就是鸽鸽对妹妹的帮助机制：
如果此分钟鸽鸽没有打怪，且妹妹有未打的怪，则鸽鸽帮助妹妹打一个怪；
（只能帮助一个，如果鸽鸽上一分钟没有打怪，帮助的即为此分钟刷出的一个；如果上一分钟有打怪，则鸽鸽此分钟只能打一个）

加入队列时，比较该队列长度+1与最近打此怪时间的最大值。

对于maxn为什么要取2e5还是不太清楚。

另：多给自己两组样例

输入1

1
5
1 1
1 2
1 3
1 2
1 3

输出1

3

输入2

1
5
1 1
2 2
2 3
2 2
2 3

输出2

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
#include<bits/stdc++.h>
using namespace std;
 
const int MAXN = 2e5+5;

int main()
{
	int t,n,tim1,tim2;
	int vis[MAXN];
    scanf("%d",&t);
    while(t--){
        tim1=tim2=0;
        memset(vis,0,sizeof(vis));
        scanf("%d",&n);
        vector<int>arr[MAXN];
        for(int i=1;i<=N;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            arr[a].push_back(b);
        }
        for(int i=1;i<MAXN;i++)
        {
            for(int j=0;j<arr[i].size();j++)
                if(!vis[arr[i][j]])
                {
                    tim1=max(tim1+1,i);
                    vis[arr[i][j]]=i;
                }
                else
                {
                    if(i==vis[arr[i][j]])tim2=max(tim2+1,i+1);
                    else tim2=max(tim2+1,i);
                }
            if(tim2>tim1&&tim1<i)
            {
                tim2--;
                tim1=i;
            }
        }
        printf("%d\n",max(tim2,tim1));
    }
    return 0;
}

ED

\

算法竞赛 > 比赛与题集
2021牛客寒假算法基础集训营5（A B D F G）
https://tanyuu.github.io/2021.01-06/2021牛客寒假算法基础集训营5（A B D F G）/
作者
F Juny
发布于
2021年2月23日
许可协议