寒鸽儿のBlog

A

判定状态是否合法 , 首先初始状态中 $p_0 \geqslant c_0$ ，然后在增量中 , $p$ 的增量大于 $c$ 的增量 , 即 $p_i - p_{i-1} \geqslant c_i - c_{i-1} , i \in [1, n-1]$ 。

#include <bits/stdc++.h>
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define per(i,a,b) for(int i=a;i>=(b);--i)
#define repp(i,a,b) for(int i=a;i<(b);++i)
#define perr(i,a,b) for(int i=a;i>(b);--i)
#define pb push_back
#define rz resize
#define VI vector<int>
#define VL vector<long long>
#define VD vector<double>

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tests;
	cin>>tests;
	while(tests--) {
		int n, p, c, pi, ci;
		bool flg = true;
		cin>>n;
		--n;
		cin >> p >> c;
		if(p < c) flg = false;
		while(n--) {
			cin >> pi >> ci;
			if(pi < p || ci < c || pi - p < ci - c || pi < ci) flg = false;
			p = pi; c = ci;
		}
		if(flg) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}

B

因为要平均分配 , 所以选择加入原先拥有钱数尽可能多的人一定是最优的。

因此对钱数排序 , 然后从左往右扫过去 , 看看平均值是否还大于等于 $x$ , 最后一次满足平均值大于等于 $x$ 的人数即为最大总人数。

复杂度 $\mathcal{O(n \log n)}$

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define per(i,a,b) for(int i=a;i>=(b);--i)
#define repp(i,a,b) for(int i=a;i<(b);++i)
#define perr(i,a,b) for(int i=a;i>(b);--i)
#define pb push_back
#define rz resize
#define VI vector<int>
#define VL vector<long long>
#define VD vector<double>

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f, maxn = 12345;
const ll linf = 0x3f3f3f3f3f3f3f3f;

VI a;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tests;
	cin>>tests;
	while(tests--) {
		int n, x;
		cin >> n >> x;
		a.assign(n+2, 0);
		rep(i,1,n) cin >> a[i];
		sort(&a[1], &a[n + 1], [&](int ai, int bi){ return ai > bi; });
		unsigned long long sum = 0;
		rep(i,1,n) {
			sum += a[i];
			if(sum / i < x) {
				cout << i - 1 << endl;
				break;
			}
			if(i == n) cout << n << endl;
		}
	}
	return 0;
}

C

关键在于考虑尽量利用 $b_i$ 。

一个怪 $i$ 如果对后面一个产生爆炸伤害 , 就节省 $c_i = \min \{b_i , a_{(i+1)\%n}\}$ 。

如果是在一条链上 , 显然从头部打到尾部 , 就能充分利用 $c_i$ 。

在一个环上 , 我们首先打掉一个怪 $i$ ， 那么怪 $i-1 \mod n$ 对答案的贡献 $c_{i-1 \mod n}$ 就不能计在内了 , 因此考虑找出最小的 $c_i$ , 舍去其爆炸伤害的贡献。

#include <bits/stdc++.h>
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define per(i,a,b) for(int i=a;i>=(b);--i)
#define repp(i,a,b) for(int i=a;i<(b);++i)
#define perr(i,a,b) for(int i=a;i>(b);--i)
#define pb push_back
#define rz resize
#define VI vector<int>
#define VL vector<long long>
#define VD vector<double>

using namespace std;

typedef long long ll;


const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;

VL a, b;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tests;
	cin>>tests;
	while(tests--) {
		int n;
		ll ans = 0, reg = linf;
		cin >> n;
		a.resize(n + 2);
		b.resize(n + 2);
		rep(i,1,n) cin >> a[i] >> b[i], ans += a[i];
		rep(i,1,n) {
			ans -= min(b[i], a[i%n+1]);
			reg = min(reg, min(b[i], a[i%n+1]));
		}
		ans += reg;
		cout << ans << endl;
	}

	return 0;
}

D

考虑规律 , 通过简单的贪心或者打表可以得到

$n : 1\space 2\space 1\space 3\space 1\space 4\space ...\space 1\space n\space 2\space 3\space 2\space 4\space ...\space 2\space n\space 3\space 4\space 3\space 5\space ...\space 3\space n\space ...\space ...\space n-1\space n\space 1$

关键在于如何确定 $[l, r]$ 内的序列 , 换言之 , 给定下标 $i$ , 求出在序列中对应的值。

撇开最后一个 $1$ 不谈。

考虑奇数位 , 有 $n-1$ 个 $1$ , $n-2$ 个 $2$ , $...$ , $1$ 个 $n-1$ 。

考虑偶数位 , 有 $2\space 3\space 4\space 5\space ...\space n\space 3\space 4\space 5\space ...\space n\space 4\space 5\space ...\space n\space ...\space ...\space n-1\space n$ 注意到每一组的长度也为 $n-1\space n-2\space ...\space 1$ 。

因此预处理数列 $n-1\space n-2\space ...\space 1$ 的前缀和 , 用原下标在奇数/偶数数列中对应的下标在该数列中二分查找即可定位。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define per(i,a,b) for(int i=a;i>=(b);--i)
#define repp(i,a,b) for(int i=a;i<(b);++i)
#define perr(i,a,b) for(int i=a;i>(b);--i)
#define pb push_back
#define rz resize

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f, maxn = 123456;
const ll linf = 0x3f3f3f3f3f3f3f3f;

ll a[maxn], b[maxn];

ll tobound(ll l, ll r, ll key) {
	while(l < r) {
		int mid = (l + r) >> 1;
		if(a[mid] >= key) r = mid;
		else l = mid + 1;	
	}
	return l;
}

ll gen(ll n, ll idx) {
	if(idx == n*(n-1) + 1) return 1;
	if(idx % 2 == 1) {
		idx = idx / 2 + 1;
		return tobound(1, n - 1, idx);
	} else {
		idx /= 2;
		int blk = tobound(0, n - 1, idx);
		idx -= a[blk-1];
		return n - (a[blk] - a[blk-1]) + idx;
	}
}
int main() {
	int tests;
	cin>>tests;
	while(tests--) {
		ll n, l, r;
		cin >> n >> l >> r;
		rep(i,1,n) a[i] = n - i, a[i] += a[i-1];
		for(ll i = l; i <= r; ++i) {
			cout << gen(n, i) << ' ';
		}
		cout << endl;
	}
	return 0;
}