Codeforces Round #733 (Div.1 + Div.2) A - D

2024-01-02 12:04:16

A - Binary Decimal

思路:
直接看十进制数的每一位最高为多少

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define eb emplace_back
#define MP make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define lson rt<<1
#define rson rt<<1|1
#define CLOSE std::ios::sync_with_stdio(false)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-6;

void solve() {
	int n;scanf("%d",&n);
	int ans = 0;
	while(n) {
		ans = max(ans,n % 10);
		n /= 10;
	}
	printf("%d\n",ans);
}

int main() {
	int T;scanf("%d",&T);
	while(T--) solve();
	return 0;
}

B - Putting Plates

思路：
直接照着样例模拟就行，注意下边界情况能否放1的判断。

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define eb emplace_back
#define MP make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define lson rt<<1
#define rson rt<<1|1
#define CLOSE std::ios::sync_with_stdio(false)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-6;
int mp[30][30];

void solve() {
	int n,m;
	cin >> n >> m;
	for(int i = 1;i <= n;i ++) for(int j = 1;j <= m;j ++) mp[i][j] = 0;
	if((n % 2 == 1) && (m % 2 == 1)) {
		for(int j = 1;j <= m;j += 2) {
			mp[1][j] = 1;
		}
		for(int j = 1;j <= m;j += 2) {
			mp[n][j] = 1;
		}
		for(int i = 1;i <= n;i += 2) {
			mp[i][1] = 1;
		}
		for(int i = 1;i <= n;i += 2) {
			mp[i][m] = 1;
		}
	}
	else if((n % 2 == 0) && (m % 2 == 0)) {
		for(int j = 2;j <= m - 2;j += 2) {
			mp[1][j] = 1;
		}
		for(int j = 3;j <= m;j += 2) {
			mp[n][j] = 1;
		}
		for(int i = 3;i <= n;i += 2) {
			mp[i][1] = 1;
		}
		for(int i = 2;i <= n - 2;i += 2) {
			mp[i][m] = 1;
		}
	}
	else if((n % 2 == 1 && m % 2 == 0)) {
		for(int j = 2;j <= m;j += 2) {
			mp[1][j] = 1;
		}
		for(int j = 1;j <= m;j += 2) {
			mp[n][j] = 1;
		}
		for(int i = 3;i <= n;i += 2) {
			mp[i][1] = 1;
		}
		for(int i = 1;i <= n - 2;i += 2) {
			mp[i][m] = 1;
		}
	}
	else if((n % 2 == 0 && m % 2 == 1)) {
		for(int j = 1;j <= m - 2;j += 2) {
			mp[1][j] = 1;
		}
		for(int j = 3;j <= m;j += 2) {
			mp[n][j] = 1;
		}
		for(int i = 1;i <= n;i += 2) {
			mp[i][1] = 1;
		}
		for(int i = 2;i <= n;i += 2) {
			mp[i][m] = 1;
		}
	}
	for(int i = 1;i <= n;i ++) {
		for(int j = 1;j <= m;j ++) {
			printf(j == m ? "%d\n" : "%d",mp[i][j]);
		}
	}
	puts("");
}

int main() {
	int T;scanf("%d",&T);
	while(T--) solve();
	return 0;
}

C - Pursuit

思路：
看到要求最小的额外场次且每次\(check\)比较容易的\(O(n)\)判断，我就直接二分了，赛后得知可能一遍处理一下即可。
预处理一下得分的和，然后二分需要的场次即可。

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define eb emplace_back
#define MP make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define lson rt<<1
#define rson rt<<1|1
#define CLOSE std::ios::sync_with_stdio(false)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-6;
const int N = 1e5 + 10;
int a[N],b[N],suma[N],sumb[N],n;
bool cmp(int x,int y) {
	return x > y;
}
bool check(int x) {
	int num = n + x - (n + x) / 4;//需要进行的场数
	ll sum1,sum2;
	if(x >= num) {
		sum1 = num * 100,sum2 = sumb[min(n,num)];
	}
	else {//额外小于需要
		sum1 = x * 100 + suma[num - x],sum2 = sumb[min(n,num)];
	}
	if(sum1 >= sum2) return true;
	else return false;
}
void solve() {
	scanf("%d",&n);
	for(int i = 1;i <= n;i ++) suma[i] = sumb[i] = 0;
	for(int i = 1;i <= n;i ++) {
		scanf("%d",&a[i]);
	}
	for(int i = 1;i <= n;i ++) {
		scanf("%d",&b[i]);
	}
	sort(a + 1,a + 1 + n,cmp);
	sort(b + 1,b + 1 + n,cmp);
	for(int i = 1;i <= n;i ++) suma[i] = a[i] + suma[i - 1];
	for(int i = 1;i <= n;i ++) sumb[i] = b[i] + sumb[i - 1];
	int l = 0,r = 10000000,ans;
	while(l <= r) {
		int mid = (l + r) >> 1;
		// cout << l << ‘ ‘ << r << ‘\n‘;
		if(check(mid)) {
			r = mid - 1;
			ans = mid;
			// cout << mid << "-----\n";
		}
		else {
			l = mid + 1;
		}
	}
	printf("%d\n",ans);
}

