【算法】最大权闭合子图

日常安利两篇文章[网络流]最大权闭合图(转载)
hiho 第119周 最大权闭合子图
闭合图是啥,就是说所有的点连出去的边都指向我们所选的点集,这就是闭合图
那么我们现在要求一个最大权的闭合图,可以通过网络流来解决
我们首先转化模型,我们将所有的正权点与源点s相连,所有的负权点与汇点t相连,原来的图流量我们都换成无穷大
首先我们来证明这么一张图上最小割是简单割
简单割的定义就是割上每条边都与起点或者汇点相连
那么首先我们可以将与起点相连的边都割掉,这些边里面没有无穷大的边,当然这种割法并不一定是最小割
那么对于最小割,它付出的代价一定小于等于刚才那种方案的代价,这就要求最小割不存在无穷大的边。因此,最小割所有的边都会与起点或者终点相连
第二步,我们要证明简单割即为闭合图,闭合图即为简单割。
如果闭合图不是简单割,必然存在一条无穷大的边,那么这个图还保持联通,与割断不相合
如果简单割不是闭合图,那么一定有无穷大的边连向另一个集合,那么这个图也是不连通的,不符合前提
那么到了最关键的一步,最大权闭合子图的权值w = 所有正权点权值之和w0 – 最小割c
证明
设最小割将点集分为两半,有源点的为点集s,有汇点的为点集t,那么最小割容量c = t内原图正权点点权之和 + s中负权点点权绝对值之和,w = s内所有正权点点权之和 – s内所有负权点绝对值之和
所以c + w = 所有正权点点权和
所以w = 所有正权点点权和
例题
luogu P2762 太空飞行计划问题
这个题就是一个比较典型的最大权闭合子图问题,我们可以将实验和仪器划分到两个集合,分别以点权的绝对值向起点/汇点建边,我们割掉与起点相连的边,说明这个实验不够优,不足以让我们去购买相应的仪器,我们割掉与终点相连的边,就说明仪器的代价要小于收益

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int
using namespace std;

const int mo = 1000000007;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

char a;

bool flag;

inline void re(int &x)
{
    x = 0;
    bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x *= -1;
    if(a == '\r' || a == '\n')
        flag = 1;
}

int n, m, t, he, ta, lx, ans, tot = -1;

int q[500], v1[110], v2[110], de[110], head[110], hea[110];

struct in
{
    int to, ne, co;
}ter[10010];

inline void build(int f, int l, int c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], 0}, head[l] = tot;
}

inline bool bfs()
{
    memset(de, 0, sizeof(de));
    q[he = ta = 0] = 0, de[0] = 1;
    while(he <= ta)
    {
        int qaq = q[he ++];
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(de[to] == 0 && ter[i].co > 0)
                de[to] = de[qaq] + 1, q[++ ta] = to;
        }
    }
    return de[t] > 0;
}

int dfs(int no, int fl)
{
    if(no == t || fl == 0)
        return fl;
    for(ri &i = hea[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(de[to] == de[no] + 1 && ter[i].co)
        {
            int rt = dfs(to, min(fl, ter[i].co));
            if(rt > 0)
            {
                ter[i].co -= rt, ter[i ^ 1].co += rt; return rt;
            }
        }
    }
    return 0;
}

int main()
{
    memset(head, -1, sizeof(head));
    re(m), re(n), t = n + m + 1;
    for(ri i = 1; i <= m; i ++)
    {
        re(v1[i]), ans += v1[i], flag = 0, build(0, i, v1[i]);
        while(!flag)
            re(lx), build(i, lx + m, mo);
    }
    for(ri i = 1; i <= n; i ++)
        re(v2[i]), build(i + m, t, v2[i]);
    while(bfs())
    {
        for(ri i = 0; i <= t; i ++)
            hea[i] = head[i];
        while(int ret = dfs(0, mo))
             ans -= ret;
    }
    for(ri i = 1; i <= m; i ++)
        if(de[i] > 0)
            printf("%d ", i);
    printf("\n");
    for(ri i = 1; i <= n; i ++)
        if(de[i + m] > 0)
            printf("%d ", i);
    printf("\n%d", ans);
}

luogu P2805 [NOI2009]植物大战僵尸

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = gch()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = gch();
    if(b == 1)
        x *= -1;
}

int h, t, ta, n, m, lx, ly, lz, tot = -1, ans, pri;

int q[1010], de[1010], num[1010], v[1010], he[1010], head[1010];

struct in
{
    int to, ne, co;
}edge[1600010], ter[1600010];

bool flag[1010];

inline int ask(int x, int y)
{
    return (x - 1) * m + y;
}

inline void build(int f, int l, int c)
{
    num[l] ++, edge[++ tot] = (in){l, he[f], c}, he[f] = tot;
}

inline void rebuild(int f, int l, int c)
{
    //cout << f << ' ' << l << ' ' << c << '\n';
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], 0}, head[l] = tot;
}

inline void init()
{
    h = 1;
    for(ri i = 1; i <= n * m; i ++)
        if(num[i] == 0)
            q[++ t] = i;
    while(h <= t)
    {
        int qaq = q[h ++]; flag[qaq] = 1;
        for(ri i = he[qaq]; i >= 0; i = edge[i].ne)
        {
            int to = edge[i].to; num[to] --;
            if(num[to] == 0)
                q[++ t] = to;
        }
    }
    t = 0;
    for(ri i = 1; i <= n * m; i ++)
        if(flag[i] == 0)
            q[++ t] = i;
    while(h <= t)
    {
        int qaq = q[h ++]; flag[qaq] = 0;
        for(ri i = he[qaq]; i >= 0; i = edge[i].ne)
        {
            int to = edge[i].to;
            if(flag[to] == 1)
                q[++ t] = to;
        }
    } 
    tot = -1, t = n * m + 1;
    for(ri i = 1; i <= n * m; i ++)
        if(flag[i] == 1)
        {
            if(v[i] > 0)
                ans += v[i], rebuild(i, t, v[i]);
            else
                rebuild(0, i, - v[i]);
            for(ri j = he[i]; j >= 0; j = edge[j].ne)
            {
                int to = edge[j].to;
                if(flag[to] == 1)
                    rebuild(i, to, 1e9 + 7);
            }
        }
}

inline bool bfs()
{
    memset(de, 0, sizeof(de)), de[q[h = ta = 0] = 0] = 1;
    while(h <= ta)
    {
        int qaq = q[h ++];
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(de[to] == 0 && ter[i].co > 0)
                de[q[++ ta] = to] = de[qaq] + 1;
        }
    }
    return de[t] > 0;
}

