2021牛客寒假算法基础集训营6（全题解）

比赛链接：这里

OP

个人能力有限，有的题目实在知识点欠缺太多，这里是大佬的题解。
这一场总的来说友好极了，就是自己的基础数据总算错，自然也就推了个寂寞。

A 回文括号序列计数

回文序列，阅读理解

思路

对于任意一个左半串，比如说"()()("，其回文右半串为"()()("，而不是")()()"；
回文对称中是左右对调，而不是左右对称。

所以只有空串是合法的回文括号序列。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main()
{
    int n,t;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%d",&n);
		printf("%d\n",(n==0)?1:0);
    }
    return 0;
}

阅读理解

B 系数

lucas定理（可以参照这里与这里）

思路

(x2+x+1)n%3=(x2−3∗x+x+1)n%3=(x+1)2n%3(x^2+x+1)^n\%3=(x^2-3*x+x+1)^n\%3=(x+1)^{2n}\%3

故答案即为(−1)kC(2n,k)%3(-1)^kC(2n,k)\%3

由于 1e15 的数据量和逆元的互质要求，正向计算很困难，所以使用lucas定理进行计算。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=3;

ll qm(ll a,ll b)
{
    ll ans=1;
    for(;b;b>>=1)
    {
        if(b&1)ans=ans*a%M;
        a=a*a%M;
    }
    return ans;
}

ll C(ll a, ll b, ll mod){
    if(a < b)return 0;
    ll up = 1, down = 1;
    for(int i = a,j = 1;j <= b;i--,j++){
        up = up*i%mod;
        down = down*j%mod;
    }
    return up*qm(down, mod - 2)%mod;
}

ll lucas(ll a, ll b, ll mod){
    if(a < mod && b < mod)return C(a, b, mod);
    else return C(a%mod,b%mod,mod)*lucas(a/mod,b/mod,mod)%mod;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
    ll n,k;
    scanf("%lld%lld",&n,&k);
    ll ans=1;
    if(k % 2 == 1)ans = -1;
    ans = ans * lucas(2*n,k,M);
    ans = (ans + 3*M)%M;//防负
    cout << ans << endl;
    }
    return 0;
}

C 末三位

快速幂or找规律

思路

读到题第一反应就是快速幂板子啦~
事实上确实能过；

但是也可以直接找规律做：
对于n=0,1,2,3,4,5,6,7…
应输出 001,005,025,125,625,125,625…
所以就是从 n=3 开始两个一循环，特判 n=0,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
include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=1000;
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,a;
    while(~scanf("%lld",&n))
    {
        a=qm(5,n);
        if(a<10)printf("00%lld\n",a);
        else if(a<100)printf("0%lld\n",a);
        else printf("%lld\n",a);
    }
    return 0;
}

D 划数

取模运算性质

思路

由于 cnt>=11 ，可知剩下的数一定是初始数；

既然需要求剩下的另一个数，根据取模运算性质，即是求其余所有初始数之和对11的模；
至于实现上，个人是 全部求和 取模 之后减去剩余数 处理后 再取模；

注意要特判 n==2 ，此时另一个初始数有可能大于等于11，不能按上面方法做，摘出来即可。

代码

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<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main()
{
    int n,cnt;
    while(~scanf("%d",&n))
    {
        if(n!=2){
        ll md=0,g,i;
        scanf("%d",&cnt);
        for(i=1;i<=n;i++)
        {
            scanf("%lld",&g);
            md+=g;
            md%=11;
        }
        md-=cnt;
        while(md<0)md+=11;
        md%=11;
        printf("%lld\n",md);}
        else
        {
            int a,b;
            scanf("%d",&cnt);
            scanf("%d%d",&a,&b);
            if(a==cnt)printf("%d\n",b);
            else printf("%d\n",a);
        }
    }
    return 0;
}

E 网格

dp

思路

水平方向与竖直方向对答案的贡献是独立的，下面用水平方向说明具体dp过程。

用 dp[i][d](d∈{0,1})dp[i][d](d\in\{0,1\})表示该行遍历至第 i 个时，选择d方向（1为右，0为左）时，对答案的最大贡献度；

