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我还是菜啊。

分类: 文章

quhengyi11

喵(ฅ>ω<*ฅ)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *