2021牛客寒假算法基础集训营2（C D E F G H I J）

比赛链接：这里

OP

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

C 牛牛与字符串border

最大公因数，字符串

思路

依照样例来说，很像求nn与ll的最大公因数，实际上当 l>n2l>\frac{n}{2} 时，循环节长为 n−ln-l，其余情况即为gcd(n,l)gcd(n,l)，画图推导一下即可，具体证明可以参照文首链题解；

循环节上每一位应该取在当位数量最多的字母，以求更改次数最少。

代码

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

ll gcd(ll a,ll b)
{return b==0?a:gcd(b,a%b);}

int main()
{
    int n,l,i,t;
    char get[100005],ans[100005];
    int mx[100005],cnt[100005][26];
    cin>>t;
    while(t--)
    {
        scanf("%d%d",&n,&l);
        if(2*l>n)l=n-l;
        else l=gcd(l,n);
        scanf("%s",&get);
        for(i=0;i<=l;i++)//初始化，用memset会TLE
        {
            mx[i]=0;
            for(int j=0;j<26;j++)cnt[i][j]=0;
        }
        for(i=0;i<n;i++)
        {
            cnt[i%l][get[i]-'a']++;
            if(cnt[i%l][get[i]-'a']>mx[i%l])//更新当位众数字母
            {
                mx[i%l]=cnt[i%l][get[i]-'a'];
                ans[i%l]=get[i];
            }
        }
        for(i=0;i<n;i++)//输出n个
        {
            printf("%c",ans[i%l]);
        }
        printf("\n");
    }
	return 0;
}

D 牛牛与整除分块

数学

思路

我们先找规律，依照如下两图
在这里插入图片描述

在这里插入图片描述
我们可以发现，在某点之前，对于每一个x，均有一个不同的 ⌊n/x⌋⌊ n / x ⌋，在该点之后，就会存在多个 x 值共用同一个 ⌊n/x⌋⌊ n / x ⌋ 的情况。

我们只需要找到这个分界点 a ，如果 x <= a ，即可直接输出x；否则就输出 ⌊n/a⌋−⌊n/x⌋+a⌊ n / a ⌋-⌊ n / x ⌋+a ，此时 x 当点的商与 a 点的商的差值为 a 点后至 x 点有的不同商值的个数，再加上 a 即为 x 之前存在的不同商值的总数。

现在我们要找到这个 a ：

用函数 f(x)=n/xf(x)=n/x 来讲，我们需要找出一最小整数 a ，满足 f′(a)>=−1f'(a)>=-1 ;
由于 f′(x)=−n/x2f'(x)=-n/x^2 , f′(a)>=−1f'(a)>=-1 即等价于 n/a2<=1n/a^2<=1 ;
即为 a2>=na^2>=n ；
故 a=⌈n⌉a=⌈\sqrt{n}⌉

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,x,sq;//sq即为上文的a
        scanf("%d%d",&n,&x);
        sq=sqrt(n);
        if(sq*sq!=n)sq++;//向上取整
        if(x<=sq)printf("%d\n",x);
        else printf("%d\n",n/sq-n/x+sq);
    }
    return 0;
}

E 牛牛与跷跷板

bfs，双指针

思路

这道题十分明显是bfs，只不过数据量对建图造成了一定的困难；

对于同行，只需要判断相邻两板的左右缘是否相接；

对于临行，可以通过双指针来判断联通；

由于板与板不重叠的限制，我们可以放心用set存储，不会出现去重，而且lineleft与linerig的相同位置存储的必定是同一块板的数据。

代码

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

set<pair<int,int> >linelef[100005],linerig[100005];
set<pair<int,int> >::iterator it1,it2,it3,it4;
vector<int> con[100005];
int n,dis[100005];
queue<int>que;

void dfs()
{
    while(!que.empty())
    {
        int now=que.front();
        que.pop();
        for(int i=0;i<con[now].size();i++)
        {
            //printf("%d %d\n",now,con[now][i]);
            if(!dis[con[now][i]])
            {
                dis[con[now][i]]=dis[now]+1;
                que.push(con[now][i]);
            }
        }
    }
}

int main()
{
    cin>>n;
    int i,lin,gl,gr,lmi=100005,lma=0;
    for(i=1;i<=n;i++)
    {
        scanf("%d%d%d",&lin,&gl,&gr);
        linelef[lin].insert({gl,i});
        linerig[lin].insert({gr,i});
        lmi=min(lmi,lin);//框定行数范围
        lma=max(lma,lin);
    }
    for(i=lmi;i<=lma;i++)//建图
    {
        for(it1=linerig[i].begin(),it2=linelef[i].begin(),it2++;it2!=linelef[i].end();it1++,it2++)//单行扫描建图
        {
            if((*it1).first==(*it2).first)
            {
                con[(*it1).second].push_back((*it2).second);
                con[(*it2).second].push_back((*it1).second);
            }
        }
        if(i!=lma)
        {
            for(it1=linelef[i].begin(),it2=linerig[i].begin(),it3=linelef[i+1].begin(),it4=linerig[i+1].begin()
                ;it1!=linelef[i].end()&&it3!=linelef[i+1].end();)//临行双指针建图
            {
                if((*it2).first<=(*it3).first)it1++,it2++;
                else if((*it1).first>=(*it4).first)it3++,it4++;
                else
                {
                    con[(*it3).second].push_back((*it1).second);
                    con[(*it1).second].push_back((*it3).second);
                    if((*it2).first<=(*it4).first)it1++,it2++;//存在一块板搭多块板的情况，依据右缘判断哪组指针后移
                    else it3++,it4++;
                }
            }
        }
    }
    memset(dis,0,sizeof dis);
    dis[1]=1;//设定1距1距离1，最后减去
    que.push(1);
    dfs();
    printf("%d",dis[n]-1);
	return 0;
}

