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;
}原文地址：https://blog.csdn.net/2301_80105412/article/details/140653571
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！