补题计划-牛客周赛Round67

牛客周赛Round67

A 题

很简单，暴力处理就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<cstdio>
#include<iostream>
#include<cstring>

using namespace std;

int main()
{
	int n;
	string s;
	cin>>n>>s;
	string s1,s2,s3;
	for(int i=0;i<n;i++){
		if(s[i] >= 'a' && s[i] <= 'z')
			s1 += s[i];
		else if(s[i] >= '0' && s[i] <= '9')
			s2 += s[i];
		else
			s3 += s[i];
	}
	cout<<s1<<s2<<s3<<endl;
	return 0;
}

B 题

写起来非常简单，注意精度问题，最后比较的时候同时乘以分母可以忽略精度问题。比赛时就没想起这个东西，导致分低。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>

using namespace std;

int main()
{
	long long n;
	long long a,b,c,d;
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
		long long ay = c*b/d;
		if(ay*d >= b*c)		ay--;
		cout<<a-ay<<" ";
	}
	return 0;
}

C 题

其实就是限定枚举。只枚举一个，另一个可以通过 C 算出来。复杂度就降低一个。话说比赛时因为以为相加的有无限多个，而直接想错思路，应该是只有两个加分。（哭

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>

using namespace std;
const int maxn = 200010;
int a[maxn];

int main()
{
	int n,c;
	cin>>n>>c;
	int ans = 0;
	for(int i=0;i<=c;i++){
		int b = c - i;
		if(to_string(i).length() + to_string(b).length() + to_string(c).length() + 2 == n)
			ans ++;
	}
	cout<<ans<<endl;
	return 0;
}

D 题

这道题真的可惜，比赛时差一点点就能满分了，但是整体思路没问题。看样例以及稍加分析，就可以看出最优的区间就创造一个像滑动窗口一样的组，长度为 \(n-k+1\) 的一个从 \(1\) 到 \(n-k+1\) 的区间，然后让队头移除窗口，队尾加上刚刚移除的数，这样一定可以构造出一个 k 个的 “极大不同区间”。

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<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>

using namespace std;
const int maxn = 200010;
int a[maxn];

int main()
{
	int n,k;
	cin>>n>>k;
	if(n < k){
		cout<<"NO"<<endl;
	}
	else{
		cout<<"YES"<<endl;
		if(n == k){for(int i=1;i<=n;i++)	cout<<1<<" ";}
		els{e
			for(int i=1;i<=n-k+1;i++){cout<<i<<" ";a[i] = i;}
			a[0] =a[n-k+1];
			for(int i=1;i<=k-1;i++){cout<<a[i % (n-k+1)]<<" ";}
		}
	}
	return 0;
}

剩下两个都没学过了，等到后面学到了，再来补吧，每天学的太多了，基本上没有什么休息时间，全在看代码。