F 牛牛与交换排序

思路

此题看起来 k 会有好多个可行取值，但是由于下一次做区间翻转的位置将会比上一次更靠右的限制，实际上只有一个可行的 k 。

如果 1 在第 i 位（ i != 1 ），则唯一的可行 k 为 i ，确定 k 后，持续进行模拟操作即可；
如果 1 位置正确，2 在第 i 位（ i != 2 ），则 k 为 i - 2 + 1，同理。
如果 k 已经被确定的情况下，数字 i 既不在第 i 位，也不在第 i + k - 1 位，那就永远不可能排好序了。

本来担心持续的模拟操作会导致TLE，结果来看时间卡得没有那么严。

//悲：
在这里插入图片描述

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main()
{
    int n,i,a[100005],k=0,j,f=1;
    cin>>n;
    for(i=1;i<=n;i++)scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
    {
        if(a[i]!=i)
        {
            if(k==0)//如果k未定义
            {
                for(j=i;j<=n;j++)
                if(a[j]==i)break;
                k=j-i;
                for(j=i;j<=i+k/2;j++)
                swap(a[j],a[2*i+k-j]);
            }
            else if(i+k>n||a[i+k]!=i){f=0;break;}//凉凉
            else if(a[i+k]==i)
            {
                for(j=i;j<=i+k/2;j++)//操作
                swap(a[j],a[2*i+k-j]);
            }
        }
    }
    if(f==0)printf("no");
    else printf("yes\n%d",k+1);
}

G 牛牛与比赛颁奖

代码

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

const int N=2e5+5;
map<int,int>mp;
map<int,int>::iterator it;
int cot[N];

int main()
{
    int n,m;
    cin>>n>>m;
    int l,r;
    for(int i=0;i<m;i++){
        cin>>l>>r;
        mp[l]++;
        mp[r+1]--;
    }
    int linej=0,liney=0,linet=0,
        j=ceil(1.0*n/10),y=ceil(1.0*n/4),t=ceil(1.0*n/2);
    int last=1,cnt=0,maxx=0;
    for(it=mp.begin();it!=mp.end();it++){
        cot[cnt]+=it->first-last;
        last=it->first;
        cnt+=it->second;
        maxx=max(maxx,cnt);
    }
    for(int i=maxx;i>=0;i--){
        cot[i]+=cot[i+1];
        if(cot[i]>=j&&!linej)linej=max(1,i);
        if(cot[i]>=y&&!liney)liney=max(1,i);
        if(cot[i]>=t&&!linet)linet=max(1,i);
    }
    cout<<cot[linej]<<' '<<cot[liney]-cot[linej]<<' '<<cot[linet]-cot[liney]<<'\n';
  return 0;
}

H 牛牛与棋盘

签到题

思路

找规律，输出内容相同的点 横纵坐标之和奇偶性相同。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,i,j;
    cin>>n;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        if((i+j)&1)printf("1");
        else printf("0");
        printf("\n");
    }
}

I 牛牛的“质因数”

思路

我们需要处理出每一个 i 的全部质因数再做处理，首先想到的便是分解定理，奈何时间复杂度略大，具体可以参照下面的第二片代码。

同时，用到质因子的地方还有欧拉筛，在欧拉筛中，每一个合数是被其最小质因子筛掉的，我们便可以利用这个性质，递推处理每一个合数。

具体过程如下：
对于某一合数 i ，假设其被其最小质因子 p 和某数 q 组成的 p * q 筛掉，则 i 的对应值 z[ i ] 即为 -pz[q]- 打不出来标准的表示法，即把 p 接到 z[ q ] 的前面。

具体实现起来，我们要妥善处理位数，对位数的求取一定要慎重，具体可以参照惨案代码片三
//倒腾一晚上求余运算

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 4000006;
const ll M = 1000000007;
static int p[N];
static bool n[N];
static ll w[N],z[N];
int main()
{
    int i,j,c=0;
    n[1]=1,z[1]=0;
    for(i=2; i<N; i++)
    {
        if(!n[i])
        {
            p[c++]=i;
            z[i]=i;//素数对应值是其本身
            ll ten=10;
            for(; ten<i; ten*=10);//求取质数位数
            w[i]=ten;
        }
        for(j=0; j<c&&i*p[j]<N; j++)
        {
            n[i*p[j]]=1;
            z[i*p[j]]=(p[j]*w[i]+z[i])%M;//求取合数对应值
            w[i*p[j]]=w[i]*w[p[j]]%M;//求取合数位数，注意不能用素数求位数的方法
            if(i%p[j]==0)break;
        }
    }
    long long ans=0,n;
    cin>>n;
    for(i=2;i<=n;i++){
        ans+=z[i],ans%=M;}
    printf("%llu",ans);
}

