昨晚ABC题解(A,B,C,F)

复仇者_帅童

2025-08-31 19:52:27

发布于：广东

27阅读

0回复

0点赞

上大大大大大分！！！

A

题意解析：自己翻译去。

没什么好说的，使用 string 数组，for 循环输入，判断用 ==。我这里使用了三目运算符，等价于 if else。

#include <iostream>
#include <cstdio>
using namespace std;
string a[100005];
int n;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	int idx;
	string val;
	cin >> idx >> val;
	cout << (a[idx] == val ? "Yes" : "No");

	return 0;
}

时间复杂度： $O(n|s|)$ 。

B

题意解析：
定义 $f(x)$ 为 $x$ 的十进制位反转后的结果。如 $f(114514)=415411$ 。
定义 “反转斐波那契数列” $A_n$ 如下：

$A_n= \begin{cases} x & n=1\\ y & n=2\\ f(A_{n-1}+A_{n-2}) & n\ge 3 \end{cases}$

现给定 $x,y$ ，求 $A_{10}$ 的值。

我们可以用 to_string 和 stoi（stoll）模拟反转过程，然后递推求就行了。注意开 long long。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
int a[11];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> a[1] >> a[2];
	for(int i = 3; i <= 10; i++){
		string tmp = to_string(a[i - 1] + a[i - 2]);
		reverse(tmp.begin(), tmp.end());
		a[i] = stoll(tmp);
	}
	cout << a[10];

	return 0;
}

时间复杂度： $O(1)$ 。

C

题意解析：
给定一个 AB 字符串，每次操作可以交换相邻两个元素，问最少操作多少次可以变成一个 ABABAB... 或 BABABA... 字符串。

懒得写了，反正就是不考虑 A 或 B 把交换当做移动就行。直接亮代码。

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n;
	string s;
	cin >> n >> s;
	s = ' ' + s;
	int idx = 1, ans = 0, ans2 = 0;
	for(int i = 1; i <= n * 2; i++){
		if(s[i] == 'A'){
			ans += abs(i - idx);
			idx += 2;
		}
	}
	idx = 1;
	for(int i = 1; i <= n * 2; i++){
		if(s[i] == 'B'){
			ans2 += abs(i - idx);
			idx += 2;
		}
	}
	cout << min(ans, ans2);

	return 0;
}

时间复杂度： $O(n)$ 。

F

题意解析：给定一个数组 $A$ ， $A$ 最初只有一个元素，该元素为 $0$ 。

你需要进行 $q$ 次操作，每次操作分为操作 $1$ 和操作 $2$ 。

操作 $1$ ：给定一个正整数 $x$ ，在 $A$ 数组元素为 $x$ 的后一个位置添加一个元素 $i$ 。
操作 $2$ ：给定两个正整数 $x,y$ ，令 $x,y$ 在 $A$ 数组的下标分别为 $p,q$ ，则请你输出 $A$ 数组中区间 $[\min\{p,q\}+1,\max\{p,q\}-1]$ 的所有元素和，并删除该区间。

显然，操作 $2$ 影响不到操作 $1$ ，因为无论何时 $A$ 中的元素都互不相同，如果某个数 $k$ 被删除了，那么操作 $1$ 就不能让 $x=k$ 了。同理，操作 $2$ 之间也互不影响。

所以我们可以离线所有的操作，预处理出如果没有操作 $2$ ，最终的 $A$ 中每个位置的值和每个值对应的下标。显然可以使用链表求出。

然后按顺序执行每次操作，开一个线段树，操作 $1$ 直接将 $x$ 对应的下标改成 $x$ ，操作 $2$ 用求出区间和，然后将区间的所有值都设为 $0$ 即可。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
class Segtree{// 线段树
	private:
	vector <int> tree, lazytag, left, right;
	int n;
	void push_up(int u){
		tree[u] = tree[u << 1] + tree[u << 1 | 1];
	}
	void push_down(int u){
		if(!lazytag[u]) return;
		lazytag[u << 1] = 1;
		lazytag[u << 1 | 1] = 1;
		tree[u << 1] = 0;
		tree[u << 1 | 1] = 0;
		lazytag[u] = 0;
	}
	void build(int u, int l, int r){
		left[u] = l, right[u] = r;
		if(l == r) return;
		int mid = l + r >> 1;
		build(u << 1, l, mid);
		build(u << 1 | 1, mid + 1, r);
		push_up(u);
	}
	void _modify_id(int u, int idx, int val){
		if(left[u] == idx && right[u] == idx){
			tree[u] = val;
			return;
		}
		push_down(u);
		int mid = left[u] + right[u] >> 1;
		if(idx <= mid) _modify_id(u << 1, idx, val);
		else _modify_id(u << 1 | 1, idx, val);
		push_up(u);
	}
	void _modify(int u, int l, int r){
		if(left[u] >= l && right[u] <= r){
			tree[u] = 0;
			lazytag[u] = 1;
			return;
		}
		push_down(u);
		int mid = left[u] + right[u] >> 1;
		if(l <= mid) _modify(u << 1, l, r);
		if(r > mid) _modify(u << 1 | 1, l, r);
		push_up(u); 
	}
	
