这次比赛只AC了第一题，而且花了40多分钟，貌似是A掉第一题里面最晚的

而且还有一个半小时我就放弃了……

下次即使想不出也要坚持到最后

第二题没思路

第三题想用分块搞一搞，然后发现空间开不下（其实可以用分块搞）

主要是认识了今天AK的曲恒毅大佬，收获很大

 

小D有一棵树，这棵树有n个节点，n-1条边，保证连通。树上每个点要么被染成黑色，要么是白色。他定义一棵树的奇怪值为：这棵树中，白色节点与黑色节点数量的差的绝对值。

比如这个例子中，树上有5个白节点，3个黑节点，奇怪值就是|3-5|=2。

小D想让你在原树中砍出来一个连通块，使得这个连通块的奇怪值最大。（注意连通块当然也会是棵树。）

Input

首先输入n。接下来一行n个数c_1,c_2,…,c_n 。若c_i=0，表示节点i颜色为白色，否则为黑色。接下来n-1行，每行两个数u,v，描述树上一条连接节点u,v的边。对于20%的数据，n≤20对于40%的数据，n≤100对于60%的数据，n≤1000对于100%的数据，n≤10^5,1≤x,y≤n,c_i∈{0,1}

Output

输出一行，表示最大的奇怪值。

Input示例

81 0 0 1 1 0 0 07 13 51 64 36 32 37 8

Output示例

4

---

看完第一反应树形dp 但是感觉这个绝对值不好处理，同时不知道怎么求这个连通块 然后绕了半天突然想到可以绝对值可以分开处理 求连通块的话更新的时候贪心一下，只加入dp值>0的子树，最后枚举哪个子树为根统计一下答案就好了

#include
       
        #define REP(i, a, b) for(register int i = (a); i < (b); i++)#define _for(i, a, b) for(register int i = (a); i <= (b); i++)using namespace std;const int MAXN = 1e5 + 10;struct Edge{ int to, next; };Edge e[MAXN << 1];int head[MAXN], tot;int c[MAXN], d[MAXN], dp[MAXN], n;void AddEdge(int from, int to){    e[tot] = Edge{to, head[from]};    head[from] = tot++;}void dfs(int u, int fa){    dp[u] = d[u];    for(int i = head[u]; ~i; i = e[i].next)    {        int v = e[i].to;        if(v == fa) continue;        dfs(v, u);        if(dp[v] > 0) dp[u] += dp[v];    }}int main(){    memset(head, -1, sizeof(head)); tot = 0;    scanf("%d", &n);    _for(i, 1, n) scanf("%d", &c[i]);    REP(i, 1, n)    {        int u, v;        scanf("%d%d", &u, &v);        AddEdge(u, v); AddEdge(v, u);     }        int ans = 0;    _for(i, 1, n) d[i] = c[i] ? 1 : -1;    dfs(1, -1);    _for(i, 1, n) ans = max(ans, dp[i]);    _for(i, 1, n) d[i] = c[i] ? -1 : 1;    dfs(1, -1);    _for(i, 1, n) ans = max(ans, dp[i]);        printf("%d\n", ans);    return 0;}
       

 

小D对字符串有着奇怪的认识。对于一个字符串S，他认为S是满足“奇数-回文”性质，当且仅当这个串的所有长度为奇数的子串都是回文串。注意一个串的子串指的是串中任意连续位置形成的串，一个“奇数-回文”串本身并不需要长度为奇数。

现在小D有一个长度为N的字符串S。他有K次修改这个字符串的机会。每次修改，他可以选择字符串上的任意一个位置，把这个位置修改成任意一种字符。他希望使得修改后的串中满足“奇数-回文”性质的子串的长度最大。注意K次机会不必用完。

Input

第一行包含两个整数K,N。接下来一行N个整数，第i个整数代表字符串S第i位的字符。对于20%的数据，N≤10对于40%的数据，N≤100对于60%的数据，N≤5000对于100%的数据，1≤K≤N≤500000，保证给定的字符串的字符为1到10^9间的整数。

