• 欢迎光临~

Codeforces Round #799 (Div. 4) B E F G题解

开发技术 开发技术 2022-07-27 次浏览

1. B

problem B

每次删除两个元素,问最后可以保留的最大的序列长度:满足序列中每个元素都不相同。

思路:(map) 来统计一下数字出现的次数。我们接着记录奇数次数以及偶数次数的个数,次数为奇数的显然可以全部保留,对于偶数的 (-1)

点击查看代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<bitset>
#include<ctime>
#include<deque>
#include<stack>
#include<functional>
#include<sstream>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 200005
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const int mod = 1e9 + 7;
#define pi acos(-1.0)
#define pii pair<int,int>
#define eps 1e-5
#define pll pair<ll,ll>
#define lson 2*x
#define rson 2*x+1

long long  qupower(int a, int b) {
	long long  ans = 1;
	while (b) {
		if (b & 1)ans = ans * a;
		b >>= 1;
		a = a * a;
	}
	return ans;
}

inline int read() {
	int an = 0, x = 1; char c = getchar();
	while (c > '9' || c < '0') {
		if (c == '-') {
			x = -1; 
		}
		c = getchar();
	}
	while (c >= '0'&&c <= '9') {
		an = an * 10 + c - '0'; c = getchar();
	}
	return an * x;
}

int t;
int a[52];
map<int,int> mp;

void solve(){
	int n = read();
	ms(a); mp.clear();
	int fg = 0;
	for(int i=0;i<n;i++){
		a[i] = read();
		mp[a[i]]++;
		if(mp[a[i]]>1) fg = 1;
	}
	if(!fg)cout<<n<<endl;
	else{
		int cnt1 = 0;
		int cnt2 = 0;
		for(auto it:mp){
			if(it.second % 2)cnt1++;
			else cnt2++;
		}
		if(cnt2%2)cnt2--;
		cout<<cnt1+cnt2<<endl;
	}

}

int main(){
    //ios::sync_with_stdio(false);
	t = read();
	while(t--){
		solve();
	}
}

2. E

problem E

给定一个仅有 (0,1) 的序列,每次只能删除首尾元素,问经过若干次操作后能不能得到总和为 (s)(subarray).

仅考虑存在解的情况,注意到当固定左端点 (l) 时,我们可以二分右端点(因为总和是递增的)

点击查看代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<bitset>
#include<ctime>
#include<deque>
#include<stack>
#include<functional>
#include<sstream>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 200005
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const int mod = 1e9 + 7;
#define pi acos(-1.0)
#define pii pair<int,int>
#define eps 1e-5
#define pll pair<ll,ll>
#define lson 2*x
#define rson 2*x+1

long long  qupower(int a, int b) {
	long long  ans = 1;
	while (b) {
		if (b & 1)ans = ans * a;
		b >>= 1;
		a = a * a;
	}
	return ans;
}

inline int read() {
	int an = 0, x = 1; char c = getchar();
	while (c > '9' || c < '0') {
		if (c == '-') {
			x = -1; 
		}
		c = getchar();
	}
	while (c >= '0'&&c <= '9') {
		an = an * 10 + c - '0'; c = getchar();
	}
	return an * x;
}

int t;
int a[200003];
int pre_sum[200003];


void solve(){
	int n = read(), s = read();
	ms(a);
	int sum = 0;
	for(int i=1;i<=n;i++){
		a[i] = read(); sum += a[i];
		pre_sum[i] = pre_sum[i - 1] + a[i];
	}
	if(sum<s){cout<<-1<<endl;}
	else if(sum==s) cout<<0<<endl;
	else{
		int ans = 9999999;
		for(int l=1;l<n;l++){
			int r = n;
			int tmp = l;
			int pos = -1;
			while(tmp<=r){
				int mid = (tmp + r) >> 1;
				if(pre_sum[mid]-pre_sum[l-1]<=s){
					pos = mid; tmp = mid+1;
				}
				else r = mid-1;
			}
			if(pos==-1 || pre_sum[pos]-pre_sum[l-1]!=s) continue;
			//cout<<l<<" "<<pos<<endl;
			ans = min(ans, n-(pos-l+1));
		}
		cout<<ans<<endl;
	}
}

int main(){
    //ios::sync_with_stdio(false);
    t = read();
	while(t--){
		solve();
	}
}

3. F

problem F