	int _query(int u, int l, int r){
		if(left[u] >= l && right[u] <= r) return tree[u];
		push_down(u);
		int ans = 0;
		int mid = left[u] + right[u] >> 1;
		if(l <= mid) ans += _query(u << 1, l, r);
		if(r > mid) ans += _query(u << 1 | 1, l, r);
		return ans;
	}
	
	public:
	Segtree(){}
	void init(int n){
		this -> n = n;
		tree.resize(n << 2 | 1, 0);
		left.resize(n << 2 | 1, 0);
		right.resize(n << 2 | 1, 0);
		lazytag.resize(n << 2 | 1, 0);
		build(1, 1, n);
	}
	void modify_id(int idx, int val){// 将坐标 idx 的值改成 val
		_modify_id(1, idx, val);
	} 
	void modify(int l, int r){// 将区间 [l,r] 的值都改为 0
		_modify(1, l, r);
	}
	int query(int l, int r){// 求区间 [l,r] 的和
		return _query(1, l, r);
	}
	
}tr;
struct queries{//离线操作
	int tmp;
	int x, y;
	int id;
}q[500005];
int id[500005];
int nxt[500005];
int t;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> t;
	for(int i = 1; i <= t; i++){
		int tmp;
		cin >> tmp;
		if(tmp == 1){
			int x;
			cin >> x;
			q[i] = {tmp, x, 0, i};
			nxt[i] = nxt[x];// 在链表中插入元素
			nxt[x] = i;
		}else{
			int x, y;
			cin >> x >> y;
			q[i] = {tmp, x, y, i};
		}
	}
	vector <int> cur = {0}; 
	while(nxt[cur.back()]){
		cur.push_back(nxt[cur.back()]);// 求出没有操作 2 的最终数组
	}
	for(int i = 0; i < cur.size(); i++){
		id[cur[i]] = i + 1;// 记录下每个元素的下标
	}
	tr.init(cur.size() + 1);
	for(int i = 1; i <= t; i++){
		if(q[i].tmp == 1){
			int x = id[i];
			tr.modify_id(x, i);// 修改
		}else{
			int x = id[q[i].x], y = id[q[i].y];// 获取对应的下标
			if(x > y) swap(x, y);
			cout << tr.query(x + 1, y - 1) << '\n';// 求区间和
			tr.modify(x + 1, y - 1);// 将区间都变成 0
		}
	}

	return 0;
}

时间复杂度： $O(q\log q)$ 。

有帮助，赞一个

去预览

0/2000

全部评论 5

༺ཌༀཉི༒白·羊༒༃ༀད༻
F题你做出来了？我D题卡了好久

22小时前来自上海
1
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复༺ཌༀཉི༒白·羊༒༃ༀད༻
  有石粒
  
  22小时前来自上海
  1
天之神—༺ཌༀ༒∞申博源∞༒ༀད
6这是什么网站呀？

2小时前来自北京
0
\
orz

17小时前来自广东
0
复仇者_帅童
d

17小时前来自广东
0
AAA混泥土批发ppl哥

我上面两个大sb（（（

22小时前来自浙江
0
- AAA混泥土批发ppl哥
  回复AAA混泥土批发ppl哥
  20min切掉ABC，剩下的时间全给G了，cao，早知道先做D了，摸你题
  
  22小时前来自浙江
  0
- \
  回复AAA混泥土批发ppl哥
  红温了
  
  17小时前来自广东
  0
- \
  回复AAA混泥土批发ppl哥
  全都1000+了
  
  17小时前来自广东
  0

A

B

C

F

全部评论 5

热门讨论