首页 > 其他分享 >2024/03/18

2024/03/18

时间:2024-03-20 22:55:20浏览次数:37  
标签:03 val int 18 cin 2024 ++ mp dp

ABC344

A - Spoiler

题意:

给出一个字符串,串中有两个$|$,输出$|$两边的内容。

思路:

我写的代码非常丑陋,模拟写的。

赛后看到string的stl,感觉非常妙。

rfind(str)是从字符串右侧开始匹配str

#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  int a = s.find('|');
  int b = s.rfind('|');
  s.erase(a, b-a+1);
  cout << s;
}

D - String Bags

题意:

给一个目标串和n$[1, 100]$个背包,每个背包有m$[1, 10]$个串,需要按顺序从每个背包拿出一个或者不拿,这些串能组成目标串。

求最少需要的背包数。

思路:

刚开始我以为是个dfs,判断子串,然后按照下标进行dfs。

zyw说是个dp,我觉得很妙。

写了一发,wa了一个点。

是因为题目要求每个背包只能最多拿一个串,我在dp的时候会同一组的字符串同时作用。

还有一个细节就是一个小字符串只能单独作用,需要从后往前更新(类似于01背包)

解决方法是开一个新的ndp数组,在每一个dp中用之前的ndp数组更新,这样背包里的每一个字符串的更新都是独立的。

#include <bits/stdc++.h>
using namespace std;

#define int long long

vector<string> v[101];

void solve() {
	string str;
	cin >> str;
	int ls = str.length();

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		string st;

		for (int j = 0; j < t; j++) {
			cin >> st;
			v[i].push_back(st);
		}
	}

	vector<int> dp(ls + 1, 1e18);
	dp[0] = 0;
	for (int i = 0; i < n; i++) {
		vector<int> ndp = dp;
		for (auto s : v[i]) {
			int len = s.length();
			for (int  j = ls - len; j >= 0; j--) {
				if(str.substr(j, len) == s) {
					ndp[j + len] = min(ndp[j + len], dp[j] + 1);
				}
			}
		}
		dp = ndp;
	}
	
	if(dp[ls] == 1e18) {
		cout << -1 << endl;
	}
	else {
		cout << dp[ls] << endl;
	}
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int T = 1;
	// cin >> T;

	while(T--) {
		solve();
	}

	return 0;
}

E - Insert or Erase

题意:

模拟链表,按照数值插入和删除。

#include <bits/stdc++.h>
using namespace std;

#define int long long

struct node {
	int val, l, r;
};

void solve() {
	int n;
	cin >> n;

	vector<node> v(n + 2);
	v[0].val = -1;
	v[0].r = 1;
	v[n + 1].val = -2;

	map<int, int> mp;
	for (int i = 1; i <= n; i++) {
		int t;
		cin >> t;
		v[i].val = t;
		v[i].l = i - 1;
		v[i].r = i + 1;
		mp[t] = i;
	}

	int m;
	cin >> m;

	for (int i = 0; i < m; i++) {
		int op;
		cin >> op;

		if(op == 1) {
			int x, y;
			cin >> x >> y;
			
			int loc1 = mp[x];
			int loc2 = v[loc1].r;

			node nt;
			nt.val = y;
			nt.l = loc1, nt.r = loc2;
			v.push_back(nt);
			v[loc1].r = v.size() - 1;
			v[loc2].l = v.size() - 1;
			mp[y] = v.size() - 1;
		}
		else {
			int x;
			cin >> x;

			int loc = mp[x];
			int ll = v[loc].l;
			int rr = v[loc].r;
			v[ll].r = rr;
			v[rr].l = ll;
		}
		
	}

	for (int i = 0; v[i].val != -2; i = v[i].r) {
		if(v[i].val == -1) { 
			continue;
		}
		cout << v[i].val << " ";
	}

	cout << endl;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int T = 1;
	// cin >> T;

	while(T--) {
		solve();
	}

	return 0;
}

ABC343

D Diversity of Scores

题意:

