算法 数学 欧拉函数

2022牛客寒假算法基础集训营1

2022牛客寒假训练营1补题

Posted by zhangmh on 2022-01-25
Estimated Reading Time 12 Minutes
Words 2.5k In Total
Viewed Times

不是说好了基础训练营嘛，，，蒟蒻落泪

讲解的老师讲得很好，有兴趣可以看一下题喔 链接

目录

A-九小时九个人九扇门

[C-Baby’s first attemp on CPU](#C-Baby’s first attemp on CPU)

D-牛牛做数论

E-炸鸡块君的高中回忆

F-中位数切分

H-牛牛看云

I-B站与各唱各的

J-小朋友做游戏

L-牛牛学走路

A-九小时九个人九扇门

img

思路：看了题解，有个规律可以记一下：对于一个数字，对9取模的值为它的根，若取模为0，根为9。那就可以转化为01背包问题了，f[i][j]表示前i个满足根为j的种类数。

AC代码：

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;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=998244353;
const int N=1e5+5;
int n,a[N],f[N][15];

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
    	f[i][a[i]%9]=1;
    	for(int j=0;j<=8;j++)
    	{
    		int tmp=a[i]%9;
    		if(f[i-1][(j-tmp+9)%9])
    		{
    			f[i][j]=(f[i-1][(j-tmp+9)%9]+f[i][j])%mod;
			}
			f[i][j]=(f[i][j]+f[i-1][j])%mod;
		}
	}
	for(int i=1;i<=8;i++)
	cout<<f[n][i]<<' ';
	cout<<f[n][0]<<'\n';
	return 0;
}

os：有用的结论记一波

C-Baby’s first attemp on CPU

img

思路： 直接模拟，若要满足不存在先写后读问题至少要加入几条空语句。

AC代码：（看的网友代码，很奇妙）

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;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
int n,a[105],t; //a[i]计算到第i个语句前面一共有多少语句

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    	a[i]=a[i-1];
    	for(int j=1;j<=3;j++)
    	{
    		cin>>t;
    		if(t==1)
    		{
    			a[i]=max(a[i],a[i-j]+3);
			}
		}
		a[i]++;//每加一个语句，a[i]++
	}
	cout<<a[n]-n<<'\n';
	return 0;
}

os：多看别人的代码，学学大佬们怎么想题，，这个题读题想题意花了好久

D-牛牛做数论

img

思路： 第一个问题的答案是前若干个素数的成绩中小于n最大的一个，第二个问题是小于n最大的素数，欧拉函数的相关知识复习。证明：（标解）

img

AC代码：

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;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
int prime[20]={2,3,5,7,11,13,17,19,23,29,31};
int t,n;

bool isprime(int x)
{
	if(x==2||x==3) return true;
	for(int i=2;i<=sqrt(x);i++)
	if(x%i==0) return false;
	return true;
}

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>n;
    	if(n==1) cout<<"-1"<<'\n';
    	else
    	{
    		int i=0;
    		ll ans=1;
    		while(ans*prime[i]<=n)
    		ans*=prime[i++];
    		cout<<ans<<' ';
    		while(!isprime(n))
    		n--;
    		cout<<n<<'\n';
		}
	}
	return 0;
}

os：有一点要学习：怎样找小于n的最大素数。。。

E-炸鸡块君的高中回忆

img

思路：除法和余数的分类讨论。数据范围较大，直接循环模拟会TLE。

AC代码：

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;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
ll t,n,m;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>n>>m;
    	if(m==1&&n!=1) cout<<"-1"<<'\n';
    	else if(n==m) cout<<"1"<<'\n';
    	else if(m==2) cout<<(n-3)*2+3<<'\n';
    	else
    	{
    		ll cnt=n/(m-1);
    		if(n%(m-1)==0||n%(m-1)==1) cout<<cnt*2-1<<'\n';
    		else cout<<cnt*2+1<<'\n';
		}
	}
	return 0;
}

os：这个题多少坑了点，，，一千多人过题，交了九千多次，我也卡了好久

F-中位数切分

img

思路： 简单思路是遍历数组之后计算大于等于m的个数，还有小于m的个数，若两个差值大于0，输出差值；若小于等于0，输出-1。贴证明：

img

img

img

