Atcoder ABC 393

给出

N

个点和

M

条边的无向图，最少需要删除多少边使得这个图成为简单图，即没有重边和自环。

遇到自环直接删除。
用 $map$ 记录重边

CPP

#include<bits/stdc++.h>
using namespace std;
map<pair<int, int>, int>mp;
// mp [{u,v}] -> u到v的边有没有出现过
int main(){
	int n, m;
	cin >> n >> m;
	int ans = 0;
	
	for(int i = 1; i <= m; i++){
		int u, v;
		cin >> u >> v;
		//默认让小的点 连向大的点
		if(u > v) swap(u, v);
		if(u == v) ans++;
		else if(mp.count({u, v})) ans++;
		mp[{u, v}] = 1;
	}	
	cout << ans << endl;
	return 0;
}

D - Swap to Gather

先确定移动的位置，可以大胆猜一下，往哪个1去靠。显然往中间的1去靠，比边上的1会更优。类似中位数求最短距离一样。

把所有是1的位置都找出来，放入

pos

数组中，可以先求出中位数的位置

mid

。

对于第

i

个1，它贡献的答案为

abs(pos[mid] - pos[i] - (mid - i))

CPP

#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 < n; i++)
        if (s[i] == '1')
            pos.push_back(i);
            
    int cnt = pos.size();

    if (cnt <= 1){
        cout << 0 << endl;
        return 0;
    }
	 
    int mid = cnt / 2, ans = 0;
    for (int i = 0; i < pos.size(); i++)
        ans += abs(pos[mid] - (mid - i) - pos[i]);

    cout << ans << endl;

    return 0;
}

解法2：

考虑对0的移动，对于第

i

位上的0，统计左侧

1

的个数为

x

，右侧

1

的个数为

y

。

最终的得到的字符串形状：0...01...10..0，前面0的数量可能是

0

个，后面0的数量可能是

0

个。

从左往右考虑`0',它对答案的贡献是

min(x, y);

E - GCD of Subset

思路：考虑枚举最大公约数

d

，再看

d

的倍数个数和

k

的关系，来决定

d

能不能作为答案。

做法：

$mp[i]$ 统计数字 $i$ 的数量， $ans[i]$ 表示数字 $i$ 的答案。
枚举当前最大公约数 $d$ , 再枚举 $d$ 的倍数，得到原数组中有约数的数量为 $cnt$ 个。
若 $cnt >= k$ , 则说明一定能从原数组中选出k个数，使得他们的最大公约数至少为 $d$ ，所以可以把所有 $d$ 的倍数的答案更新为 $d$
考虑完所有的 $d$ 后，此时 $ans[i]$ 就是数字i的最优答案。

例如样例1：

3 4 6 7 12

d

1

时，则当前算出

ans[3] = ans[4] = ans[6] = ans[7] = ans[12] = 1

d

2

时，更新

ans[4] = ans[6] = ans[12] = 2

d

3

时，更新

ans[3] = ans[6] = ans[12] = 3

...

CPP

#include<bits/stdc++.h>
using namespace std;
const int N = 12e5 + 10;

int a[N], mp[N], ans[N];

signed main(){
	int n, k;
	cin >> n >> k;
	int lim = 0;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		mp[a[i]]++;
		lim = max(lim, a[i]);
	}
	
	for(int d = 1; d <= lim; d++){
		int cnt = 0;
		for(int i = d; i <= lim; i += d)
			cnt += mp[i];
		
		if(cnt >= k){
			for(int i = d; i <= lim; i += d)
				ans[i] = d;
		}
	}	
	for(int i = 1; i <= n; i++)
		cout << ans[a[i]] << endl;                             
	return 0;
}

F - Prefix LIS Query

根据

DP

求

LIS

的思想，设

f[i]

为当前项时长度为

i

的

LIS

序列末项最小值，

由于

f[i]

具有递增性，每次二分查找在数组

f

中第一个大于等于

a[i]

的位置更新。

离线查询，每次在对应的r的位置，二分求在当前状态下数组

f

中最后一个不大于

x

的位置需要即为答案。

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10, inf = 1e18;
int n, q, a[N], f[N];

struct node{
	int id, r, x, ans;
}qry[N];

bool cmp(node A, node B){
	return A.r < B.r;
}

bool cmp2(node A, node B){
	return A.id < B.id;
}

signed main(){
	scanf("%lld%lld", &n, &q);
	for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
	for(int i = 1; i <= q; i++){
		int r, x;
		scanf("%lld%lld", &r, &x);
		qry[i] = {i, r, x, 0};
	}
	
	sort(qry + 1, qry + q + 1, cmp);
	
	for(int i = 1; i <= n; i++) f[i] = inf;
	
	f[0] = 0;
	for(int i = 1, j = 1; i <= n; i++){
		int k = lower_bound(f, f + n + 1, a[i]) - f;
		f[k] = min(f[k], a[i]);
		
		while(j <= q && qry[j].r == i){
			qry[j].ans = upper_bound(f, f + n + 1, qry[j].x) - f - 1;
			j++;
		}
	}
	
	sort(qry + 1, qry + q + 1, cmp2);
	
	for(int i = 1; i <= q; i++)
		printf("%lld\n", qry[i].ans);
	
	return 0;
}

文章操作

相关推荐

评论

Atcoder ABC 393