int dfs(int no, int fl)
{
    if(no == t)
        return fl;
    int lin = 0;
    for(ri &i = he[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(de[to] == de[no] + 1 && ter[i].co > 0)
        {
            int rt = dfs(to, min(fl - lin, ter[i].co));
            ter[i].co -= rt, ter[i ^ 1].co += rt, lin += rt;
            if(lin == fl)
                return lin;
        }
    }
    return lin;
}

/*
这个题其实是一个比较板子的最大权闭合子图,但是之前没有认真了解过
闭合子图:图内所有点的出边,都指向图内所有点构成的集合中的一个点
这个东西我们可以转化成原图正权点点权之和减去新图最小割
新图怎么建
我们现在考虑植物之间的关系,它是由一堆保护和被保护这样的东西组成的
那么对于一对这样的关系,我们从保护植物向被保护的植物建边
然后跑拓扑排序,将图中的环和受环庇护的植物去掉
那么现在就剩下了一堆一定可以被删除掉的植物
那么我们就需要考虑删除哪些植物划算哪些植物不划算了
现在还是按照保护和被保护的关系建图,流量无限 
但是我们加入一个汇点和一个源点,所有正权点向汇点连边,流量为点权
负权点向源点建边,流量为点权的绝对值
然后跑最小割,答案就是所有正点点权之和减去最小割
至于为什么这么干 我们现在最小割只会割两种边 ,与起点相连和与终点相连的边
那么对于割掉与起点有关系的点,就表示我们现在决定割掉某个植物获取更大的利益
割掉与终点有关系的点,就表示我们现在决定不要某种植物的点权来减少损失 
*/ 

int main()
{
    //freopen("qwq.out", "w", stdout);
    re(n), re(m), memset(he, -1, sizeof(he)), memset(head, -1, sizeof(head));
    for(ri i = 1; i <= n; i ++)
        for(ri j = 1; j <= m; j ++)
        {
            re(lx), v[ask(i, j)] = lx, re(lz);
            while(lz --)
                re(lx), re(ly), lx ++, ly ++, build(ask(i, j), ask(lx, ly), 1);
        }
    for(ri i = 1; i <= n; i ++)
        for(ri j = m; j > 1; j --)
            build(ask(i, j), ask(i, j - 1), 1);
    init(); 
    while(bfs())
        memcpy(he, head, sizeof(he)), ans -= dfs(0, 1e9 + 7);
    printf("%d", ans);
    return 0;
} 

【算法】后缀数组

其实后缀数组是个数据结构啊……但是我习惯学个新东西叫算法了
其实也不是最近才学的,之前3月学过一次,但是印象并不是完全深刻,这次再复习一遍
先安利https://blog.csdn.net/YxuanwKeith/article/details/50636898 五分钟搞懂后缀数组!后缀数组解析以及应用(附详解代码),这篇博客讲的挺好的,特别是height数组的证明
这篇http://www.cnblogs.com/zwfymqz/p/8413523.html 也是不错的,图画的挺明白的,不过代码讲的并不是特别详细
后缀数组是个非常有趣又有用的东西,有两种构建办法,O(nlogn)的倍增法和O(n)的DC3法,但是最常用的还是倍增,因为好写啊。所以这里讲的也是倍增法
我们先从一个个单个字母考虑,这个时候显然他们字典序是第一关键字,在原序列位置是第二关键字,那么我们排个序,就可以得到现在的一个相对排名,这个排名的大小也就是这个字符串字典集的大小
然后我们现在将每个字母后面的关键字和它本身的关键字按照前为第一关键字,后为第二关键字,将它们拼起来,这个时候我们发现我们得到了长度为2的字串的相对顺序

也就是这张图画的了
那么我们既然可以从长度为1的关系推出长度为2的关系,当然也可以从长度为2的推出长度为4的……一直推到我们成功的将所有后缀区分成功停止。最坏的时间复杂度是nlogn的
接下来是整个过程

这是一个大体的算法流程,具体实现呢?
先设几个数组
rak[i]表示原字符串以第i位开头的后缀的排名,sa[i]表示当前排名为i的后缀起点在哪,tp[i]表示第二关键字排第i的它所在后缀起点在哪
那么显然rak[sa[i]] = i, sa[rak[i]] = i
这样我们就可以互相转化了
那么我们就可以先处理出之前的sa数组和之前的tp数组,然后将这两个分别作为第一关键字和第二关键字,去跑个排序,就可以得出新的sa数组,再通过sa得到rak数组
现在我们用快排什么的复杂度都是nlogn,这样太慢了,因为我们有更快的排序——基数排序
基数排序思想和桶排有点相像,但是它要比桶排高明,因为它复杂度是几乎可以达到O(n)的,而且它空间也远远小于桶排
还记得刚才我们说通过两个关键字得到新的顺序吗,基数排序和这个类似,我们每次将一个数截成好几部分,然后我们开个桶,桶的大小称为基数,然后我们用桶排的思想,按照当前比较关键字的大小放到相应的桶,我们就可以得知该关键字某个值有多少个,我们再求一边前缀和,再倒序塞回去,我们默认并保证之前的关键字从小到大排序,这样就得到了几个连续的块,这些块内按照当前考虑的所有关键字严格有序,我们从低位到高位排,因为低位已经保证有序了,对于每次高位更新,都是先插入低位值较大的,而本身目前最高位关键字也是有序的,保证每个最高位关键字都有个属于自己的块,所以目前被考虑的所有关键字才严格有序。这样就能保证排序的正确性了。代码会和构建后缀数组的其他步骤放在一起
那么每次我们倍增的过程相当于新增关键字,先处理好tp数组,有些长度较短的后缀没有第二关键字,我们就认为它们第二关键字是0,剩下的我们按照上一轮的sa[i]来处理,假设我们现在考虑的是长度为w的字串,我们要用它们转移到w << 1的字串,显然tp[i]就等于sa[i] – w,因为sa[i]是当所有子串长度不超过w的时候排名为i的字串,那么w << 1之后,他就会作为sa[i] – w这个位置上的第二关键字,所以tp[i]的起点为sa[i] – w
然后我们再去跑基数排序,求每个位置上的后缀目前的排名,并同时求出字典集大小,直到字典集大小和原字符串长度一样长
luogu P3809【模板】后缀排序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

const int ms = 1000010;

int m = 127, len, s[ms], rak[ms], sa[ms], tp[ms], sz[ms];

inline void re()
{
    char a = getchar();
    while((a >= 'a' && a <= 'z') || (a >= 'A' && a <= 'Z') || (a >= '0' && a <= '9'))
        s[++ len] = a - 48, a = gch();
}

inline void rsort()
{
    for(ri i = 0; i <= m; i ++)
        sz[i] = 0;
    for(ri i = 1; i <= len; i ++)
        sz[rak[i]] ++;
    for(ri i = 1; i <= m; i ++)
        sz[i] += sz[i - 1];
    for(ri i = len; i >= 1; i --)
        sa[sz[rak[tp[i]]] --] = tp[i];/*tp[i]表示第二关键字排i的位置在tp[i]
        rak[tp[i]]就是单纯只按第二关键字排名为i的后缀开头位置 
        这个位置按照第一关键字排序,排名第几
        这样做我们首先保证tp是从大往小走的
        然后又因为基数排序的性质我们把前面的第一关键字按照数值大小丢进新的序列中
        所以这就保证了正确性*/ 
}

int main()
{
    re();
    for(ri i = 1; i <= len; i ++)
        rak[i] = s[i], tp[i] = i;
    rsort(); 
    for(ri w = 1, p = 1; p < len; m = p, w <<= 1)
    {
        p = 0;
        for(ri i = 1; i <= w; i ++)
            tp[++ p] = len - w + i;//因为后面这些后缀没有第二关键字,自然按第二关键字排名小
        for(ri i = 1; i <= len; i ++)
            if(sa[i] > w)//如果这个后缀往前走w步,这个位置上的后缀有第二关键字的话 
                tp[++ p] = sa[i] - w;/*因为对于排好序的sa数组,在我们要求w << 1后缀时候
                sa[i]的前w个字符是sa[i - w]接下来的后w个字符,因此我们- w*/
        rsort(), swap(rak, tp), rak[sa[1]] = p = 1;
        for(ri i = 2; i <= len; i ++)
            rak[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++ p;
        //比较排名相邻两个串,如果俩关键字相同没必要管,否则++p 
    }
    for(ri i = 1; i <= len; i ++)
        printf("%d ", sa[i]);
}

但是求sa和rak并不是后缀数组最为重要的功能,它真正的用处在与求height数组
我们定义height[i] = lcp(sa[i], sa[i – 1]),h[i] = height[rak[i]], h[i] >= h[i – 1] – 1
这个是为啥呢?
h[i]表示的是以i的开头的后缀和它前一名的后缀的公共前缀,那么我们设sa[k]是sa[i – 1]前一名的后缀,那么显然h[i – 1]是这两者的公共前缀,我们现在都向前一位,变成了sa[k + 1]和sa[i],那么它们就相当于同时砍掉开头的一个字符,它们的公共前缀也就是h[i – 1] – 1,那么对于刚才那个不等式,如果h[i – 1]为0或者1的时候显然成立,否则我们继续假设与i最匹配的后缀为x,那么lcp(sa[k + 1], sa[i]) = h[i – 1] – 1,如果x比k + 1一样或者还要匹配的话,那么h[i] >= h[i – 1] – 1
所以我们可以两句话求出这个height
for(ri i = 1; i <= n; h[rak[i ++]] = k)
for(k = k ? k - 1 : k, j = sa[rak[i] - 1]; s[i + k] == s[j + k]; k ++);

这两句话非常直接,k就是之前的h[i]这个值,我们每次从上次结束的位置继续开始,不停往下找,直到不公共为止
例题
poj 1743 Musical Theme
这个题目是求两个不相重叠的相同字串的最长长度,当然你要先把这个序列差分下,求差分值相同的。我们可以用二分+后缀数组解决这个题,这个题就是利用的height数组的性质,假如height数组有一个连续大于x的区间,那么至少可以保证这个区间所包含的所有后缀有个共同的长度为x的后缀,因为lcp(i, j, k) = min(lcp(i, j), lcp(j, k))
那么这个时候二分答案就很明显了,我们可以二分答案,然后在height数组上找一个长度大于mid值并且的所有数都大于等于mid的这么一个区间,之所以长度要大于mid,是因为我们中间需要留个空不让这两个子串连在一起

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin));
}

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 20020;

int n, m, l, r, b[ms], s[ms], sa[ms], rak[ms], tp[ms], num[260], h[ms];

inline void rsort()
{
    for(ri i = 0; i <= m; i ++)
        num[i] = 0;
    for(ri i = 1; i <= n; i ++)
        num[rak[i]] ++;
    for(ri i = 1; i <= m; i ++)
        num[i] += num[i - 1];
    for(ri i = n; i >= 1; i --)
        sa[num[rak[tp[i]]] --] = tp[i];
}

inline void asksa()
{
    rsort();
    for(ri w = 1, p = 0; p < n; m = p, w <<= 1)
    {
        p = 0;
        for(ri i = 1; i <= w; i ++)
            tp[++ p] = n - w + i;
        for(ri i = 1; i <= n; i ++)
            if(sa[i] > w)
                tp[++ p] = sa[i] - w;
        rsort(), swap(rak, tp), rak[sa[1]] = p = 1;
        for(ri i = 2; i <= n; i ++)
            rak[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++ p;
    }
    ri k = 0, j;
    for(ri i = 1; i <= n; h[rak[i ++]] = k)
        for(k = k ? k - 1 : k, j = sa[rak[i] - 1]; s[i + k] == s[j + k]; k ++);
}

inline bool check(int x)
{
    int mx = - 1e9 - 7, mi = 1e9 + 7;
    for(ri i = 3; i <= n; i ++)
    {
        if(h[i] >= x)
        {
            mi = min(mi, min(sa[i], sa[i - 1])), mx = max(mx, max(sa[i], sa[i - 1]));
            if(mx - mi > x)
                return 1;
        }
        else
            mx = - 1e9 - 7, mi = 1e9 + 7;
    }
    return 0;
}

int main()
{
    re(n);
    while(n > 0)
    {
        m = 233;
        for(ri i = 1; i <= n; i ++)
            re(b[i]); 
        for(ri i = 1; i < n; i ++)
            s[i] = b[i + 1] - b[i] + 88;
        s[n] = 0;
        for(ri i = 1; i <= n; i ++)
            rak[i] = s[i], tp[i] = i;
        asksa(); l = 0, r = (n - 1) >> 1;
        while(l < r)
        {
            int mid = (l + r + 1) >> 1;
            if(check(mid))
                l = mid;
            else
                r = mid - 1;
        }
        printf("%d\n", (l >= 4) ? l + 1: 0); re(n);
    }
    return 0;
}

luogu P2852 [USACO06DEC]牛奶模式Milk Patterns
这个题目和刚才大同小异,只不过现在从不可重叠变成了可以重叠,从2个变成了k个,那么我们稍微改改,还是二分一个mid值,然后只要有个长度连续大于k的区间就行
我就改了改check函数和预处理

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin));
}

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 20020;

int n, m, k, l, r, b[ms], s[ms], sa[ms], rak[ms], tp[ms], num[20060], h[ms];

