Codeforces Round 961 (Div. 2)
A. Diagonals
题目大意
给 Vitaly503 一个方格棋盘，棋盘的一边有 ( n ) 个单元格，并且有 ( k ) 个筹码。他意识到所有这些 ( k ) 个筹码都需要放置在棋盘的单元格上（一个单元格上不能放置超过一个筹码）。
让我们把第 ( i ) 行和第 ( j ) 列中的单元格表示为 ( (i, j) )。对角线是指 ( i + j ) 值相同的单元格集合。例如，单元格 ( (3, 1) )、( (2, 2) ) 和 ( (1, 3) ) 位于同一条对角线上，但 ( (1, 2) ) 和 ( (2, 3) ) 不在同一条对角线上。如果一条对角线上至少有一个筹码，那么这条对角线就被称为“被占据”的对角线。
我们需要计算在所有放置 ( k ) 个筹码的方法中，被占据的对角线的最少数目。
输入描入
每个测试由多组输入数据组成。第一行包含一个整数 t (1 \le t \le 500) —— 输入数据集的数量。然后是各组输入数据的说明。
每组输入数据的唯一一行包含两个整数 n, k (1 \le n \le 100, 0 \le k \le n^2) —— 分别是棋盘的边数和可用筹码数。
输出描述
对于每组输入数据，输出一个整数--在放置所有 k 个筹码后，他能得到的至少有一个筹码的对角线的最小占位数。
样例输入
7
1 0
2 2
2 3
2 4
10 50
100 239
3 9
样例输出
0
1
2
3
6
3
5
样例说明
在第一个测试案例中，没有筹码，因此 0 个对角线将被占用。在第二个测试案例中，两个筹码都可以放置在对角线 (2, 1), (1, 2) 上，因此答案是 1。在第三个测试案例中，3 个筹码不能放置在一条对角线上，但是将它们放置在 (1, 2), (2, 1), (1, 1) 上会占据 2 条对角线。在第 7 个测试情形中，无论如何放置，筹码都会占据所有 5 条对角线。
思路
这题读题读了半天，最后才明白什么意思，还因为顺序问题错了一会儿。就在于要从大到小的遍历，它的对角线最大是n第二大是n-1，第三大是n-2，除了n以外，其他的角线都各有两条,只考虑一个顺序是因为问题中说了一个对角线集是i +j都相等的。所以只能考虑从右上到左下的这条线，而从左上到右下的对角线它i,j都是增大的，显然不符合对角线级集的定义。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b, int p) {
int res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}
int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}
int n, m;
void solve() {
cin >> n >> m;
if (m == 0) {
cout << 0 << "\n";
return ;
}
int cnt = n, sum = n;
for (int i = 1; ; ++ i) {
if (m <= sum) {
cout << i << "\n";
return;
}
if (i & 1) cnt --;
sum += cnt;
}
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _ = 1;
cin >> _;
while (_--) {
solve();
}
return 0;
}
B1. Bouquet (Easy Version)
题目大意
这是问题的简单版本。唯一不同的是，在这个版本中，每朵花的数量是 1 。
一个女孩准备过生日，她想买一束最漂亮的花。商店里一共有 n 种花，每种花都有花瓣数，一朵有 k 个花瓣的花需要花费 k 枚金币。女孩决定，花束中任何两朵花的花瓣数之差都不能超过 1。同时，女孩希望花束的花瓣数尽可能多。不幸的是，她只有 m 枚金币，无法再花费更多。她能组合的花束的花瓣总数最多是多少？
输入描述
每个测试由多个测试用例组成。第一行包含一个整数 t (1 \le t \le 10\,000) —— 测试用例数。随后是测试用例的说明。
每个测试用例的第一行包含两个整数 n, m (1 \le n \le 2 \cdot 10^5, 1 \le m \le 10^{18}) —— 分别是商店里的鲜花数量和女孩拥有的硬币数量。每个测试用例的第二行包含 n 个整数 a_1, a_2, \ldots, a_n (1 \le a_i \le 10^9)，其中 a_i 是商店里第 i 朵花的花瓣数。
所有测试用例的 n 之和不超过 2 \cdot 10^5。
输出描述
对于每个测试用例，输出一个整数，即在满足上述所有条件的情况下，女孩在花束中可能组合的最大花瓣数。
样例输入
5
5 10
1 1 2 2 3
8 20
4 2 7 5 6 1 1 1
8 100000
239 30 610 122 24 40 8 2
11 13
2 4 11 1 1 2 3 5 4 3 2
8 1033
206 206 206 207 207 207 207 1000
样例输出
7
13
610
13
1033
思路
这个题其实就是让你在找x和x+1最多能组成大的值，其中x是数组a中的值，x +1也是数组一中的值。可以暴力的去求，不管x+1，只要x使得到小于等于m的最大值。然后我们再考虑x和x+1都有的情况。从1开始枚举x的个数，枚举个数<=x总共的个数。
并且枚举个数乘x要<=m，这样去求x+1的个数。在<=m的时候，让结果最大，每一次结果取max。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b, int p) {
int res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}
int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}
int n, m, a[N];
void solve() {
cin >> n >> m;
map<int,int>mp;
for (int i = 1; i <= n; ++ i) cin >> a[i], mp[a[i]] ++;
int ans = 0;
for (auto [x, y] : mp) {
ans = max(ans, x * min(y, m / x));
if (mp.count(x + 1)) {
int z = mp[x + 1];
for (int i = 1; i <= y && i * x <= m; ++ i) {
ans = max(ans, x * i + (x + 1) * min(z, (m - x * i) / (x + 1)));
}
}
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _ = 1;
cin >> _;
while (_--) {
solve();
}
return 0;
}
B2. Bouquet (Hard Version)
题目大意
这是问题的困难版本。唯一不同的是，在这个版本中，不是列出每种花的花瓣数，而是为所有类型的花设置花瓣数和商店中的花的数量。
一个女孩准备过生日，想买一束最漂亮的花。店里一共有 n 种不同类型的花，每种花的花瓣数和数量都是固定的。一朵有 k 个花瓣的花的价格是 k 个金币。女孩决定，她用来装饰蛋糕的任何两朵花的花瓣数之差都不能超过 1。同时，女孩还想用尽可能多的花瓣组合成一束花。不幸的是，她只有 m 枚金币，无法再花费更多。她能组合的花束花瓣总数最多是多少？
输入描述
每个测试由多个测试用例组成。第一行包含一个整数 t (1 \le t \le 10\,000) —— 测试用例数。随后是测试用例的说明。
每个测试用例的第一行包含两个整数 n, m (1 \le n \le 2 \cdot 10^5, 1 \le m \le 10^{18}) —— 分别是商店中鲜花的种类数和女孩拥有的硬币数。每个测试用例的第二行包含 n 不同的整数 a_1, a_2, \ldots, a_n (1 \le a_i \le 10^9)，其中 a_i 是商店中第 i 朵花的花瓣数（对于不同的索引 i \neq j，必须是 a_i \neq a_j）。每个测试用例的第三行包含 n 个整数 c_1, c_2, \ldots, c_n (1 \le c_i \le 10^9)，其中 c_i 是商店中第 i 种鲜花的数量。
所有测试用例的 n 之和不超过 2 \cdot 10^5。
输出描出
对于每个测试用例，打印一个整数 - 在遵守上述所有条件的情况下，女孩在花束中可能收集到的最大花瓣数。
样例输入
7
3 10
1 2 3
2 2 1
3 1033
206 207 1000
3 4 1
6 20
4 2 7 5 6 1
1 2 1 3 1 7
8 100000
239 30 610 122 24 40 8 2
12 13123 112 1456 124 100 123 10982
6 13
2 4 11 1 3 5
2 2 1 2 2 1
8 10330
206 210 200 201 198 199 222 1000
9 10 11 12 13 14 15 16
2 10000000000
11 12
87312315 753297050
样例输出
7
1033
19
99990
13
10000
9999999999
样例说明
在第一个测试用例中，某些有效花束为 (1, 1, 2, 2), (2, 2, 3), (1, 1), (2, 2)。所有不大于 10 的有效花束的最大值为 7，即 (2, 2, 3)。在第二个测试案例中，你可以用 (206, 206, 207, 207, 207) 组合出一个有效花束，花束总数为 1033，这是女孩可以购买的最大花瓣数。在第三个测试用例中，可以用总和为 19 的 (5, 5, 5, 4) 组合出有效花束。由此可见，任何有效花束都不可能有 20 个花瓣。
思路
这题将复杂的提高，我们就不能像简单的那样暴力的去枚举x的个数。实际上我们每每遇到一个ai。都可以得到一个ai和ai+1组成的取值区间。而我们要的就是这个取值区间的最大值，也就是最右端点。详细看代码注释。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b, int p) {
int res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}
int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}
int n, m, a[N];
void solve() {
cin >> n >> m;
map<int,int>mp;
for (int i = 1; i <= n; ++ i) cin >> a[i];
for (int i = 1; i <= n; ++ i) {
int c; cin >> c;
mp[a[i]] = c;
}
sort(a + 1, a + 1 + n);
int ans = 0, sum = 0;
for (auto [x, y] : mp) {
ans = max(ans, x * min(m / x, y));//单个的
if (mp.count(x + 1)) {
int z = mp[x + 1];//加一的个数
int c;//x和x + 1中的x部分有多少个
if (x * y >= m) {
//如果x都用不完，那就只要x的，等着后面一个个将x换成x + 1
c = m / x;
}else {
//都则看看总共要多少个x和x + 1，
c = y + min(z, (m - x * y) / (x + 1));
}
//x + 1我可能只用了一部分，可能x + 1还有很多多到我可以把所有x都换成x + 1
//我这里要求的是尽量换到最大因为我要尽可能接近m
//如果能超过m就取m最大，否则就尽量换成x + 1接近m
ans = max(ans, min(m, c * x + min(c, z)));
//c * x是x和x + 1中的x部分，我们要尽可能接近m，就是将x替换成x + 1
//如果x + 1很多，那我最多可以加c代表c个x + 1
//否则就只有c个x和z个1，因为我只有z个x + 1不能再替换了，这是最大值
}
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _ = 1;
cin >> _;
while (_--) {
solve();
}
return 0;
}
C. Squaring
题目大意
ikrpprpp 发现了一个由整数组成的数组 a。他喜欢公平，所以想让 a 变得公平，也就是让它不递减。为此，他可以在数组的索引 1 \le i \le n 上执行一个公正的操作，将 a_i 替换为 a_i^2（位置 i 的元素及其平方）。例如，如果 a = [2,4,3,3,5,3] 并且 ikrpprpp 选择在 i = 4 上执行正义行动，那么 a 就会变成 [2,4,3,9,5,3]。
要使数组不递减，最少需要多少次正义行动？
输入描述
第一行包含一个整数 t (1 \le t \le 1000) —— 测试用例的数量。随后是测试用例说明。
对于每个测试用例，第一行包含一个整数 n —— 数组大小 a。第二行包含 n (1 \le n \le 2 \cdot 10^5) 个整数 a_1, a_2, \ldots, a_n (1 \le a_i \le 10^6).
输出描述
对于每个测试用例，打印一个整数--使数组 a 不递减所需的最小正义行为数。如果无法做到，则打印-1。
样例输入
7
3
1 2 3
2
3 2
3
3 1 5
4
1 1 2 3
3
4 3 2
9
16 2 4 2 256 2 4 2 8
11
10010 10009 10008 10007 10006 10005 10004 10003 10002 10001 10000
样例输出
0
1
-1
0
3
15
55
样例说明
注
在第一个测试案例中，无需执行正义行为。数组本身就是公平的！
在第三个测试案例中，可以证明数组不可能非递减。
在第五个测试用例中，ikrpprpp 可以对索引 3 执行一次正义行动，然后对索引 2 执行一次正义行动，最后对索引 3 执行另一次正义行动。之后，a 将变成 [4, 9, 16]。
这样，特殊符号已经被替换成了标准的数学符号。如果您需要进一步的帮助或解答，请随时告诉我。
思路
这道题适用于数学计算。由于它增加的话，数值增长得很大，所以我们不能去模拟将前面每一个数字都变大。可以去取log：
{a_{i-1}}^{2^{x}}\leqslant{a_{i}}^{2^{y}}\Rightarrow a^{2^{b}}\leq c^{2^{x}}，与我们枚举到ai的时候，ai-1和之前一定是已经计算完的，所以上述4个未知量，我们原知道3个，这个3个传入参数去求。两边同时取对数，2^{b}\cdot\log_{2}a\leq2^{x}\log_{2}c\Rightarrow2^{b}\cdot\frac{\log_{2}a}{\log_{2}c}\leq2^{x},再取一次对数得b+\log_{2}\frac{\log_{2}a}{\log_{2}c}\leq x，由此可得只要将结果上位取整即可， C++内置有log函数， 需要让分数部分用double来存即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
int inv(int x) {return qmi(x, MOD - 2);}
int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}
int n, m, a[N];
int cal(int a, int b, int c) {
if (a == 1 || c == 1) {
return 0;
}
double it = log2(a) / log2(c);
int x = ceil(b + log2(it));
return max(0ll, x);
}
void solve() {
cin >> n;
vector<int> dp(n + 1, 0);
for (int i = 1; i <= n; ++ i) cin >> a[i];
int ans = 0;
vector<int>b(n + 1);
for (int i = 2; i <= n; ++ i) {
if (a[i - 1] != 1 && a[i] == 1) {
cout << -1 << "\n";
return;
}
b[i] = cal(a[i - 1], b[i - 1], a[i]);
}
for (int i = 1; i <= n; ++ i) ans += b[i];
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _ = 1;
cin >> _;
while (_--) {
solve();
}
return 0;
}