int main() {
	int T;scanf("%d",&T);
	while(T--) solve();
	return 0;
}

D - Secret Santa

题意：
一共有\(n\)个人，他们之间要相互赠送礼物，在赠送的过程中呢，每个人只能给一个送礼物，但不能送给自己，每个人必须且只能收到一份礼物。
对于第\(i\)个人，\(a_i\)表示这个人期望把礼物送给谁，多个人可能期望把礼物送给同一个人，现在需要你给出一种方案使得满足礼物期望的人数尽可能的多。

思路：
①
这道题好像乱搞就可直接过。
直接处理出，在期望送礼物的人选中，没有出现的人是哪些，对于\(i\)来说，如果\(a_i\)只出现了一次，那么丛贪心的角度考虑，我们就一定要把\(i\)的礼物送给\(a_i\)。
我们从小到大枚举，如果当前的\(i\)的\(a_i\)出现次数多于一次，那么我们就从预处理的未被指定的集合中，从大到小的挑选\(i\)送礼物的合法人选，如果都没有合法选择，那么我们只能维持它的送礼对象不变，因为两边是对着枚举，所以是可行的。
但其实这么做的正确性也是感性理解的，并不会证明

②
也可以从图的角度来考虑这个问题，假如我们从\(i\)向\(a_i\)连一条有向边，那么所有的\(i\)和\(a_i\)就会行成一个有向图。
然后我们只需要用\(dfs\)从图的每个合法点进行遍历，找到当前的一个环或者一条路径，那么这个环或者路径中的点可以直接处理。
但是这样的处理有一种特殊情况，就是最后剩余的出来一个单点的情况并且其他的点全部组成了环，那么这时最后的剩余的这个点就不得不自己连向自己，很明显这不是合法的，所以每次\(dfs\)之后，我们都判断一下是否形成了这样的局面，如果有的话，我们就不从这个点开始，从另一点开始。

方法①的代码：

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define eb emplace_back
#define MP make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define lson rt<<1
#define rson rt<<1|1
#define CLOSE std::ios::sync_with_stdio(false)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-6;
const int N = 2e5 + 10;
int n,a[N],ans[N],vis[N],readylist[N];

void solve() {
	cin >> n;
	for(int i = 1;i <= n;i ++) ans[i] = vis[i] = 0;
	for(int i = 1;i <= n;i ++) {
		cin >> a[i];
		vis[a[i]]++;
	}
	int used = 0,tot = 0;
	for(int i = 1;i <= n;i ++) {
		if(!vis[i]) {
			readylist[++used] = i;
		}
	}
	int cnt = used;;
	for(int i = 1;i <= n;i ++) {
		if(vis[a[i]] > 1 && readylist[used] != i) {//一定是对着来换应该会更优
			ans[i] = readylist[used--];
			vis[a[i]]--;
		}
		else {//能换就先换掉 不能换就不管了
			ans[i] = a[i];
		}
	}
	printf("%d\n",n - cnt);
	for(int i = 1;i <= n;i ++) {
		printf(i == n ? "%d\n" : "%d ",ans[i]);
	}
}

int main() {
	int T;cin >> T;
	while(T--) solve();
	return 0;
}

Codeforces Round #733 (Div.1 + Div.2) A - D

上一篇：【环境准备】19c安装sample数据（sh用户）


下一篇：【转】Win32 创建控件风格不是Win XP解决方案