C/C++教程

Codeforces Round #733

本文主要是介绍Codeforces Round #733,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

image

  • 只要统计一下给的数字中最大的那一位十位数就是所求答案
#include <bits/stdc++.h>
using namespace std;

void solve(){
	int n;
	cin >> n;
	int maxn = -1;
	while(n){
		maxn = max(maxn, n % 10);
		n /= 10;
	}
	cout << maxn << endl;
}
int main(){
	int t;
	cin >> t;
	while(t --){
		solve();
	}
	
	return 0;
}

image
image

  • 贪心 + 模拟,为了使1的数量尽可能多,需要讨论一下行和列的奇偶性
#include <bits/stdc++.h>
using namespace std;

int maze[22][22];
void solve(){
	int h, w;
	cin >> h >> w;
	memset(maze, 0, sizeof maze);
	if(h % 2 == 0 && w % 2 == 0){
		for(int i = 1; i <= w; i += 2)
			maze[1][i] = 1, maze[h][i] = 1;
		for(int i = 3; i <= h - 2; i += 2)
			maze[i][1] = 1, maze[i][w] = 1;
	}else if(h % 2 == 1 && w % 2 == 1){
		for(int i = 1; i <= w; i += 2)
			maze[1][i] = 1, maze[h][i] = 1;
		for(int i = 3; i <= h; i += 2)
			maze[i][1] = 1, maze[i][w] = 1;
	}else if(h % 2 == 0 && w % 2 == 1){
		for(int i = 1; i <= w; i += 2)
			maze[1][i] = 1, maze[h][i] = 1;
		for(int i = 3; i <= h - 2; i += 2)
			maze[i][1] = 1, maze[i][w] = 1;
	}else if(h % 2 == 1 && w % 2 == 0){
		for(int i = 1; i <= w; i += 2)
			maze[1][i] = 1, maze[h][i] = 1;
		for(int i = 3; i <= h - 2; i += 2)
			maze[i][1] = 1, maze[i][w] = 1;
	}
	for(int i = 1; i <= h; i ++){
		for(int j = 1; j <= w; j ++)
			cout << maze[i][j];
		cout << endl;
	}
}
int main(){
	int t;
	cin >> t;
	while(t --){
		solve();
	}
	
	return 0;
}

image
image

  • 一道思维 + 贪心题目,很有意思,重点是在贪心过程中不断更新和弹出需要进来的那个值,对于A来说,为了使他尽可能胜利,那么每次进来新的值为100则为最优,并且弹出去的是之前进入的最小的那个,对于B,每次都给他放入一个0,这样能保证差距最大,速度也最快。
    可恶的是当时队列没在函数里更新,导致一直WA在第二个样例
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int a[N], b[N];

int cnt;
void solve(){
	priority_queue<int> p11, p22;
	int n;
	cin >> n;
	for(int i = 1; i <= n; i ++){
		int x;
		cin >> x;
		p11.push(x);
		a[i] = x;
	}
	for(int i = 1; i <= n; i ++){
		int x;
		cin >> x;
		p22.push(x);
		b[i] = x;
	}
	sort(a + 1, a + 1 + n, greater<int>());
	sort(b + 1, b + 1 + n, greater<int>());
	int sum1 = 0, sum2 = 0;
	for(int i = 1; i <= n - n / 4; i ++){
		int t = p11.top();
		p11.pop();
		sum1 += t;
		t = p22.top();
		p22.pop();
		sum2 += t;
	}
	if(sum1 >= sum2){
		cout << 0 << endl;
		return;
	}
	int ans = 0;
	int flag = n - n / 4;
	while(sum1 < sum2){
		++ ans;
		if((n + ans) % 4 == 0){
			if(flag){
				sum1 -= a[flag];
				flag --;
				sum1 += 100;
			}else
				sum1 += 100;
		}else{
			sum1 += 100;
		}
		
		if(p22.size()){
			if((n + ans) % 4 == 0){
				sum2 += 0;
			}else{
				sum2 += p22.top();
				p22.pop();
			}
		}else
			sum2 += 0;
	}
		cout << ans << endl;
}
int main(){
	int t;
	cin >> t;
	while(t --){
		cnt ++;
		solve();
	}
	
	return 0;
}

image
image

  • 一道图论题
    关键在于如何处理那些没人爱和有花给不了的人,对于这些人,肯定最后要将他们进行匹配的,而那些先下手的是名正言顺的,暂时不用管。
    到了最后肯定会有某个点等于自身,这个可以进行证明。此处略。
    而对于这个等于自身的点,只需要让他送给他原来想送的那个人,而将送给他梦中情人的那个情敌送给他,这样就拐过来了,并且不会出现矛盾。
    另外,需要注意的是,数组的大小一定要是指定的大小,而不是最大值!!!!!!
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;

void solve(){
	int n, cnt = 0;
	vector<int> vec1, vec2;
	scanf("%d", &n);
	int a[n + 1], source[n + 1], ans[n + 1];
	memset(ans, 0, sizeof ans);
	memset(source, 0, sizeof ans);
	for(int i = 1; i <= n; i ++){
		scanf("%d", &a[i]);
		if(!source[a[i]]){
			cnt ++;
			source[a[i]] = i;
			ans[i] = a[i];
		}else{
			vec1.push_back(i);
		}
	}
	for(int i = 1; i <= n; i ++){
		if(source[i] == 0)
			vec2.push_back(i);
	}
	for(int i = 0; i < vec1.size(); i ++)
		ans[vec1[i]] = vec2[i];
	for(int i = 1; i <= n; i ++){
		if(ans[i] == i){
			ans[i] = a[i];
			int s = source[a[i]];
			ans[s] = i;
			source[a[i]] = i;
		}
	}
	printf("%d\n", cnt);
	for(int i = 1; i <= n; i ++)
		printf("%d ", ans[i]);
	printf("\n");
}
int main(){
	int t;
	scanf("%d", &t);
	while(t --){
		solve();
	}
	
	return 0; 
}
这篇关于Codeforces Round #733的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!