Codeforces Round 905 (Div. 2)(VP-6,寒假加训)

发布时间:2024年01月05日

VP时间

A.

删除k,k无关

k奇数删两边+中间

k偶数删两边

拿个桶计数一下,如果是1,2222222就yes(多个样例,初始化)

2的倍数

计算出个数

偶数有几个,偶数不用管,只要对称排布就行了

奇数有几个,奇数分偶数+1,偶数继续对称排布,1只能有一个

1.ac

B.

操作,++

看哪个数更快变成k的倍数(包括1)就可以了

这样就是k的倍数

比较更快变成k的倍数还是k的前一个倍数:ans=min(ans,k-a[i]%k)防止a[i]>k;

7 4

9 5 1 5 9 5 1

1+1=2;

1+1=2;

2*2=4;

cout<<2;

数据范围k(2,5);

2,3,5 质数就必须要a[i]=k*n

4 合数可以分开+

也只有一种办法2*2;比较这个就可以了

找一下有没有超过2个1

没有就是质数的ans

有操作次数为2

还有别的办法可以打表

存在6(2*3)

10(2*5)

也得计算

分开计数吧

5,7,9

都只需要2就可以完成

如果有6,10

就只需要1个

1.tle

为什么能tle?

可能是memset

2.wa

只有一个2没考虑到

如果只有一个2这种应该记录在6,10

写ans比较最后输出ans比较好

3.wa(可能是忘记考虑7+1==8==4*4)(貌似不是4.wa)

重新分类讨论一下

如果k=2,3,5;

就直接ans=min(ans,k-a[i]%k)

如果k=4;

要质因子分解

只需要2次操作两次到2*2

只需要1次操作一次到2*2,以及a[i]==3

元素范围小

开个桶很复杂

//

讨论一下这里面的数要么是奇数,要么是偶数

有偶数就1次

没有偶数有奇数没有3就2次,有3就一次

5.wa

7也是一次

6.wa

return?

7.wa

k==4计算偶数有2就0

有1就1

有0就2

3,7情况包含到

ans=min(ans,k-a[i]%k);

8.ac

题解

A.

// Problem: A. Chemistry
// Contest: Codeforces - Codeforces Round 905 (Div. 2)
// URL: https://codeforces.com/contest/1888/problem/A
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//へ     /|
//  /\7    ∠_/
//  / │   / /
// │ Z _,< /   /`ヽ
// │     ヽ   /  〉
//  Y     `  /  /
// イ● 、 ●  ??〈  /
// ()  へ    | \〈
//  >ー 、_  ィ  │ //
//  / へ   / ノ<| \\
//  ヽ_ノ  (_/  │//
//	  7       |/
//	  >―r ̄ ̄`ー―_
#include <iostream>
#include <cstring>
#include <iomanip>
#include <ctime>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define eps 1e-5
#define INF 1e9
using namespace std;
typedef long long ll;
const int N =100;
int c[N];
void solve() {
	int n,k;
	cin>>n>>k;
	string s;
	cin>>s;
	for(int i=0;i<=27;i++){
		c[i]=0;
	}
	for(int i=0;i<n;i++){
		c[s[i]-'a']++;
	}
	int ans=0;
	for(int i=0;i<=27;i++){
		if(c[i]&1){
			ans++;
		}
	}
	if(ans<=1){
		cout<<"YES"<<'\n';
	}else{
		if(k>=ans-1){
			cout<<"YES"<<'\n';
		}else{
			cout<<"NO"<<'\n';
		}
	}


}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int q;
	cin >> q;
	while (q--) {
		solve();
	}

	return 0;
}

B.

// Problem: B. Raspberries
// Contest: Codeforces - Codeforces Round 905 (Div. 2)
// URL: https://codeforces.com/contest/1888/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//へ     /|
//  /\7    ∠_/
//  / │   / /
// │ Z _,< /   /`ヽ
// │     ヽ   /  〉
//  Y     `  /  /
// イ● 、 ●  ??〈  /
// ()  へ    | \〈
//  >ー 、_  ィ  │ //
//  / へ   / ノ<| \\
//  ヽ_ノ  (_/  │//
//	  7       |/
//	  >―r ̄ ̄`ー―_
#include <iostream>
#include <cstring>
#include <iomanip>
#include <ctime>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define eps 1e-5
#define INF 1e9
using namespace std;
typedef long long ll;
const int N = 2e6 + 9;
int a[N];
void solve() {
	int n,k;
	cin>>n>>k;
	if(k!=4){
		int ans=INF;
		for(int i=1;i<=n;i++){
			int x;
			cin>>x;
			ans=min(ans,x%k?k-x%k:0);
		}
		cout<<ans<<'\n';
	}else{
		int res=INF,cnt=0;
		for(int i=1;i<=n;i++){
			int x;
			cin>>x;
			res=min(res,x%k?k-x%k:0);
			if(cnt<2 && !(x&1)){
				cnt++;
			}
		}
		cout<<min(res,2-cnt)<<'\n';
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int q;
	cin >> q;
	while (q--) {
		solve();
	}

	return 0;
}

C.

找最后一个重复数字的index,和前面重复的边界

剩余的就是有效的

// Problem: C. You Are So Beautiful
// Contest: Codeforces - Codeforces Round 905 (Div. 2)
// URL: https://codeforces.com/contest/1888/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//へ     /|
//  /\7    ∠_/
//  / │   / /
// │ Z _,< /   /`ヽ
// │     ヽ   /  〉
//  Y     `  /  /
// イ● 、 ●  ??〈  /
// ()  へ    | \〈
//  >ー 、_  ィ  │ //
//  / へ   / ノ<| \\
//  ヽ_ノ  (_/  │//
//	  7       |/
//	  >―r ̄ ̄`ー―_
#include <iostream>
#include <cstring>
#include <iomanip>
#include <ctime>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define eps 1e-5
#define INF 1e9
using namespace std;
typedef long long ll;
const int N = 2e6 + 9;
ll a[N],pre[N],suf[N];
void solve() {
	set<ll>st;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		if(!st.count(a[i])){
			st.insert(a[i]);
			pre[i]=1;
		}
	}
	st.clear();
	for(int i=n;i>=1;i--){
		if(!st.count(a[i])){
			st.insert(a[i]);
			suf[i]=1;
		}
	}
	ll ans=0,sum=0;
	for(int i=1;i<=n;i++){
		sum+=pre[i];
		pre[i]=0;
		if(suf[i]==1){
			ans+=sum;
			suf[i]=0;
		}	
	}
	cout<<ans<<'\n';
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int q;
	cin >> q;
	while (q--) {
		solve();
	}
	return 0;
}

文章来源:https://blog.csdn.net/Lanthamum/article/details/135407178
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。