# Codeforces Round #529(Div.3)个人题解

时间：2024-01-16 10:13:02

Codeforces Round #529(Div.3)个人题解

前言： 闲来无事补了前天的cf，想着最近刷题有点点怠惰，就直接一场cf一场cf的刷算了，以后的题解也都会以每场的形式写出来

A. Repeating Cipher

传送门

题意：第一个字母写一次，第二个字母写两次，依次递推，求原字符串是什么

题解：1、2、3、4，非常明显的d=1的等差数列，所以预处理一个等差数列直接取等差数列的每一项即可

代码：

#include<bits/stdc++.h>

using namespace std;

int num[100000];

void init(){

	int ans=0;

	for(int i=1;i<=1000;i++){

		ans+=i;

		num[i]=ans;

	}

	return;

}

char str[10000];

int main(){

	int n;

	init();

	scanf("%d %s",&n,str+1);

	int tmp=1;

	while(num[tmp]!=n){

		tmp++;

	}

	for(int i=1;i<=tmp;i++){

		cout<<str[num[i]];

	}

	cout<<endl;

}

B. Array Stabilization

传送门

题意：给你一串数字，要你删除一个数最小化这串数字中最大值-最小值的差

题解：用multiset存一下，然后讨论删去最大的数更好还是删去最小的数更好

代码：

#include <map>

#include <set>

#include <cmath>

#include <ctime>

#include <stack>

#include <queue>

#include <cstdio>

#include <cctype>

#include <bitset>

#include <string>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <functional>

#define PI acos(-1)

#define eps 1e-8

#define fuck(x) cout<<#x<<" = "<<x<<endl;

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define FIN freopen("input.txt","r",stdin);

#define FOUT freopen("output.txt","w+",stdout);

//#pragma comment(linker, "/STACK:102400000,102400000")

using namespace std;

typedef long long LL;

typedef unsigned long long ull;

typedef pair<int, int> PII;

const int maxn = 3e5 + 5;

const LL INF = 1e18 + 7;

const ull mod = 9223372034707292160;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}

LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}

LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}

double dpow(double a, LL b) {double ans = 1.0; while (b) {if (b % 2)ans = ans * a; a = a * a; b /= 2;} return ans;}

multiset<int> s;

int main() {

#ifndef ONLINE_JUDGE

	FIN

#endif

	int n;

	cin >> n;

	int x;

	for (int i = 0; i < n; i++) {

		scanf("%d", &x);

		s.insert(x);

	}

	multiset<int>::iterator it;

	it = s.begin();

	int minn = *it;

	it = s.end();

	it--;

	int maxx = *it;

	if (s.count(minn) != 1 && s.count(maxx) != 1) {

		cout << maxx - minn << endl;

	} else if (s.count(minn) == 1 && s.count(maxx) == 1) {

		it = s.begin();

		it++;

		int tmp1 = *it;

		it = s.end();

		it--;

		it--;

		int tmp2 = *it;

		int ans1 = maxx - tmp1;

		int ans2 = tmp2 - minn;

		cout << min(ans1, ans2) << endl;

	} else {

		if (s.count(minn) == 1) {

			it = s.begin();

			it++;

			cout << maxx - *it << endl;

		} else {

			it = s.end();

			it--;

			it--;

			cout << *it - minn << endl;

		}

	}

}

C. Powers Of Two

传送门

题意：给你一个数n，要求你用k个2的幂次数去拼出这个数，如果不能输出-1

题解：先将n转换为相对应的二进制数 ，如果n的二进制数中的1的个数大于k，显然是没有解的，如果n的二进制数中的1的个数小于1，那么就把每一个大于2的数分解（x->x/2+x/2），凑出k个1即可，最后输出 一下就行

代码

#include <map>

#include <set>

#include <cmath>

#include <ctime>

#include <stack>

#include <queue>

#include <cstdio>

#include <cctype>

#include <bitset>

#include <string>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <functional>

#define PI acos(-1)

#define eps 1e-8

