CF1661B Getting Zero
考虑到2^15 = 32768，bfs也许最多跑15层，但每一层都会入队许多数，不加剪枝的情况下是2^15次，因为一个数出队都会让两个新数入队。去重剪枝后，实测极端情况下，一个数进行bfs仍需要入队最多1e4次，如此时间复杂度就过高。
考虑我们最终得到的数是2^15，与其先执行操作乘2一步步加到32768，显然先加再乘是更优的
证明：如果一个数可以通过先乘2再加一的方式得到32768，我们可以先设n经过k次乘2操作得到了数x，那么x一定是偶数，因此需要偶数次加一操作最后得到32768。我们可以假设进行了（32768-x）次加一操作，那么在乘2之前，我们只需要进行 (32768 - x) / 2^k次加一操作就能得到相同的结果，这样明显是比先乘再加更优。由于32768 = 2^15, x 也是2^k的倍数，因此(32768 - x) / 2^k一定是整数，为2^(15-k) - n
但15的范围本身并不大，不需要推公式得来，公式只用于证明正确性。我们可以枚举加一操作进行 i ∈ [0, 15]次，然后经过k次乘2操作得到0，最终答案即为min(i + k)
#include <bits/stdc++.h>
#define int long long
#define mp(A, B) make_pair(A, B)
#define sz(a) signed(a.size())
#define pb push_back
#define all(x) x.begin(), x.end()
#define endl '\n'
#define fi first
#define se second
#define eps 1e-8
#define debug(a) cout << #a << "=" << a << endl;
using namespace std;
typedef double db;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const int maxn = 400010;
const int inf = 0x3f3f3f3f;
const int mod1 = 100000007;
const int mod2 = 998244353;
const int inv_p_6 = 166374059;
const int inv_p_2 = 499122177;
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}
//int h[maxn], ne[maxn], e[maxn], w[maxn], idx;
int tt;
int n, m, k;
//int q[maxn];
void solve() {
scanf("%lld", &n);
int ans = 1e18;
for (int i = 0; i <= 15; i ++ ) {
int now = n + i, cnt = i;
int more = 0;
while (more < 15 && now % 32768 != 0) {
now = (now * 2) % 32768;
more ++ , cnt ++ ;
if (now == 0) break;
}
ans = min(ans, cnt);
}
printf("%lld ", ans);
}
signed main() {
// cin.tie(nullptr), cout.tie(nullptr);
// ios::sync_with_stdio(false);
tt = 1;
scanf("%lld", &tt);
while (tt -- )
solve();
return 0;
}CF1644C Increase Subarray Sums
数据范围只有5000，n^2枚举长度为len的最大连续子段和，然后对于k∈[0, n]分别枚举len，求出最大值。
注：初始化ans为0，代表一个都不取的情况。
#include <bits/stdc++.h>
#define int long long
#define mp(A, B) make_pair(A, B)
#define sz(a) signed(a.size())
#define pb push_back
#define all(x) x.begin(), x.end()
#define endl '\n'
#define fi first
#define se second
#define eps 1e-8
#define debug(a) cout << #a << "=" << a << endl;
using namespace std;
typedef double db;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const int maxn = 5010;
const int inf = 0x3f3f3f3f;
const int mod1 = 100000007;
const int mod2 = 998244353;
const int inv_p_6 = 166374059;
const int inv_p_2 = 499122177;
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}
//int h[maxn], ne[maxn], e[maxn], w[maxn], idx;
int tt;
int n, m, k, x;
int q[maxn];
int dp[maxn];
void solve() {
scanf("%lld%lld", &n, &x);
for (int i = 1; i <= n; i ++ ) {
scanf("%lld", &q[i]);
q[i] += q[i - 1];
}
memset(dp, -inf, sizeof dp);
for (int len = 1; len <= n; len ++ ) {
for (int l = 1; l + len - 1 <= n; l ++ ) {
int r = l + len - 1;
dp[len] = max(dp[len], q[r] - q[l - 1]);
}
}
for (int i = 0; i <= n; i ++ ) {
int ans = 0;
for (int len = 1; len <= n; len ++ ) {
if (i < len) ans = max(ans, dp[len] + i * x);
else ans = max(ans, dp[len] + len * x);
}
printf("%lld ", ans);
}
puts("");
}
signed main() {
// cin.tie(nullptr), cout.tie(nullptr);
// ios::sync_with_stdio(false);
int tt = 1;
scanf("%lld", &tt);
while (tt -- )
solve();
return 0;
}CF1648B Integral Array
这题很好，展开说一下：
1.刚开始我一直在想，给出范围c到底有什么用，甚至一度以为这是一个无用信息。既然给出范围c，目的就是为了限制循环，不让我们越界。而如果按照题上的要求，通过除法来考虑该题，c就是用不上的条件，因为除法不可能越除越多。因此我们需要转换一个角度，把除法转化为乘法，这样题目上给的约束c就是一个有利的条件。
2.数组内可能存在许多相等的数，这会带来许多重复计算。
根据题上给的条件，假设 ：
$$
\left\lfloor\dfrac{x}{y}\right\rfloor = r
$$
由于要化除为乘，我们可以设y，r已知。那么根据下取整的性质，x是有多种情况的，具体范围是 [y * r , y * (r + 1) - 1]，如果x/y=r不存在在数组中，那么对于一个不存在在数组中的r，如果数组中有在y * r的范围内存在的x，即是无解的情况。因此，我们只需要枚举y和r（y在c的限制范围内的倍数 且 不在数组中），判断数组内是否含有 [y * r , y * (r + 1) - 1]
。
注：
1.枚举y时，不能用1 ~ n枚举，因为数组中有许多重复元素，这样就会导致我们重复计算很多次y * c。而如果只枚举1 ~ c，数组中相同的元素只会重复一次，其实相当于起到了去重的效果
2.用前缀和进行O(1)查询。
#include <bits/stdc++.h>
//#define int long long
#define mp(A, B) make_pair(A, B)
#define sz(a) signed(a.size())
#define pb push_back
#define all(x) x.begin(), x.end()
#define endl '\n'
#define fi first
#define se second
#define eps 1e-8
#define debug(a) cout << #a << "=" << a << endl;
using namespace std;
typedef double db;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
const int mod1 = 100000007;
const int mod2 = 998244353;
const int inv_p_6 = 166374059;
const int inv_p_2 = 499122177;
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}
//int h[maxn], ne[maxn], e[maxn], w[maxn], idx;
int tt;
int n, m, k, c;
int q[maxn];
int cnt[maxn], precnt[maxn];
void solve() {
scanf("%d%d", &n, &c);
for (int i = 0; i <= c; i ++ ) {
cnt[i] = precnt[i] = 0;
}
for (int i = 1;i <= n; i ++ ) {
scanf("%d", &q[i]);
cnt[q[i]] ++ ;
}
for (int i = 0; i <= c; i ++ ) precnt[i] = precnt[i - 1] + cnt[i];
for (int i = 2; i <= c; i ++ ) {
if (cnt[i]) {
for (int j = 1; j * i <= c; j ++ ) {
if (!cnt[j]) {
int r = min(c, (j + 1) * i - 1);
if (precnt[r] - precnt[j * i - 1]) {
puts("NO");
return;
}
}
}
}
}
puts("YES");
}
signed main() {
// cin.tie(nullptr), cout.tie(nullptr);
// ios::sync_with_stdio(false);
int tt = 1;
scanf("%lld", &tt);
while (tt -- )
solve();
return 0;
}CF1661C Water the Trees
官方题解中有很妙的二分思路。
首先证明，对于操作后的结果，所有树的大小等于mx或mx+1，且不可能比mx+1更大。
假设最后树的大小均等于mx+2，那么我们可以删除一些动作，使得高度为mx， 对于mx+1来说，仅有某些情况比mx更优（如样例这种，1加到较大值而2加到较小值，且较小值和较大值只差1，这样不会浪费每一天），所以，我们要计算最终答案为mx和mx+1，从中取较小者。
如何二分？
二分天数mid，如此有操作一 (mid+1)/2 次，操作二 (mid) / 2次。首先贪心地使用操作二，有二则用二，中间的1用操作1弥补，如果操作二用完，可以用两次操作一替代操作二。
#include <bits/stdc++.h>
#define int long long
#define mp(A, B) make_pair(A, B)
#define sz(a) signed(a.size())
#define pb push_back
#define all(x) x.begin(), x.end()
#define endl '\n'
#define fi first
#define se second
#define eps 1e-8
#define debug(a) cout << #a << "=" << a << endl;
using namespace std;
typedef double db;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
const int mod1 = 100000007;
const int mod2 = 998244353;
const int inv_p_6 = 166374059;
const int inv_p_2 = 499122177;
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}
//int h[maxn], ne[maxn], e[maxn], w[maxn], idx;
int tt;
int n, m, k, mx;
int q[maxn];
bool check (int x) {
int op2 = x / 2, op1 = x - op2;
for (int i = 1; i <= n; i ++ ) {
int res = (mx - q[i]) / 2;
if ((mx - q[i]) & 1) op1 -- ;
if (op2 >= res) op2 -= res;
else {
res -= op2;
op2 = 0;
op1 -= res * 2;
}
}
return op1 >= 0;
}
void solve() {
scanf("%lld", &n);
mx = 0;
for (int i = 1; i <= n; i ++ ) {
scanf("%lld", &q[i]);
mx = max(mx, q[i]);
}
int l = 0, r = 1e18;
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
int ans1 = l;
mx ++ ;
l = 0, r = 1e18;
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
int ans2 = l;
printf("%lld\n", min(ans1, ans2));
}
signed main() {
// cin.tie(nullptr), cout.tie(nullptr);
// ios::sync_with_stdio(false);
int tt = 1;
scanf("%lld", &tt);
while (tt -- )
solve();
return 0;
}CF1667A Make it Increasing
还是比较简单的一道题，找到某个分界点为0，让左边的值都小于0，右边的值都大于0。
数据范围很小，O(n^2)暴力枚举所有分界点。
#include <bits/stdc++.h>
#define int long long
#define mp(A, B) make_pair(A, B)
#define sz(a) signed(a.size())
#define pb push_back
#define all(x) x.begin(), x.end()
#define endl '\n'
#define fi first
#define se second
#define eps 1e-8
#define debug(a) cout << #a << "=" << a << endl;
using namespace std;
typedef double db;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const int maxn = 200010;
const int inf = 0x3f3f3f3f;
const int mod1 = 100000007;
const int mod2 = 998244353;
const int inv_p_6 = 166374059;
const int inv_p_2 = 499122177;
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}
//int h[maxn], ne[maxn], e[maxn], w[maxn], idx;
int tt;
int n, m, k;
int q[maxn];
void solve() {
scanf("%lld", &n);
for (int i = 1; i <= n; i ++ ) scanf("%lld", &q[i]);
int ans = 1e18;
for (int mid = 1; mid <= n; mid ++ ) {
int now = 0;
int ls = 0;
for (int i = mid + 1; i <= n; i ++ ) {
int res = ls / q[i];
res ++ ;
ls = res * q[i];
now += res;
}
// printf("%lld\n", ans);
ls = 0;
for (int i = mid - 1; i >= 1; i -- ) {
int res = ls / q[i];
res -- ;
ls = res * q[i];
now += abs(res);
}
// printf("%lld\n", ans);
ans = min(ans, now);
}
printf("%lld\n", ans);
}
signed main() {
// cin.tie(nullptr), cout.tie(nullptr);
// ios::sync_with_stdio(false);
int tt = 1;
// scanf("%lld", &tt);
while (tt -- )
solve();
return 0;
}CF1660F Promising String
先说ezver，数据范围5000所以可以n^2，因此可以找出所有lr。
判断能否使用操作的方法：根据抽屉原理，如果’-‘的个数大于’+’个数2个以上，那么一定会有两个’-‘并排。假设当前’+’和’-‘的个数是a和b，如果执行一次操作，b的个数减少2，a的个数增加2，即ab差值减3，而要ab相等，即差值为0，所以枚举前缀和，如果差值%3为0，即为合法答案。
#include <bits/stdc++.h>
#define int long long
#define mp(A, B) make_pair(A, B)
#define sz(a) signed(a.size())
#define pb push_back
#define all(x) x.begin(), x.end()
#define endl '\n'
#define fi first
#define se second
#define eps 1e-8
#define debug(a) cout << #a << "=" << a << endl;
using namespace std;
typedef double db;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const int maxn = 200010;
const int inf = 0x3f3f3f3f;
const int mod1 = 100000007;
const int mod2 = 998244353;
const int inv_p_6 = 166374059;
const int inv_p_2 = 499122177;
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}
//int h[maxn], ne[maxn], e[maxn], w[maxn], idx;
int tt;
int n, m, k;
int q[maxn];
void solve() {
scanf("%lld", &n);
string a;
a.resize(n);
scanf("%s", a.c_str());
vector<int> plus(n + 1), minus(n + 1);
for (int i = 0; i < a.size(); i ++ ) {
plus[i] = plus[i - 1], minus[i] = minus[i - 1];
if (a[i] == '+') plus[i] ++ ;
else minus[i] ++ ;
}
int ans = 0;
for (int i = 0; i < n; i ++ ) {
for (int j = i + 1; j < n; j ++ ) {
int pls = plus[j] - plus[i - 1], mns = minus[j] - minus[i - 1];
if (pls == mns) ans ++ ;
else if (mns - pls >= 2) {
while (mns > pls) {
mns -= 3;
if (mns == pls) {
ans ++ ;
break;
}
}
}
}
}
printf("%lld\n", ans);
}
signed main() {
// cin.tie(nullptr), cout.tie(nullptr);
// ios::sync_with_stdio(false);
int tt = 1;
scanf("%lld", &tt);
while (tt -- )
solve();
return 0;
}hardver:
数据范围大后不能再枚举所有lr了，但是可以只枚举右边界r，来判断合法的左边界。
如何判断？
设’+’个数为a，’-‘个数为b
首先考虑合法的条件，根据ezver的推论可知，需要ab的差值%3为0，且b>=a，（这是因为C语言中的取余无法判断正负。
约束一：对于某个q[i]的贡献，我们只看之前和q[i]%3相等的那些数，与其他的数无关，所以我们可以单独把%3相等的放在同一组中判断。
约束二：如果要查询之前出现的所有b>=a的情况。首先考虑使用前缀和数组q，将+和-的权值变为-1和+1，那么如果b>=a，就是q[r] >= q[l]，我们可以边遍历边计算，对于当前遍历到的r，在它的同余组中，只有小于它的q[l]才会被计算贡献，因此维护三个树状数组（三个约数，进行查逆序对的操作。
#include <bits/stdc++.h>
#define int long long
#define mp(A, B) make_pair(A, B)
#define sz(a) signed(a.size())
#define pb push_back
#define all(x) x.begin(), x.end()
#define endl '\n'
#define fi first
#define se second
#define eps 1e-8
#define debug(a) cout << #a << "=" << a << endl;
using namespace std;
typedef double db;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const int maxn = 200010;
const int inf = 0x3f3f3f3f;
const int mod1 = 100000007;
const int mod2 = 998244353;
const int inv_p_6 = 166374059;
const int inv_p_2 = 499122177;
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}
//int h[maxn], ne[maxn], e[maxn], w[maxn], idx;
int tt;
int n, m, k;
int q[maxn];
int tr[4][maxn << 1 | 1];
int lowbit (int x) {
return x & -x;
}
void add (int c, int x, int k) {
for (; x <= (n << 1 | 1); x += lowbit(x)) tr[c][x] += k;
}
int query (int c, int x) {
int ans = 0;
for (; x; x -= lowbit(x)) ans += tr[c][x];
return ans;
}
void solve() {
scanf("%lld", &n);
string a; a.resize(n);
scanf("%s", a.c_str());
for (int i = 0; i < 3; i ++ ) {
for (int j = 0; j <= (n << 1 | 1); j ++ ) tr[i][j] = 0;
}
int now = n + 1;
for (int i = 1; i <= n; i ++ ) {
q[i] = q[i - 1];
if (a[i - 1] == '-') q[i] ++ ;
else q[i] -- ;
}
puts("");
int ans = 0;
for (int i = 0; i <= n; i ++ ) {
ans += query((q[i] % 3 + 3) % 3, q[i] + now);
add((q[i] % 3 + 3) % 3, q[i] + now, 1);
}
printf("%lld\n", ans);
}
signed main() {
// cin.tie(nullptr), cout.tie(nullptr);
// ios::sync_with_stdio(false);
int tt = 1;
scanf("%lld", &tt);
while (tt -- )
solve();
return 0;
}第一天集训结束，congratulations!