给定一个序列,问是否存在 (a_i+a_j+a_k) 满足最后一位是 (3).

我们只关注最后一位,所以我们可以先预处理 (a_i%10),最后一位只有 (0sim 9),所以直接暴力即可

点击查看代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<bitset>
#include<ctime>
#include<deque>
#include<stack>
#include<functional>
#include<sstream>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 200005
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const int mod = 1e9 + 7;
#define pi acos(-1.0)
#define pii pair<int,int>
#define eps 1e-5
#define pll pair<ll,ll>
#define lson 2*x
#define rson 2*x+1

long long  qupower(int a, int b) {
	long long  ans = 1;
	while (b) {
		if (b & 1)ans = ans * a;
		b >>= 1;
		a = a * a;
	}
	return ans;
}

inline int read() {
	int an = 0, x = 1; char c = getchar();
	while (c > '9' || c < '0') {
		if (c == '-') {
			x = -1; 
		}
		c = getchar();
	}
	while (c >= '0'&&c <= '9') {
		an = an * 10 + c - '0'; c = getchar();
	}
	return an * x;
}

int t;
int a[200003];
map<int,int> mp;
int res[200003];

int get_last_digit(int x){
	return x%10;
}

bool check(int x){
	return x%10==3;
}

void solve(){
	int n = read();
	ms(a); ms(res); mp.clear();
	for(int i=0;i<n;i++)a[i] = read(), a[i] = get_last_digit(a[i]);
	int cnt=0;
	for(int i=0;i<n;i++){
		if(mp[a[i]]>3)continue;
		res[cnt] = a[i];
		mp[a[i]]++; cnt++;
	}
	int fg = 0;
	for(int i=0;i<cnt;i++){
		for(int j=i+1;j<cnt;j++){
			for(int k=j+1;k<cnt;k++){
				if(check(res[i]+res[j]+res[k])){
					fg = 1;
					break;
				}
			}
			if(fg)break;
		}
		if(fg)break;
	}
	if(fg)cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
}

int main(){
    //ios::sync_with_stdio(false);
    t = read();
	while(t--){
		solve();
	}
}

4. G

problem G

给定一个序列,找到满足条件的 (subarray) ([a_i,...,a_k]) 数量:

[2^0cdot a_i<2^1cdot a_{i+1}<...<2^kcdot a_{i+k} ]

其中 (1leq ileq n-k)

思路:注意到不等式的传递性,我们只需要满足:

[a_i<2cdot a_{i+1} ]

我们用一个新的数组来记录: (b_i=1) 当满足上述条件。
那么我们只需要用前缀和就可以求解出来了。

点击查看代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<bitset>
#include<ctime>
#include<deque>
#include<stack>
#include<functional>
#include<sstream>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 200005
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const int mod = 1e9 + 7;
#define pi acos(-1.0)
#define pii pair<int,int>
#define eps 1e-5
#define pll pair<ll,ll>
#define lson 2*x
#define rson 2*x+1

long long  qupower(int a, int b) {
	long long  ans = 1;
	while (b) {
		if (b & 1)ans = ans * a;
		b >>= 1;
		a = a * a;
	}
	return ans;
}

inline int read() {
	int an = 0, x = 1; char c = getchar();
	while (c > '9' || c < '0') {
		if (c == '-') {
			x = -1; 
		}
		c = getchar();
	}
	while (c >= '0'&&c <= '9') {
		an = an * 10 + c - '0'; c = getchar();
	}
	return an * x;
}

int t;
int n,k;
int a[200003], b[200003], sum[200003];

void solve(){
	n = read(); k = read();
	ms(a);ms(b);ms(sum);
	for(int i=1;i<=n;i++) a[i] = read();
	for(int i=1;i<=n-1;i++){
		if(a[i]<2*a[i+1])b[i] = 1;
	}
	b[n] = 1;
	for(int i=1;i<n;i++)sum[i] = sum[i-1]+b[i];
	int ans = 0;
	for(int i=1;i<=n-k;i++){
		if(sum[i+k-1]-sum[i-1]==k)ans++;
	}
	cout<<ans<<endl;
}

int main(){
    //ios::sync_with_stdio(false);
    t = read();
	while(t--){
		solve();
	}
}
程序员灯塔
转载请注明原文链接:Codeforces Round #799 (Div. 4) B E F G题解
喜欢 (0)