Output

输出一个整数，表示最大可能的满足“奇数-回文”性质的子串长度。

Input示例

1 61 2 3 4 5 6

Output示例

3

---

这道题没怎么深入思考 首先要看出一个结论 如果所有奇数子串都是回文串，等价于所有长度为3的字串都为回文串 所有长度为3的字串都为回文串等价于奇数位置字符同，偶数位置字符同 这个结论画画图就可以发现 那么我们显然可以枚举子串，然后分别算出偶数位置和奇数位置同一个字符最多有多少个 如果分别由w0, w1个 那么就需要修改 序列长度-w0-w1次 那么问题就怎么高效地维护这个最大值 我们可以用一个滑动窗口来做 固定左端点，每次右端点在次数小于k的情况下尽量拓展，用序列长度更新答案 然后左端点加加，重复上个过程 在其中写两个支持删除操作的堆，维护奇数位置和偶数位置中同一个字符最多有多少个 支持删除操作的堆可以用堆优化dijsktra算法中的堆的思路 右端点共右移n次，左端点同样，所以滑动窗口的复杂度是O（n）的 然后每次操作维护堆是logn的 总复杂度是O（nlogn）的 然后我惊奇的发现用unorderer_map和手写离散化跑出来的时间基本相同。 那以后就可以用unordered_map离散化了，不需要手写了

#include
         
          #define REP(i, a, b) for(register int i = (a); i < (b); i++)#define _for(i, a, b) for(register int i = (a); i <= (b); i++)using namespace std;const int MAXN = 5e5 + 10;int a[MAXN], n, k;unordered_map
          
            cnt[2];struct node{    int id, w;    bool operator < (const node& rhs) const    {        return w < rhs.w;    }};priority_queue
           
             q[2];int main(){    scanf("%d%d", &k, &n);    _for(i, 1, n) scanf("%d", &a[i]);        int l = 1, r = 1, ans = 0;    _for(i, 1, n)    {                while(r <= n)        {            if(r & 1) q[1].push(node{a[r], ++cnt[1][a[r++]]});            else q[0].push(node{a[r], ++cnt[0][a[r++]]});            node t1, t0;            while(!q[1].empty())            {                t1 = q[1].top();                if(cnt[1][t1.id] == t1.w) break;                q[1].pop();            }            while(!q[0].empty())            {                t0 = q[0].top();                if(cnt[0][t0.id] == t0.w) break;                q[0].pop();            }                        if(r - l - t1.w - t0.w > k) break;            ans = max(ans, r - l);        }                if(l & 1) q[1].push(node{a[l], --cnt[1][a[l++]]});        else q[0].push(node{a[l], --cnt[0][a[l++]]});    }        printf("%d\n", ans);    return 0;}
           
          
         

 

小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。

 

Input

首先输入两个数n,q。接下来一行n个数a_0,a_1,…,a_(n-1) 。接下来q行，每行四个数left,right,x,y，描述一个询问。总共有10个数据点。对于第1，2个数据点，n,q≤1000对于第3，4，5，6个数据点，x≤1000对于100%的数据，1≤n,q≤40000,0≤a_i≤40000,1≤x≤40000,0≤y
        

Output

输出q行，表示每个询问对应的答案。

Input示例

5 3250 501 5000 5 40 4 5 00 4 10 00 4 3 2

Output示例

322

---

这道题曲恒毅大佬用莫队跑过去了，他说因为数据比较水 我学习了一下他的写法，自己写了一遍，练习一波莫队 这道题是问l到r中符合a_i≡y(mod x)的有多少个 直观的想法是枚举每一个a_i看满不满足 但我们可以逆向思维 枚举所有 mod x等于y的数，看这些数在l到r中出现了几次。 所以可以用莫队维护一个桶 不过这个算法显然可以卡掉，当很多x非常小而最大x非常大的时候就要遍历很多次 但是这题的数据是随机的比较水。

