Codeforces Round #733 (Div. 1 + Div. 2）

2023-12-24 10:02:16

Codeforces Round #733 (Div. 1 + Div. 2）

A - Binary Decimal

定义好数为各位是$0$或者$1$的十进制数。

给出数$n$，求出最少的好数的数量，使得这些好数相加恰好为$n$

对于$100\%$的数据满足$1 \leq n \leq 10^9$

注意到，十进制数的减法是按位减去，增加一个好数，意味着将$n$各位上减去这个好数对应位子上的$0$或者$1$

最终情况是$n$各个位置上的数都为$0$，因此最少的好数的数量等于$n$各个数位上的数值的最大值。

时间复杂度$O(lg n)$

# include <bits/stdc++.h>
using namespace std;
int a[10];
int main() {
	int t; scanf("%d",&t);
	while (t--) {
			int n; scanf("%d",&n); int ans=0;
		while (n) {
			ans=max(ans,n%10);
			n/=10;
		}
		printf("%d\n",ans);
	}
	return 0;
}

B - Putting Plates

$n\times m$的桌子，只有边缘处才能放盘子$1$，否则是$0$。

且两个盘子不能相邻摆放，求出放最多盘子时的方案。

对于$100\%$的数据满足$3 \leq n,m \leq 20$

分$n,m$奇偶性情况讨论即可。

时间复杂度$O(nm)$

# include <bits/stdc++.h>
using namespace std;
int a[25][25];
int main()
{
	int t; scanf("%d",&t);
	while (t--) {
		int n,m;
		scanf("%d%d",&n,&m);
		for (int i=1;i<=n;i++)
			for (int j=1;j<=m;j++)
				a[i][j]=0;
		if ((n&1)&&(m&1)) {
			for (int i=1;i<=m;i+=2) a[1][i]=1,a[n][i]=1;
			for (int i=1;i<=n;i+=2) a[i][1]=1,a[i][m]=1;
		} else if (n%2==0&&m%2==0) {
			for (int i=2;i<=m-1;i+=2) a[1][i]=1;
			for (int i=m-1;i>=2;i-=2) a[n][i]=1;
			for (int i=2;i<=n-1;i+=2) a[i][m]=1;
			for (int i=n-1;i>=2;i-=2) a[i][1]=1;
		} else if (n%2==1&&m%2==0) {
			for (int i=2;i<=m;i+=2) a[1][i]=1;
			for (int i=1;i<=m-1;i+=2) a[n][i]=1;
			for (int i=n;i>=2;i-=2) a[i][1]=1;
			for (int i=1;i<=n-1;i+=2) a[i][m]=1;
		} else {
			for (int i=1;i<=m-1;i+=2) a[1][i]=1;
			for (int i=m;i>=2;i-=2) a[n][i]=1;
			for (int i=1;i<=n;i+=2) a[i][1]=1;
			for (int i=2;i<=n;i+=2) a[i][m]=1;
		}
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=m;j++)
				printf("%d",a[i][j]);
			puts("");
		}	
	}
	return 0;
}

C - Pursuit

一场比赛由若干轮组成，每轮会有一个得分$w\in[0,100]$。

第$k$轮比赛后的得分为之前轮次的最高的$k-\lfloor \frac{k}{4} \rfloor$个分数之和。

$A,B$进行了$n$轮比赛，每轮的得分分别为$a_i,b_i$

询问至少再过多少轮比赛$A$得分有可能大于等于$B$的得分。

对于$100\%$的数据$1 \leq n\leq 10^5$

本题答案具有单调性，先二分这个答案。

check答案是否合法的时候可以贪心，$A$在后面的比赛中全部获得$100$分，$B$在后面的比赛中全部获得$0$分。

时间复杂度为$O(n log_2^2 n)$

# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N=3e5+10;
int a[N],aa[N],b[N],bb[N],n;
bool check(int x) {
	for (int i=1;i<=n;i++) {
		a[i]=aa[i]; b[i]=bb[i];
	}
	for (int i=n+1;i<=n+x;i++) a[i]=100; 
	for (int i=n+1;i<=n+x;i++) b[i]=0; 
	sort(a+1,a+1+n+x); reverse(a+1,a+1+n+x);
	sort(b+1,b+1+n+x); reverse(b+1,b+1+n+x);
	x=(n+x)-(n+x)/4;
	int res1=0; for (int i=1;i<=x;i++) res1+=a[i];
	int res2=0; for (int i=1;i<=x;i++) res2+=b[i];
	return res1>=res2;
}
signed main()
{
	int t; scanf("%lld",&t);
	while (t--) {
		scanf("%lld",&n);
		for (int i=1;i<=n;i++) scanf("%lld",&aa[i]);
		for (int i=1;i<=n;i++) scanf("%lld",&bb[i]);
		int l=0,r=2*n,ans;
		while (l<=r) {
			int mid=(l+r)/2;
			if (check(mid)) ans=mid,r=mid-1;
			else l=mid+1;
		}
		printf("%lld\n",ans);	
	}
	return 0;
}

D - Secret Santa

给出$n$个数字$a_i$，且保证$a_i\ne i$

求一个排列$b_i$满足$b_i\ne i$ 且$a_i = b_i$的值尽量多。

对于$100\%$的数据满足$2 \leq n \leq 2\times 10^5$

可以证明最终$a_i = b_i$尽量多的最终值为$a_i$中不同元素个数。

必要性显然，下面给出一个构造方案说明充分性：

首先对于每一个$i$，建一条$i $到$a_i$的有向边。然后对有有多个进入该点的边任意保留一条。

将这些边上的点，设为已经加入图中。

下面对于未加入图中的点$i$处理。

找到$a_i$，并求出$a_i$为目标的唯一一条边连接的点$u$，保留$i$到$a_i$的边，把$u$到$a_i$的边改为$u$到$i$的边。

这样，增加一个满足$a_i=b_i$，又减少一个满足$a_i = b_i$的点。

由于按照这样构造，每个点$i$有且只有一个出边，$b_i$构造完成。

时间复杂度为$O(n)$

# include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
map<int,int>mp;
vector<int>in[N];
int a[N],ans[N];
int main() {
	int t; scanf("%d",&t);
	while (t--) {
		int n; scanf("%d",&n);
		mp.clear();
		for (int i=1;i<=n;i++) in[i].clear(),ans[i]=0;
		for (int i=1;i<=n;i++) {
			scanf("%d",&a[i]);
			mp[a[i]]=1; in[a[i]].push_back(i);
		}
		for (int i=1;i<=n;i++) if (in[i].size()) {
			ans[in[i][0]]=i;
		}
		for (int i=1;i<=n;i++) if (in[i].size()==0) {
			int u=i,v=i; while (ans[v]) v=ans[v];
			if (u==v) continue;
			ans[v]=u;
		}
		for (int i=1;i<=n;i++) if (!ans[i]) {
			ans[i]=a[i]; ans[in[a[i]][0]]=i; in[a[i]][0]=i;
		}
		printf("%d\n",mp.size());
		for (int i=1;i<=n;i++) printf("%d ",ans[i]);
		puts("");
	}
	return 0;
}

E - Minimax

一个字符串$s$，每个位置$i$有函数$f(i)$，其值其前缀和后缀（长度不能是$i$）重合的最大距离。

而$g(s) = min_{i=1}^{len(s)} f(i)$。

重新排列$s$中字母时，要求字典序最小的构造$s$字符串的方案，使得$g(s)$的值最小。

对于$100\%$的数据$1 \leq |s|\leq 10^5$

分类讨论：

当字母数只有$1$种时，输出原字符串即可。
当存在一个字符只出现一次时，将这种字符中字典序最小的放在首位，后面排序即可，答案为$0$
当所有字符出现都大于等于$2$次,
- 当字母数只有$2$种时，不妨设字典序较小的字符为$a$，字典序较大的字符为$b$
  - 当$a$的数目足够少，答案为$1$,$aabababab...abbbb$。
  - 当$a$的数目不多也不少的时候，答案为$1$,$aababab...aba$。
  - 当$a$的数目足够多，答案为$1$,$abbb...bbbaa...aa$。
