Blog

【练习】#564 (Div. 2)

C传送门

题意是给定1-n的序列，附加n个0，每次a序列可以任意取出一张加入b序列尾部并且从b序列头部取出一张加入a序列。问最少多少步能完成排序。

分类贪心。第一类情况是b序列的尾部已经是一个完整的上升序列，并且a序列和b序列前部能顺序完成拼出上升序列，这种情况模拟一下，最后判断是否能成立。

另一种情况是必须把b序列取出一定的数。这种情况，对于每个取到的数子a[i] = k.他在第一个数字1加入a序列以后，最迟要在之后k步内取到，所以取如a序列的数字的步数就是tmp = max(tmp, i – a[i] + 1),在最大一个步数的数字取完后，就能保证顺序加入b序列的尾部时能完成排序，此时答案是tmp + n;因为加入n个数字需要n步。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 233;
int a[maxn], b[maxn], vis[maxn];
int n; 
int go()
{
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        if(b[i]) ans = max(ans, i - b[i] + 1);
    }
    return ans + n;
}
int go2()
{
    set<int> st;
    for(int i = 1; i <= n; i++) if(a[i]) st.insert(a[i]);
    int ans 

【最小区间覆盖】Minimal Segment Cover

传送门

题意是给定N个区间，询问M个区间最少能用多少个给定的线段覆盖，允许重合/超过。

首先很明显的是被某个区间完全覆盖的小区间是没有用的。

然后需要发现，对于每一个左端点，找到包含这个点而且右端点最远的一个区间肯定是最优解。

那么对于给定区间的右端点，按照降序排列。对排好序的每个区间 i ，这些点最远的右端点就是 i 这个区间的右端点。然后对于下一个区间 j ，小于上一个区间 i 左端点的那些点 的最远右端点就是当前区间 j 的右端点。

这样既消除了被完全覆盖的区间，又找到了包含每个点最远的区间。

然后按照上述关系建立图，实际上是一颗树。

对于每个询问[l, r]，通过树上倍增找到大于r最小的父亲。深度相减就是区间个数。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 233;
struct rec{int l, r;};
bool cmp(const rec &x, const rec &y)
{
    return x.r > y.r;
}
rec a[maxn], b[maxn];
int h[maxn], e[maxn], pre[maxn], cnt;
void add(int u, int v)
{
    e[cnt] = v; pre[cnt] = h[u]; h[u] = cnt++;
}
int mt[maxn];
int fa[maxn][20], d[maxn], t;
void 

【记录】Google KickStart 2019C

A题

注意到横坐标和纵坐标其实是独立不影响的。只要知道了某一列有哪些连续的格子，就可以知道某一步应该走到哪里。这种思想在很多题目都出现过。

接下来变成了维护一些不相交区间，要支持快速查询某个点的左边和右边是否有区间，并且插入/合并区间。用set来实现。注意使用哨兵元素处理迭代器运算异常减少代码量。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 233;
char op[maxn];
typedef set<pair<int,int> > spi;
spi r[maxn], c[maxn];
void add(spi &s, int pos)
{
    int l = pos, r = pos;
    auto it = s.lower_bound({pos, pos});
    auto jt = it--; // jt: >=   it <=
    if(it->second == pos - 1) l = it->first;
    if(jt->first == pos + 1) r = jt->second;
    s.insert({l, r});
    if(l != pos) s.erase(it); 
    if(r != pos) s.erase(jt); 
}
void move(spi &s, 

【整体二分】AcWing268

传送门

其实整体二分就是在二分答案的同时把询问也二分了。排除询问不可能的值域。

树状数组可以区间更新单点查询，不要傻傻地去写区间更新区间查询的树桩上数组。。。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 233;
int o[maxn], b[maxn], lb[maxn], rb[maxn];
vector<int> pos[maxn];
ll p[maxn];
int ans[maxn];
int n, m, k;
struct rec{
    int l, r; ll v;
}a[maxn];
ll c[2][maxn];
void add(int t, int x, ll v)
{
    for(; x <= m; x += x & -x) c[t][x] += v;
}
ll ask(int t, int x)
{
    ll res = 0;
    for(; x; x -= x & 

【整体二分】ZOJ2112 – 动态区间第k大

传送门

我永远喜欢离线分治算法

题意不多说，带修改的区间第k大。

整体二分。

整体二分也叫基于值域的分治算法。

二分答案，先将整个序列的值域二分得mid。对于整个操作序列1~M，可以依次知道在操作区间Mi ：[ l , r ] <= mid 的值有多少个。具体来说就是利用一个树状数组，如果A[ i ] <= mid 那么树状数组add( i , 1)。 如果带有修改操作，那么就把修改拆成在位置 i 加一个数和减一个数。

如果对于第k大查询Mi，有cnt个数在区间内小于k，很明显如果cnt = k的话答案就在左值域里面。否则就在右值域里面。(注意，二分值域的意义就是二分查询的答案)

然后，对于这些询问进行分类。在左值域的询问和操作分一堆，在右值域的询问和操作分一堆。这是个分治的过程，继续往下递归这两类询问。直到值域二分的边界，所剩下的询问的答案就是这个值。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 233;
struct rec{
    int t, x, y, z;
}a[maxn], lb[maxn], rb[maxn];
unordered_map<int,int> ump, rg;
set<int> st;
int n, m;
int seq[maxn];
int c[maxn], tot;
void add(int x, int v)
{
    for(; x <= n; x += x & -x) 

【kmp】AcWing160

传送门

题意是说给定长度为n的字符串A，长度为m的字符串B，q个询问

每次询问有A的所有后缀里有多少个使得与B的前缀匹配长度恰好为K

在对A字符串做匹配的时候，本来 f[i] = j 表示的是A中以A[i]结尾的后缀与B的前缀的最大匹配长度。现在要改一下定义。f[x]表示匹配长度至少为x的有多少个位置。

当A中以A[i]结尾的字符串与B的最大匹配长度为j的时候，证明产生了一个匹配长度至少为j的后缀，但是不一定是恰好为j，因为此时的A[i]结尾字串并不是A数组的后缀。然后需要发现：匹配长度至少为next[j]的后缀的数量也增加了。

于是f函数的各个函数值之间是拓扑的关系。f[k] = \sum\limits_{next[j]=k} f[j]

于是匹配长度恰好为x的数量就是f[ x ] – f[ x + 1 ]

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 233;
int n, m, q;
char a[maxn], b[maxn];
int ne[maxn], f[maxn];
int main()
{
    cin >> n >> m >> q;
    cin >> a + 1 >> b + 1;
    ne[1] = 0;
    for(int i =2, j = 0; i <= m; i++)
    {
        while(j > 

【CDQ分治】AcWing 267

传送门

一般CDQ分治。

如果用二维BIT在线做的话，空间是不能承受的。所以考虑CDQ离线。

如果没有加数操作，只有询问，那么按照x排序，在y方向维护树状数组，就可以算出每个询问的答案。

现在有了加数操作，相当于时间变成了第三位。于是先按第三维排序，进行CDQ分治。每次分治之后把前一半的修改对后一半询问的影响看成一个离线询问。

然后玄学的地方出现了

把y坐标进行离散化。TLE

优化常数一，对每个y坐标改为它离散化后的相对大小，减小查询常数。TLE（甚至一组都过不了

优化常数二，把坐标离散化后再离线，对于每个下标 i 的坐标y，都存在idx[]数组里访问。TLE

优化常数三，把unorder_map改为了int数组，查询y坐标的时候直接访问数组，TLE

以上操作二和操作三是分开的，也就是说，两个理论查询复杂度O(1)的操作都是TLE

优化常数四，把操作二和操作三合并，理论上还是O(1)的而且常数还稍大了一点。AC……

#include<bits/stdc++.h>
using namespace std;
//unordered_map<int,int> ump;
const int maxn = 1e6 + 233;
struct Node{
    int x, y, t, v;
}q[maxn], b[maxn];
int ans[maxn], c[maxn], tot = 0, idx[maxn];
int ump[maxn * 2];
inline void add(int x, int v)
{
    for(; x <= tot; x += x & -x) c[x] += v;
}
inline int ask(int x)
{
    int res = 0;
    

【有根树最小表示】AcWing 157

传送门

最小表示这颗有根树，注意要加入哨兵元素

#include<bits/stdc++.h>
using namespace std;
string s1, s2;
string gao(string &s, int &i)
{
    vector<string> v;
    i++;
    while(s[i] == '0')
    {
        v.push_back(gao(s, i));  
    }
    i++;
    string res = "0";
    sort(v.begin(), v.end());
    for(auto &str: v) res += str;
    res += "1";
    return res;
}
int main()
{
    int T; cin >> T;
    while(T--)
    {
        cin >> s1 >> s2;
        s1 = '0' + s1 + '1';
        s2 = '0' + s2 + '1';
        int n = 0, m = 0;
        

【逆序对/贪心】BZOJ4240

传送门

题意是说给定一个序列，只能交换相邻的两个数。问最后形成单峰序列（单调也是单峰）所需要的最小交换步数。

首先如果只需要单调数列，那么排序后，每个数在原序列中的下标所形成的逆序对就是交换次数。

由这个性质可以知道，旧序列的下标在新序列的逆序对就是答案。

接下来考虑如何形成单峰，做法是贪心，尽量形成少的逆序对。可以用树状数组动态维护。最开始的想法是说把尽量小的数往两边扔。但这样并没有很好的性质继续贪。
正确的做法是先考虑最大的数字。因为最终序列每个数字的相对位置都是固定的，所以先考虑最高的数字。

此时还需要发现一个性质：在一个序列（无论这个序列如何调整顺序）的两端加入一个数，所形成的新的逆序对/顺序对是固定的

也就是说，考虑第k大数字的时候的时候，只需要比较加在第k – 1大的数字的左边还是右边。由于k – 1大的数字所形成的序列是连续的，那么就等于在序列两端加数字，使得产生尽量少的逆序对。而在序列内部的数字如何调整对于要新加入的数字在左边还是右边是没有影响的。此时可以发现贪心策略是正确的。

对于值一样大的数字，由于相同的值最后肯定是相对顺序的，所以在考虑逆序对的时候不需要考虑和相同数字所产生的逆序对。具体来说，就是把所有一样的数字的结果先算出来，再把他们加入树状数组。

#include<bits/stdc++.h>
using namespace std;
const int maxn  = 3e5 + 233;
typedef long long ll;
typedef pair<int,int> pii;
vector<pii> a;
int n; 
int c[maxn];
void add(int x)
{
    for(; x <= n; x += x & -x) c[x] += 1;
}
int ask(int x)
{
    int res = 0;
    for(; x; x -= x & -x) res += c[x];
    return res;
}
int main()
{
    cin 

【树形dp】acwing758

传送门

题意是给一棵树，每个节点有颜色，只有白色和黑色，切成若干部分，使得每部分只有一个白色点。
求切割方案。

状态设计

f[i][0]代表i节点的儿子都符合条件，且 i 点所在的连通块有白色点。
f[i][1]代表i节点的儿子都符合条件，且 i 点所在的连通块没有白色点

1. 当 i 点是白色点的时候。f[i][1] = 0因为他不可能存在一个连通块内并且不包含白色。f[i][0]由其所有的儿子的方案累乘。具体来说，对于一个儿子j，可以选择切割这条边，+f[j][0]，也可以不切这条边 +f[j][1]

f[i][1] = 0

f[i][0]=\prod{(f[j][0] + f[j][1])}

2. 当 i 点是黑色点的时候。f[i][1]也是同理由其儿子选择切割与不切割转移来，f[i][0]则是由贡献白点的儿子转移，由于只能有一个儿子贡献白点，其他儿子贡献的是全黑点的连通块，所以各个儿子贡献之间是加法关系

f[i][1] = \prod{(f[j][0] + f[j][1])}

f[i][0] = \sum f[j][1] * \prod\limits_{i != j}{f[j][0]}

这里的由于需要 i != j 的乘法积，可以直接先全部乘起来，再分别除f[i][0]。但是由于有取模操作，并且模数很大且是一个质数，所以用逆元来代替除法。

不过xc大佬用的前缀后缀积，更简单但是开始的确是没想到。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 233;
const ll mod = 1000000007; 
int e[maxn * 2], h[maxn], pre[maxn * 2], c[maxn], cnt;