Codeforces Round #776 (Div. 3)

菜鸡在这里做做笔记，各位进来的大佬我先 orz 了

B

#include<bits/stdc++.h>
#define ll long long
using namespace std;
 
const int N = 2e5 + 10;
const int inf = 0x3f3f3f3f;
int n;
int main()
{
	long long l, r, a;
	cin >> n;
	while (n--)
	{
		cin >> l >> r >> a;
		if (a == 1)
		{
			cout << r << endl;
			continue;
		}
		ll p = (r / a) * a - 1LL;//p为mod a后等于a-1的数
		if (p < l)p = l;
		ll ans = max(p / a + p % a, r / a + r % a);
		cout << ans << endl;
	}
	return 0;
}

p = (r / a) * a - 1LL的原理 

        C

本题为贪心算法，权重最高的前2n个节点权重累加，建立嵌套段系统时只需讲第i个位置和n+1-i位置连接起来即可，输出时使用该输出方法使得节点下标小的节点在前。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
 
const int N = 2e5 + 10;
const int inf = 0x3f3f3f3f;
struct node
{
	ll loc, w;
	ll idx;
}a[N],b[N];
 
bool cmp1(node x1, node x2)
{
	return x1.w < x2.w;
}
 
bool cmp2(node x1, node x2)
{
	return x1.loc < x2.loc;
}
void solve()
{
	ll n, m, ans = 0;
	cin >> n >> m;
	for (ll i = 1; i <= m; i++)
	{
		cin >> a[i].loc >> a[i].w;
		a[i].idx = i;
	}
	sort(a + 1, a + 1 + m, cmp1);
	ll r = n * 2;
	for (ll i = 1; i <= r; i++)
	{
		ans += a[i].w;
		b[i] = a[i];
	}
	sort(b + 1, b + 1 + r, cmp2);
	cout << ans << endl;
	for (int i = 1; i <=n; i++)
		cout << min(b[i].idx, b[r - i + 1].idx) << " " << max(b[i].idx, b[r + 1 - i].idx) << endl;
	cout << endl;
}
int main()
{
	int _;
	cin >> _;
	while (_--)
	{
		solve();
	}
	return 0;
}