- 当字母数大于等于$3$时，
  - 当$a$的数目足够少时，答案为$1$, $aabababacacadddeeefff...$
  - 当$a$的数目足够多时，答案为1，$abaaa...aaacbbb...bccc...cddd...$

时间复杂度为$O(|s|)$

# include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
char s[N];
int c[27];
void solve(){
	int cnt=0,l=0;
	for (int i=0;i<26;i++) if (c[i]==1) {
		putchar(i+‘a‘); c[i]--;
		for (int j=0;j<26;j++)
			for (int k=1;k<=c[j];k++)
				putchar(j+‘a‘);
		return;		
	} else if (c[i]>1) cnt++,l+=c[i];
	if (cnt==1) {
		printf("%s",s);
	}else if (cnt==2) {
		
		int p1=-1,p2=-1;
		for (int i=0;i<26;i++) if (c[i]) {
			if (p1==-1) p1=i; else p2=i;
		}
		if (c[p1]<=(l+1)/2) {
			putchar(p1+‘a‘);
			for (int i=2;i<=c[p1];i++) putchar(p1+‘a‘),putchar(p2+‘a‘);
			for (int i=c[p1];i<=c[p2];i++) putchar(p2+‘a‘);
		} else if (c[p1]<=l/2+1){
			putchar(p1+‘a‘);
			for (int i=3;i<=c[p1];i++) putchar(p1+‘a‘),putchar(p2+‘a‘);
			putchar(p1+‘a‘);
		} else {
			putchar(p1+‘a‘);
			for (int i=1;i<=c[p2];i++) putchar(p2+‘a‘);
			for (int i=2;i<=c[p1];i++) putchar(p1+‘a‘);
		}
	} else {
		int ps=-1;
		for (int i=0;i<26;i++) if (c[i]) {
			ps=i; break;
		}
		if (c[ps]<=(l+1)/2) {
			vector<char>tmp; tmp.clear();
			for (int i=0;i<26;i++) if (i!=ps) {
				for (int j=1;j<=c[i];j++) tmp.push_back(i+‘a‘);
			}
			putchar(ps+‘a‘);
			int res=c[ps]-1;
			for (int i=0;i<tmp.size();i++) {
				if (res) putchar(ps+‘a‘);
				putchar(tmp[i]);
				if (res) res--;
			}
		} else if (c[ps]-1<=l/2) {
			vector<char>tmp; tmp.clear();
			for (int i=0;i<26;i++) if (i!=ps) {
				for (int j=1;j<=c[i];j++) tmp.push_back(i+‘a‘);
			}
			putchar(ps+‘a‘);
			int res=c[ps]-1;
			for (int i=0;i<tmp.size();i++) {
				if (res) putchar(ps+‘a‘);
				putchar(tmp[i]);
				if (res) res--;
			}
			putchar(ps+‘a‘);	
		} else {
			int p1=-1,p2=-1,p3=-1;
			for (int i=0;i<26;i++) if (c[i]) {
				if (p1==-1) p1=i;
				else if (p2==-1) p2=i;
				else if (p3==-1) p3=i;
			}
			putchar(p1+‘a‘); putchar(p2+‘a‘);
			for (int i=2;i<=c[p1];i++) putchar(p1+‘a‘);
			putchar(p3+‘a‘);
			for (int i=2;i<=c[p2];i++) putchar(p2+‘a‘);
			for (int i=2;i<=c[p3];i++) putchar(p3+‘a‘);
			for (int i=0;i<26;i++) if (i>p3) {
				for (int j=1;j<=c[i];j++) putchar(i+‘a‘); 
			}
		}
	}
}
int main() {
	int t; scanf("%d",&t);
	while (t--) {
		scanf("%s",s); int l=strlen(s);
		for (int i=0;i<26;i++) c[i]=0;
		for (int i=0;i<l;i++) c[s[i]-‘a‘]++;
		solve();
		puts("");	
	}
	return 0;
}

Codeforces Round #733 (Div. 1 + Div. 2）

码农公寓

Codeforces Round #733 (Div. 1 + Div. 2）

A - Binary Decimal

B - Putting Plates

C - Pursuit

D - Secret Santa

E - Minimax

相关文章