线段树,两个操作,

  • 一个操作是改值
  • 一个操作是求区间第二大出现的次数

思路:

改值容易,求区间第二大的数量需要同时记录最大和次大。

和正常的线段树差不多,主要是query有分裂区间需要比较两个区间,所以query的返回值我们干脆设置成node

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn = 2e5 + 5;

struct node {
	int l, r;
	pair<int, int>p1, p2;
}tree[maxn << 2];

int arr[maxn];

void push_up(int u) {
	map<int, int>mp;
	mp[-tree[u << 1].p1.first] += tree[u << 1].p1.second;  
	mp[-tree[u << 1].p2.first] += tree[u << 1].p2.second;
	mp[-tree[u << 1 | 1].p1.first] += tree[u << 1 | 1].p1.second;  
	mp[-tree[u << 1 | 1].p2.first] += tree[u << 1 | 1].p2.second;

	int cnt = 0;
	for (auto [x, y] : mp) {
		if(!cnt) {
			cnt++;
			tree[u].p1 = {-x, y};
		}
		else {
			tree[u].p2 = {-x, y};
			break;
		}
	}  
}
void build_tree(int u, int l, int r) {
	tree[u].l = l, tree[u].r = r;

	if(l == r) {
		tree[u].p1 = {arr[l], 1};
		tree[u].p2 = {-1, 0};
		return ;
	}

	int mid = (l + r) >> 1;
	build_tree(u << 1, l, mid);
	build_tree(u << 1 | 1, mid + 1, r);
	push_up(u);
}

void add(int u, int l, int r, int k) {
	if(tree[u].l == l && tree[u].r == r) {
		arr[l] += k;
		tree[u].p1 = {arr[l], 1};
		return ;
	}
	int mid = (tree[u].l + tree[u].r) >> 1;
	if(mid >= l) {
		add(u << 1, l, r, k);
	}
	if(mid < r) {
		add(u << 1 | 1, l, r, k);
	}
	push_up(u);
}

node query(int u, int l, int r) {
	if(tree[u].l >= l && tree[u].r <= r) {
		return tree[u]; 
	}
	else {
		node a, b;
		bool flag1 = 0, flag2 = 0;
		int mid = (tree[u].l + tree[u].r) >> 1;
		if(mid >= l) {
			flag1 = 1;
			a = query(u << 1, l, r);
		}
		if(mid < r) {
			flag2 = 1;
			b = query(u << 1 | 1, l, r);
		}

		if(flag1 && flag2) {
			node c;

			map<int, int>mp;
			mp[-a.p1.first] += a.p1.second;  
			mp[-a.p2.first] += a.p2.second;
			mp[-b.p1.first] += b.p1.second;  
			mp[-b.p2.first] += b.p2.second;

			int cnt = 0;
			for (auto [x, y] : mp) {
				if(!cnt) {
					cnt++;
					c.p1 = {-x, y};
				}
				else {
					c.p2 = {-x, y};
					break;
				}
			}
			return c;  
		}
		else if(flag1) {
			return a;
		}
		else {
			return b;
		}
	}
}
void solve() {
	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}	

	build_tree(1, 1, n);
	
	for (int i = 0; i < m; i++) {
		int op;
		cin >> op;

		if(op == 1) {
			int x, y;
			cin >> x >> y;
			add(1, x, x, y - arr[x]);
		}
		else {
			int l, r;
			cin >> l >> r;
			cout << query(1, l, r).p2.second << endl;
		}
	}
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int T = 1;
	// cin >> T;

	while(T--) {
		solve();
	}

	return 0;
}

标签:03,val,int,18,cin,2024,++,mp,dp
From: https://www.cnblogs.com/yyc4591/p/18086327

