Codeforces Round 961 (Div. 2)

A题：Diagonals

题意

给定一个n x n的网格，k个筹码，放在某个位置，则其对应的右上-左下对角线被占用，问占用的对角线数量最少是多少？

思路

模拟

每次我们都往格子最多的对角线上放，然后次多...

很容易看出来

代码

inline void solve() {
     int n, k; cin >> n >> k;
     if (k == 0) return cout << 0 << endl, void();
     if (k - n <= 0) return cout << 1 << endl, void();
     k -= n;
     int ans = 2;
     for (int i = n - 1; i; i -- ) {
     	if (k - i <= 0) return cout << ans << endl, void();
     	k -= i, ans += 1;
     	if (k - i <= 0) return cout << ans << endl, void();
     	k -= i, ans += 1;
     }
	 return;
}

B1：Bouquet (Easy Version) 

题意

一个小女孩去买花，花店中有n种花，每种花有ai个花瓣

小女孩买来的花束中要求任意两个花瓣数相差不超过1

买ai个花瓣的花，需要ai元，她有m元

问最多花多少元

思路

如果你是用map做的话，B1和B2就会做的飞快）

我们贪心地想，买的多花的也就越多，那么对于t个花瓣的和t+1个花瓣的

我们尽可能地去买t个花瓣的，再去看t+1个花瓣能买多少

但是这再最后一个样例中是错误的

还可以通过少买一个t个花瓣的，多买一个t+1个花瓣的操作，来实现多花一块

那我们只需要先按贪心的来，再看能进行上述操作最多几次即可。

代码

inline ll min(ll a, ll b) {
	return a > b ? b : a;
}
inline ll max(ll a, ll b) {
	return a > b ? a : b;
}
inline void solve() {
     int n; ll k; cin >> n >> k;
     map<int, int> cnt;
     for (int i = 1; i <= n; i ++ ) {
     	int x; cin >> x;
     	cnt[x] += 1;
     }
     ll ans = 0;
     for (auto [t, c] : cnt) {
     	ll res = t * min(c, k / t);
     	if (cnt.count(t + 1)) {
     		ll cnt0 = min(c, k / t);
     		ll last = k - res;
     		ll cnt1 = min(last / (t + 1), cnt[t + 1]);
     		res += cnt1 * (t + 1) + min(cnt0, min(cnt[t + 1] - cnt1, last - cnt1 * (t + 1)));
     	}
     	ans = max(ans, res);
     }
     cout << ans << endl;
	 return;
}

B2：Bouquet (Hard Version) 

没啥区别，只是对于map的输入改了下而已，笑qwq

代码

inline ll min(ll a, ll b) {
	return a > b ? b : a;
}
inline ll max(ll a, ll b) {
	return a > b ? a : b;
}
inline void solve() {
     int n; ll k; cin >> n >> k;
     vector<PII> a(n);
     for (int i = 0; i < n; i ++ ) cin >> a[i].first;
     for (int i = 0; i < n; i ++ ) cin >> a[i].second;
     map<int, int> cnt;
     for (int i = 0; i < n; i ++ ) {
     	cnt[a[i].first] = a[i].second;
     }
     ll ans = 0;
     for (auto [t, c] : cnt) {
     	ll res = t * min(c, k / t);
     	if (cnt.count(t + 1)) {
     		ll cnt0 = min(c, k / t);
     		ll last = k - res;
     		ll cnt1 = min(last / (t + 1), cnt[t + 1]);
     		res += cnt1 * (t + 1) + min(cnt0, min(cnt[t + 1] - cnt1, last - cnt1 * (t + 1)));
     	}
     	ans = max(ans, res);
     }
     cout << ans << endl;
	 return;
}

C题：Squaring 

题意

给定一个数组，每次你可以选定一个元素使其成为本身的平方，问至少经过几次操作可以使得整个数组不递减？

思路

平方操作，时间上肯定过的去，但是对于最后一个样例，肯定会爆long long

所以我们的比较，只能是基于ai的本身上

我们可以用一个数组来记录每个位置各用了多少次操作

对于i + 1的位置，若i的位置用了p次操作

   

两边可以不断开方，直到剩到一个数本身ai或者ai+1

即可以为ai <= ai+1的k次  k = q - p    由贪心，k要小

也可以是ai的k次 <= ai      k = p - q    由贪心，k要大

我们通过枚举k就可以知道q，又因为平方增长快，k的枚举范围很小

此外，最后ans将所有次数相加的时候，要开long long，爆了一次...

代码

inline void solve() {
     int n; cin >> n;
     vector<ll> a(n + 1);
     for (int i = 1; i <= n; i ++ ) cin >> a[i];
     int j = 1;
     while (j <= n && a[j] == 1) j += 1;
     vector<int> c(n + 1);
     for (int i = max(j, 2); i <= n; i ++ ) {
     	if (a[i] == 1) return cout << -1 << endl, void();
     	int k = 0;
     	if (a[i] < a[i - 1]) {
     		ll cur = a[i];
     		while (cur < a[i - 1]) {
     			cur *= cur;
     			k += 1;
     		}
     		c[i] = k + c[i - 1];
     	}else {
     		if (a[i - 1] == 1) continue;
     		ll cur = a[i - 1];
     		while (cur * cur <= a[i]) {
     			cur *= cur;
     			k += 1;
     		}
     		c[i] = max(0, c[i - 1] - k);
     	}
     }
     ll ans = 0;
     for (int i = 1; i <= n; i ++ ) ans += c[i];
     cout << ans << endl;
	 return;
}