[数据结构与算法]Codeforces Round #776 (Div. 3)

Codeforces Round #776 (Div. 3)

A. Deletions of Two Adjacent Letters

题目大意

给定一个字符串s和一个字符c,能对字符串进行删除操作,删除相邻两个,求能否的到字符c

思路

每次删除两个,可以想到如果c在字符串的奇数位置最后肯定能获得

参考代码

#include <bits/stdc++.h>
#define int long long
#define debug(x) \
    ;            \
    cout << x << "---" << endl;
 
using namespace std;
const int N = 1e6;
int a[N], b[N];
 
void slove()
{
    string s;
    char c;
    cin >> s >> c;
    bool flag = 0;
    for (int i = 0; i < s.size(); i++)
    {
        if (i % 2 == 0 && s[i] == c)
            flag = 1;
    }
    if (flag)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}
 
signed main()
{
    int _;
    cin >> _;
    while (_--)
        slove();
    return 0;
}

B. DIV + MOD

题目大意

定义fa(x) = x/a + x mod a , 然后给定 [l,r] 求结果的最大值

思路

当 a = 1 时直接输出 r, 否则我们就得判断是否能凑出a-1,如果凑不出来f?为最大

代码

#include <bits/stdc++.h>
#define int long long
#define debug(x) \
	;            \
	cout << x << "---" << endl;

using namespace std;
const int N = 1e6;

signed main()
{
	int _, l, r, a, cnt, u;
	cin >> _;
	while (_--)
	{
		cin >> l >> r >> a;
		if (a == 1)
		{
			cout << r << endl;
			continue;
		}
		l = max(l, r - a + 1);
		cnt = l / a;
		u = r - l;
		l %= a;
		r = l + u;
		if (r >= a - 1)
			cnt += a - 1;
		else
			cnt += r % a;
		cout << cnt << endl;
	}
	return 0;
}

C. Weight of the System of Nested Segments

题目大意

找到n个符合条件的区间,找出他们权值最小的值,并且输入每一个对应的 i

思路

我们只需找出前n2的最小权值,然后将这n2个点用双指针输出序列

代码

#include <bits/stdc++.h>
#define int long long
#define debug(x) \
	;            \
	cout << x << "---" << endl;
 
using namespace std;
const int N = 1e6;
struct A
{
	int x, w, o;
} a[N];
 
bool cmp(A n, A m)
{
	return n.w < m.w;
}
 
void slove()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> a[i].x >> a[i].w;
		a[i].o = i + 1;
	}
	sort(a, a + m, cmp);
	int sum = 0;
	vector<pair<int, int>> ans;
	for (int i = 0; i < n * 2; i++)
	{
		sum += a[i].w;
		ans.push_back({a[i].x, a[i].o});
	}
	cout << sum << endl;
	sort(ans.begin(), ans.end());
	for (int i = 0, j = n * 2 - 1; i <= j; i++, j--)
		cout << ans[i].second << " " << ans[j].second << endl;
	cout << endl;
}
 
signed main()
{
	int _;
	cin >> _;
	while (_--)
		slove();
	return 0;
}