相关文章

  • 2024-03-20 leetcode写题记录
    目录2024-03-20leetcode写题记录23.合并K个升序链表题目链接题意解法4.寻找两个正序数组的中位数题目链接题意解法25.K个一组翻转链表题目链接题意解法2024-03-20leetcode写题记录23.合并K个升序链表题目链接23.合并K个升序链表题意给你一个链表数组,每个链表......
  • 20240320每日一题题解
    20240320每日一题题解Problem阿克曼(Ackermann)函数\(A(m,n)\)中,\(m,n\)定义域是非负整数(\(m\le3\),\(n\le10\)),函数值定义为:\(\mathit{akm}(m,n)=n+1\);(\(m=0\)时)。\(\mathit{akm}(m,n)=\mathit{akm}(m-1,1)\);(\(m>0\)、\(n=0\)时)。\(\mathit{akm}(m,n)=......
  • 专题2024.03.21
    2024.03.21专题T1Bombs答案显然具有单调性,多删一定比少删更优,这是明显的一个数\(a_i=x\)不被删掉的充要条件为:\[\sum\limits_{j=1}^{i-1}[a_j<x]\leqk\]其中\(k\)为\(i\)之前的炸弹数量由单调性,考虑每次加一个炸弹后怎么快速的检查一个数合不合法,可以用线段树维......
  • 水果软件FL Studio 21 for mac 21.2.3.3586破解版的最新版本2024介绍安装
    音乐是人类最美好的语言,它能够跨越国界、文化和语言,将人们紧密地联系在一起。在当今数字化时代,音乐创作已经不再是专业人士的专利,越来越多的音乐爱好者开始尝试自己动手制作音乐。而FLStudio21中文版编曲软件正是这样一个为你打开音乐创作之门的工具。FLStudio21中文版编......
  • 复习java的第一天3.18的文章
    大家好,我准备在这里记录我每天的学习(复习)java的成果,以及计划和规划,为的就是希望能找几个月后能找一份工作,并且我希望自己能坚持下去,养成一个良好的习惯,让自己不再那么迷茫,与其内耗不如做点有意义有方向的事情.之前我一直想不明白自己到底想要干什么,因为网上看着大家都说......
  • 2024-03-19 leetcode写题记录
    目录2024-03-19leetcode写题记录85.最大矩形题目链接题意解法2024-03-19leetcode写题记录85.最大矩形题目链接85.最大矩形题意给定一个仅包含0和1、大小为rowsxcols的二维二进制矩阵,找出只包含1的最大矩形,并返回其面积。解法先对每个元素求出其往上能延伸......
  • 厉害啊!分离人声,全靠这4款2024最新款音频分离工具
    在音频处理中,人声分离是一个常见的需求。简单来说,人声分离就是将混合音频中的人声和背景音乐(或其他环境声音)分离的过程。随着科技的发展,我们已经有多种方法和技术可以实现这一目标。在本文中,我们将介绍四种可以实现人声分离的工具和方法。一、金舟音频大师(1)工具介绍:金舟音......
  • 史上最全Java核心面试题(带全部答案)2024年最新版
    今天要谈的主题是关于求职,求职是在每个技术人员的生涯中都要经历多次。对于我们大部分人而言,在进入自己心仪的公司之前少不了准备工作,有一份全面细致面试题将帮助我们减少许多麻烦。在跳槽季来临之前,特地做这个系列的文章,一方面帮助自己巩固下基础,另一方面也希望帮助想要换工......
  • 2024年跨境电商发展前景
    2024年跨境电商发展前景根据搜索结果,2024年跨境电商仍将保持较强的增长势头。据eMarketer预测,到2026年,电子商务在全球零售领域的渗透率将上升至23.6%[1]。因此,跨境电商市场潜力巨大,现在入局并不算晚。如何做好2024年的跨境电商选择合适的平台亚马逊是最受欢迎的......
  • 2024年03月 Discourse 3.3.0.beta1 版本的更新
    在这个版本的更新中Discourse完成了Ember5版本的升级和更新。Ember.js是一个用于创建web应用的开源JavaScriptMVC框架,采用基于字符串的Handlebars模板,支持双向绑定、观察者模式、计算属性(依赖其他属性动态变化)、自动更新模板、路由控制、状态机等。Ember是一个雄心勃......