#define fuck(x) cout<<#x<<" = "<<x<<endl;

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define FIN freopen("input.txt","r",stdin);

#define FOUT freopen("output.txt","w+",stdout);

//#pragma comment(linker, "/STACK:102400000,102400000")

using namespace std;

typedef long long LL;

typedef unsigned long long ull;

typedef pair<int, int> PII;

const int maxn = 3e5 + 5;

const LL INF = 1e18 + 7;

const ull mod = 9223372034707292160;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}

LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}

LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}

double dpow(double a, LL b) {double ans = 1.0; while (b) {if (b % 2)ans = ans * a; a = a * a; b /= 2;} return ans;}

int main() {

#ifndef ONLINE_JUDGE

	FIN

#endif

	LL n, k;

	cin >> n >> k;

	if (k > n) {

		cout << "NO" << endl;

	} else {

		multiset<int> ans;

		multiset<int>::iterator it;

		for (int i = 0; i < 30; i++)

			if ((n >> i) & 1)

				ans.insert(i);

		if (ans.size() > k)

		{

			cout << "NO";

			return 0;

		}

		cout << "YES\n";

		while ((int)ans.size() < k)

		{

			it = ans.end();

			it--;

			int x = (*it);

			ans.erase(ans.lower_bound(x));

			ans.insert(x - 1);

			ans.insert(x - 1);

		}

		for (it = ans.begin(); it != ans.end(); it++)

			cout << (1 << *it) << " ";

		return 0;

	}

}

D. Circular Dance

传送门

题意：n个人围成一圈，每个人报出接下来两个人的序号，但是不保证按照顺序来，求解这一圈人的编号顺序，题目有spj

题解：将每个人报的编号想成两个点，然后就行成了一个图的关系，那么现在我们就只需要判定这个图的连通性即可

代码：

#include <map>

#include <set>

#include <cmath>

#include <ctime>

#include <stack>

#include <queue>

#include <cstdio>

#include <cctype>

#include <bitset>

#include <string>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <functional>

#define PI acos(-1)

#define eps 1e-8

#define fuck(x) cout<<#x<<" = "<<x<<endl;

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define FIN freopen("input.txt","r",stdin);

#define FOUT freopen("output.txt","w+",stdout);

//#pragma comment(linker, "/STACK:102400000,102400000")

using namespace std;

typedef long long LL;

typedef unsigned long long ull;

typedef pair<int, int> PII;

const int maxn = 3e5 + 5;

const LL INF = 1e18 + 7;

const ull mod = 9223372034707292160;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}

LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}

LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}

double dpow(double a, LL b) {double ans = 1.0; while (b) {if (b % 2)ans = ans * a; a = a * a; b /= 2;} return ans;}

vector<int> ans;

vector<int> mp[maxn];

bool check(int a, int b) {

	for (int i = 0; i < mp[a].size(); i++) {

		if (mp[a][i] == b) {

			return 1;

		}

	}

	return 0;

}

int get_next(int x){

	int v1=mp[x][0];

	int v2=mp[x][1];

	if(check(v1,v2)){

		return v1;

	}

	return v2;

}

int main() {

#ifndef ONLINE_JUDGE

	FIN

#endif

	int n;

	scanf("%d", &n);

	int u, v;

	for (int i = 1; i <= n; i++) {

		scanf("%d%d", &u, &v);

		mp[i].push_back(u);

		mp[i].push_back(v);

	}

	if (n == 3) {

		cout << "1 2 3" << endl;

		return 0;

	}

	ans.push_back(1);

	while (ans.size() < n) {

		int val = ans.back();

		int nxt = get_next(val);

		ans.push_back(nxt);

	}

	for (int i = 0; i < ans.size(); i++) {

		if (i)

			cout << " ";

		cout << ans[i];

	}

	cout << endl;

}

E. Almost Regular Bracket Sequence

传送门

题意：给你一个括号序列，你需要翻转其中一个括号使得括号序列合法，求应该翻哪个，有spj