比赛时我的代码只能大概算到1e6，否则就超时，于是我就阶段打表，每1e6算一个结果，对于 n ，只算 n ~ n/1e6*1e6 这段就OK了。代码贴在下面，仅供参考；

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
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 4000006;
const ll M = 1000000007;
static int p[N],w[N];
static bool n[N];
long long a1=631719342,a2=220078001,a3=827425989;
long long wf(long long a)
{
    if(!n[a])return a;
    ll ans=0,i;
    for(i=0; p[i]<=sqrt(a); i++)
    {
        while(a%p[i]==0)
        {
            a/=p[i];
            ans*=w[i];
            ans+=p[i];
            ans%=M;
        }
    }
    if(a>1)
    {
        int ten=10;
        for(; ten<a; ten*=10);
        ans*=ten,ans+=a,ans%=M;
    }
    return ans;
}
int main()
{
    //printf("*");
    int i,j,c=0;
    n[1]=1;
    for(i=2; i<=N; i++)
    {
        if(!n[i])
        {
            p[c++]=i;
            int ten=10;
            for(; ten<i; ten*=10);
            w[c-1]=ten;
        }
        for(j=0; j<c&&i*p[j]<=N; j++)
        {
            n[i*p[j]]=1;
            if(i%p[j]==0)break;
        }
    }
    ll ans,n;
    cin>>n;
    if(n/1000000==0)
    {
        ans=0;
        for(i=1; i<=n; i++)
        {
            ans+=wf(i);
            ans%=M;
            //printf("%5d %10lld\n",i,wf(i));
        }
    }
    else if(n/1000000==1)
    {
        ans=a1;
        for(i=1000001; i<=n; i++)
        {
            ans+=wf(i);
            ans%=M;
        }
    }
    else if(n/1000000==2)
    {
        ans=a2;
        for(i=2000001; i<=n; i++)
        {
            ans+=wf(i);
            ans%=M;
        }
    }
    else
    {
        ans=a3;
        for(i=3000001; i<=n; i++)
        {
            ans+=wf(i);
            ans%=M;
        }
    }
    printf("%lld",ans);
}

//有个同学打了34M的表，交不上去 -_-||

还有一段错误代码，这里对于合数 如果用for求位数，先求位数再取模也不行，只要在过程中历史值进行过取模运算就会改变真实长度，再搭配for求位数结果就是错误的；用成积求位数是，尽管位数本身经过取模，但仍是真实位数的取模值。惨案贴上来供批判

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 4000006;
const unsigned long long M = 1000000007;
static int p[N];
static bool n[N];
static unsigned long long w[N],z[N];
int main()
{
    int i,j,c=0;
    n[1]=1,z[1]=0;
    for(i=2; i<N; i++)
    {
        if(!n[i])
        {
            p[c++]=i;
            z[i]=i;
            ll ten=10;
            for(; ten<i; ten*=10);
            w[i]=ten;
        }
        for(j=0; j<c&&i*p[j]<N; j++)
        {
            n[i*p[j]]=1;
            z[i*p[j]]=(p[j]*w[i]+z[i]);
            unsigned long long ten=10;
            for(; ten<z[i*p[j]]; ten*=10);
            w[i*p[j]]=ten%M;
            z[i*p[j]]%=M;
            if(i%p[j]==0)break;
        }
    }
    unsigned long long ans=0,n;
    cin>>n;
    for(i=2;i<=n;i++){//printf("%4d %9lld %9lld\n",i,z[i],w[i]);
        ans+=z[i],ans%=M;}
    //printf("%4d %9lld %9lld\n",i-1,z[i-1],w[i-1]);
    printf("%llu",ans);
}

J 牛牛想要成为hacker

构造

思路

首先计算可知，n <= 27 时，C( n , 3 ) < n2log2n ，也就是说，此时输出的前 27 项不能含有任何合法组，这里可以用斐波那契数列来解决。

n > 27 时，即可认为 n2⌊ log2n⌋ 中的 ⌊ log2n⌋ 是第一个元素的遍历量，n = 105 时， ⌊ log2n⌋ = 16 ，也就是说此时前16项的任意一项无法与后面的元素组成任何合法组。所以说，为了便于输出，只需要保证第 17 项及之后的每一位均小于等于 第一项/2。在前一种情况中，因为前 27 项均无合法组，所以第 27 项及之后保证每一位均小于等于 第一项/2 即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int f[30]={1,1},a[100005],i;
    for(i=2;i<=28;i++)
    f[i]=f[i-1]+f[i-2];
    for(i=1;i<=27;i++)a[i]=f[i];
    for(i=28;i<=100000;i++)a[i]=1;
    int n;
    cin>>n;
    for(i=1;i<=n;i++)printf("%d ",a[i]);
}

ED

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