maya 我突然发现你们都在水 blog（那我也来）
可能是我上次写自己爆炸的缘故，但更多的是数据辣鸡的缘故，我这次莫名其妙 AK 了）：
而且题解和我的 2,3 题根本不一样，我甚至刚开始没看懂（：
而且讲题人周日晚上咕咕咕了，周一晚上 51nod 在维修所以只能今天订正题目 QAQ（蒟蒻只有晚修在机房 QAQ
好进入正题
A. 砍树
description: 小 D 有一棵树，这棵树有 n 个节点，n-1 条边，保证连通。树上每个点要么被染成黑色，要么是白色。他定义一棵树的奇怪值为：这棵树中，白色节点与黑色节点数量的差的绝对值。比如树上有 5 个白节点，3 个黑节点，奇怪值就是|3-5|=2。小 D 想让你在原树中砍出来一个连通块，使得这个连通块的奇怪值最大。（注意连通块当然也会是棵树。）$n\leq 10^5$
签到题，就随便树形 dp 一下就行
$f[u][0]$表示白点减黑点的最大值，$f[u][1]$表示黑点到白点的最大值，显然把每个点所在的子树节点正的答案累加起来就行了，复杂度 $O(n)$，代码比赛时候打的有点丑（打了一堆没用的东西
#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 100005
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mod 998244353
#define up 10000
int n, ans;
struct edge{
int nxt, v;
}e[N << 1];
int head[N], tot, sz[N], bl[N], sum, a[N], u, v, f[N][2];
inline void addedge (int u, int v)
{
e[++tot] = (edge) {head[u], v};
head[u] = tot;
}
inline int abs (int x) {return x < 0 ? -x : x;}
inline void dfs (int u, int fa)
{
if (a[u])
{
bl[u] = 1;
f[u][0] = -1;
f[u][1] = 1;
}
else
{
f[u][0] = 1;
f[u][1] = -1;
}
sz[u] = 1;
edge (i, u)
{
if (v == fa) continue;
dfs(v, u);
sz[u] += sz[v];
bl[u] += bl[v];
if (f[v][0] > 0)
f[u][0] += f[v][0];
if (f[v][1] > 0)
f[u][1] += f[v][1];
}
}
int main ()
{
scanf("%d", &n);
fo (i, 1, n)
{
scanf("%d", &a[i]);
sum += a[i];
}
fo (i, 2, n)
{
scanf("%d %d", &u, &v);
addedge(u, v);
addedge(v, u);
}
dfs(1, 0);
fo (i, 1, n)
ans = std::max(ans, std::max(f[i][0], f[i][1]));
printf("%d", ans);
return 0;
}
B. 奇怪的回文串
description: 小 D 对字符串有着奇怪的认识。对于一个字符串 S，他认为 S 是满足 “奇数-回文” 性质，当且仅当这个串的所有长度为奇数的子串都是回文串。注意一个串的子串指的是串中任意连续位置形成的串，一个 “奇数-回文” 串本身并不需要长度为奇数。现在小 D 有一个长度为 N 的字符串 S。他有 K 次修改这个字符串的机会。每次修改，他可以选择字符串上的任意一个位置，把这个位置修改成任意一种字符。他希望使得修改后的串中满足 “奇数-回文” 性质的子串的长度最大。注意 K 次机会不必用完。$N,K\leq 5e5$，权值 $1e9$
这个题我写了一个魔法贪心然后就莫名其妙 A 了，首先题目就是让你修改 K 次求一个’ABABAB..’ 形的最长子串，我就二分了一个答案，然后滑动这个窗口，维护奇数位和偶数位的相同字符出现次数的最大值，我就暴力离散化后写了个桶，那怎么求相同字符出现次数的最大值呢？暴力显然是会 gg 的，因为是滑动窗口，我就记录了一下上一次的最大值，因为每次移动一次窗口只会增加一个数减少一个数，我们就看一下增加的那个数可不可能更新上一次的最大值，如果能的话就暴力求一遍最大值复杂度是 $O(n)$的，否则最大值还是上一次的最大值（其实也不是那么容易卡这种贪心了啦 QAQ）（但是写了 150 行心态快崩了还是压时间过的）
然而题解显然更简单呀，维护一对双指针 l,r，l 从左往右移，r 找到能扩展到的最远距离，用一个可删除的堆就可以维护相同字符出现次数的最大值了，复杂度 $O(nlogn)$的，但是懒得写手写堆，我们魔改一下优先队列就行，维护当前区间每个字符出现的最大次数，堆是按字符出现次数排序的大根堆，如果这个堆的顶部这个字符=当前区间该字符出现的最大次数，那就是它最大了，否则删除堆顶继续（说明这个字符已经被删除过了）
代码：
#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 500005
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mod 998244353
#define up 10000
struct node{
int cnt, id;
friend bool operator < (node x, node y)
{
return x.cnt < y.cnt;
}
};
int a[N], q, ans, n, m;
std::map<int, int> cnt1, cnt2;
std::priority_queue<node> q1, q2;
int main ()
{
scanf("%d %d", &m, &n);
fo (i, 1, n)
scanf("%d", &a[i]);
int l = 1, r = 0, now;
node max1, max2;
fo (i, 1, n)
{
while (r < n)
{
++r;
if (r & 1)
{
q1.push((node){++cnt1[a[r]], a[r]});
while (!q1.empty())
{
max1 = q1.top();
if (max1.cnt == cnt1[max1.id]) break;
q1.pop();
}
}
else
{
q2.push((node){++cnt2[a[r]], a[r]});
while (!q2.empty())
{
max2 = q2.top();
if (max2.cnt == cnt2[max2.id]) break;
q2.pop();
}
}
now = r - l + 1 - max1.cnt - max2.cnt;
if (now > m) break;
ans = std::max(ans, r - l + 1);
}
if (l & 1)
{
cnt1[a[l]]--;
}
else
{
cnt2[a[l]]--;
}
++l;
}
printf("%d", ans);
return 0;
}
启示：不要瞎二分验证，答案满足单调性也可以是双指针+数据结构维护，减一个 log 是一个 log。
C. 范围查询
小 D 得到了一个数组 $A=[a_0,a_1,…,a_(n-1)]$。他对这个数组 A 进行了 q 个查询，每个查询都会给定四个数 left,right,x,y，你需要求出在数组 A 中，有多少位置 i 满足下列条件：
$1.left≤i≤right$
$2.a_i≡y(mod x)$
其中 a_i≡y(mod x) 表示，a_i 对 x 取模的值为 y。
$1≤n,q≤40000,0≤a_i≤40000,1≤x≤40000,0≤left≤right$
数据出锅了，有 $left>right$
后来改了数据之后又有 y>x 的点，而且标程似乎没有处理这个情况，我现在都 A 不了这题 QAQ
不过里面的思想还是值得借鉴的
当 x 比较大的时候，我们直接就暴力查询有多少值=kx+y，怎么查等等看程序就行，这里比较简单。
当 x 比较小的时候比如小于 1000，我们可以暴力枚举 x，可是现在的问题是什么呢？查询的区间是和 n 同数量级的，区间我们又想到了什么呢？就直接转换成前缀和，在一头一尾打个标记就行。
具体来讲，就是从左往右枚举数组，将它们弄到统计数组 c 里面，在如果碰到了标记的话就更新答案就行。
代码：
#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 40005
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mod 1000000007
int n, m, ans[N], a[N], opt, cnt[2];
struct node{
int l, r, x, y, id;
inline friend bool operator < (node qwq, node qaq)
{
return qwq.x < qaq.x;
}
}q[2][N], tmp;
struct fen{//差分统计答案
int id, y, v;
};
std::vector<int> vet[N];
std::vector<fen> t[N];
int c[1005];
int Max;
inline void solve1 ()//在 x 小的时候，我们可以暴力枚举 x，然后对于每一个 q[i].x，将它前缀和处理一把，那么答案就是 q[i].r 之前等于 y 的数-(q[i].l-1) 之前的数 [注意，核心思想就是差分，减小枚举区间的复杂度]
{
for (int i = 1, j; i <= cnt[0]; i = j + 1)
{
j = i;
memset(c, 0, sizeof c);
while (q[0][i].x == q[0][j].x)
{
int l = q[0][j].l, r = q[0][j].r;
t[l - 1].pb((fen){q[0][j].id, q[0][j].y, -1});
t[r].pb((fen){q[0][j].id, q[0][j].y, 1});
++j;
}
--j;
int x = q[0][i].x;
fo (k, 1, n)
{
++c[a[k] % x];
if (t[k].size())
{
int sz = t[k].size() - 1;
fo (l, 0, sz)
{
ans[t[k][l].id] += c[t[k][l].y] * t[k][l].v;
}
t[k].clear();
}
}
}
}
inline void solve2 ()//统计区间有多少个数字 x 的方法，值域小的时候可以反过来跑，将权值的 pos 存入 vet，我们就可以在给定权值的 vet 里面找出有多少个符合这个区间，二分即可。
{
fo (i, 1, n)
vet[a[i]].pb(i);
fo (i, 1, cnt[1])
{
int l = q[1][i].l, r = q[1][i].r;
for (int j = q[1][i].y; j <= Max; j += q[1][i].x)
if (vet[j].size())
{
int L = lower_bound(vet[j].begin(), vet[j].end(), l) - vet[j].begin();
int R = upper_bound(vet[j].begin(), vet[j].end(), r) - vet[j].begin();
ans[q[1][i].id] += R - L;
}
}
}
int main ()
{
scanf("%d %d", &n, &m);
fo (i, 1, n) {scanf("%d", &a[i]); Max = std::max(Max, a[i]);}
fo (i, 1, m)
{
scanf("%d %d %d %d", &tmp.l, &tmp.r, &tmp.x, &tmp.y);
tmp.id = i;
if (tmp.x == 0) continue;
// tmp.y %= tmp.x;
++tmp.l; ++tmp.r;
opt = (1000 < tmp.x);
q[opt][++cnt[opt]] = tmp;
}
std::sort(q[0] + 1, q[0] + cnt[0] + 1);
solve1();
solve2();
fo (i, 1, m)
printf("%d\n", ans[i]);
return 0;
}
总结：前缀和各种奇怪的 trick 我还是菜啊。
0 条评论