inline void rsort()
{
    for(ri i = 0; i <= m; i ++)
        num[i] = 0;
    for(ri i = 1; i <= n; i ++)
        num[rak[i]] ++;
    for(ri i = 1; i <= m; i ++)
        num[i] += num[i - 1];
    for(ri i = n; i >= 1; i --)
        sa[num[rak[tp[i]]] --] = tp[i];
}

inline void asksa()
{
    rsort();
    for(ri w = 1, p = 0; p < n; m = p, w <<= 1)
    {
        p = 0;
        for(ri i = 1; i <= w; i ++)
            tp[++ p] = n - w + i;
        for(ri i = 1; i <= n; i ++)
            if(sa[i] > w)
                tp[++ p] = sa[i] - w;
        rsort(), swap(rak, tp), rak[sa[1]] = p = 1;
        for(ri i = 2; i <= n; i ++)
            rak[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]) ? p : ++ p;
    }
    ri k = 0, j;
    for(ri i = 1; i <= n; h[rak[i ++]] = k)
        for(k = k ? k - 1 : k, j = sa[rak[i] - 1]; s[i + k] == s[j + k]; k ++);
}

inline bool check(int x)
{
    int mx = 1, mi = 1;
    for(ri i = 2; i <= n; i ++)
    {
        if(h[i] >= x)
            mx ++;
        else
            mi = mx = i; 
        if(mx - mi + 1 >= k)
            return 1;
    }
    return 0;
}

int main()
{
    re(n);
    m = 20000, re(k);
    for(ri i = 1; i <= n; i ++)
        re(s[i]); 
    for(ri i = 1; i <= n; i ++)
        rak[i] = s[i], tp[i] = i;
    asksa(); l = 1, r = n;
    while(l < r)
    {
        int mid = (l + r + 1) >> 1;
        if(check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    printf("%d\n", l);
    return 0;
}

【算法】cdq分治&整体二分

这两天学了学cdq分治和整体二分,感觉世界真奇妙
这两个东西用处就是在离线的时候代替恶心的树套树(然而有的时候还不如树套树好调emmmm),通过分治将询问修改按照一定顺序进行并且求出答案
cdq分治是一种用来解决偏序问题的好办法,归并排序就是一个cdq分治的个例,所以学过归并排序理解这里就会强很多。所谓偏序就是形如a.x < b.x a.y < b.y这种关系。当然小于号可以换成大于号,也可以不止两个不等式,有多个维度多个不等式。最多的一般是三维偏序。对于三维偏序,我们一般先会按照关键字顺序排个序(首先保证第一关键字有序),之后剩下两个维度,我们再像归并排序进行,不过一般不能直接归并,需要其他的数据结构来去维护。但是这样我们就将一些本来只有二维数据结构才能解决的问题通过cdq分治强行压掉一维,代码上要好写很多,而且常数也小了
放例题
luogu P3157[CQOI2011]动态逆序对
这个题就是一个典型的cdq分治,我们现在考虑原来的逆序对,实际上就是一个a.x < b.x a.y > b.y的二维偏序,支持删除操作后,我们又多了个新的关键字——被修改时间。然后删除挺烦人的,我们将删除变为插入,将操作倒过来,这样我们每次新插入一个值,三个关键字(被修改时间t,原序列位置pos,数字大小num)他们的关系就是a.t < b.t a.pos < b.pos a.num > b.num
那么这就是一个典型的三维偏序,预处理t,排序,然后按照归并做后面两个维度,用线段树/树状数组维护

// luogu-judger-enable-o2
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x *= -1;
}

const int ms = 100010;

int n, m, lx, ta, tail, sta[ms], a[ms], pos[ms];

lo ans[ms];

bool flag[ms];

struct in
{
    int t, pos, num; bool fl;//那么对于这个题目,我们设加入序列时间为t,位置为pos,数字大小为num,现在求a.t < b.t a.pos < b.pos a.num > b.num的个数 
}ter[ms], lin[ms];

struct es
{
    int l, r, v;
}ing[ms << 2];

inline bool cmpt(in a, in b)
{
    return a.t < b.t;//首先按照t排序,保证cdq分治中这一维度不会产生影响 
}

inline void up(int w)
{
    ing[w].v = ing[w << 1].v + ing[w << 1 | 1].v;
}

inline void insert(int w, int l, int v)//值域线段树,维护某段值域上的数的个数 
{
    if(ing[w].l == l && ing[w].r == l)
    {
        ing[w].v = (v == 0) ? 0 : (ing[w].v + v); return;
    }
    int mid = (ing[w].l + ing[w].r) >> 1;
    if(l <= mid)
        insert(w << 1, l, v);
    else
        insert(w << 1 | 1, l, v);
    up(w);
}

int ask(int w, int l, int r)//值域线段树查询 
{
    if(l > r)
        return 0;
    if(ing[w].l == l && ing[w].r == r)
        return ing[w].v;
    int mid = (ing[w].l + ing[w].r) >> 1;
    if(r <= mid)
        return ask(w << 1, l, r);
    else if(l > mid)
        return ask(w << 1 | 1, l, r);
    else
        return ask(w << 1, l, mid) + ask(w << 1 | 1, mid + 1, r);
}

void merge(int l, int r)//cdq分治具体过程 
{
    if(l == r)
        return;
    int mid = (l + r) >> 1, ll = l, rr = mid + 1, ta = l; lo d;
    merge(l, mid), merge(mid + 1, r);//先处理好两侧 
    while(ll <= mid && rr <= r)//对于t我们事先排序了,并不影响答案 
    {
        if(ter[ll].pos < ter[rr].pos)//然后我们就把它转化成一个二维的偏序问题了,这个时候和归并差不多,只是需要线段树维护 
            lin[ta ++] = ter[ll ++], insert(1, ter[ll - 1].num, 1);//每次先去pos小的,这是第二维 
        else//否则把答案处理下 
            ans[ter[rr].t] += (d = ask(1, ter[rr].num + 1, n)), lin[ta ++] = ter[rr ++];//要记住按哪维度记录答案!! 
    }
    while(ll <= mid)//把没进行完的操作进行完 
        lin[ta ++] = ter[ll ++], insert(1, ter[ll - 1].num, 1);
    while(rr <= r)
        ans[ter[rr].t] += (d = ask(1, ter[rr].num + 1, n)), lin[ta ++] = ter[rr ++];
    for(ri i = l; i <= mid; i ++)//删除每个点对线段树的影响 
        insert(1, ter[i].num, 0);
    for(ri i = l; i <= r; i ++)//把改好的序列放回去 
        ter[i] = lin[i];
    for(ri i = r; i >= l; i --)//我们不仅要正向考虑,还要反向考虑,即a.t > b.t a.pos > b.pos a.num < b.num 
    {
        if(ter[i].t <= mid)
            insert(1, ter[i].num, 1);
        else
            ans[ter[i].t] += (d = ask(1, 1, ter[i].num));
    }
    for(ri i = l; i <= r; i ++)//依然记得清空 
        insert(1, ter[i].num, 0);
}

inline void build(int w, int l, int r)//线段树建树 
{
    ing[w] = (es){l, r, 0};
    if(l == r)
        return;
    int mid = (l + r) >> 1;
    build(w << 1, l, mid), build(w << 1 | 1, mid + 1, r);
}

int main()
{
    re(n), re(m); int ci = n; ta = m;
    for(ri i = 1; i <= n; i ++)
        re(a[i]), pos[a[i]] = i;
    for(ri i = 1; i <= m; i ++)//首先我们逆向考虑,倒序看删除,即为插入 
        re(lx), flag[lx] = 1, ter[i] = (in){ci --, pos[lx], lx}, sta[++ tail] = lx;
    for(ri i = 1; i <= n; i ++)
        if(flag[a[i]] == 0)//这些一开始就插入的肯定时间要早 
            ter[++ ta] = (in){ci -- , i, a[i]};//对于答案,现在有3个因素影响,加入序列的时间,在序列中的位置,数字大小 
    sort(ter + 1, ter + 1 + n, cmpt), build(1, 1, n);
    merge(1, n);
    lo pri = 0;
    for(ri i = 1; i <= n; i ++)
        pri += ans[i];
    for(ri i = n; i >= n - m + 1; i --)
        printf("%lld\n", pri), pri -= ans[i];
}

luogu P3810【模板】三维偏序(陌上花开)
这个题和刚才那个题目基本一样,就是需要去个重这样的,但是我的代码只能在luogu拿到90分,因为剩下一个点mle,但是我在本机测那个点,只用了17m空间,bzoj上也通过了……所以我就精神ac了233333333333

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register long long

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x *= -1;
}

const int ms = 200010;

lo n, k, tre[ms], a[ms], lx, ly, lz, tot;

lo f[ms];

struct in
{
    lo a, b, c, cnt, ans;
}ter[ms], lin[ms];

inline bool cmpa(in a, in b)//这个题和刚才那个一样,只不过求的是顺序对 
{
    if(a.a != b.a)//依然要分关键字 
        return a.a < b.a;
    if(a.b != b.b)
        return a.b < b.b;
    if(a.c != b.c)
        return a.c < b.c;
}

inline lo lowbit(lo x)
{
    return x & (-x);
}

inline void add(lo x, lo v)
{
    while(x <= k)
        tre[x] += v, x += lowbit(x);
}

inline lo ask(lo x)
{
    lo rt = 0;
    while(x > 0)
        rt += tre[x], x -= lowbit(x);
    return rt;
}

inline void merge(lo l, lo r)
{
    if(l == r)//这个地方因为对于相同的操作来说,答案增加了cnt-1,一共会有cnt个cnt-1的答案 
    {
        ter[l].ans += ter[l].cnt - 1; return;
    }
    lo mid = (l + r) >> 1, ta = l;
    merge(l, mid), merge(mid + 1, r);
    for(ri i = l, j = mid + 1; i <= mid ||j <= r;)//压缩了下合并方式 
    {
        if(j > r || (i <= mid && ter[i].b <= ter[j].b))
            add(ter[i].c, ter[i].cnt), lin[ta ++] = ter[i ++];
        else
            ter[j].ans += ask(ter[j].c), lin[ta ++] = ter[j ++];
    }
    for(ri i = l; i <= mid; i ++)//删除…… 
        add(ter[i].c, -ter[i].cnt);
    for(ri i = l; i <= r; i ++)
        ter[i] = lin[i];
}

