首页 > 其他分享 >ABC 223 复盘

ABC 223 复盘

时间:2024-04-04 13:45:17浏览次数:31  
标签:ABC int check 括号 swap str ans 223 复盘

ABC 223 复盘

[ABC223C] Doukasen

思路解析

根据题目可知,燃烧的总时长肯定不变,所以我们可以直接从头开始遍历找到第一根香使得烧完这根香后的时间会大于总时长的一半,然后加上剩余时间下会烧掉的长度即可。

时间复杂度:一次遍历,\(O(N)\)。

code

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, a[N], b[N];
double t[N], st = 0;
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d%d", &a[i], &b[i]);
		t[i] = 1.0 * a[i] / b[i];
		st += t[i];
	}
	double ans = 0, s = 0;
	for(int i = 1; i <= n; i++) {
		if(s + t[i] > st / 2.0) {
			ans += ((st / 2.0) - s) * b[i];
			break;
		}
		else ans += a[i], s += t[i];
	}
	printf("%.15lf", ans);
	return 0;
}

[ABC223D] Restricted Permutation

思路解析

题目说的很明白,给定 \(m\) 个约束条件,求排列,很版的一道拓扑。可见这是一道拓扑排序板子,唯一不同的地方就在于一定要字典序最小,我们只需要讲普通拓扑用的普通队列改成优先队列即可。

时间复杂度:由于有优先队列自带 \(\log\) 复杂度,同时每个点最多入队一次,复杂度为 \(O(N \log N)\)。

code

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, ind[N], d[N], ans[N];
vector<int> g[N];
map<int, int> mp[N];
bool cmp(int x, int y) {
	if(d[x] != d[y]) return d[x] < d[y];
	else return x < y;
}
int main() {
	cin >> n >> m;
	for(int i = 1, u, v; i <= m; i++) {
		cin >> u >> v;
		g[u].push_back(v);
		mp[u][v] = 1;
		ind[v]++;
	}
	priority_queue<int, vector<int>, greater<int>> q;
	for(int i = 1; i <= n; i++) {
		if(ind[i] == 0) d[i] = 1, q.push(i);
	}
	vector<int> v;
	while(!q.empty()) {
		int u = q.top(); q.pop();
		v.push_back(u);
		for(auto it : g[u]) {
			ind[it]--;
			if(ind[it] == 0) {
				d[it] = d[u] + 1;
				q.push(it);
			}
		}
	}
	for(int i = 1; i <= n; i++) {
		ans[i] = i;
		if(d[i] == 0) {puts("-1"); return 0;}
	}
	for(auto it : v) cout << it << ' ';
	return 0;
}

[ABC223E] Placing Rectangles

思路解析

根据题目可知,其实三个长方形无非只有以下两种摆放方式。

若大长方形长为 \(y\),宽为 \(x\),则我们对于第一种情况就固定住宽,判断能否使长度小于等于长;对于第二种情况同样固定住宽,此时 A 长方形右边空间的长就确定了,就只需要判断 B,C 的宽之和能否小于大长方形的宽即可。

注意大长方形的长宽可以互换,小长方形的顺序可以互换。

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define double long double
ll x, y, a, b, c;
bool check() {
	ll ax = ceil((double)a / x), bx = ceil((double)b / x), cx = ceil((double)c / x);
	if(ax + bx + cx <= y) return true;
	ll yy = y - ax;
	if(yy <= 0) return false;
	ll by = ceil((double)b / yy), cy = ceil((double)c / yy);
	if(by + cy <= x) return true;
	return false;
}
int main() {
	cin >> x >> y >> a >> b >> c;
	bool ans = check();
	swap(a, b); ans |= check();
	swap(a, c); ans |= check();
	
	swap(x, y); ans |= check();
	swap(a, b); ans |= check();
	swap(a, c); ans |= check();
	if(ans) puts("Yes");
	else puts("No");
	return 0;
}

[ABC223F] Parenthesis Checking

思路解析