题解：我们可以用前缀和来很好的解决括号匹配问题，首先我们规定‘（’是1，‘）’是-1求出这个序列的前缀和，然后用一个数组来记录从后往前的前缀和的最小值，最后从前往后扫一遍，判断翻转这个位置是否能够使得序列合法即可

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+5;

string str;

int n;

bool check(string str){

	int len=str.length();

	int tmp=len/2;

	for(int i=0;i<tmp;i++){

		if(str[i]!=str[len-i]) return 0;

	}

	return 1;

}

int sum[maxn];

int minn[maxn];

int main(){

	cin>>n>>str;

	sum[0]=0;

	for(int i=0;i<n;i++){

		if(str[i]=='(') sum[i+1]=sum[i]+1;

		else if(str[i]==')') sum[i+1]=sum[i]-1;

	}

	minn[n]=sum[n];

	for(int i=n-1;i>=0;i--){

		minn[i]=min(minn[i+1],sum[i]);

	}

	int ans=0;

	for(int i=0;i<n;i++){

		if(sum[i]<0) break;

		int tmp=sum[i];

		if(str[i]==')'){

			tmp++;

		}else if(str[i]=='('){

			tmp--;

		}

		if(tmp<0) continue;

		if(sum[n]-sum[i+1]+tmp!=0) continue;

		if(minn[i+1]-sum[i+1]+tmp<0) continue;

		ans++;

 	}

 	cout<<ans<<endl;

}

F. Make It Connected

传送门

题意：给你一个无向图，有n个点，每个点有一个权值，从a点走到b点的花费是a、b的权值和，有m条边可以连接，如果连接u和v则花费w的权值，当然也可以选择不连，求使得这个图联通的最小花费

题解：我们找到一个起点，要想使得这个生成这个图的花费最小，那么起点一定是权值最小的那个，连边时将这个起点和所有的点连接起来，然后最后跑一个最小生成树即可

代码

#include <map>

#include <set>

#include <cmath>

#include <ctime>

#include <stack>

#include <queue>

#include <cstdio>

#include <cctype>

#include <bitset>

#include <string>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <functional>

#define PI acos(-1)

#define eps 1e-8

#define fuck(x) cout<<#x<<" = "<<x<<endl;

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define FIN freopen("input.txt","r",stdin);

#define FOUT freopen("output.txt","w+",stdout);

//#pragma comment(linker, "/STACK:102400000,102400000")

using namespace std;

typedef long long LL;

typedef unsigned long long ull;

typedef pair<int, int> PII;

const int maxn = 3e5 + 5;

const LL INF = 1e18 + 7;

const ull mod = 9223372034707292160;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}

LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}

LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}

double dpow(double a, LL b) {double ans = 1.0; while (b) {if (b % 2)ans = ans * a; a = a * a; b /= 2;} return ans;}

int n, m;

LL a[maxn];

struct EDGE {

	int u, v;

	LL w;

	bool operator < (const EDGE&a) {

		return w < a.w;

	}

}edge[maxn<<2];

int f[maxn];

int find(int x){

	return x==f[x]?x:f[x]=find(f[x]);

}

int main() {

#ifndef ONLINE_JUDGE

	FIN

#endif

	cin>>n>>m;

	int minn=0;

	a[0]=INF;

	for(int i=1;i<=n;i++){

		scanf("%lld",&a[i]);

		if(a[i]<a[minn]) minn=i;

	}

	for(int i=1;i<=n;i++){

		edge[i]=(EDGE){i,minn,a[i]+a[minn]};

		f[i]=i;

	}

	for(int i=n+1;i<=n+m;i++){

		scanf("%d%d%lld",&edge[i].u,&edge[i].v,&edge[i].w);

	}

	sort(edge+1,edge+1+n+m);

	LL ans=0;

	for(int i=1;i<=n+m;i++){

		int u=find(edge[i].u);

		int v=find(edge[i].v);

		if(u!=v){

			f[u]=v;

			ans+=edge[i].w;

		}

	}

	cout<<ans<<endl;

}

相关文章