int main()
{
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    re(n), re(k);
    for(ri i = 1; i <= n; i ++)
        re(lx), re(ly), re(lz), ter[i] = (in){lx, ly, lz, 1, 0};
    sort(ter + 1, ter + 1 + n, cmpa); 
    for(ri i = 1; i <= n; i ++)//因为存在重复的情况,所以要去重 
    {
        if(ter[i].a != ter[i - 1].a || ter[i].b != ter[i - 1].b || ter[i].c != ter[i - 1].c)
            lin[++ tot] = ter[i], lin[tot].cnt = 1;
        else
            lin[tot].cnt ++;
    }
    for(ri i = 1; i <= tot; i ++)
        ter[i] = lin[i];
    merge(1, tot);
    for(ri i = 1; i <= tot; i +P3332 [ZJOI2013]K大数查询+)
        f[ter[i].ans] += ter[i].cnt;
    for(ri i = 0; i < n; i ++)
        printf("%lld\n", f[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

cdq分治就是这两道题了,有空再做……
整体二分,这个东西和cdq分治的思想也是类似的,我每次对询问二分答案,对于大于这个答案的我就丢到右区间,反之左区间,直到最后答案边界相同为止
至于中间怎么维护……还是要用线段树之类的数据结构了23333333
luogu P3332[ZJOI2013]K大数查询

// luogu-judger-enable-o2
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#define ri register int
#define debug(x) cout<<#x<<":"<<x<<endl
using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = gch()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = gch();
    if(b == 1)
        x = -x;
}

const lo ms = 100010;

lo la, lb, lc, ld, n, m, pri[ms];

struct in
{
    lo type, a, b, c, ans, pos;
}ter[ms], lx[ms << 1], ly[ms << 1];

struct es
{
    lo l, r, add, s;
}ing[400040];

inline void down(lo w)//下放标记 
{
    lo f = ing[w].add; ing[w].add = 0;
    ing[w << 1].add += f, ing[w << 1 | 1].add += f;
    ing[w << 1].s += (ing[w << 1].r - ing[w << 1].l + 1) * f;
    ing[w << 1 | 1].s += (ing[w << 1 | 1].r - ing[w << 1 | 1].l + 1) * f;
}

inline void up(lo w)//更新 
{
    ing[w].s = ing[w << 1].s + ing[w << 1 | 1].s;
}

void change(lo w, lo l, lo r, lo v)//维护一个区间线段树,记录区间内出现多少数 
{
    if(ing[w].l == l && ing[w].r == r)
    {
        ing[w].s += (ing[w].r - ing[w].l + 1) * v, ing[w].add += v; return;
    }
    lo mid = (ing[w].l + ing[w].r) >> 1; down(w);
    if(r <= mid)
        change(w << 1, l, r, v);
    else if(l > mid)
        change(w << 1 | 1, l, r, v);
    else
        change(w << 1, l, mid, v), change(w << 1 | 1, mid + 1, r, v);
    up(w);
}

inline void build(lo w, lo l, lo r)//建树 
{
    ing[w] = (es){l, r, 0, 0};
    if(l == r)
        return;
    lo mid = (l + r) >> 1;
    build(w << 1, l, mid), build(w << 1 | 1, mid + 1, r);
}

lo ask(lo w, lo l, lo r)//线段树查询 
{
    if(ing[w].l == l && ing[w].r == r)
        return ing[w].s;
    lo mid = (ing[w].l + ing[w].r) >> 1, rt = 0;
    down(w);
    if(r <= mid)
        rt = ask(w << 1, l, r);
    else if(l > mid)
        rt = ask(w << 1 | 1, l, r);
    else
        rt = ask(w << 1, l, mid) + ask(w << 1 | 1, mid + 1, r);
    up(w); return rt;
} 

void merge(lo s, lo t, lo l, lo r)//s t二分值域,l r二分询问 
{
    if(s == t)//如果值域答案确定,相应询问也确定了 
    {
        for(ri i = l; i <= r; i ++)
            if(ter[i].type == 2)
                ter[i].ans = s;
        return;
    }
    lo mid = (s + t) >> 1, ll = 0, rr = 0, lin;
    for(ri i = l; i <= r; i ++)
    {
        if(ter[i].type == 1)
        {
            if(ter[i].c <= mid)//对于插入的数比二分的答案较小的,这对于答案为mid以上的没有贡献,放左边 
                lx[++ ll] = ter[i];
            else//否则放在右边 
                change(1, ter[i].a, ter[i].b, 1), ly[++ rr] = ter[i];
        }
        if(ter[i].type == 2)
        {
            lin = ask(1, ter[i].a, ter[i].b);
            if(lin < ter[i].c)//同理,当查询的数排名靠后,我们就把它放在左区间 
                ter[i].c -= lin, lx[++ ll] = ter[i];
            else//否则放在右区间 
                ly[++ rr] = ter[i];
        }
    }
    for(ri i = l; i <= r; i ++)//清空线段树 
        if(ter[i].c > mid && ter[i].type == 1)
            change(1, ter[i].a, ter[i].b, -1);
    bool fa = 0, fb = 0;
    for(ri i = 1; i <= ll; i ++)//重新丢回原来数组 
        ter[i + l - 1] = lx[i], fa = 1;
    for(ri i = 1; i <= rr; i ++)
        ter[i + ll + l - 1] = ly[i], fb = 1;
    if(fa)//剪枝 
        merge(s, mid, l, l + ll - 1);
    if(fb)
        merge(mid + 1, t, l + ll, r);
}

int main()
{
    re(n), re(m); build(1, 1, n);
    for(ri i = 1; i <= m; i ++)
        re(la), re(lb), re(lc), re(ld), ter[i] = (in){la, lb, lc, ld, 0, i};
    merge(-n, n, 1, m);
    for(ri i = 1; i <= m; i ++)
        pri[ter[i].pos] = ter[i].ans;
    for(ri i = 1; i <= m; i ++)
        if(pri[i] != 0)
            printf("%d\n", pri[i]);
}

【luoguP3770】[CTSC2017]密钥

这个题之前想了个非常不正确的贪心,然后一看题解就是……woc……
这个题首先显然我们要考虑每次x向前移动后对答案的影响,那么现在这个题就变成了两个操作
1、将序列最前面的一个b放到最后
2、将序列最前面一串a放在最后
那么我们再将a分成两种情况考虑,一种是没动的a,一种是动了的a
然后我做的时候就想到这里,没有头绪
但事实上我们可以转化成前缀和问题
对于所有的a,只有它前缀和大于0,那么它才会作为答案,所以我们要动态维护一个前缀和
对于没有移动的a,进行2操作,假设有x个a被移动了,那么就是令未移动a的前缀和减少x,进行1操作,就是令所有a的前缀和+1
那么这个东西显然可以线段树/树状数组维护,时间复杂度O(nlogn)
显然过不了100%数据对吧,所以我们需要优化
仔细想一下,每次真正需要修改的只有被移动的a,剩下的我们可以统统用一个标记维护啊,每次我们暴力修改被移动的,然后剩下的修改标记就好啊,总复杂度O(n+n)
第三问看起来和前两问差不多,事实上我们可以和第一第二问一起做的,当强a数目为k-s个的时候,这就是第三问答案
证明也很好证明,我们把问题变换下,当强a数目为s的时候,强b的数目就是k-s个(很显然),而第三问就是将ab互换,因此当求第一位的时候,强a数目为k-s的时候,就相当于第一问强b数目为s,那么就相当于第三问强a数目为s
这个题就这么愉快的解决了,注意细节

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio> 
#include<cmath>
#include<queue>
#include<map>
#define ri register int

using namespace std;

typedef long long lo;

int p[20000005], seed, n, k, S;

int getrand() 
{
    seed = ((seed * 12321) ^ 9999) % 32768;
    return seed;
}

const int N = 10000007;

int a, b, c, add, cnt, num;

void generateData() 
{
    scanf( "%d%d%d", &k, &seed, &S );
    int t = 0;
    n = k * 2 + 1;
    memset(p, 0, sizeof(p));
    for( int i = 1; i <= n; ++i ) {
        p[i] = (getrand() / 128) % 2;
        t += p[i];
    }
    int i = 1;
    while( t > k ) {
        while ( p[i] == 0 ) ++i;
        p[i] = 0;
        --t;
    }
    while( t < k ) {
        while( p[i] == 1 ) ++i;
        p[i] = 1;
        ++t;
    }
}

int ci[20000040];

inline void change(int x)
{
    int na = add - (x - 1);
    for(ri i = 1; i <= x; i ++)
        ci[i - add + N] --;
    /**/for(ri i = -add + 1; i <= -na; i ++)//从-add+1一直到-na,因为add是标记,i-add+1 
        num -= ci[i + N];
    for(ri i = -na + 1; i <= -add; i ++)
        num += ci[i + N];
    for(ri i = 1; i <= x; i ++)
        ci[-x + i - na + N] ++;
    num -= x, add = na; /**/
}

inline void ask1()
{
    int s = 0, pos = 0, cnt = 0;
    for(ri i = 1; i <= n; i ++)
    {
        if(p[i] == 0)
        {
            pos = i; break;
        }
    }
    for(ri i = pos + 1; i <= n; i ++)
    {
        s += p[i] ? 1 : -1;
        if(p[i])
            ci[s + N] ++;
    }
    for(ri i = 1; i < pos; i ++)
    {
        s += p[i] ? 1 : -1;
        if(p[i])
            ci[s + N] ++;
    }
    for(ri i = 1 + N; i <= N + k; i ++)
        num += ci[i];
    if(num == 0)
        a = pos;
    if(num == S)
        b = pos;
    for(ri i = pos + 1; i <= n; i ++)
    {
        if(p[i] == 1)
            cnt ++;
        else
        {
            change(cnt), cnt = 0, pos = i;
            if(num == 0)
                a = pos;
            if(num == S)
                b = pos;
            if(num == k - S)//如果num为k-s,那么就对了 
                c = pos;
            if(a > 0 && b > 0 && c > 0)
                return;
        }
    }
}

int main()
{
    generateData(); ask1();
    printf("%d\n%d\n%d\n", a, b, c);
}

【CF785D】Anton and School – 2

这个题是伟大的红太阳学长出给我和刘神仙做的题,当时考场只想到了60分奇怪dp,考完听学长一讲才恍然大悟
首先考虑最暴力的dp
\[\sum_{i=1}^{n}\sum_{j=1}^{min(a_i-1, b_i-1)}C_{a_i}^{j}C_{b_i-1}^{j}\]
ai是表示目前左括号个数,bi右括号,这个显然n^2,过不掉
那么,我们是不是可以化简这个式子呢
\[\sum_{j=1}^{min(a_i-1, b_i-1)}C_{a_i}^{j}C_{b_i-1}^{j}=\sum_{j=1}^{min(a_i-1, b_i-1)}C_{a_i}^{a_i-j}C_{b_i-1}^{j}\]
这个式子开始变得和原来的式子不一样了,我们开始从这个式子非公式角度的去讨论它,这个式子就表示,在ai种物品里面选取ai-j种,在bi-1种物品里选择j种(我们保证i这位一定被选择)
那么这俩式子一乘,再求个和,实际上就等于\[C_{a_i+b_i-1}^{a_i}\]
这个式子就表示在ai+bi-1种物品里面选择ai个物品的方案数
那么我现在就可以得到这个式子\[\sum_{i=1}^{n}C_{a_i+b_i-1}^{a_i}\],这个东西显然可以递推,时间复杂度O(n)(线性求逆元的时候)

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register long long

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x *= -1;
}

const int ms = 200010;

const lo mo = 1e9 + 7;

int n, a[ms], b[ms];

bool fl[ms];

lo ans, inv[ms], pre[ms];

char lx;

int main()
{
    while(((lx = getchar()) != '(' && lx != ')')); inv[0] = inv[1] = pre[1] = pre[0] = 1;
    while(lx == '(' || lx == ')')
        fl[++ n] = (lx == '(') ? 0 : 1, a[n] = a[n - 1] + (fl[n] == 0), lx = getchar();
    for(ri i = n; i >= 1; i --)
        b[i] = b[i + 1] + (fl[i] == 1);
    for(ri i = 2; i <= n; i ++)
        inv[i] = inv[i - 1] * i % mo, pre[i] = (mo - mo / i) * pre[mo % i] % mo;
    for(ri i = 1; i <= n; i ++)
        pre[i] = pre[i] * pre[i - 1] % mo;
    for(ri i = 1; i <= n; i ++)
    {
        if(fl[i] == 1)
            continue;
        ans = (ans + inv[a[i] + b[i] - 1] * pre[a[i]] % mo * pre[b[i] - 1] % mo) % mo;
    }
    printf("%lld\n", ans); 
} 

【杂项】vim&gdb快速入门指南

PS:这个文章在草稿箱咕了很长时间……丢出来了
这个文章送给各位想往上走的学弟学妹&我自己qwq,写这个是因为,mmp作为一个之前从来没用过Linux也没在Linux环境下考过试的人一听说apio&ctsc要在Linux环境下考试(话说省选一轮游记还鸽着呢233333),瞬间虚了,于是开始试图学习vim&gdb&Linux的操作方法。但是好像没有什么太好的速成指南。这篇文章不求看完后把这些用的比windows还熟,只求能考得动试23333
先放几篇比较好的博文
https://blog.csdn.net/liigo/article/details/582231/ gdb十分钟教程
http://muzhou.tech/oi/2016/11/05/vim/ 备战NOIP2016-vim简明教程
https://www.cnblogs.com/huxinga/p/7942194.html 关于在vim中的查找和替换
vim常用命令(普通模式)

:w //保存文件,后面可以跟文件名,指定你保存的这个文件叫啥
:q //退出vim
:wq //前两者合并起来的操作,先保存再退出
:cd 目录 //这个操作可以使你的文件接下来都在这个指定的目录下搞事情,比如我保存在这个文件夹
:e //新建一个文件,后面可跟文件名,表示文件叫啥
:!***** //这个可以执行一些其他的文件,比如g++,gdb
:sp ***.*** //这样可以横向把vim窗口划分并且新建文件,考试可以用它加输入输出文件
:vsp ***.*** //和刚才差不多,只是纵向
?(字符串) //这样你可以非常迅速的查找,这些字符串会高亮
:s //可以替换指定字符串,具体为:{作用范围}s/{目标}/{替换}/{替换标志},:5,12s/getchar/gch为将5到12行的"getchar"换为”gch“,%s/getchar/gch是全局都替换
i/a //可以使你进入插入模式(写代码)
dd //删除整行
yy //复制整行
p //粘贴

剩下的用hjkl代替上下左右就不说了,说了我觉得也可能不用(毕竟不常用,不习惯),基本记住这些就够用了,还有在插入模式(也就是摁了a或i之后),摁esc可以回到普通模式,还有种奇奇怪怪的替换模式就不说了,用不到。
接下来就是重头,vimrc,这个东西可以让vim变得好看又好用qwq
特别感谢gryz的ZlycerQan小哥哥,这个vimrc是在他给我的vimrc的基础上改造的qwq

set et //将tab替换成四个空格
set nu //显示行号
set cuc //高亮所在行
set cul //高亮所在列
set sw=4 //>>,<<缩进4格
set ts=4 //tab缩进4格
syntax on //语法高亮
set cindent //c的缩进风格
set smarttab //一次删除4个空格
color evening //一种特别好看的主题
set autoindent //另一种缩进风格,可以合用
set guifont=Courier_New:h15 //好看的字体
inoremap ' ''<ESC>i //括号匹配
inoremap " ""<ESC>i
inoremap [ []<ESC>i
inoremap ( ()<ESC>i
inoremap { {}<ESC>i
map <F10> :call R()<CR>//只保存运行程序
map <F11> :call CR()<CR>//保存、编译、运行程序,已带调试选项
func! R()//两个函数
    exec "w"
    exec "!%<"
endfunc
func! CR()
    exec "w"
    exec "!g++ % -g -o !%<"//%是指当前文件名,<是去掉后缀
    exec "!%<"
endfunc

gdb则要好介绍的多
运行的时候在vim的普通模式下直接:!gdb 文件名(去掉后缀)即可

b 23 //表示在23行打了个断点(就是和dev上红行)
r //运行程序
n //下一句,但是不进入函数
s //和上面类似,但是可以进入具体的函数
p i //输出i这个变量当前信息
q //退出gdb
l x,y //输出x到y行的代码

Linux……咕咕咕

【SDOI 2018 R1&R2 CTSC&APIO 2018 游记】

前言:我立了个不写完所有的游记不写博客的flag,然后……然后我就光明正大的咕了很长很长时间,快咕了4个月了……也行……只能说,要学的,要提高的还有太多了,路漫漫其修远兮,吾将上下而求索。不看到oi的尽头,窝是不会甘心的。
day-∞
现在回想起来,觉得自己就是个**,太多愁善感了,肝就是啊……可惜那个时候总在害怕一轮炸掉…..哎
day0
清早六点半,和其他去划水的队友出发,路上还有说有笑的………
坐了n个小时车,然后到yt被无良的司机坑了,绕了远路,话说农大校区真大,教练倒是带着同学跑得快,就剩下我们几个找的苦……….
到了酒店后学弟还没来(lyh太神了),等了1h后才珊珊来迟,妈耶还吃了午饭,我们都没吃qwq。来了就做文化课,%%%,问他为啥,他说家长不让带(黑人问号???),我觉得海星。
傍晚吃晚饭,发现荒郊野外只能任凭酒店宰我,真鸡儿贵啊。
晚上看板子,发现splay都不会写,gg…..去试机看到了一堆dalao,瑟瑟发抖。碰见ytez的各位(哇我们教练和他们教练真的是真爱啊qwq,日后证明了一切),他们又在传葱教,心疼gjc,过去帮了一把。
发现自己进了第三考场,也就是gjc说的键盘最难用的房间,不过可以肆无忌惮敲键盘了2333,发现我和学弟之间就隔着一个人,妙啊(后来发现学弟旁边是sdoi rank2 orz,dalao和dalao都是在一起的),勉强还算比较神的抽。
出来在等车的空用lxy的手机调戏了下wyh,他还以为lxy会主席树233333,太傻了23333
10点早睡了
day1
心头隐隐不安,感觉要凉……
进考场,压缩包密码……无言以对…..
粗粗地看了遍题,t1一看,最优决策,哇,博弈论啊。看了大概1h后,才发现这是一个精心伪装的搜索/dp,然后又花了将近1h写了个搜索,没加记忆化(重大败笔之一),害怕时间不够,急忙做下面的题了
t2感觉可以从小到大整体排序,然后再分成一块块,按照从大到小排序。但是总觉得可以建树(又一个败笔),但是也没管,就又看t3了
t3不会,直接暴力算就好qwq
考完一听lyh说的,发现自己t2贪心凉了,需要建树,跑后序遍历,早知道就建树看看了qwq….
吃完饭突然四月飞雪,怕不是老天爷看我凉凉….mmp
下午听rqy讲题解(275orz),t1真的只需要加记忆化就a了……t2t3通过玄学手段转线段树dp,t3还得各种数学操作,mmp
晚上看了一下成绩,50+0+20,mmp啊……..凉了……lyh果然还是强,教练过来安慰了句,说一切皆有可能……好吧日常毒奶
day2
早上天空万里无云,看起来海星
进考场,打开题,妈耶密码和昨天是对应的qwq
t1感觉可以网络流,按照志愿顺序建图,虽然细节有待商榷,但是好像可以做。为了稳,还是暴力吧(最大的败笔),t2感觉可以树形dp,但是写完了才发现可能很多同级子树并在一棵子树上,急急忙忙写了个k=0。
t3我可以n^2处理子串,但是我发现我不会算方案了……那种好几个子串连在一起死活写不出来,最后n^3滚粗
考完就知道自己凉了,因为赶火车没听完题解,但一听到t1可以暴力网络流…….mmp啊……..我又一次想到正解不敢写啊……..
出来站在ytez的大门口,寒风凛冽,打不上车……我算是凉了………
到了车站教练说,来错了,他要是早说,我就和lc跑去那个车站了……..
临上车的最后一刻,ytez本校的gjc告诉我,day2我爆零了……教练问我需不需要回去,我说怎么都是凉了……
站在火车上,看着车窗外飞驰的景色,眼泪抑制不住了………
来自day n的后日谈
考完就滚回文化课了,没有理由停课了,以为自己彻底的凉了,每天特别绝望….却不想峰回路转,先是过了ctsc&apio的报名(虽然最后都打铁了),然后二轮扩招(感谢CGF圈钱),最后一名卡线进去。
有心插花花不开,无心插柳柳成荫。看起来失去了一切,却不想一切都未曾失去……
现在回想起来,一轮真的是沙茶,一轮前瞎想啥啊,就是肝啊,整天给自己心理负担,考场怂的一批,mmp,不过也行,彻底把我炸成了兴趣党。学会享受oi吧23333
CTSC
day-1
本来是文化课考试来着,结果为了适应考试环境让我翘掉了2333333。简直偷税啊。为了蹭wifi,去对面的新机房坐了一天,真安静,帮我自动屏蔽了一波传销233333,每次我出去考试之前都得在实验楼楼下开个演讲才行?mmp啊,幸好翘掉考试了,不然还得一遍淋着雨,一遍听传销233333。
不过最偷税的是emmmm,利用机房网下了一堆数据23333,有点皮。
修了半天博客的markdown,没修好qwq,下午才想起来弄弄linux,于是开始尝试在linux下写vimrc,用gdb。但是快捷编译键一直弄不好,直到晚上……..
day0
父母非得去送到火车站,行吧……于是我就和教练他们聊了一路天
上了车,教练坐在旁边,怂到不敢听歌qwq,其实我炒鸡想一边听着歌一边捣鼓vimrc的。弄了一路子,最后还成功的玩坏了vim,卸载后又装不上了qwq,决定直接重装。
下了车教练以一种非常悠闲姿态带着我报道。“反正下午还有人不是”,行行行,您说的对qwq,下午我还试机呢好吧qwq
到了那把行李一丢,然后和lcez的dzy(此处应有重点23333)他们打车去了80中,路上听dalao们口胡计数题,觉得自己菜爆了qwq
到了八十中,先去食堂吃了饭。第一眼看价格表,woc好贵啊。然后慢慢排队排过去,领到饭,发现,虽然很贵,但是比我们学校的饭菜质量高到不知道哪里去了233333333,tql!
吃完饭跟着dzy一起去逛校园,感觉这里炒鸡棒,卫生也灰常好,教学楼的内饰更别说qwq,直接把我校甩出几层楼啊qwq。本来想在国际部试机,结果找不到国际部的机子,最后溜去了图书馆。图书馆炒鸡凉快。
进了考场,发现有的机子键盘好用,有的不好用,我们就换了一次机子,打开题发现是1轮的原题woc,海星啊,连网都没断,许多dalao看了看就走了,我和dzy因为对系统的不熟悉摸了一下午鱼23333333
吃完饭等了半天才等到密码条,发现居然和dzy、rqy在一个考场,怕不是要被吊打2333333。之后在学校瞎逛,差点没赶上回酒店的车qwq
会酒店被秀了一脸神操作,一伙人来回的换宿舍,为什么你们这么秀啊qwq。最后换了半天发现换到了省实验的一位小哥-tsukasa,而且我们居然都在qwq圣殿,qwq这可真是缘分啊,群友相遇,相见恨晚qwq。
最后又装了下虚拟机,睡了…….
day 1
吃完饭慢悠悠赶去考场,然后从8:15等到8:30,这个时候告诉我们延期到45,45的时候又说继续延期。问sd的负责老师,她说:反正今天上午肯定能考的啊………..可还行,ccf干脆改名为cgf,中国咕咕协会好了……..mmp啊
9点终于开考了,打开机子发现capella说的那个位置的vimrc只读…….emmm,于是顶着干板子vim开始用了
t1一看,期望,凉了凉了qwq,略过略过,t2看到可以lca30分,然后企图写个树剖,结果写了将近5h,然后死活调不对……..t3草草暴力搜索。
考完就知道,凉了……
考完等了半天成绩,果然又双叒咕咕咕了,进考场和rqy聊天,听他一说,顿时觉得自己太菜了emmmmm,t1首先可以n^3背包,然后发现我们每次只去除一个人,重新再跑一遍无疑特别浪费,因此我们先跑n^2的背包,考虑所有人,每次去除一个人考虑的时候再倒序删了,这样也是n^2的,时间复杂度就降下来了,果然是神仙做法啊qwq。一看成绩单,不出意外的10分……
T1rqy顺利正解,t2边分+dp xjb做法qwq,t3数学题,一脸懵逼。
和大家交流下,发现全世界a了t1,emmmm,可惜我菜,什么都不会。铁定打铁emmm
晚上日常划水qwq,已经凉了emm,那就放宽心了
Day 2
万众瞩目的国家队答辩在一地眼镜碎裂声中开始了……
各位大神仙讲了一堆我完全听不懂的东西,神仙神仙,唯一在线的还是leafy tree,这个东西emmm,ddd讲的时候我们管他叫宗法树,lxl管他叫finger tree,不过这个算是唯一能听懂的东西了qwq
中场休息的时候,负责发论文集的老师说现场想要的选手可以来领取剩余的纸质论文集,于是我就急急忙忙地去排了个队,非常美妙的是,发到我手上的是全场最后一本纸质论文集23333333,限量珍藏版啊233333333
不过一上午令人开心的还是评委各种神仙言论啊233333,印象最深刻的还是“莫队算法是什么啊?业界约定俗称的吗?”以及“要解释下基础概念啊,让刚学oi的初学者尽可能看懂”。23333333333333333333333333333,这伙评委好皮啊
中午后台响起了钢琴声,dalao们真是多才多艺啊23333,Scarborough Fair好评!
下午是人工智能讲座,开始上来了个来自“迷”的小哥哥,感觉就是为他们公司搞了波宣传,讲了不到半个小时。接下来上来个来自360的叔叔(大主教周鸿祎23333333),给我们讲人工智能与安全,还是非常有意思的emmm,特别是讲怎么利用图像压缩算法本事的漏洞来攻击人工智能。不过他好像一直以为我们是八十中的学生emmmm,各种英文ppt看不懂qwq,不得不感叹经济差距真的也会影响教育水平高低的qwq,至少某种意义上来说,这些北京的孩纸接触的新鲜事物和资源要远远多于我们这种n线小城市的孩纸qwq
又是划水的一个晚上2333,已经完全放飞自我了
Day 3
一战打铁emmm
这次cgf终于不咕了,我也顺利配置好了vim,上来看到t1,感觉还算可做,只是怎么也想不到去一个n的做法,n^2log^2n吃枣药丸……出了考场就感觉主席树可做了qwq,t2是个奇奇怪怪的字符串题,看不懂看不懂qwq(后来这个题被一群队爷证明正解错误2333),t3是个提答题,看起来可以xjb做做233333。
下午不知道为什么,cgf死活不出成绩,5点也没戏,我们考场老师告诉我们,说有部分选手的源程序丢失了!!!然后在一脸震惊中,我们就去了礼堂从看6进4。dzd真是大神仙,比如“我知道你不会韩语,我就是想刁难你一下“,666666666.总的来说,一个走过场的面试让大爷们弄成了送命英语口试,各种答非所问、忘记台词……
面试完了又和我们说了下关于apio练习赛的问题,因为老毛子的原因,原定5月10号的试机赛变成了选手自己在自己电脑体验qwq,可真是海星。
吃完饭成绩还是不公布,在这种情况下草草开完了闭幕式,dzd在台上调戏两位落选选手:“我之前面试折磨他们,我现在还能折磨他们一下。”然后他老人家真的把那两位落选选手叫上来了qwq……
这次dzd还在台上公布了个重磅级消息,说是以后初赛要网上考试?可惜听说他老人家两年前在同样的舞台上说要在noi和ctsc上普及ioi赛制,时至今日还没有实现emmmm。我觉得我大概是看不到了233333333
闭幕式快结束时候,cgf正式解释了下午的事件:“因评测系统原因,某些同学的源程序丢失,我们正在积极找回,所以ctsc和apio一起颁奖。”那可海星,反正我打铁233333
最后八十中的小姐姐给我们带来了有氧(O2)舞蹈,全场笑喷,o2舞蹈23333333
最后走的时候cgf留了波人,听说是关于丢程序的事情,可海星
Day4 & apio day 0
早上起来,在床上墨迹了俩小时,8点出酒店买了个煎饼果子,绿豆面好评qwq,就是有点贵。然后为了防止没有地方住,我们9点多先到了珀丽,结果一直不给我办入住。等了一会领到了狗牌,决定把行李给lcez的dzy他们,再先回丽都退房,然后找了半天胜利一中的老哥,都是换房惹的祸啊qwq
退了房去丽都12点了,大家基本上都入住成功了,然后就是我的房间死活没好……等了半个多小时,终于耐不住性子催了下,才珊珊给我办了入住。当然还是有点小福利的,我的房间要比10楼其他房间多了个客厅233333,虽然卧室要比他们小23333333。因为懒,直接买了份外卖,吃完2点了,本来还想逛北京城,看来也是凉了emmmmm
吃完饭舍友还没来,我心头又有一种预感,怕不是又要和tsukasa同宿舍了233333,果然他们又是一波神操作,最后我和tsukasa又同宿舍了23333
下午4点坐车去了八十中,一个是为了吃晚饭,另一个顺便把午饭票换了emmmmm,我在车上睡了半个小时,醒来非常正好地到达了八十中。因为时间灰常宽裕,我就好好逛了逛八十中校园,感觉还是挺震撼的,起码别人家的实验楼不是荒废状态的,实验仪器一应俱全,基本每个教室都有人,搞得我不好意思拍照了qwq。操场也十分整洁,充满了课外活动的学生,感觉八十中小姐姐好多啊qwq,操场的一个角上全是可爱的吕孩子qwq
吃完饭tsukasa开始肝galgame,我还在旁边看了一会,各种肉啊qwq,我表示我还是一个纯洁的好孩纸啊
睡觉的时候才尴尬呢qwq,两个大老爷们一床被子emmmm,ccf怕不是想让我们探讨一波哲♂学啊……
Day 1
又是讲课的一天2333333
上午的二分还属于可以接受的范围,感觉还是人类智慧题,图论直接就是神仙,各种图的匹配听得我云里雾里,直接弃疗啊qwq,带花树什么我是拒绝的啊qwq,我这么菜,怎么可能会普通图匹配啊qwq
上午讲二分的时候,感觉dkw什么都做过,dkw真是tql!dkw AK NOI 2018!(大声的在noi2018前夕奶一口)
中午有八十中的小哥哥小姐姐们站台,说是过两天有艺术节,要提前排排。可惜我们看不到他们艺术节了qwq,听不了唱锅了啊
下午讲折纸,啥也听不懂emmmm,特别是英文课件极度不友好,我这种英语单词都背不过的菜鸡根本没法做到英语阅读啊。不过好在下午不只是讲折纸,要不然我就睡过去了啊qwq。讲完折纸开始讲各种奇怪的ai应用。感觉thu的大爷们好牛逼啊,写ai来打lol,好羡慕啊qwq,我也想去thu啊
Day 2
考试直接凉凉啊qwq
T1感觉是个恶心的数据结构题,隐隐约约有思路,可是一直写不出来,最后暴力5分,t2感觉可能扫描线做,但是肯定有数据能卡,比较随机海星,感觉所有圆心在x轴上的可以做,死活wa……然后7分,t3图论题,gg,最后12分选手,fe了
下午讲题解,t3瞎转圆方树,听都没听过qwq,t2可以暴力kdtree做,也有其他正解但是麻烦的做法,t1就是个炒鸡恶心的数据结构,本来松松松上台讲了个nlogn做法,结果被dkw聚聚hack了23333333
知道自己打铁预定,也就认命了qwq
Day 3
期盼已久的日子啊qwq,这是你qwq圣教面基的一天啊233333333333333333
上午是一位pku的图灵班大爷,给我们介绍了下一些计算机底层的东西(其实就是卡常),结果太困,一半时间都在睡觉。但是听了的一半还是行的,大爷还批判了一道松松松的缓存优化2333333(结果最后我也学了松式鸡排(雾))
下午讲的后缀自动机,结果我这种菜鸡啥也听不懂,sam一窍不通qwq。下午qwq圣殿在首师大附中的就陆续过来了23333,面了一波ks,capella,复读机zbr,panda还有yyq大爷他们qwq。下午ks直播了把舰b2333333,可惜很多大爷们去打thupc,没回来qwq(比如rqy大爷)
晚上qwq圣殿的大家基本凑在一起了,颁奖典礼开始,cgf先解释了波ctsc事件的后续,并声称后来补考的选手按没补考的线划出来以后相差不大?那可还行啧啧啧,慢慢圆233。然后就是发奖,rqy刚好赶在颁奖之前回来了,可惜没座位233333,最后坐在我左边那个沿上23333
我们一边看着各位大爷领奖,一遍聊天,不亦乐乎。临走的时候,大家合了波影……我想这可能是我最后一次见某些人了
上了车发现自己忘记带u盘了,悲伤,so sad,大概这就是乐极生悲了呜呜呜呜,幸好大部分文件还找得到
APIO Day4 & SDOI2018 Round2 Day0
因为车票较早关系,窝早早的就离开酒店跟着rqy他们去了车站,留tsukasa一个人在房间2336,也木有吃早饭嘤嘤嘤,最后到了车站补的。吃完饭领了车票,上去二楼,正好G121开始检票,这一路还算挺顺的23333。
下了车被父母截了波胡,强行被拉到亲戚家吃了顿饭,听说亲戚家的孩子想学oi,但是又不报清北之类正儿八经和oi有关系的班,那可海星啊2333。吃完饭住上酒店,是和一位yt的小哥,谁让我们教练和ytez的教练是好gay友…….
报上到和学弟&教练扯了半天,教练让我回去开个班会,我内心炒鸡拒绝啊qwq
报道的时候碰见了rqy,dzy和konoset他们,本来以为碰不到konoset了qwq,konoset好巨啊,明明我差不多年纪,他都高二了,跳级dalao%%%。
因为rqy他们是济南本地人,所以可以提前试机,非济南选手就必须等到晚上7点半…….编程兔这是个什么规定啊,说来编程兔好…好那个啥啊,公司开在一个偏僻无人的小居民区的两层小楼里,贴的那个欢迎横幅让人觉得哭笑不得qwq,好歹也是个sd省队选拔赛啊,就开的这么朴素。真的无语了qwq。
进去胡乱写了个dinic,又是想写主席树,企图复制一遍一轮的操作,然后又是没写完。这相似的开头就注定了相似的结尾啊23333,不过这次放开了,开心就好(然后这个flag在day1应声而倒233333)
回去挂了会机就碎觉了23333
SDOI2018 Round2 Day1
早早吃了早饭去考场,那个We_cannot_live_without_redsun_claris笑死。
t1是个计算几何,看起来要旋转向量然后贪心搞,但是写不动。最后写了个无输出….t2又是tarjan瞎搞……后悔apio完了没看圆方树,t3一看数学题,想了半天不可做。于是去写t230分。
考完没有什么想法,感觉爆零预定……唔吃枣药丸。结果吃完午饭教练和我说我有100分?????然后我还满心欢喜以为是我t2暴力过了……..结果听完题解后回到宿舍发现过的是t1????吓得不清……后来弄明白原来是spj写错了…….人生大起大落莫过于此啊……突然被sdoi弄得从天堂到地狱….心酸.jpg。
晚上完全放飞自我,补番补番…….
SDOI2018 Round2 Day2 & SDOI省队集训 Round2 & NOI 2018后日谈
今天比昨天更糟糕qwq……啥也不会做……题目什么的已经都忘光了,只有爆零和考试最后5min玩的扫雷还铭记于心……
noip2017终于结束了,真正结束了,所有与noip2017有关系的比赛都圆满或者圆满结束了?这一年,看到了很多大神传奇的故事,看到了很多oier抱着遗憾和悲伤,离开了这个洒满了他们汗水和泪水的赛场。回过头才发现,原来和自己同时代的人,已经基本上退役了。有的时候感觉真的,很无语,很难受…..再美妙的旅程,也会迎来终点,再玄妙的故事,也会画下句号。从入坑到退役,这是无法避免的。而在入坑到退役的这中间,是每一个oier成长的故事。我们无法改变已经发生的既定事实,但是,我们可以决定我们对于事实的态度。我想,对于很多oier,整个oi生涯都是在和其他oier的欢声笑语和不停地探索难题当中度过的,这也是oi最大的魅力所在,一群明明应该你死我活的人,却在一起交谈甚欢,我们是对手,但更是朋友。
无论退役与否,希望大家都不给自己的oi生涯留下遗憾,希望大家即便分隔多年后,回想起这段往事,能够会心一笑,至少,我们曾经欢笑过,曾经为此而发自真心的感动过。这,是我们用自己的青春写下的最美的诗篇。
有缘再会,noi2019。

【洛谷P4382】劈配

……no zuo no die,考场就想到正解了,但是不敢打,结果一轮就gg了,也算是报应qwq,也许以后我应该大胆一点了……
这个题目第一问我们可以动态建边,贪心的做一遍就好,并在匹配的同时记录剩余网络,便于处理第二问
第二问如果本来就满足期望值就不管,否则二分第几名才能满足这个人要求,然后每次用(二分答案-1)的剩余网络+重新建边,跑一下就可以了

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

typedef long long lo;

typedef long double ld;

const lo mo = 1000000007;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

inline void re(int &x)
{
    x = 0;
    char a = gch(); bool b = 0;
    while(a < '0' || a > '9')
    {
        if(a == '-')    
            b = 1;
        a = gch();
    }
    while(a >= '0' && a <= '9')
        x = (x << 1) + (x << 3) + a - '0', a = gch();
    if(b == 1)
        x *= -1;
}

int n, m, e, t, c, tot = -1, te, he, lx;

int pos[220][220][220], ta[220], lin[220], head[880], ta1[220], ta2[220];

int q[1010], de[1010], fir[220][880], a2[220], num[220], hop[220];

struct in
{
    int to, ne, co;
}ter[80080], wb[220][80080];

inline void build(int f, int l, int c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], 0}, head[l] = tot;
}

inline bool bfs()
{
    memset(de, 0, sizeof(de));
    q[te = he = 0] = 0, de[0] = 1;
    while(he <= te)
    {
        int qaq = q[he ++];
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(de[to] == 0 && ter[i].co > 0)
                de[to] = de[qaq] + 1, q[++ te] = to;
        }
    }
    return de[e] > 0;
}

int dfs(int no, int fl)
{
    if(no == e)
        return fl;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(de[to] == de[no] + 1 && ter[i].co > 0)
        {
            int rt = dfs(to, min(fl, ter[i].co));
            if(rt > 0)
            {
                ter[i].co -= rt, ter[i ^ 1].co += rt;
                if(no >= 1 && no <= n && to > n)
                    lin[no] = to - n;
                return rt;
            }
        }
    }
    return 0;
}

