首页 > 其他分享 >Codeforces Round 954 (Div. 3 A ~ E)

Codeforces Round 954 (Div. 3 A ~ E)

时间:2024-12-17 20:30:41浏览次数:7  
标签:tem min int cin 954 Codeforces ++ Div dp

1.A. X Axis

x的范围是[1, 10],可以直接枚举。

void solve(){
	cin>>x1>>x2>>x3;
	int res = inf;
	for(int i = 1; i <= 10; i++){
		res = min(res, abs(i - x1) + abs(i - x2) + abs(i - x3));
	}
	cout<<res<<"\n";
}

2.B. Matrix Stabilization

依照题目意思,只有满足上下左右都小于本身的数才能进行aij = aij - 1的操作,因此进行操作的数最小减小到四个方向中最大的数,那么如果满足要求(大于四个方向的数)就把这个位置的数替换为四个方向的最大数即可(不用担心四个方向的数会减小,因为如果中间的数满足要求,那么它的四个方向的数肯定不满足要求,也就不会减小)。不过得注意不要取到边界。

void solve(){
	cin>>n>>m;
	vvi a(n + 2, vi(m + 2));
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin>>a[i][j];
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(a[i][j] > a[i - 1][j] && a[i][j] > a[i][j - 1] && a[i][j] > a[i][j + 1] && a[i][j] > a[i + 1][j]){
				int tem = 0;
				if(i - 1 >= 1)tem = max(tem, a[i - 1][j]);
				if(j - 1 >= 1)tem = max(tem, a[i][j - 1]);
				if(j + 1 <= m)tem = max(tem, a[i][j + 1]);
				if(i + 1 <= n)tem = max(tem, a[i + 1][j]);
				a[i][j] = min(a[i][j], tem);
			}
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cout<<a[i][j]<<" ";
		}
		cout<<"\n";
	}
}

3.C. Update Queries

由题可知,我们可以根据给的m个索引对原字符串的字符进行替换,并且题目要求原字符串s的字典序要尽可能小,那么只要我们尽可能给小的索引赋值小的字符即可。

void solve(){
	map <int,int> ma1;
	map <char,int> ma2;
	cin>>n>>m>>s;
	vi c(m);
	for(int i = 0; i < m; i++){
		cin>>c[i];
		ma1[c[i]] = 1;
	}
	cin>>s1;
	for(int i = 0; i < m; i++){
		ma2[s1[i]] ++;
	}
	for(auto x : ma1){
		for(auto y : ma2){
			if(y.second > 0){
				s[x.first - 1] = y.first;
				ma2[y.first] --;
				break;
			}
		}
	}
	cout<<s<<"\n";
}

4.D. Mathematical Problem

