abc-347

title: abc 347
date: 2024-04-01 01:57:25
tags: 比赛
categories: 赛后思考与总结

A

思路

能够被整除的就输出

代码

void solve()
{
	int n,k;
	cin >> n >> k;
	vector<int> vec;
	for(int i = 1; i <= n ; i ++){
		int x; cin >> x;
		if(x % k == 0) vec.push_back(x / k);
	}
	
	for(auto x : vec) cout << x << ' ';
	
}

B

思路

用set存储每一个不同的子串，输出个数即可

代码

void solve()
{
	
	set<string> s;
	string str; cin >> str;
	
	for(int i = 0; i < str.size(); i ++){
		string t;
		for(int j = i; j < str.size(); j ++){
			t += str[j];
			//cout << t << endl;
			s.insert(t);
		}
	}
	
	cout << s.size() << endl;
	
}

C

思路

我们只关心这些日子在一周内的相对位置，将位置排序我，然后两个相对日子的位置中间可以插入一个b，则输出 Yes。

代码

int c[N];

void solve()
{
	int n,a,b;
	cin >> n >> a >> b;
	
	for(int i = 1; i <= n; i ++){	
		cin >> c[i];
		c[i] %= (a + b);
	}
	
	sort(c + 1,c + 1 + n);
	c[n + 1] = c[1] + a + b;
	for(int i = 2; i <= n + 1; i ++){
		//cout << c[i] << ' ';
		if(c[i] - c[i - 1] > b){
			cout << "Yes\n";
			return;
		}
	}
	cout << "No" << endl;
	
}

D

思路

当x与y之和比目标数1的数量还要少，那一定是无解。异或是相同的为0不同的为1，那么我们在构造的时候，先将目标数位数为1的时候进行构造。当填完1的时候，剩余为0的部分，a 和 b的大小一定要相同，否则无法构造，则无解。最后在判断一下a 与 b是否都为0，否则无解，最后输出结果即可

代码

int c[N];

void solve()
{
	int a,b;
	cin >> a >> b;
	ll n;cin >> n;
	int cnt = bpt(n);
	ll x = 0, y  = 0;
	if(a + b < cnt){
		cout << -1 << endl;
		return ;
	}
	for(int i = 0; i <= 60; i ++){
		if(n & (1ll << i)){
			if(a > b){
				a --;
				x += (1ll << i);
			}
			else if(b){
				b --;
				y += (1ll << i);
			}
		}
	}
	if(a != b){
		cout << -1 << endl;
		return;
	}
	
	for(int i = 0 ; i <= 60; i ++){
		if(a && b && !(n & (1ll << i))){
			a --,b --;
			x += (1ll << i);
			y += (1ll << i);
		}
	}
	if(a || b){
		cout << -1 << endl;
		return;
	}
	cout << x << ' ' << y << endl;
}

E

思路

朴素做法是，每一次操作将数组的值更新，这肯定超时。一个x在集合s当中做出的贡献是一段连续的区间，在这段出现然后删除的这段区间里，x的贡献值就是这个操作区间的前缀和。因此我们维护一个操作区间的前缀和，同时维护x何时放入的位置即可。

代码

void solve()
{
	int n,q;
	cin >> n >> q;
	
	vector<ll> ans(n + 1);
	vector<ll> pre;
	vector<int> lt(n);
	
	set<int> s;
	pre.push_back(0);
	for(int i = 1; i <= q;  i++){
		int x; cin >> x;
		if(s.count(x)){
			ans[x] += pre[i - 1] - pre[lt[x] - 1];
			s.erase(x);
		}
		else{
			s.insert(x);
			lt[x] = i;
		}
		pre.push_back(pre.back() + s.size());
	}
	
	
	for(auto i : s){
		ans[i] += pre[q] - pre[lt[i] - 1];
	}
	
	for(int i = 1; i <= n ; i ++ ) cout << ans[i] << ' ';
}