Atcoder ABC393游记

太爽了

Atcoder ABC393游记（A~F）

比赛链接

A.Poisonous Oyster

题目描述

有四个东西，编号为$1~4$，其中有一个有毒，如果吃了有毒的东西就会挂掉。

第一个人吃了编号为$1,2$的东西，第二个人吃了编号为$1,3$的东西。

现在给你两个字符串$S_1$和$S_2$，分别代表两个人的状态，如果是sick表示这个人挂了，如果是fine说明还活着。

问你哪个东西有毒？

思路

没啥好说的

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s1, s2;
	cin >> s1 >> s2;
	bool c1 = (s1 == "sick"), c2 = (s2 == "sick");
	if (c1 && c2) {
		cout << 1;
	} else if (c1 && !c2) {
		cout << 2;
	} else if (!c1 && c2) {
		cout << 3;
	} else {
		cout << 4;
	}
	return 0;
}

B.A…B…C

题目描述

给你一个字符串$S$，求有几组$(i,j,k)$满足：

• $i<j<k$且$S_i=$A且$S_j=$B且$S_k=$C且$j-i=k-j$。

思路

这里$N$最大到$100$，枚举即可。

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	cin >> s;
	int cnt = 0;
	for (int i = 0; i < s.length(); i++) {
		for (int j = i + 1; j < s.length(); j++) {
			for (int k = j + 1; k < s.length(); k++) {
				if (j - i == k - j && s[i] == 'A' && s[j] == 'B' && s[k] == 'C') { 
					cnt++;
				}
			}
		}
	}
	cout << cnt;
	return 0;
}

C.Make it Simple

题目描述

给你一个$N$个点$M$条边的无向图，问你最少删除几条边可以使这张图变成简单图？

一个图被称作简单图当且仅当这个图没有重边或自环。

思路

不是，这回abc有点过于简单了吧

我们读入边的时候就可以把答案搞出来，当遇到set中存在的边或者起点和终点相同的时候我们就把答案$+1$，最后直接输出就行了

代码

#include<bits/stdc++.h>
using namespace std;
int n, m;
int main()
{
	int ans = 0;
	cin >> n >> m;
	set<pair<int, int>> have;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		if (have.count({u, v}) || have.count({v, u})) {
			ans++;
			continue;
		} else {
			have.insert({u, v});
			have.insert({v, u});
		}
		if (u == v) {
			ans++;
		}
	}
	cout << ans;
	return 0;
}

D.Swap to Gather

题目描述

给你一个$N$以及一个长度为$N$的01串$S$，每次可以交换相邻两个字符的位置。

问你最少进行几次交换可以让所有的1连续？

思路

简单贪心，把所有的1往中间移就是最优方案。

对了，别忘了开ll。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
	int n;
	string s;
	cin >> n >> s;
	vector<int> pos;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '1') {
			pos.push_back(i);
		}
	}
	int mid = pos.size() / 2;
	int m = pos[mid];
	int ans = 0;
	for (int i = 0; i < pos.size(); i++) {
		ans += abs(pos[i] - (m - mid + i));
	}
	cout << ans;
	return 0;
}

E.GCD of Subset

题目描述

给你两个整数$N$和$K$，和一个长度为$N$的序列$A=(A_1,A_2,...,A_N)$，对于每个$1 \leq i \leq N$，输出这个问题的解：

• 当你从$A$中选出$K$个包含$A_i$的元素，最大可能得到的他们的最大公因数是多少？

思路

我们把$cnt[i]$定义为因数中有i的数的个数，然后通过这个算答案就行了，具体细节还是要看代码。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	int maxx = 0;
	for (int i = 0; i < n; i++){
		cin >> a[i];
		maxx = max(maxx, a[i]);
	}
	vector<int> tim(maxx + 1, 0);
	for (int i = 0; i < n; i++) {
		tim[a[i]]++;
	}
	vector<int> cnt(maxx + 1, 0);
	for (int d = 1; d <= maxx; d++){
		for (int j = d; j <= maxx; j += d){
			cnt[d] += tim[j];
		}
	}
	vector<int> ans(maxx + 1, 0);
	for (int d = 1; d <= maxx; d++){
		if(cnt[d] >= k){
			for (int j = d; j <= maxx; j += d){
				ans[j] = max(ans[j], d);
			}
		}
	}
	for (int i = 0; i < n; i++){
		cout << ans[a[i]] << '\n';
	}
	return 0;
}

F.Prefix LIS Query

题目描述

给你一个长度为$N$的数组$A=(A_1,A_2,\dots,A_N)$。

回答$Q$个问题。第$i$个询问是这样的:

给你两个整数$R$和$X$，考虑$A$的前$R$个元素$(A_1,A_2,\dots,A_R)$的一个子序列（不一定非得连续），满足它严格递增并且元素的最大值$\leq X$，输出这个子序列的最大长度。

思路

我们定义$dp_i$为以$a_i$结尾的LIS答案。

对于每个位置，用树状数组得到所有比当前的小的数组对应的$dp$的最大值，然后$dp_i$就是这个最大值$+1$。

然后我们就可以对于每个询问离线查询就可以搞定了！

upd:这题貌似有二分并且不用数据结构做出来的dalao，太奇妙了。

代码

#include <bits/stdc++.h>
using namespace std;
vector<array<int,3>> tc; 
vector<int> vals;
struct node
{
	int n;
	vector<int> tree;
	node(int _n) {
		n = _n;
		tree.resize(_n + 1, 0);
	}
	void update(int idx, int val) {
		for(; idx <= n; idx += idx & -idx) {
			tree[idx] = max(tree[idx], val);
		}
	}
	int query(int idx) {
		int res = 0;
		for(; idx; idx -= idx & -idx) {
			res = max(res, tree[idx]);
		}
		return res;
	}
};
bool cmp(const array<int, 3> &a1, const array<int, 3> &b1)
{
	return a1[0] < b1[0];
}
int getidx(int x)
{
	return int(lower_bound(vals.begin(), vals.end(), x) - vals.begin()) + 1;
}
int main(){
	int n, q;
	cin >> n >> q;
	vector<int> a(n);
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	vals = a;
	for(int i = 0; i < q; i++){
		int r, x;
		cin >> r >> x;
		vals.push_back(x);
		tc.push_back({x, r, i});
	}
	sort(vals.begin(), vals.end());
	vals.erase(unique(vals.begin(), vals.end()), vals.end());
	node ndp(vals.size());
	vector<int> dp(n, 0);
	for(int i = 0; i < n; i++){
		int pos = getidx(a[i]);
		dp[i] = ndp.query(pos - 1) + 1;  
		ndp.update(pos, dp[i]);
	}
	vector<array<int, 3>> info;
	for (int i = 0; i < n; i++){
		info.push_back({a[i], i + 1, dp[i]});
	}
	sort(info.begin(), info.end(), cmp);
	sort(tc.begin(), tc.end(), cmp);
	node nans(n);
	vector<int> ans(q, 0);
	int cnt = 0;
	for(int i = 0; i < tc.size(); i++){
		array<int, 3> tp = tc[i];
		int x = tp[0], r = tp[1], idx = tp[2];
		while(cnt < n && info[cnt][0] <= x) {
			int pos = info[cnt][1];
			int val = info[cnt][2];
			nans.update(pos, val);
			cnt++;
		}
		ans[idx] = nans.query(r);
	}
	for (int i = 0; i < q; i++) {
		cout << ans[i] << '\n';
	}
	return 0;
}

总结

我也不知道