dp[i][1]=max(dp[i−1][1],dp[i−1][0])dp[i][1]=max(dp[i-1][1],dp[i-1][0])，即第 i 位选择向右时，不会产生贡献增量，继承第 i - 1 位两个方向中最大值即可；
dp[i][0]=max(dp[i−1][0],dp[i−1][1]+w(a[i][j]^a[i−1))dp[i][0]=max(dp[i-1][0],dp[i-1][1]+w(a[i][j]\hat{}a[i-1))，即第 i 位选择向左时，第 i - 1 位选择向右才能产生增量，选择存入 i - 1 位向右的最大值与增量之和与 i - 1 位选择向左的最大值 的最大值即可；

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

int main()
{
    int bit[1050],n,m,i,j,dp[1003][2]={0};
    static int a[1003][1003];
    for(i=0;i<=1024;i++)
    {
        bit[i]=i;
        j=i;
        for(;j;j>>=1)
            if(j&1)bit[i]++;
    }
    cin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    //dp begin
    ll ans=0;
    for(i=1;i<=n;i++)
    {
        for(j=2;j<=m;j++)
        {
            dp[j][1]=max(dp[j-1][1],dp[j-1][0]);
            dp[j][0]=max(dp[j-1][0],dp[j-1][1]+bit[a[i][j]^a[i][j-1]]);
        }
        ans+=max(dp[m][1],dp[m][0]);
    }
    for(j=1;j<=m;j++)
    {
        for(i=2;i<=n;i++)
        {
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]);
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+bit[a[i][j]^a[i-1][j]]);
        }
        ans+=max(dp[n][1],dp[n][0]);
    }
    cout<<ans;
    return 0;
}

F 组合数问题

数学

思路

手算计算器可得
Sum(4)=2;Sum(4)=2;
Sum(8)=72;Sum(8)=72;
Sum(12)=992;Sum(12)=992;
Sum(16)=16512;Sum(16)=16512;
Sum(20)=261632;Sum(20)=261632;
经过找规律，得出
Sum(4)=22−21;Sum(4)=2^2-2^1;
Sum(8)=26+23;Sum(8)=2^6+2^3;
Sum(12)=210−25;Sum(12)=2^{10}-2^5;
Sum(16)=214+27;Sum(16)=2^{14}+2^7;
Sum(20)=218−29;Sum(20)=2^{18}-2^{9};
规律已经找出来了，这个规律的代码可以过，接下来是得到的证明：

由于二项式定理，我们可以如下表示：
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210224233814350.png
（截自文首链题解）
由于(1+i)4=(1−i)4=−4(1+i)^4=(1-i)^4=-4，所以原式=2n+2(−4)n44=2n−2+(−1)n42n−22=\frac {2^n+2(-4)^{\frac{n}{4}}} {4}=2^{n-2}+(-1)^{\frac {n} {4}}2^{\frac{n-2}{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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=998244353;
ll qm(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)ans=(ans%M)*(a%M)%M;
        a=a*a%M;
        b>>=1;
    }
    return ans%M;
}
int main()
{
    ll n,ans;
    cin>>n;
    ans=qm(2,n-2>>1);
    if((n/4)&1)ans=M-ans;
    ans+=qm(2,n-2);
    ans%=M;
    printf("%lld",ans);
    return 0;
}

G 机器人

排序问题，高精度（或__int128）

思路

首先所有系数均大于0；

我们可以把机器人的排序问题转化成从初始状态的有限次相邻对换；

接下来我们要判断对换的条件：

假设现有两机器人 i , i + 1 ，传入数据为 X ；
则对换前的传出数据Xold=aiai+1X+ai+1bi+bi+1X_{old}=a_ia_{i+1}X+a_{i+1}b_i+b_{i+1};
对换后的传出数据Xnew=aiai+1X+aibi+1+biX_{new}=a_ia_{i+1}X+a_{i}b_{i+1}+b_{i};

若使Xnew>XoldX_{new}>X_{old}，则需满足ai−1b1>ai+1−1bi+1\frac{a_i-1}{b_1}>\frac{a_{i+1}-1}{b_{i+1}};
即所有机器人应按照ai−1b1\frac{a_i-1}{b_1}升序排列。

由于答案上限在 2120≈2.7e2621^{20}≈2.7e26 左右，所以要高精度处理。

类似于这道题 耍杂技的牛

代码

