前言
考试期间, 只需要考虑考试策略即可, 别的都别管了
先打暴力, 想正解不超过 \(40 \ \rm{min}\) , 最后拼高档 / 正解, 冷静, 认真分析
看题
现在看到不按难度排序已经免疫了, 感觉是防锅专用语?
\(\rm{T1}\)
题意非常清楚, 可能挖下性质还是可以做的
\(\rm{T2}\)
我不到啊, 但是 \(N\) 很小应该可以乱搞吧
\(\rm{T3}\)
似 \(\rm{dp}\) , 不知道能不能做, 看看能不能搞个高档
\(\rm{T4}\)
难评, 能不能做取决于前面的做不做出来
\(\rm{T1}\)
思路
题意非常清楚, 但是还是理一下
你发现从 \(a\) 中选出 \(b\) 构成排列
满足这个条件的基础上选择一个 \(T\) 最大的排列
首先我们考虑给定一个 \(a\) , 如何找到符合条件的 \(b\) , 也即 \(\mathcal{O} (NQ)\) 的做法
先玩一下样例, 怎么看不懂?
抛开题面不谈, 这题问的应该是对于 \(a\) 升序排序后, \(T\) 的值
不然样例都是错的
好的猜完题意, 我们考虑继续思考 \(\mathcal{O} (NQ)\) 的做法
这样做是简单的, 按照题意模拟每次排序即可, 到手 \(40 \ \rm{pts}\)
考虑优化,
显然的是每次操作只更新序列中的一个元素, 那么直接去排序一定不会是最优的, 怎么做可以快速的做到排序的效果?
注意到 \(\mathcal{O} (Q \log N)\) 是可以接受的, 我们考虑二分找到插入点
每次更改一个数, 我们二分查找更改后这个数应该在哪里, 记为 \(p\), 对于原来的数组, 贡献的变化即为被修改的数的贡献清零, 在 \(p\) 后面的数贡献增大, \(p\) 位置的贡献
唯一的问题是怎么求在 \(p\) 后面的数贡献增大了多少, 而且必须 \(\mathcal{O} (1)\) 求
然后你发现这个贡献增大的值其实就是按照值排序后的后缀和, 那么这个题就解决了
实现
框架
首先对于原序列排序, 计算出初始的 \(T\)
对于每一次询问, 首先找到询问点的位置 \(p\) , 然后找到更改的位置 \(p^{\prime}\)
记点的贡献为 \(C_i\) , 当前的 \(T^{\prime} = T - C_p + C_{p^{\prime}} + S_{p^{\prime}}\) , 判断一下 \(S_{p^{\prime}}\) 是否包含了非法部分即可
时间复杂度 \(\mathcal{O} (n \log n) - \mathcal{O} (Q \log N)\)
代码
调了一会过掉了大样例, 确实不太好写
#include <bits/stdc++.h>
// #define FILE_IO
#define int long long
const int MAXN = 1.5e5 + 20;
int N, Q;
int a[MAXN];
int apre[MAXN];
int Tpre; // 最初的 T 值
int S[MAXN]; // 后缀和
signed main()
{
#ifdef FILE_IO
freopen("perm.in", "r", stdin);
freopen("perm.out", "w", stdout);
#endif
scanf("%lld", &N);
for (int i = 1; i <= N; i++) scanf("%lld", &a[i]), apre[i] = a[i];
std::sort(a + 1, a + N + 1);
for (int i = 1; i <= N; i++) Tpre += i * a[i];
for (int i = N; i >= 1; i--) S[i] = a[i] + S[i + 1];
scanf("%lld", &Q);
while (Q--) {
int x, y; scanf("%lld %lld", &x, &y);
int p = std::lower_bound(a + 1, a + N + 1, apre[x]) - a; // 找到询问点的位置
int pp; // 修改后的位置
int Tnow;
if (y > apre[x]) pp = std::upper_bound(a + 1, a + N + 1, y) - a - 1, Tnow = Tpre - p * a[p] + pp * y + S[pp + 1] - S[p + 1];
else pp = std::upper_bound(a + 1, a + N + 1, y) - a, Tnow = Tpre - p * a[p] + pp * y + S[pp] - S[p];
printf("%lld\n", Tnow);
}
return 0;
}
\(\rm{T2}\)
前言
上一题其实还是不够冷静, 其实可以更快开到这里的, 大众分上不应该浪费太多时间
思路
转化题意,
定义对 \(01\) 串串 \(a, b\) 的操作 :
- 对于一个 \(i \in [1, N], b_i = \mathop{\sim} b_i\)
- \(\forall b_i = 1, a_i = \mathop{\sim} a_i\)
- 对于 \(b\) 循环移位
看题的时候以为 \(N\) 很小, 看到 \(T \leq 2 \times 10^5\) 没绷住
玩下样例, 这个肯定是有性质的
好吧不太会做, 打完暴力跑路了
暴力是简单的, 你每次枚举翻转, 然后把 \(a, b\) 当数存下来即可
搞个迭代加深搜索应该能快一点, 应该能打掉 \(30 \ \rm{pts}\)
实现
代码
#include <bits/stdc++.h>
// #define FILE_IO
const int INF = 0x3f3f3f3f;
int T, N;
int ans = INF;
void IDdfs(int A, int B, int MaxDep, int NowDep) {
if (A == 0) { ans = std::min(ans, NowDep); return; }
if (NowDep >= MaxDep) return;
for (int i = 0; i < N; i++) { // 外层枚举 b 取反的位置
int nowA = A, nowB = B;
int Bi = (B >> i) & 1; nowB = B - (Bi << i) + ((!Bi) << i);
for (int j = 0; j < N; j++) // 对 a 进行取反
if ((nowB >> j) & 1) { int Ai = (A >> j) & 1; nowA = nowA - (Ai << j) + ((!Ai) << j); }
nowB <<= 1; nowB |= (nowB >> N) & 1; nowB &= ((1 << N) - 1); // 对 b 进行循环移位
IDdfs(nowA, nowB, MaxDep, NowDep + 1);
}
}
int main()
{
#ifdef FILE_IO
freopen("edit.in", "r", stdin);
freopen("edit.out", "w", stdout);
#endif
scanf("%d %d", &T, &N);
while (T--) {
std::string a, b; std::cin >> a >> b;
int A = 0, B = 0;
for (int i = 0, pow2 = 1; i < N; i++, pow2 *= 2) A += pow2 * (a[i] - '0'), B += pow2 * (b[i] - '0');
ans = INF;
for (int i = 1; i <= 25; i++) {
IDdfs(A, B, i, 0);
if (ans ^ INF) { printf("%d\n", ans); break; }
}
}
return 0;
}
调暴力太久了, 后面的题就算可做也很难写得完, 所以接下来全都打暴力
\(\rm{T4}\)
思路
\(\mathcal{O} (n^3)\) 的暴力很好打
我们首先枚举保留的段落, 然后只要段落外的颜色与段落内的颜色不交即可删除这样一种情况
其实这个可以优化, 组合数学算一下就行了, 时间不够了
好像 \(\mathcal{O} (n)\) 求区间, 组合数乘起来即可, 但是没时间了, 寄
先想一下 \(\mathcal{O} (n ^ 2)\) 的优化, 你发现可以预处理降低 \(\rm{check}\) 的复杂度
代码
\(\mathcal{O} (n^3)\)
#include <bits/stdc++.h>
// #define FILE_IO
const int MAXN = 520; // 641
int Col[MAXN];
bool check(int l, int r, int n) {
bool vis[MAXN];
memset(vis, false, sizeof(vis));
for (int i = 1; i < l; i++) vis[Col[i]] = true;
for (int i = r + 1; i <= n; i++) vis[Col[i]] = true;
for (int i = l; i <= r; i++) if (vis[Col[i]]) return false;
return true;
}
int main()
{
#ifdef FILE_IO
freopen("del.in", "r", stdin);
freopen("del.out", "w", stdout);
#endif
int T; scanf("%d", &T);
while (T--) {
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &Col[i]);
int Ans = 0;
for (int l = 1; l <= n; l++) {
for (int r = l; r <= n; r++) {
if (check(l, r, n)) Ans++;
}
}
printf("%d\n", Ans);
}
return 0;
}
\(\mathcal{O} (n^2)\)
#include <bits/stdc++.h>
// #define FILE_IO
const int MAXN = 1e4 + 20; // 641
int Col[MAXN];
bool Check[MAXN][MAXN];
bool check(int l, int r, int n) {
bool vis[MAXN];
for (int i = 1; i <= n; i++) vis[i] = false;
for (int i = 1; i < l; i++) vis[Col[i]] = true;
for (int i = r + 1; i <= n; i++) vis[Col[i]] = true;
for (int i = l; i <= r; i++) if (vis[Col[i]]) return false;
return true;
}
int main()
{
#ifdef FILE_IO
freopen("del.in", "r", stdin);
freopen("del.out", "w", stdout);
#endif
int T; scanf("%d", &T);
while (T--) {
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &Col[i]);
for (int l = 1; l <= n; l++) {
for (int r = l; r <= n; r++) {
Check[l][r] = check(l, r, n);
}
}
int Ans = 0;
for (int l = 1; l <= n; l++) {
for (int r = l; r <= n; r++) {
if (Check[l][r]) Ans++;
}
}
printf("%d\n", Ans);
}
return 0;
}
\(\rm{T3}\)
容易发现 \(k = 1\) 时和求逆序对是等价的, 直接算即可
对于至多包含 \(8\) 个 \(1\) 的情况, 我们直接处理 \(1\) 的移动即可
具体的, 我不知道怎么打
代码
#include <bits/stdc++.h>
// #define FILE_IO
const int MAXN = 1e6 + 20;
int Sum1[MAXN], Sum2[MAXN];
int LSY[MAXN];
int main()
{
int N, K;
scanf("%d %d", &N, &K);
std::string a, b; std::cin >> a >> b;
for (int i = N - 1; i >= 0; i--) Sum1[i] = Sum1[i + 1] + (b[i] == '1'), Sum2[i] = Sum2[i + 1] + (a[i] == '1');
int cnt = 0;
for (int i = 0; i < N; i++) {
if (b[i] == '0') LSY[++cnt] = Sum1[i];
}
cnt = 0;
int Ans = 0;
for (int i = 0; i < N; i++) {
if (a[i] == '0') Ans += std::abs(LSY[++cnt] - Sum2[i]);
}
printf("%d", Ans);
return 0;
}