题目意思:将n个个位数中的某两个连续的个位数结合成一个十位数,然后在n - 1个数中间添加+/*。

首先,观察n的范围[2, 20],很小,那么我们就可以考虑一下模拟 + 贪心

方法一:模拟 + 贪心

思路:先枚举两个数进行结合,然后寻找结合过后的n - 1个数中是否有0存在,如果有直接输出0(有0,当然直接*0就好了),如果没有0,就要考虑+和*在什么情况下会让答案更优。

一、如果遇到1,就应当用*,因为只有可以比+少1

二、如果遇到大于1的数,用*的结果 >= 用+的结果,那么我们干脆全部用+

void solve(){
	cin>>n>>s;
	int res = inf;
	for(int i = 0; i < n - 1; i++){
		vi a;
		for(int j = 0; j < n; j++){
			if(i == j){
				a.push_back(10 * (s[j] - '0') + (s[j + 1] - '0'));
				j ++;
			} else {
				a.push_back(s[j] - '0');
			}
		}
		int sum = 0, ans = 0, flag = 0;
		map <int,int> ma;
		for(int j = 0; j < n - 1; j++){
			if(a[j] == 1)flag = 1;
			else flag = 0;
			sum += a[j];
			if(flag == 1)ans ++;
			ma[a[j]] = 1;
		}
		if(ma.count(0)){
			cout<<"0\n";
			return;
		}
		if(ma.size() == 1)ans = max(ans - 1, 0ll);
		res = min(res, sum - ans);
	}
	cout<<res<<"\n";
}

方法二:状态机 + 线性dp

题目要求某一个位置进行结合操作之后的最小值,那么我们可以用状态机来表示某一时刻是否完成结合操作

定义dp[个位数的个数][2(是否完成结合)]

vector <vector> dp(n, vector<int>(2));

状态转移方程

dp[i][0] = min(dp[i - 1][0] + (s[i] - '0'), dp[i - 1][0] + (s[i] - '0'));

dp[i][1] = min(min(dp[i - 1][1] + (s[i] - '0'), dp[i - 1][1] * (s[i] - '0')), min(dp[i - 2][0] + (10 * (s[i - 1] - '0') + (s[i] - '0')), dp[i - 2][0] * (10 * (s[i - 1] - '0') + (s[i] - '0'))));

void solve(){
	cin>>n>>s;
    vector <vector<int>> dp(n, vector<int>(2));
	dp[0][0] = (s[0] - '0');
	dp[1][0] = min(dp[0][0] + (s[1] - '0'), dp[0][0] * (s[1] - '0'));
	dp[1][1] = (s[0] - '0') * 10 +(s[1] - '0');
	for(int i = 2; i < n; i++){
		int x1 = (s[i] - '0'), x2 = ((s[i - 1] - '0') * 10 + (s[i] - '0'));
		dp[i][0] = min(dp[i - 1][0] + x1, dp[i - 1][0] * x1);
		dp[i][1] = min(min(dp[i - 1][1] + x1, dp[i - 1][1] * x1),min(dp[i - 2][0] + x2, dp[i - 2][0] * x2));
	}
	cout<<dp[n - 1][1]<<"\n";
}

5.E. Beautiful Array

先放代码,思路明天补

void solve(){
	map <int,vector<int>> ma;
	cin>>n>>k;
	for(int i = 0; i < n; i++){
		int x;
		cin>>x;
		ma[x % k].push_back(x);
	}
	int sum = 0, ans = 0;
	for(auto x : ma){
		auto a = x.second;
		sort(a.begin(), a.end());
		if(a.size() % 2 == 0){
			for(int i = 0; i < a.size(); i += 2){
				sum += (a[i + 1] - a[i]) / k;
			}
		}else {
			ans ++;
			int tem = 0;
			for(int i = 1; i < a.size(); i += 2){
				tem += (a[i + 1] - a[i]) / k;
			}
			int res = tem;
			for(int i = 0; i < a.size() - 1; i += 2){
				tem -= (a[i + 2] - a[i + 1]) / k;
				tem += (a[i + 1] - a[i]) / k;
				res = min(res, tem);
			}
			sum += res;
		}
		
	}
	if(ans > 1)sum = -1;
	cout<<sum<<"\n";
}

标签:tem,min,int,cin,954,Codeforces,++,Div,dp
From: https://blog.csdn.net/hsjwhe/article/details/144542585

相关文章

  • 如何让span在div中垂直居中?
    在前端开发中,有多种方法可以使<span>元素在其父元素<div>中垂直居中。以下是几种常见的方法:方法一:使用FlexboxFlexbox是一个现代的CSS布局模型,它可以轻松地实现各种复杂的布局。你可以使用Flexbox来使<span>元素在<div>中垂直居中。<divclass="container"><s......
  • (补题)Codeforces Round 993 (Div. 4) E.Insane Problem
    显然不可暴力解出,因此是到数学题。已知$$y=x*k^n$$所以我们可以利用y的区间范围$$[l1,r1]$$得出x的新的区间范围$$[l2/k^n(向上取整),r2/k^n(向下取整)]$$接着与原来的范围取交集然后不断枚举n即可,注意k^n不可能超过y#include<iostream>#defineintlonglongusingnamespa......
  • 【经管数据】企业排污许可企业信息数据大全(1954-2022年)
    一、数据范围:数据量庞大,能统计的企业均有二、包含字段:企业名称      登记状态      法定代表人      注册资本      成立日期      核准日期      所属省份      所属城市      所属区县      电话......
  • 【Z函数】codeforces 2010 C2. Message Transmission Error (hard version)
    前言Z函数的定义对于一个字符串\(s\),定义Z函数\(Z[i]\)为以\(s[i]\)为起始位置的后缀与整个字符串\(s\)的最长公共前缀的长度。Z函数的应用字符串匹配问题题目https://codeforces.com/problemset/problem/2010/C2题意给定一个字符串\(s\),若其可以找到真前缀......
  • Codeforces Round 993 (Div. 4)
    https://codeforces.com/contest/2044A.EasyProblem签到题。对于大小为n的矩阵,有n-1个a>0&&b>0的(a,b)pair,满足b=n-a。#include<iostream>#include<map>#include<string>usingnamespacestd;intmain(){intt;cin>>t;while(......
  • 如何让img自动适应div容器大小?
    在前端开发中,要使图像(<img>)自动适应其包含的<div>容器的大小,你可以使用CSS的一些属性。下面是一些常见的方法:1.使用max-width和height:auto你可以将图像的max-width设置为100%,这样它就不会超过其容器的宽度。同时,将height设置为auto可以保持图像的原始纵横比。......
  • CF补题 991-Div
    CF补题991-Div.3-20241210Dashboard-CodeforcesRound991(Div.3)-CodeforcesA:题目大意:给出\(n\)个字符串,求前多少个字符串的大小之和小于\(m\)#include<iostream>#include<string>usingnamespacestd;stringa[52];intmain(){ intT; cin>>T; w......
  • 使用button当按钮和使用div当按钮有什么区别?
    在前端开发中,使用<button>元素和<div>元素作为按钮时,有一些关键的区别,这些区别涉及到语义、可访问性、默认行为和样式等方面。1.语义<button>:语义明确,表示一个按钮,用于提交表单或触发某些动作。屏幕阅读器和其他辅助技术可以正确识别并宣布这是一个按钮,从而提高网站的......
  • Codeforces Round 992 (Div. 2) C. Ordered Permutations
    给出数字n,构造一个符合的数组很容易想到,n1时,只有1符合。n2时,有12;21符合。n==3时,有123;132;231;321;发现必须分为1和2——n的两块数字,有某种递归的感觉,答案与2次方有关于是做出代码:#include<iostream>#include<algorithm>usingnamespacestd;#defineffp(x,y......
  • F - Diversity
    F-DiversityProblemStatementThereare$N$productsforsaleinastore.The$i$-thproducthasapriceof$P_i$yen,autilityvalueof$U_i$,andacolor$C_i$.Youwillchoosesomesubsetofthese$N$productstobuy(possiblynone).Thetotalprice......