在开始之前,首先我们需要知道合法括号序列的判断方法。我们可以给每个括号打上权值,设左括号权值为 \(1\),右括号权值为 \(-1\),这样一个 \(\texttt{(()())}\) 括号串用数字存下就是 \(1,1,-1,1,-1,-1\),这时我们再给序列计算一下前缀和就成了 \(1,2,1,2,1,0\)。此时我们发现序列有一个性质就是元素全部大于等于 \(0\),同时结尾的元素一定为 \(0\)。而例如我们找一个括号序列 \(\texttt{)()(}\),它的前缀和数组为 \(-1,0,-1,0\),可见虽然结尾是 \(0\),但中间有元素小于 \(0\),因此该括号序列并不合法。

现在我们已经知道了如何通过序列的前缀和数组判断该序列是否合法,接下来我们就考虑如何修改。我们可以先把前缀和数组存下来,然后考虑每一次交换会对这个数组产生怎样的影响。首先,若交换 \(l,r\) 两个位置上的括号,我们可以发现区间 \([1,l-1]\) 和 \([r,n]\) 是没有影响的,真正有影响的只有 \([l,r-1]\) 这个区间。接下来我们分两种情况考虑:

  • 若 \(l\) 位上的括号交换前是左括号时,可见由于第 \(l\) 位从 \(1\) 改成了 \(-1\),所以就会对该区间加上 \(-2\) 的权值。
  • 若 \(l\) 位上的括号交换前是右括号时,可见由于第 \(l\) 位从 \(-1\) 改成了 \(1\),所以就会对该区间加上 \(2\) 的权值。

最后考虑如何实现,我们需要做到区间求最小值,单点查询,区间加三种操作,可以想到使用线段树维护。注意由于我们存的值是前缀和,所以需要减去 \(l-1\) 位置上的值才能得到正确的值。记得特判 \(l-1=0\) 时的情况。

code

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, M = 8e5 + 10;
string str;
int n, q, a[N], s[M], t[M];
void push_up(int p) {
	int ls = (p << 1), rs = (p << 1) + 1;
	s[p] = min(s[ls], s[rs]);
}
void build(int p, int l, int r) {
	if(l == r) {
		s[p] = a[l];
		return;
	}
	int m = l + ((r - l) >> 1), ls = (p << 1), rs = (p << 1) + 1;
	build(ls, l, m);
	build(rs, m + 1, r);
	push_up(p);
}
void addt(int p, int l, int r, int k) {
	s[p] += k;
	t[p] += k;
}
void push_down(int p, int l, int r) {
	if(!t[p]) return;
	int m = l + ((r - l) >> 1), ls = (p << 1), rs = (p << 1) + 1;
	addt(ls, l, m, t[p]);
	addt(rs, m + 1, r, t[p]);
	t[p] = 0;
}
void add(int p, int l, int r, int x, int y, int k) {
	if(r < x || l > y) return;
	if(l >= x && r <= y) {
		addt(p, l, r, k);
		return;
	}
	push_down(p, l, r);
	int m = l + ((r - l) >> 1), ls = (p << 1), rs = (p << 1) + 1;
	add(ls, l, m, x, y, k);
	add(rs, m + 1, r, x, y, k);
	push_up(p);
}
int ask(int p, int l, int r, int x, int y) {
	if(r < x || l > y) return 2e9;
	if(l >= x && r <= y) return s[p];
	push_down(p, l, r);
	int m = l + ((r - l) >> 1), ls = (p << 1), rs = (p << 1) + 1;
	return min(ask(ls, l, m, x, y), ask(rs, m + 1, r, x, y));
}
int main() {
	cin >> n >> q;
	cin >> str;
	str = ' ' + str;
	for(int i = 1; i <= n; i++) {
		a[i] = a[i - 1];
		if(str[i] == '(') a[i]++;
		else a[i]--;
	}
	build(1, 1, n);
	while(q--) {
		int op, l, r;
		cin >> op >> l >> r;
		if(op == 1) {
			if(str[l] != str[r]) {
				if(str[l] == '(') add(1, 1, n, l, r - 1, -2);
				else add(1, 1, n, l, r - 1, 2);
				swap(str[l], str[r]);
			}
		}
		else {
			int tmp = ask(1, 1, n, l - 1, l - 1);
			if(l == 1) tmp = 0;
			int t1 = ask(1, 1, n, l, r - 1) - tmp, t2 = ask(1, 1, n, r, r) - tmp;
			if(t1 >= 0 && t2 == 0) cout << "Yes\n";
			else cout << "No\n";
		}
	}
	return 0;
}