int main()
{
    re(t), re(c);
    for(ri ci = 1; ci <= t; ci ++)
    {
        memset(pos, 0, sizeof(pos)), memset(fir, -1, sizeof(fir));
        memset(head, -1, sizeof(head)), memset(ta, 0, sizeof(ta));
        memset(ta2, 63, sizeof(ta1)), memset(lin, 63, sizeof(lin));
        re(n), re(m), e = n + m + 5, tot = -1;
        for(ri i = 1; i <= m; i ++)
            re(num[i]), build(i + n, e, num[i]);
        for(ri i = 1; i <= n; i ++)
            for(ri j = 1; j <= m; j ++)//pos[i][j][0]表示第i个人第j志愿一共选了多少导师 
                re(lx), pos[i][lx][++ pos[i][lx][0]] = j, lx = (lx == 0) ? 1000000007 : lx, ta2[i] = min(ta2[i], lx);
        for(ri i = 1; i <= n; i ++)//第m + 1志愿设为m + 1位导师(没匹配成功) 
            re(hop[i]), pos[i][m + 1][++ pos[i][m + 1][0]] = m + 1;
        for(ri i = 0; i <= e; i ++)//fir[i][j]表示当前匹配到i号学员的head[j] 
            fir[0][i] = head[i];
        for(ri i = 0; i <= tot; i ++)//wb[i][j]表示当前匹配到i号学员,第j条边的情况,记录残余网络 
            wb[0][i] = ter[i];
        ta1[0] = tot;
        for(ri i = 1; i <= n; i ++)
        {
            build(0, i, 1);
            int ll = tot;
            while(++ ta[i] <= m + 1)//动态加边 
            {
                head[i] = ll;//每回合将之前这个点连的边基本踢掉,只留从它到起点的 
                if(pos[i][ta[i]][0] == 0)
                    continue;
                for(ri j = 1; j <= pos[i][ta[i]][0]; j ++)//建边 
                    build(i, pos[i][ta[i]][j] + n, 1);
                if(bfs())//如果可以增广,说明可以匹配了 
                {
                    while(int ret = dfs(0, 1000000007));
                    break;
                }
            }
            for(ri j = 0; j <= e; j ++)//记录每次的残余网络 
                fir[i][j] = head[j];
            for(ri j = 0; j <= tot; j ++)
                wb[i][j] = ter[j];
            ta1[i] = tot;//记录到此时用的边 
        }
        for(ri i = 1; i <= n; i ++)
            ta[i] = (ta[i] > m + 1) ? m + 1 : ta[i], printf("%d ", ta[i]);
        printf("\n");
        for(ri i = 1; i <= n; i ++)//然后接下来二分答案,第几名才能满足第i个人的要求 
        {
            int lia = 0;
            if(ta[i] <= hop[i])
                a2[i] = 0;
            else
            {
                int l = 1, r = i - 1, mid;
                while(l <= r)
                {
                    mid = (l + r) >> 1;
                    for(ri j = 0; j <= e; j ++)//替换成原来的剩余网络 
                        head[j] = fir[mid - 1][j];
                    for(ri j = 0; j <= ta1[mid - 1]; j ++)
                        ter[j] = wb[mid - 1][j];
                    int rr = tot;
                    build(0, i, 1);
                    for(ri j = 1; j <= hop[i]; j ++)//然后把期望值之前的志愿连边就行,任意一个能匹配就可以 
                        for(ri k = 1; k <= pos[i][j][0]; k ++)
                            build(i, pos[i][j][k] + n, 1);
                    bool fl = bfs() && dfs(0, 1000000007);
                    if(fl == 1)
                        l = mid + 1, lia = mid;
                    else
                        r = mid - 1;
                    tot = rr;
                }
                a2[i] = i - lia;
            }
        }
        for(ri i = 1; i <= n; i ++)
            printf("%d ", a2[i]);
        printf("\n");
    }
    return 0;
}