#include
         
          #define REP(i, a, b) for(register int i = (a); i < (b); i++)#define _for(i, a, b) for(register int i = (a); i <= (b); i++)using namespace std;const int MAXN = 4e4 + 10;int bl[MAXN], ans[MAXN], a[MAXN];int f[MAXN], n, m, blo, maxt;struct node{    int l, r, x, y, id;    bool operator < (const node& rhs) const    {        return bl[l] < bl[rhs.l] || bl[l] == bl[rhs.l] && r < rhs.r;    }}q[MAXN];int main(){    scanf("%d%d", &n, &m);    blo = sqrt(n);        _for(i, 1, n)     {        scanf("%d", &a[i]);        maxt = max(maxt, a[i]);        bl[i] = i / blo;    }        _for(i, 1, m)     {        scanf("%d%d%d%d", &q[i].l, &q[i].r, &q[i].x, &q[i].y);        q[i].l++; q[i].r++;        q[i].id = i;    }        sort(q + 1, q + m + 1);        int l = 1, r = 0;    _for(i, 1, m)    {        while(r < q[i].r) ++f[a[++r]];        while(l > q[i].l) ++f[a[--l]];        while(r > q[i].r) --f[a[r--]];        while(l < q[i].l) --f[a[l++]];        for(int j = q[i].y; j <= maxt; j += q[i].x)            ans[q[i].id] += f[j];    }        _for(i, 1, m) printf("%d\n", ans[i]);    return 0;}
         

 

讲一下正解，写了好久好久才AC，而且发现最慢的点984ms，还不如写莫队时间快

顺便吐糟一下数据有问题，竟然有x=0的，题目中给的是x>0的，我交上去RE，调试了好久才发现是数据本身的问题

正解包含了x<=1000的解法, 所以先讲x比较小的情况

对于x<=1000的时候，而询问有40000，这意味着有很多很多的x是重复的，平均下来重复40个x

那么这种情况下就启发我们可以把x相同的一起处理

那么我们就按照x排序，把x相同的一起处理

对于每个询问，我们可以打标机，在l-1处打上id, y, -1的标记，在r处打上id, y, 1的标记， id是这个询问在题目输入中是第几个，方便统计答案

有什么用呢？

打完标机后我们可以从1到n扫一遍数组，同时用一个cnt记录每个数模x等于y中y有多少次

那么遇到标记就可以使 ans[id] += cnt[y] * p; 

这个p有什么用？对于区间[l, r]， 可以转化为[1,r] - [1, l - 1]

这个p就是维护这个正负的

同时注意一个位置可能有很多个标记，所以要用一个vector存

复杂度的话，有xmax组（xmax表示最大的x），每组要扫一遍数组O(n)

所以复杂度是O(nxmax)，和最大的x有关。

40000*1000其实很极限了，所以有一个点是9秒多卡过去的

 

如果最大的x比较小，就用上述方法。然后我们考虑x比较大的情况 

这时候的解法和莫队的写法有一点点相似之处

莫队的写法使用与x比较大的情况，所以去枚举所有modx=y的数不会太慢

而这道题也因为x比较大，所以也去枚举modx=y的数

那么对于枚举出的每一个数，怎么迅速这个数在[l，r]中存在多少次？

不知道大家有没有做过区间众数那道题，那道题也存在上一行的问题

我们可以把数组中每一数，以值作为下标，位置作为值扔到一个vector中

 

比如对于5的数，在3 4 6 7这4个位置中出现过

那么如果询问在位置3到5中存在几个5

那么首先可以二分出左边界，也就是找>=3的第一个数是的位置

因为在3 4 6 7这4个位置中出现过，所以这个数显然是3，位置是1（3 4 6 7的下标从1开始，从0开始也可以，反正求的是差值）