标签:ABC,int,check,括号,swap,str,ans,223,复盘
From: https://www.cnblogs.com/2020luke/p/18114124

相关文章

  • [ABC223F] Parenthesis Checking 题解
    [ABC223F]ParenthesisChecking题解思路解析在开始之前,首先我们需要知道合法括号序列的判断方法。我们可以给每个括号打上权值,设左括号权值为\(1\),右括号权值为\(-1\),这样一个\(\texttt{(()())}\)括号串用数字存下就是\(1,1,-1,1,-1,-1\),这时我们再给序列计算一下前缀和......
  • CHC5223数据结构和算法
    CHC5223数据结构和算法2023-2024第2学期第1页,共4页课业1价值40%的课程个人工作学习成果学生将能够理解:1.1数据结构1.2数据结构的应用1.3面向对象编程概念1.4程序测试方法学生将掌握以下方面的技能:2.1数据抽象2.2数据结构的使用2.3使用高级面向对象语言进行更高级的编程2.4程序......
  • [ABC211F] Rectilinear Polygons 题解
    [ABC211F]RectilinearPolygons题解思路什么的上一篇题解已经写的非常明白了,这里只是提供一个补充&另一个实现的方法。思路解析先说结论:扫描线。顾名思义,扫描线的本质就是用一条线沿着\(x\)或\(y\)轴扫过去,每碰到一条边就记录一下加边后是面积是增加还是减少,然后用树状......
  • [ABC211D] Number of Shortest paths 题解
    [ABC211D]NumberofShortestpaths题解思路解析题目其实说得很明白了,就是最短路计数。我们可以用一个\(s_i\)表示从起点到\(i\)的最短路计数,然后进行bfs,由于边权为\(1\),所以可以使用bfs求最短路。如果\(u\tov\)是\(v\)的最短路的其中一段,就把\(s_u\tos_v\)......
  • [ABC221D] Online games 题解
    [ABC221D]Onlinegames题解思路解析可以发现题目就是单纯区间加和查询每一个值有多少次出现。首先看到区间修改加结束时查询可以想到差分,但是通过\(A_i\le10^9\)发现值域很大没法直接根据值差分。于是想到离散化,将每个点离散下来,统计每两个离散的时间之间在线的人乘上时间......
  • [ABC223E] Placing Rectangles 题解
    [ABC223E]PlacingRectangles题解思路解析根据题目可知,其实三个长方形无非只有以下两种摆放方式。若大长方形长为\(y\),宽为\(x\),则我们对于第一种情况就固定住宽,判断能否使长度小于等于长;对于第二种情况同样固定住宽,此时A长方形右边空间的长就确定了,就只需要判断B,C......
  • ABC221 复盘
    ABC221复盘[ABC221A]Seismicmagnitudescales思路解析数据范围\(B\leA\le10\),可以发现能直接暴力求解。注意开longlong。code//ABC221A#include<bits/stdc++.h>usingnamespacestd;inta,b;intmain(){ cin>>a>>b; a-=b; longlongans=1; for......
  • [ABC221E] LEQ 题解
    [ABC221E]LEQ题解思路解析很有思维量的一道题。首先根据题目要求发现,新求的子序列只跟子序列的头尾有关,而在确定头尾之后中间的元素选或不选没有任何关系。也就是确定新子序列的头尾下标分别为\(i,j\),那么以当前头尾的可行子序列个数就是\(2^{j-i-1}=2^j\div2^{i+1}\)种......
  • Java后端新手的第一次面试复盘
    昨天经历了第一次Java后端实习生面试,在无数次的简历投递后,很难得的一次面试机会,收获很多,也深刻感受到自己能力的不足(还需要继续沉淀半个学期),在此记录下收获和感悟,如有错误,欢迎指正!1.面试流程闲聊(5分钟):自我介绍+询问背景动机技术问答(45分钟):包括Java基础、数据库技......
  • [ABC259F] Select Edges 题解
    很容易想到树形dp。考虑在有根树内,每个点都有两种状态:不选自己和父亲的边;要选自己和父亲的边。那么单独对于子树内部而言,就要分两种情况:最多可以向\(d_i\)个孩子连边,对应上述第一种情况,我们称之为\(f_i\);最多可以向\(d_i-1\)个孩子连边,对应上述第二种情况,我们称之......