【杂项】2018.4.21题解

前前言:我的博客好不好看2333333333
前言:其实我是想把题目的标题出成“一道二分好题”这种格式的,然后被冷漠义正言辞的拒绝了,说这种暗示不好
1 梅花桩
1.1 解法一
将靠近东岸的所有梅花桩放进队列,对整张图跑一个bfs,即可判断靠近西岸的梅花桩是否能被全部到达。假设全部到达,那么显然,只选择一个点作为起点的话,最后西岸能被到达的点将会连成一片,成一条线段。因为如果中间有断点的话,就存在无法到达的点,与初始条件相违背。这样我们就可以将第二问转化为用尽可能少的线段,令整个区间全部被覆盖。可以贪心,也可以dp。
2 大霸星祭
原题出自sdwc2018 day3 运动会,网上应该找不到。
2.1 解法一
考虑先二分答案。假设当前选择某个运动项目的人数超过了二分值,我们
就必须删掉它,然后再重新计算每个人选择的项目。如果最后所有运动项目都
删光了就说明不合法。删运动项目的时候暴力重算的话每次需要 O(nm) 的复
杂度,我们可以维护一下每个人的前几个喜欢的项目被删掉了,那么删项目的
总复杂度就只需要 O(nm) 了。
时间复杂度 O(nm log m),期望得分 70-100 分。
2.2 解法二
实际上解法二的二分答案是不必要的。我们要想使得答案减小,就必须删
掉当前最多人选择的那个运动项目。一边做一边更新一下答案就可以了。
时间复杂度 O(nm),期望得分 100 分。
3 可爱的阿福
原题出自bzoj(爆炸oj)2763飞行路线
3.1 解法一
考虑没有阿福,答案为朴素的最短路,显然与最短路(这里我们用spfa)有关系。现在阿福可以使某些边边权变为0,那么spfa进行转移的时候有两种方法,一种是将这条边的边权变为0,另一种是不变,那么就可以建出一张分层图。设dis[i][j]表示当前走到第i点,之前使用过j次阿福时的最短路径,看做一个二维的状态,就可以spfa了。
时间复杂度O(玄学),期望得分70分
3.2 解法二
既然数据范围支持spfa,且没有负权边,说明dij也可以做。我们把spfa换成dij即可。
数据范围O(nlogn),期望得分100分
注:此题用spfa可以在bzoj上通过,所以bzoj应该是总时限10s内即可
4 人际关系
原题出自SDOI 2017 Round1 day2 t3 相关分析
现在我们求线性回归方程里带个平均数,令我们难以维护,所以我们试图将这个式子变形