下面的是高精度的，上面的直接用__int128了，大整数真香

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=998244353;
void print(__int128 x)
{
    if(x < 0)
    {
        x = -x;
        putchar('-');
    }
    if(x > 9) print(x/10);
    putchar(x%10 + '0');
}
struct r
{
    int a,b;
}rob[22];
bool cmp(r a,r b)
{
    return (a.a*1.0-1)/a.b<(b.a*1.0-1)/b.b;
}
int main()
{
    int n,x,a,b,i;
    cin>>n>>x;
    __int128 ans=x;
    for(i=1;i<=n;i++)scanf("%d%d",&rob[i].a,&rob[i].b);
    sort(rob+1,rob+n+1,cmp);
    for(i=1;i<=n;i++)
    ans=ans*rob[i].a+rob[i].b;
    print(ans);
    return 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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=998244353;
vector<int> ans;
vector<int> mul(vector<int> &A, int b)
{
    vector<int>mid;
    int t = 0;
    for(int i = 0; i < A.size() || t; i++)
    {
        if(i < A.size()) t += A[i] * b;
        mid.push_back(t % 10);
        t = t / 10;
    }
    while (mid.size() > 1 && mid.back() == 0)mid.pop_back();
    return mid;
}
struct r
{
    int a,b;
}rob[22];
bool cmp(r a,r b)
{
    return (a.a*1.0-1)/a.b<(b.a*1.0-1)/b.b;
}
int main()
{
    int n,x,a,b,i;
    cin>>n>>x;
    ans.push_back(x);
    for(i=1;i<=n;i++)scanf("%d%d",&rob[i].a,&rob[i].b);
    sort(rob+1,rob+n+1,cmp);
    for(i=1;i<=n;i++)
    {
    	ans=mul(ans,rob[i].a);
    	ans[0]+=rob[i].b;
   	}
    ans=mul(ans,1);
    reverse(ans.begin(), ans.end());
    for(vector<int>::iterator it=ans.begin();it!=ans.end();it++)
    	printf("%d",*it);
    return 0;
}

H 动态最小生成树

贪心，并查集

思路

由于数据比较水，按天空之城的代码直接改就行，暴力过；

注意要保证初始路的顺序，摘取和排序可以用另一个组解决。

代码

天空之城的注释还没删/

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

int fa[2002],cnt[2002];//fa存该城所在集合的根节点（城市），cnt存以该城为根的集合城市数
ll len[2002];//len存以该城为根的集合内部的连通代价

struct road
{
    int fr,to;
    ll lrd;
} rod[30004],z[30004];

bool cmp(road a,road b)
{
    return a.lrd<b.lrd;
}

int find(int x)
{
    if(fa[x]!=x)fa[x]=find(fa[x]);
    return fa[x];
}

int main()
{
    int n,m,q,i,g1,g2;
    ll glen;
    scanf("%d%d%d",&n,&m,&q);
    {
        for(i=1; i<=m; i++)
        {
            scanf("%d%d%lld",&g1,&g2,&glen);
            rod[i].fr=g1,rod[i].to=g2,rod[i].lrd=glen;//存路
        }
        while(q--)
        {
            int o;
            scanf("%d",&o);
            if(o==1)
            {
                scanf("%d%d%d%lld",&i,&g1,&g2,&glen);
                rod[i].fr=g1,rod[i].to=g2,rod[i].lrd=glen;
            }
            else
            {
                int l,r;
                scanf("%d%d",&l,&r);
                for(i=l;i<=r;i++)z[i-l].fr=rod[i].fr,z[i-l].to=rod[i].to,z[i-l].lrd=rod[i].lrd;
                sort(z,z+1+r-l,cmp);
                for(i=1; i<=n; i++)fa[i]=i,cnt[i]=1,len[i]=0; //初始化并查集
                for(i=0; i<=r-l; i++)
                {
                    //printf("%d*%d*%lld\n",z[i].fr,z[i].to,z[i].lrd);
                    int frn=z[i].fr,ton=z[i].to;
                    if(find(frn)!=find(ton))
                    {
                        if(find(frn)>find(ton))swap(frn,ton);//保证两集以较小根为新根
                        cnt[find(frn)]+=cnt[find(ton)];//处理城市数
                        len[find(frn)]+=len[find(ton)]+z[i].lrd;//处理连通代价
                        fa[find(ton)]=find(frn);
                    }
                }
                if(cnt[1]==n)printf("%lld\n",len[1]);
                else printf("Impossible\n",cnt[1]);
            }
        }
    }
    return 0;
}

I 贪吃蛇

bfs

思路

bfs板题，身体不会消失即代表不能回到重复坐标。

注意单位转换。

代码

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<bits/stdc++.h>
using namespace std;
typedef long long ll;
queue<pair<int,int> > que;
const ll M=1000;
int a[102][102]={0},n,m,fi,fj,ti,tj,l[102][102]={0};
void bfs()//l-1;
{
    int di[]={0,1,0,-1},dj[]={1,0,-1,0};
    while(!que.empty())
    {
        pair<int,int> now=que.front();
        que.pop();
        for(int i=0;i<4;i++)
        {
            int ni=now.first+di[i],nj=now.second+dj[i];
            if(ni>=0&&ni<=n&&nj>=0&&nj<=m&&a[ni][nj]==1&&!l[ni][nj])
            {
                l[ni][nj]=l[now.first][now.second]+1;
                que.push({ni,nj});
            }
        }
    }
}
int main()
{
    int i,j;
    string g;
    scanf("%d%d",&n,&m);
    scanf("%d%d",&fi,&fj);
    scanf("%d%d",&ti,&tj);
    for(i=1;i<=n;i++)
    {
        cin>>g;
        for(j=1;j<=m;j++)
        {
            if(g[j-1]=='.')a[i][j]=1;
        }
    }
    l[fi][fj]=1;
    que.push({fi,fj});
    bfs();
    if(l[ti][tj])
    printf("%d00",l[ti][tj]-1);
    else printf("-1");
    return 0;
}

J 天空之城

并查集，贪心

思路

出于由于天空之城具有魔力，如果希达想再走一次自己之前走过的路，则她可以在这条路上不花费任何时间。这一性质，我们可以将目前可以被联通的城市块放入同一个并查集中，如果某条道路可以连接任意两个不同集合中的城市，那么我们就可以认为这两个集合连通，且连通的代价为该路的代价。

至于上一段的“目前”，出于贪心策略，我们应该优先检索代价更低的道路，如果它能连通两个不同集，新集的连通代价即为两该路代价与两旧集的连通代价三者之和，新集的城市数即为两旧集城市数之和。

为方便结果判断，我们可以规定某集合的根为该集合内序号最小的点，如此，如果路网能抵达所有城市，该集合的根即为1，开始时将起始点标记成1号即可；

之后补充：我这不就是Kruskal求的最小生成树嘛，流下了什么都没学过的泪水。

代码

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

int fa[5003],cnt[5003];//fa存该城所在集合的根节点（城市），cnt存以该城为根的集合城市数
ll len[5003];//len存以该城为根的集合内部的连通代价

struct road
{
    int fr,to;
    ll lrd;
}rod[200005];

bool cmp(road a,road b)
{
    return a.lrd<b.lrd;
}

map<string,int> mp;//存城市名与编号的映射

int find(int x)
{
    if(fa[x]!=x)fa[x]=find(fa[x]);
    return fa[x];
}

int main()
{
    int n,q,i;
    while(~scanf("%d%d",&n,&q))
    {
        mp.clear();
        int ccty=0,glen;
        string g1,g2;
        cin>>g1;
        mp[g1]=(++ccty);//将开始城设为1
        for(i=1;i<=q;i++)
        {
            cin>>g1;
            cin>>g2;
            scanf("%d",&glen);
            if(!mp[g1])mp[g1]=++ccty;
            if(!mp[g2])mp[g2]=++ccty;
            rod[i].fr=mp[g2],rod[i].to=mp[g1],rod[i].lrd=glen;//存路
        }
        if(ccty!=n){printf("No!\n");continue;}//如果提到的城市数!=n，则必有城市在路网之外
        sort(rod+1,rod+1+q,cmp);
        for(i=1;i<=n;i++)fa[i]=i,cnt[i]=1,len[i]=0;//初始化并查集
        for(i=1;i<=q;i++)
        {
            int frn=rod[i].fr,ton=rod[i].to;
            if(find(frn)!=find(ton))
            {
                if(find(frn)>find(ton))swap(frn,ton);//保证两集以较小根为新根
                cnt[find(frn)]+=cnt[find(ton)];//处理城市数
                len[find(frn)]+=len[find(ton)]+rod[i].lrd;//处理连通代价
                fa[find(ton)]=find(frn);
            }
        }
        if(cnt[1]==n)printf("%lld\n",len[1]);
        else printf("No!\n");
    }
    return 0;
}

ED

终于不用担心掉分了/

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