然后可以二分出右边界+1，也就是找出大于（没有等于）5的第一个数是多少

因为在3 4 6 7这4个位置中出现过，这个数显然是6，位置是3

那么答案就是右边界+1-左边界，也就是3 - 1 = 2

我们验证一下，在3 4 6 7中3到5有3和4两个地方

所以答案是对的

可能看一遍看不懂，多看几遍，注意哪个是下标，哪个是值

 

如果设最大的数组中的值为M

那么这个复杂度是O（Q * M / xmin * logn）

 

那么现在存在一个问题，到底以x为多少分界线是最优的，这个时候我们可以用类似算分块大小中每一块多大的的方法来算

总复杂度是O（Q * M / xmin * logn +n＊xmax）

这里的xmax和xmin就是我们要求的分界值，设为L

那么O（Q * M / L * logn +n＊L）

这里Q和n都是小于等于40000，是同阶的，可以都看作Q

那么Q提出来

O（ Q（M / L * logn +L））

那么由均值不等式知

当M / L * logn =L时，它们相乘最小

可得L = sqrt(M * logn)

 

最后提一下我代码中用了unordered_map

如果本地没有加c++11的编译命令的话会CE（怎么加自行百度）

提交代码的时候也要注意选C++11， 选C++会CE

#include
         
          #define REP(i, a, b) for(register int i = (a); i < (b); i++)#define _for(i, a, b) for(register int i = (a); i <= (b); i++)using namespace std;const int MAXN = 4e4 + 10;struct node{    int l, r, x, y, id;    bool operator < (const node& rhs) const    {        return x < rhs.x;    }}q1[MAXN], q2[MAXN];int a[MAXN], cnt1, cnt2;int M, n, m, L, ans[MAXN];struct flag{    int id, y, p;};vector
          
            t[MAXN];unordered_map
           
             cnt;void solve1(){    sort(q1 + 1, q1 + cnt1 + 1);    int i = 1;    while(i <= cnt1)    {        cnt.clear();        int j = i - 1;        while(j + 1 <= cnt1 && q1[j+1].x == q1[i].x)        {            j++;            t[q1[j].l - 1].push_back(flag{q1[j].id, q1[j].y, -1});            t[q1[j].r].push_back(flag{q1[j].id, q1[j].y, 1});        }                _for(k, 1, n)        {            cnt[a[k] % q1[i].x]++;            if(t[k].size())            {                REP(r, 0, t[k].size())                    ans[t[k][r].id] += cnt[t[k][r].y] * t[k][r].p;                t[k].clear();            }        }        i = j + 1;    }}vector
            
              g[MAXN];void solve2(){    _for(i, 1, n) g[a[i]].push_back(i);    _for(i, 0, M) sort(g[i].begin(), g[i].end());    _for(i, 1, cnt2)        for(int j = q2[i].y; j <= M; j += q2[i].x)        {            int L = lower_bound(g[j].begin(), g[j].end(), q2[i].l) - g[j].begin();            int R = upper_bound(g[j].begin(), g[j].end(), q2[i].r) - g[j].begin();            ans[q2[i].id] += R - L;        }}int main(){    scanf("%d%d", &n, &m);    _for(i, 1, n)     {        scanf("%d", &a[i]);        M = max(M, a[i]);    }        L = sqrt(M * log2(n));           _for(i, 1, m)    {        node t;        scanf("%d%d%d%d", &t.l, &t.r, &t.x, &t.y); t.l++, t.r++;        if(t.x == 0) continue; //好坑！！         if(t.x < L) q1[++cnt1] = t, q1[cnt1].id = i;        else q2[++cnt2] = t, q2[cnt2].id = i;    }        solve1();    solve2();    _for(i, 1, m) printf("%d\n", ans[i]);    return 0;}
            
           
          
         

 

 

总结

（1）认识大佬

（2）字符串观察结论，写带删除的堆

（3）位置二分，逆向思维，莫队，合并处理