AC代码：

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<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=1e5+5;
int t,n,m;
int a[N];

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    scanf("%d",&t);
    while(t--)
    {
    	scanf("%d%d",&n,&m);
    	memset(a,0,sizeof(a));
    	int cnt1=0,cnt2=0;
    	for(int i=1;i<=n;i++) 
    	{
    		scanf("%d",&a[i]);
    		if(a[i]>=m) cnt1++;
    		else cnt2++;
		}
		if(cnt1-cnt2>0)
		printf("%d\n",cnt1-cnt2);
		else printf("-1\n");
	}
	return 0;
}

H-牛牛看云

img

思路： 可以发现a[i]的值很小，且在组合求和的时候极限数据下会有很多重复值，利用这一点求解，值得注意的是，若两个数相等时，算贡献时为a[i]+C(a[i],2)，不能直接用a[i]*a[j]。

AC代码：

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;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=1e3;
int n,x;
int a[N+1]; 

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>x,a[x]++;
    ll ans;
    for(int i=0;i<=1000;i++)
    {
    	for(int j=i;j<=1000;j++)
    	{
    		ll res;
    		if(i==j) res=a[i]+a[i]*(a[i]-1ll)/2ll;
    		else res=a[i]*a[j];
    		ans+=res*(ll)abs(i+j-1000);
		}
	}
	cout<<ans<<'\n';
	return 0;
}

os：比赛的时候想到重复值这个问题了，但是没想到怎么处理www

I-B站与各唱各的

img

思路： 若每个人选择唱的概率均为p，那么结果是m乘每句唱成功的概率。成功概率=1-失败概率，失败概率为两种失败情况的和，即所有人唱了这一句和这一句没有人唱，即p^n+(1-p)^n，当p=1/2时取得最小值，最后成功的概率为(2^n-2)/2^n，结果就是m*(2^n-2)/2^n，注意是以逆元形式计算结果。

AC代码：

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;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
ll t,n,m;

ll pmod(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1) res=res*a%mod;
		b/=2;
		a=a*a%mod;
	}
	return res%mod;
}

ll inv(ll x)
{
	return pmod(x,mod-2);
}

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>n>>m;
    	cout<<(pmod(2,n)-2)*m%mod*inv(pmod(2,n))%mod<<'\n';
	}
	return 0;
}

os:取模运算也不熟练。。。

J-小朋友做游戏

img

思路： 注意A的最小取值，是n/2向上取整。先取最少的A小朋友数，剩下的取最大的幸福度，小小的贪心思想。

AC代码：

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

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=1e4+5;
int t;
int A,B,n;
int a[N],b[N],c[N*2];

bool cmp(int a,int b)
{
	return a>b;
}

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>A>>B>>n;
    	memset(a,0,sizeof(a));
    	memset(b,0,sizeof(b));
    	memset(c,0,sizeof(c));
    	for(int i=1;i<=A;i++) cin>>a[i];
    	for(int i=1;i<=B;i++) cin>>b[i];
    	int cnt=(int)ceil(((double)n/2));
    	if(A>=cnt)
    	{
    		sort(a+1,a+1+A,cmp);
    		sort(b+1,b+1+B,cmp);
    		int ans=0;
    		for(int i=1;i<=cnt;i++)
    		ans+=a[i];
    		int tot=0;
    		for(int i=cnt+1;i<=A;i++)
    		c[++tot]=a[i];
    		for(int i=1;i<=B;i++)
    		c[++tot]=b[i];
    		sort(c+1,c+1+A-cnt+B,cmp);
    		for(int i=1;i<=n-cnt;i++)
    		ans+=c[i];
    		cout<<ans<<'\n';
		}
		else cout<<"-1"<<'\n';
	}
	return 0;
}

os：之前的比赛中学到的ceil()函数，很好用！

L-牛牛学走路

img

思路：每走一步计算一次距离原点的距离，取最大值。

AC代码：

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<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
int t,n;
string s; 

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>n;
    	cin>>s;
    	int x=0,y=0;
    	double ans=0;
    	for(int i=0;i<n;i++)
    	{
    		if(s[i]=='U') y++;
    		if(s[i]=='D') y--;
    		if(s[i]=='R') x++;
    		if(s[i]=='L') x--;
    		ans=max(ans,sqrt(y*y+x*x));
		}
		printf("%.10lf\n",ans);
	}
	return 0;
}

没补的题里看到有一个之前没见过的点，ST表，去了解一下咯

若有错误请赐教

Orz

If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

FEATURED TAGS
算法 数学 欧拉函数
FRIENDS
ESC