Rank 264/3889. Solved 6/11.写完 \(6\) 题后干活去了，结果发现还有个不太难的题（
A. 柠檬可乐
题意
给定三个整数 \(a, b, k\)，判断 \(a \geq k \times b\) 是否成立。
思路
如题。
时间复杂度：\(O(1)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int a, b, k;
cin >> a >> b >> k;
cout << (a >= k * b ? "good\n" : "bad\n");
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}手速
B. 左右互博
题意
给定 \(n\) 堆石子，第 \(i\) 堆包含 \(a_i\) 个石子，定义 \(A, B\) 之间的博弈如下：
\(A\) 先手；
轮到的人选择一堆石子，记石子数为 \(x\)，然后选择一个整数 \(y\ (2 \leq y \leq x)\)，并将这堆石头分成两堆，数量分别为 \(\lfloor \frac{x}{y} \rfloor\) 和 \(x - \lfloor \frac{x}{y} \rfloor\)；
不能操作的人输
输出先手是否有必胜策略。
思路
显然，当我们将其分成 \(1, x - 1\) 时，能让当前可操作的堆数不变或减少 \(1\)，否则堆数就会变多。
可以发现的是，无论怎么任意操作，最后都等价于一直执行上面的取 \(1\) 操作。
于是我们从这个角度出发，很容易就可以知道，\(\sum (a_i - 1)\) 为奇数时，先手必胜。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for(int i=1;i<=n;i++) cin >> a[i];
cout << ((accumulate(all(a), 0ll) - n) % 2 == 0 ? "sweet\n" : "gui\n");
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}当然乱猜就完事了
C. 冬眠
题意
给定一个 \(n \times m\) 的矩阵，以及 \(q\) 个操作，每个操作分成两种：
第 \(z\) 行循环右移一格；
第 \(z\) 列循环下移一格
现在，将上述 \(q\) 个操作视为一组操作，给定整数 \(p, x, y\)，输出执行 \(p\) 组操作后，第 \(x\) 行第 \(y\) 列的字符。
思路
数据范围很小，于是直接暴力。
倒着循环，然后 \(swap\) 上来即可。
时间复杂度：\(O(pq(n+m))\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, m, x, y;
cin >> n >> m >> x >> y;
vector<string> s(n + 1);
for(int i=1;i<=n;i++) {
cin >> s[i];
s[i] = " " + s[i];
}
int p, q;
cin >> p >> q;
vector<pii> ppp(q + 1);
for(int i=1;i<=q;i++) cin >> ppp[i].fs >> ppp[i].sc;
for(int i=1;i<=p;i++) {
for(int j=1;j<=q;j++) {
auto &[op, x] = ppp[j];
if(op == 1) {
for(int k=m-1;k>=1;k--) swap(s[x][k], s[x][k + 1]);
}else {
for(int k=n-1;k>=1;k--) swap(s[k][x], s[k + 1][x]);
}
}
}
cout << s[x][y] << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}一顿乱写
D. 守恒
题意
给定一个长为 \(n\) 的数组 \(a\)，定义一次操作为选定任意两个数，并将一个数 \(-1\)，另一个数 \(+1\)，需要保证操作后所有数都是正整数。
输出任意次操作后，整个数组的最大公约数有多少种不同的可能。
思路
首先，不难发现的是，操作不影响整个数组的和。
其次，根据数论的基础知识，既然最大公约数能整除所有元素，那么它自然也能整除整个数组的和。
换个视角来看，就是最大公约数一定是数组的和的因数。
那么我们只需枚举因数，并检查即可。
至于如何检查，在满足 \(x\) 为数组和的因数的条件下，如果要让数组的最大公约数变为 \(x\)，那么数组的最小值就得为 \(x\)。
也就是说，如果数组的和比 \(n \times x\) 小，自然就无法满足这个条件，而相反的，满足这个条件就一定有构造方案。
如上即可通过本题...吗？
还有坑，\(n = 1\) 的时候需要特判。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for(int i=1;i<=n;i++) cin >> a[i];
if(n == 1) {
cout << 1 << '\n';
return;
}
int sum = accumulate(all(a), 0ll);
int ans = 0;
for(int i=1;i<=sum/i;i++) {
if(sum % i != 0) continue;
if(sum >= i * n) ans ++;
if(i != sum / i && sum >= (sum / i) * n) ans ++;
}
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}被坑了！
E. 漂亮数组
题意
给定一个长为 \(n\) 的数组，将其任意划分为若干个子数组，输出划分后 和为 \(k\) 的倍数 的子数组的最大数量。
思路
假设我们有一个前缀和数组 \(pre\)，那么如果 \([l, r]\) 子数组满足和为 \(k\) 的倍数，条件等价于 \(pre[r] \equiv pre[l - 1] \pmod k\)。
并且，如果我们有多个选择，不难发现，选右端点 \(r\) 小的区间更好，因为这样才能让后面更有选择的余地。
从而出现了一个很正确的贪心思路：
令 \(sum\) 为当前区间的和，每遍历一个数，就将其加入区间中，也就是说，\(sum := sum + a[i]\)。
考虑标记 \(sum \bmod k\)。在标记前，判断其是否已经被标记，如果被标记，那么存在一对左右端点符合条件，我们将其计入答案，并清空当前区间，清空标记。
注意，\(0\) 需要提前被标记，因为什么数都不选的时候，\(sum = 0\)。
时间复杂度：\(O(n \log n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n + 1);
for(int i=1;i<=n;i++) cin >> a[i];
set<int> st;
st.ep(0);
int sum = 0, ans = 0;
for(int i=1;i<=n;i++) {
sum += a[i];
if(st.count(sum % k)) {
ans ++;
sum = 0;
st.clear();
st.ep(0);
continue;
}
st.ep(sum % k);
}
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}一开始差点看成签到题，不过确实也不难吧（
F. 来点每日一题
题意
给定一个长度为 \(n\) 的数组 \(a\)，令初始分数为 \(0\)。
按照从左到右的顺序选择数字，当选满 \(6\) 个数字时，可以获得分数，并继续向右选择（而不是从头开始）。
记所选数字从左到右依次为 \(b_1, b_2, b_3, b_4, b_5, b_6\)，获得的分数为 \(((b_1 - b_2) \times b_3 - b_4) \times b_5 - b_6\)。
输出最后可以获得的分数的最大值。
思路
首先，如果我们只选 \(6\) 个数字，那么该如何计算？
如果没有乘法，我们只需取 \(b_1{\max}, b_2{\min}, b_4{\min}, b_6{\min}\)。而既然有乘法，那么乘上一个负数后，最大值会变成最小值。
从而，如果我们分别找到 \(b_i{\max}, b_i{\min}\)，并代入，就可以得到最大值。
注意我们需要满足 \(b\) 的顺序，所以我们换个角度，维护 \(b_1, b_1 - b_2, (b_1 - b_2) \times b_3, \ldots\) 的最值，这样我们就可以在遍历到新元素的时候，按照式子，从前者的最值转移到后者的最值。
接下来我们来考虑多个区间的情况。这很简单，\(dp\) 即可。
我们令 \(dp[i]\) 为以第 \(i\) 个元素为最右侧区间的第 \(6\) 个元素得到的最大分数和。
那么我们只需枚举 \(i\) 作为上一个区间右侧的第一个元素，并枚举 \(j\) 作为当前区间的第 \(6\) 个元素，按照上面的操作求出 \(mx5 = \max\{((b_1 - b_2) \times b_3 - b_4) \times b_5\}\)，转移方程就很简单了：
\(dp[j] = \max(dp[j], dp[i - 1] + (mx5 - a[j]))\)
如上，最后取 \(dp\) 数组所有元素的最大值即可，因为右端点是不固定的。
时间复杂度：\(O(n ^ 2)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for(int i=1;i<=n;i++) cin >> a[i];
vector<int> dp(n + 1);
for(int i=1;i<=n;i++) {
int mn1 = inf, mn2 = inf, mn3 = inf, mn4 = inf,
mx1 = -inf, mx2 = -inf, mx3 = -inf, mx4 = -inf, mx5 = -inf;
for(int j=i;j<=n;j++) {
if(mx5 != -inf) dp[j] = max(dp[j], dp[i - 1] + mx5 - a[j]);
if(mn4 != inf) mx5 = max(mx5, mn4 * a[j]);
if(mx4 != -inf) mx5 = max(mx5, mx4 * a[j]);
if(mn3 != inf) {
mn4 = min(mn4, mn3 - a[j]);
mx4 = max(mx4, mn3 - a[j]);
}
if(mx3 != -inf) {
mn4 = min(mn4, mx3 - a[j]);
mx4 = max(mx4, mx3 - a[j]);
}
if(mn2 != inf) {
mn3 = min(mn3, mn2 * a[j]);
mx3 = max(mx3, mn2 * a[j]);
}
if(mx2 != -inf) {
mn3 = min(mn3, mx2 * a[j]);
mx3 = max(mx3, mx2 * a[j]);
}
if(mn1 != inf) {
mn2 = min(mn2, mn1 - a[j]);
mx2 = max(mx2, mn1 - a[j]);
}
if(mx1 != -inf) {
mn2 = min(mn2, mx1 - a[j]);
mx2 = max(mx2, mx1 - a[j]);
}
mn1 = min(mn1, a[j]);
mx1 = max(mx1, a[j]);
}
}
cout << *max_element(all(dp)) << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}代码很长，跑得飞快
G. 数三角形（easy）
题意
定义三角形如下：
...*...
..*.*..
.*...*.
*******由一个底边为 \(2x + 1\)，高为 \(x + 1\) 的等边三角形的边组成。单独一个点不算三角形。
给定一个 \(n \times m\) 的矩阵，求出三角形的个数。
思路
本题数据范围小，可以考虑直接暴力。
最优雅的暴力是 \(O(n ^ 3)\) 的，我们只需预处理出每一行 \([l, r]\) 区间中有多少个 "."，然后枚举每一个 "*" 作为三角形的顶点，往下扫的过程中三角形的底边端点也已知，只需利用前面的预处理就可在常数时间内判断两个端点间是否都是 "*"。
时间复杂度：\(O(n ^ 3)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, m;
cin >> n >> m;
vector<string> s(n + 1);
for(int i=1;i<=n;i++) {
cin >> s[i];
s[i] = " " + s[i];
}
vector<vector<int>> pre(n + 1, vector<int>(m + 1));
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
pre[i][j] = pre[i][j - 1];
if(s[i][j] == '.') pre[i][j] ++;
}
}
int ans = 0;
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(s[i][j] == '*') {
int l = j - 1, r = j + 1, ln = i + 1;
while(l >= 1 && r <= m && ln <= n) {
if(s[ln][l] == '*' && s[ln][r] == '*') {
if(pre[ln][r] - pre[ln][l - 1] == 0) ans ++;
}else break;
l --, r ++, ln ++;
}
}
}
}
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}而且很好写
H. 数三角形（hard）
题意
定义三角形如下：
...*...
..*.*..
.*...*.
*******由一个底边为 \(2x + 1\)，高为 \(x + 1\) 的等边三角形的边组成。单独一个点不算三角形。
给定一个 \(n \times m\) 的矩阵，求出三角形的个数。
思路
本题数据范围大，无法直接 \(O(n ^ 3)\)。
我们考虑换一个视角，从边的角度入手，而不是顶点。
可以发现，左腰和右腰都是分别互相平行的。
从而我们考虑预处理两个数组 \(le, re\)，其中 \(le[x][y]\) 为以 \((x, y)\) 为最下方的点为起点，向右上方的连续 "*" 的长度，也就是左腰的最长长度；\(re\) 则是左上方，也就是右腰的最长长度。
然后，我们枚举每一段连续的横向 "*"，计算以这段 "*" 的一部分或全部作为底边，有多少个三角形。
我们可以直接从左往右，枚举每个点作为三角形的底边右侧端点。记这个点为 \((i, r)\)，那么根据前面的预处理，右腰最长为 \(re[i][r]\)。
我们可以以此推出，只要够长的话，以这个右腰作为腰，底边左侧端点最远为 \((i, r - 2 \times re[i][r] + 2)\)。
但是我们肯定不能暴力判断是否够长，以及暴力计算数量，而有趣的是，计算数量就和区间求和类似，我们要维护的就是前缀和。
那么加速维护前缀和的数据结构自然就是树状数组了。
跟前面一样的，在从左往右枚举底边右侧端点的时候，我们如果将其作为底边左侧端点，可以发现，右侧端点可以拓展到 \((i, l + 2 \times le[i][l] - 2)\)。
那么这就好办了，我们直接把 \(l\) 对应的值 \(+1\)，并在 \(l + 2 \times le[i][l] - 2\) 处将 \(l\) 对应的值 \(-1\) 即可。
需要注意的是，顶点一定在方格上，从而左侧顶点和右侧顶点的奇偶性需要保持一致，所以我们要按奇偶分开计算。
时间复杂度：\(O(n^2 \log n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) (x).rbegin(),(x).rend()
#define all(x) (x).begin(),(x).end()
constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
template<class Info = int>
struct BinaryIndexTree {
int n;
vector<Info> info;
BinaryIndexTree() : n(0) {}
explicit BinaryIndexTree(int _n, Info _v = Info()) : info(_n + 1, _v), n(_n) {}
inline static int lowbit(int x) { return x & (-x); }
void pointUpdate(int pos, Info _info) {
for (int i = pos; i <= n; i += lowbit(i)) info[i] = info[i] + _info;
}
Info rangeQuery(int r) {
Info ans{};
for (int i = r; i > 0; i -= lowbit(i)) ans = ans + info[i];
return ans;
}
Info rangeQuery(int l, int r) {
return rangeQuery(r) - rangeQuery(l - 1);
}
};
void solve() {
int n, m;
cin >> n >> m;
vector<string> s(n + 1);
for(int i=1;i<=n;i++) {
cin >> s[i];
s[i] = " " + s[i];
}
vector le(n + 1, vector(m + 2, 0ll)),
re(n + 1, vector(m + 2, 0ll));
int ans = 0;
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(s[i][j] == '.') continue;
le[i][j] = le[i - 1][j + 1] + 1;
re[i][j] = re[i - 1][j - 1] + 1;
ans --;
}
}
BinaryIndexTree bit(m + 1);
vector<vector<int>> fr(m + 1);
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(s[i][j] == '.') continue;
int l_ = j, r_ = j;
while(r_ + 1 <= m && s[i][r_ + 1] == '*') r_ ++;
int mx = max(l_, r_ - (r_ - l_) % 2);
for(int p=l_;p<=r_;p+=2) {
int l = p, r = p + le[i][p] * 2 - 2;
fr[min(r, mx)].pb(l);
bit.pointUpdate(p, 1);
r = p, l = p - re[i][p] * 2 + 2;
ans += bit.rangeQuery(max(1ll, l), r);
for(auto &e : fr[p]) bit.pointUpdate(e, -1);
fr[p].clear();
}
mx = max(l_ + 1, r_ - (r_ - l_ + 1) % 2);
for(int p=l_+1;p<=r_;p+=2) {
int l = p, r = p + le[i][p] * 2 - 2;
fr[min(r, mx)].pb(l);
bit.pointUpdate(p, 1);
r = p, l = p - re[i][p] * 2 + 2;
ans += bit.rangeQuery(max(1ll, l), r);
for(auto &e : fr[p]) bit.pointUpdate(e, -1);
fr[p].clear();
}
j = r_;
}
}
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}想到按边做应该就不至于不会做了（
I. 回头
待补充
J. 画直线
待补充
K. 方块掉落
待补充