4.1 解法一

【洛谷P4126】最小割

……时间有点紧,就不写了qwq,要写的都在代码里了qwq

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

typedef long long lo;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

inline void re(int &x)
{
    x = 0;
    char a = gch(); bool b = 0;
    while(a < '0' || a > '9')
    {
        if(a == '-')
            b = 1;
        a = gch();
    }
    while(a >= '0' && a <= '9')
        x = (x << 1) + (x << 3) + a - '0', a = gch();
    if(b == 1)
        x *= -1;
}

struct in
{
    int fr, to, ne, co;
}ter[200020];

int n, m, s, t, he, ta, lx, ly, tt, lz, ret, ans, cnt, ci, tot = -1;
int lin[20020], low[20020], sta[20020], dfn[20020], scc[20020], q[20020], de[20020], head[4020];

bool flag[20020];

inline void build(int f, int l, int c)
{
    ter[++ tot] = (in){f, l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){l, f, head[l], 0}, head[l] = tot;
}

inline bool bfs()
{
    memset(de, 0, sizeof(de));
    q[he = ta = 0] = s, de[s] = 1;
    while(he <= ta)
    {
        int qaq = q[he ++];
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(de[to] == 0 && ter[i].co)
                q[++ ta] = to, de[to] = de[qaq] + 1;
        }
    }
    return de[t] > 0;
} 

int dfs(int no, int fl) 
{
    if(no == t)
        return fl;
    int used = 0;
    for(ri i = lin[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to, ret;
        if(de[to] == de[no] + 1)
        {
            ret = dfs(to, min(ter[i].co, fl - used));
            ter[i].co -= ret, ter[i ^ 1].co += ret;
            if(ter[i].co)//优化,边权为0的边就不需要跑了 
                lin[no] = i;
            used += ret;
            if(used == fl)//能跑到这里的最大流量,一起返回,减少递归次数 
                return fl;
        }
    }
    if(used == 0)   
        de[no] = 0;
    return used;
}

void tarjan(int no)//把剩余网络缩点 
{
    dfn[no] = low[no] = ++ ci, sta[++ tt] = no, flag[no] = 1;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(ter[i].co)
        {
            if(dfn[to] == 0)
                tarjan(to), low[no] = (low[no] > low[to]) ? low[to] : low[no];
            else if(flag[to])
                low[no] = (low[no] > dfn[to]) ? dfn[to] : low[no];
        }
    }
    if(low[no] == dfn[no])
    {
        cnt ++;
        while(233)
        {
            int qaq = sta[tt --]; scc[qaq] = cnt, flag[qaq] = 0;
            if(qaq == no)
                break;
        }
    }
}

int main()
{
    memset(head, -1, sizeof(head));
    re(n), re(m), re(s), re(t);
    for(ri i = 1; i <= m; i ++)
        re(lx), re(ly), re(lz), build(lx, ly, lz);
    while(bfs())//先dinic,跑出最小割 
    {
        for(ri i = 1; i <= n; i ++)//应该是优化qwq,用lin存储每次还有价值值得去跑的边开头qwq

            lin[i] = head[i];
        ans += dfs(s, 1000000007);
    }
    for(ri i = 1; i <= n; i ++)
        if(!dfn[i])
            tarjan(i);
    for(ri i = 0; i <= tot; i += 2)
    {
        if(ter[i].co > 0)
        {
            puts("0 0"); continue;
        }
        int f = ter[i].fr, to = ter[i].to;
        if(scc[f] != scc[to])//如果说这个边之前是满流边而且连接着两个不同的集合,那么说明一定出现在最小割的某个方案里
            printf("1 ");//可以这么想,我们有很多种方案可以把这些缩过的点分成两半,那么这些跨集合的点是一定需要这些边来切开的(但不是必须每次使用) 
        else
            printf("0 ");
        if(scc[f] == scc[s] && scc[to] == scc[t])//如果这个边连接起点和终点,那么必须切断否则还联通 
            puts("1");
        else
            puts("0");
    }
}