【洛谷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");
    }
}

【HDU4677】Graph

这个题调的我真绝望(这个题解的公式也写的我很绝望),写了三遍调了一天才过qwq,蓝瘦香菇
这个题利用了根号分治的思想,我们把按照入度把边分类,所有出入度之和大于\(\sqrt[2]{m}\)的点作为重点,剩下的点作为轻点
那么设重点个数为\(x\),所以\(\frac{x*\sqrt{m}}{2} \lt m\) ,所以\(x \lt 2 * \sqrt{m}\)
那么我们将单次修改和查询的时间复杂度都变为了\(n\sqrt{n}\),就可以接受了

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int
#define F(i,a,b) for(ri i=a;i<=b;i++)  

using namespace std;

typedef long long lo;

const int s = 100010;

char lin, qwq[20];

lo n, m, du[s], tp[s], col[s], ans[5], su[s][2], head[s][2], q, lx, ly, ci, tot, cnt, sz;

struct in
{
    lo to, ne, co;
}ter[s << 2];

struct es
{
    lo f, l, c;
    inline bool operator < (const es &a) const
    {
        if(f == a.f)
            return l < a.l;
        return f < a.f;
    }
}ing[s];

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(lo &x)
{
    x = 0;
    char a = getchar(); bool b = 0;
    while(a < '0' || a > '9')
    {
        if(a == '-')
            b = 1;
        a = getchar();
    }
    while(a >= '0' && a <= '9')
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x *= -1;
}

inline void rechar(char &x)
{
    x = getchar();
    while(x < 'A' || x > 'Z')
        x = getchar();
}

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

int main()
{
    while(~ scanf("%lld%lld", &n, &m))
    {
        tot = cnt = 0;
        for(ri i = 1; i <= n; i ++)
            re(col[i]);
        for(ri i = 0; i < m; i ++)
        {
            re(ing[i].f), re(ing[i].l), re(ing[i].c);
            if(ing[i].f > ing[i].l)
                swap(ing[i].f, ing[i].l);
        }
        sort(ing, ing + m);
        for(ri i = 0, j; i < m; i = j)//合并重边 
        {
            for(j = i + 1; ing[j].f == ing[i].f && ing[j].l == ing[i].l && j < m; j ++)
                ing[i].c += ing[j].c;
            ing[cnt ++] = ing[i];
        }
        sz = sqrt(cnt << 1);//按照根号分治 
        memset(du, 0, sizeof(du)), memset(head, -1, sizeof(head));
        for(ri i = 0; i < cnt; i ++)
            du[ing[i].f] ++, du[ing[i].l] ++;
        for(ri i = 1; i <= n; i ++)//判断所有出入大于m^(1/2)的点,因为设点的个数为X,那么x * m ^ (1 / 2) / 2 < m,所以x < 2 * sqrt(m),这样时间复杂度就降下来了 
            tp[i] = (du[i] >= sz);
        for(ri i = 0; i < cnt; i ++)//重新建没有重边的图 
        {
            lo x = ing[i].f, y = ing[i].l, c = ing[i].c;
            if(tp[x])//重点(度数大于sqrt(m))是被连的,轻点是连出去的 
                build(1, y, x, c);
            else
                build(0, x, y, c);
            if(tp[y])
                build(1, x, y, c);
            else
                build(0, y, x, c);
        }
        memset(ans, 0, sizeof(ans)), memset(su, 0, sizeof(su));
        for(ri i = 0; i < cnt; i ++)
        {
            lo f = ing[i].f, l = ing[i].l, c = ing[i].c;
            if(tp[f])//维护每个点与它相连的两种点所形成的边的边权 
                su[f][col[l]] += c;
            if(tp[l])
                su[l][col[f]] += c;
            ans[col[f] + col[l]] += c;
        }
        printf("Case %d:\n", ++ ci);
        re(q);
        while(q --)
        {
            scanf("%s", qwq), re(lx);
            if(qwq[0] == 'A')
                re(ly), printf("%lld\n", ans[lx + ly]);
            else
            {
                col[lx] ^= 1;
                if(tp[lx])//如果这个点是重点,直接修改
                    for(ri i = 0; i <= 1; i ++)
                        ans[(col[lx] ^ 1) + i] -= su[lx][i], ans[col[lx] + i] += su[lx][i];
                else//否则对与自己相连的轻点修改(不超过sqrt(m)) 
                    for(ri i = head[lx][0]; i > 0; i = ter[i].ne)
                    {
                        int to = ter[i].to;
                        ans[(col[lx] ^ 1) + col[to]] -= ter[i].co;
                        ans[col[lx] + col[to]] += ter[i].co;
                    }
                for(ri i = head[lx][1]; i > 0; i = ter[i].ne)//每次都要修改与自己相连的终边 
                {
                    int to = ter[i].to;
                    su[to][col[lx] ^ 1] -= ter[i].co, su[to][col[lx]] += ter[i].co;//减去原来的方案,加上现在的方案 
                }
            }
        } 
    }
}

【游记】2018春qqxt划水记–菜鸡绝望的挣扎

其实上次去sdwc就想写游记,不过想写的时候就太晚了qwq,所以这次早点开始吧qwq
_day0_
这次还是让家长送来了qwq,反正又是窝一个人……这次比较皮,就没合租qwq。早早从家里走,到济南报到后一点左右,然后逛了几家酒店,最后还沾了点早来的光233333,然后放下窝家长就走了,留我一个人在宿舍里颓,然后窝第一次知道自己还能在床上待辣么长时间来调网站23333,给这个博客上了把小锁23333
之后想找个背景插件实现换背景,结果都不好用,最后放弃了,一看晚上10点了,洗涮完就睡觉了qwq
_day1_
因为7点上课,所以6点就溜起来了,吃完早饭到教室发现里面摆满了零食,好像是因为清北老师担心考5个小时会饿?总之还挺好的2333333333,坐了一会,看到试题已经发下来了,于是开始敲题,结果打开题一看傻眼了
t1求什么奇奇怪怪的树上点之间的异或和?看数据范围好像是点分治加上什么别的东西去维护……maya写不动写不动,点分治好长时间前写的了qwq,一个暴力走人
t2拆分整数,然后答案是一堆公因数的和,感觉可以转化为某个数作为最大公因数出现了多少次,就可以求出答案了,但是不会统计,暴力溜了
t3是奇奇怪怪的期望,感觉可以先排序,从小到大求,然后前缀和维护前面的期望就好,于是就照着这个打,打完就剩15min了
中午去吃饭的时候碰见了zhw和他的小迷妹(雾)?还拍了找,结果被反过来暗算了qwq,蓝瘦,香菇
下午一看成绩,除了t1估分准确以外其他都emmmm,t2暴力不知道为啥没分,t3就给了10分
t1正解是点分治加奇奇怪怪线段树维护,t2确实也是转化成gcd出现次数,先跑完全背包统计方案总数再跑些奇奇怪怪的东西,t3就是期望dp,只不过窝维护的有点辣鸡而已,但是思想是对的……听完题解贼难受啊,哪个题都戳到点边,但是都不对qwq
讲完题解zhw说自习,晚上讲课?听的窝贼懵逼啊,更奇怪的是qb让我们4点半吃饭!简直有毒啊qwq
晚上zhw各种dp姿势……rqy切题如切菜,于是一晚上就在菜鸡的懵逼和dalao的ac当中度过了
_day2_
依然是zhw的题,day1晚上他说day2的题要比day1难,开始看t1确实吓了一跳,脑子连样例都跑不出来……于是连暴力都没打就去看t2(结果是题面出锅),t2给定n和一个条件,求满足这个条件的1~n方案数,看起来可以打表?但是不知道公式,于是推了一个多小时也没有推出来,结果听别人说了个公式确实可行,但是时间复杂度明显n^2,不过用这个打表可以骗到80分,还是很满足的,毕竟正解肯定不是打表,能拿到这个分数就很吼了223333333,t3n^2暴力能有40,再加上线段树就可以60分到手,60+80=140,满足.jpg。
结果下午来发现打错文件名了……尴尬,t2文件名打成t1了……超气的
t1是什么奇奇怪怪的贪心+数据结构(有点遗忘了)?t2是个近乎裸的分治ntt,可惜窝不会分治的fft/ntt,t3是个强行把两个蛾子的位置和答案压在一起的压位主席树
晚上各种数据结构题,难维护的一批,dalao日常切题,菜鸡日常懵逼qwq
_day3_
今天是钟长者出题&讲课,听说长者出完p120就不干了,不知道是不是真的,长者也大四了……
t1给你一个方程(中间加了个函数),问你方程解的个数,然后感觉是数位dp?但是我不会做,所以一个暴力打上去。
t2一看生成树个数,瞬间想到矩阵树定理,然后感觉凉凉啊……听rqy说好像是07年的noi原题,而且正解也不是矩阵树,但是我依然看不出头绪,幸好还有k=1和k=2这两个特殊值有规律,再加上30%的数据可以爆搜,所以期望50?中途出了点意外……发现爆搜会超时,但是可以把30%的数据先跑好然后打表。
t3只想到25%的数据n^3做法,没想到如何去减少一个n,老老实实打了个暴力
然后……看到成绩……崩溃了……我把输出文件名打错了……感觉内心绝望……垫底了……不是因为程序打次……而是因为文件名打错……为什么自己会犯这种低级错误……整个人心态崩盘……
t1正解是个小脑洞?稍微想想就出来了……我明明离正解只有一步之遥了……t2神一样的插头dp,一脸不可做,t3通过统计出度入度加上优化可以做。听完题解瞬间觉得自己就是个zz
长者讲课的时候谈到今年的n省联考,简单介绍了前两年联考,并鼓励我们说,好好打暴力,二轮基本不成问题。考虑到长者躲闪的语气,看来今年长者也应该参与了联考的命题工作之类的
整个人难受了一个晚上,一边一脸懵逼的看着各种图论神操作神建图,一边回想着今天的考试……感觉整个人都没有希望了,怎么什么智障错误都犯。
回到宿舍,我还是纠结于考试,内心充满了焦急和痛苦……于是逐渐开始思考一个问题,我现在到底是为什么还在学oi,难道仅仅是因为功利吗,不……肯定是因为自己也热爱着oi,功利心肯定是一部分,但不是全部,再说,考试本身也是一种享受,那么我也不应为了一次的挫折而全盘否定自己……想到这里心里舒服了很多,既然如此……就拿出最好的状态去面对下面的考试吧
_day4_
依然是可爱的长者出题,题目名字……依然是辣么清新别致,咕(pk),咕咕(pkp),咕咕咕(ppk)emmmmmmmm
t1感觉线段树可做,但是1000000又太大了,不知道怎么维护,只能写个n^2暴力挂着
t2上来就给你个暴力程序,真6,看起来贼像我之前做的一个数位dp,满心欢喜做了半天,发现这个题目还有模数的限制……弃疗
t3炒鸡幸运,我在sdwc见过这个原题,多跑几遍凸包就求出答案了,于是写了半天凸包,又调了半天,然后考试就结束了
开心的是t3 ac了,凭着t3第一次进前十2333,虽然是吊车尾的emmmmmmm,t1rqy提出了一个非常暴力的做法,而且碾压表算,真是暴力出奇迹,t2通过在dp里面加个模数的限制就可以顺利的转移了,还是数位dp做的少。某群dalao们(特别是某葱和某konoest,装弱重点户啊)为了装弱各种fake……
晚上各路神仙题啊qwq,字符串难度爆棚,套个dp的什么都是开胃菜(按长者的话来说这是基础操作,orz),各路神仙操作6到飞起,最神仙的是利用ac自动机的fail指针建棵树,把问题转化成求fail树上两点的lca,听都没听过。长者说自己已经想用fail树套个树剖之类的好几年了,说今年可能就出出来了qwq,希望n省联考不要出这么毒瘤的题目
_day5_
又是……元气满满的一天?可是窝连着考了这些天,感觉心累到无法肤系了emmmmm
天天规律的生活已经让我觉得实在没啥写的哇qwq,不过生活本就应是平静的吧……要是整天过的和电影似的,那就离出事不远了……有的时候独自一人走在济南的街头,看着逐渐西沉的斜阳,觉得时间如果停在这一刻多好,亦或者是看着熟悉的街景,回想起往日与大家一起来济南学习的日子,于是心里又生出几分惆怅(其实我觉得可能是我看石头门看的23333,现已被圈粉,整体沉迷于石头门的插曲无法自拔),反正都是胡思乱想,还是老老实实扯考试等等的qwq
t1看起来线段树可做,但是我没有想到,想了个奇奇怪怪的bitset分块(受到rqy昨日暴力启发),然后某群某konoset等人就开始奶我,说我t1 ac了,我内心就只剩下:药丸了,来自东方的神秘力量马上就要来了……
t2瞎写计算几何,企图枚举线段,判断两两之间是否相交,始终调不出啊qwq,t3几乎连看都没看,直接输出无解走人
下午来一看,果然原地爆炸,看到各路dalaoak,内心莫名冒出一句:现充都去狗带23333333333,大概是因为自己整日考炸的缘故吧,心理波动也小了很多,这次来qqxt还是有收获的……起码心态摆正了许多
t1是个主席树在线维护……大概是因为我比较傻,忘记了这么有用的算法,t2先算凸包,然后瞎建树跑,t3神仙般的把字符串转化成了图论问题,只有rqy这样的神仙才想到了正解的思路,这个题让我想到那个墨墨的等式啊……
晚上线性代数和概率论还是勉强可以接受的(知识点上)……毕竟没讲什么奇怪的东西,但是习题依然不可做,或许还是我数学底子不行emmmm,难不成还得回文化课让平哥强行填鸭qwq。最大的亮点是hzc小哥哥声音好好听啊qwq,人又帅……大概这次hzc又圈了不少迷妹吧
_day6_
今天又是考试的一天呢……不过终于快回家了qwq
t1一看是个数位dp+矩阵优化,然后就瞎推……一推就是4h……好不容易推了个方程,觉得矩阵几分钟内就能推,于是赶紧去打暴力,t2觉得是组合数瞎搞,t3和昨天的t1很像,但是都写不出来了,而且昨天的t1我也没写……
结果下午来发现自己t2暴力打次了,t1和t3符合预期,早知道就去推矩阵而不是去打t2暴力了,内心mmp,这样还能多20分呢
下午讲题,t1头一次能被讲这么长时间,得占了一半的题解内容,主要是扩展出了指数型生成函数。t2确实是组合数瞎搞,t3就是和昨天差不多emmmmm
晚上计算几何和分治,因为题目讲得少没有炸裂
_day7_
最后一天了……时间真快啊,马上就省选了啊,得好好考了
t1一眼60分了,n^2dp太好想了,但是没怎么仔细想正解,肯定是什么奇奇怪怪的数据结构优化
t2居然考了个炉石为背景的题目,只是……无限的奥术飞弹是什么鬼啊!奥弹这种东西……无力吐槽,反正不稳定,我之前玩法师带着个还让wyh笑话半天。一个奇奇怪怪的期望dp(zzk是多喜欢考dp啊),调了两三个小时,终于把30%只询问一个问题的给调出来了
t3是我人生里第一道题答题啊……结果时间不够,只能简单做几个好算的数据了
下午出成绩,t160,t2爆零,方程是没啥问题,原因是mle,这个悲惨的故事告诉窝……以后dp能滚动就滚动!t3这个题答题还真的有的dalao手玩了半天,最多手玩到600+步……这还是人吗,这是神仙!我就算对了一个……还不如老师的优……窝太菜了……
下午老师的数据疯狂被dalao们吊打&吐槽,老师的数据还不如人家手跑的优233333,spj还被卡成了tle,最6的是老师给t2足足200分,导致测了两边才出成绩233333333,我猜老师大概是脸上笑嘻嘻,心里mmp了23333333333
最后老师简单讲了讲题解,说了下提答和期望。然后……然后就4点了,也到了疏散的时候了emmmmm。大概下次大家再见面,就是你死我活的对手了吧(雾)……
2018.4.1,机房

【codeforces 160D】Edges in MST

这个题……emmmm有个小地方挺难调的
大体思想就是我们按照权值从小到大排序,比较所有权值相同的边,判断他们与最小生成树的关系。我们用并查集维护点所在的联通块,当一个边的两端点均在同一个联通块的时候,说明之前已经有更小的边使这个联通块联通了,那么这个边肯定不在最小生成树上。如果这些新加入的边形成环,则说明他们可以互相替换,可能出现在最小生成树上。如果没有成环,说明不可替代,一定在最小生成树上。

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

using namespace std;

const int s = 100010;

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, tot, cnt, dfn[s], ans[s], head[s], fa[s];

struct es
{
    int f, l, c, pos;
    inline bool operator < (const es &a) const
    {
        return c < a.c;
    }
}ing[s];

struct in
{
    int to, ne, pos;
}ter[s << 1];

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

int find(int x)
{
    return (fa[x] == x) ? x : fa[x] = find(fa[x]);
}

int dfs(int no, int f)//找环,注意这里记录上次走过的边而不是点 
{
    int lowno = dfn[no] = ++ cnt;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(dfn[to] == 0)
        {
            int lowto = dfs(to, i);
            lowno = (lowno > lowto) ? lowto : lowno;
            if(lowto > dfn[no])
                ans[ter[i].pos] = 0;
        }
        else if(dfn[to] < dfn[no] && i != (f ^ 1))
            lowno = (lowno > dfn[to]) ? dfn[to] : lowno;
    }
    return lowno;
}

inline void up(int x, int y)//并查集合并 
{
    x = find(x), y = find(y);
    if(x == y)
        return;
    fa[x] = y;
}

int main()
{
    re(n), re(m);
    for(ri i = 1; i <= m; i ++)
        re(ing[i].f), re(ing[i].l), re(ing[i].c), ing[i].pos = i;
    for(ri i = 1; i <= n; i ++)
        fa[i] = i;
    sort(ing + 1, ing + 1 + m);
    for(ri i = 1; i <= m; i ++)
    {
        ri j = i;
        while(j + 1 <= m && ing[j + 1].c == ing[j].c)
            j ++;
        tot = -1, cnt = 0;
        for(ri k = i; k <= j; k ++)
        {
            ing[k].f = find(ing[k].f), ing[k].l = find(ing[k].l);//我们用并查集合并联通块 
            head[ing[k].f] = head[ing[k].l] = -1, dfn[ing[k].f] = dfn[ing[k].l] = 0;//每次重新建图,之前的联通块已经被压成一个点 
        }
        for(ri k = i; k <= j; k ++)
        {
            int x = ing[k].f, y = ing[k].l, id = ing[k].pos;
            if(x == y)//如果这两个点之前已经合并,那么说明有更小的边使他们联通,这个边就一定不会出现在最小生成树里 
            {
                ans[id] = 2; continue;
            }
            ans[id] = 1, build(x, y, id);//否则就可能出现在最小生成树 
        }
        for(ri k = i; k <= j; k ++)
            if(!dfn[ing[k].f])//搜索,判断这些边是否能成环,如果能成环,说明这些边都是可能被替代的 
                dfs(ing[k].f, -1);
        for(; i <= j; ++ i)//合并 
            up(ing[i].f, ing[i].l);
        i --;
    }
    for(ri i = 1; i <= m; i ++)
    {
        if(ans[i] == 2)
            puts("none");
        else
            puts(ans[i] ? "at least one" : "any");
    }
}

【bzoj1143】祭祀

这个题很容易就可以想到,先判断各个点之间的联通情况,然后把点拆成作为出发点的情况和作为终点的情况,那么枚举每一个点,把所有能从他出发到达的点与他建边,然后二分图最大匹配,完了
洛谷有人在这个基础上又加了两个要求……然而我太菜了,只能解决第一个新加要求emmmmm

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#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 = getchar(); bool b = 0;
    while(a < '0' || a > '9')
    {
        if(a == '-')
            b = 1;
        a = getchar();
    }
    while(a >= '0' && a <= '9')
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x *= -1;
}

int n, m, lx, ly, q[200100], he, ta, de[4200], mmp[500][500], f = -1;

int head[4200], tot = -1, s = 0, t, ret, ans, a1[500], a2[500];

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

inline void build(int f, int l)
{
    ter[++ tot] = (in){l, head[f], 1}, 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) ? 1 : 0;
}

inline int dfs(int d, int fl)
{
    if(d == t)
        return fl;
    for(ri i = head[d]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(f > 0 && (to == f || to == f + n))
            continue;
        if(de[to] == de[d] + 1 && ter[i].co > 0)
        {
            int r = dfs(to, min(fl, ter[i].co));
            if(r > 0)
            {
                ter[i ^ 1].co += r, ter[i].co -= r; return r;
            }
        }
    }
    return 0;
}

inline void init()
{
    memset(head, -1, sizeof(head)), tot = -1;
    for(ri i = 1; i <= n; i ++)
        for(ri j = 1; j <= n; j ++)
            if(mmp[i][j] == 1)
                build(i, j + n);
    for(ri i = 1; i <= n; i ++)
        build(0, i), build(i + n, t);/*然后按照网络流的常规操作,把一个点拆成它作为出发点和作为终点的情况,二分图最大匹配*/ 
}

int main()
{
    re(n), re(m);
    t = (n << 1) + 1;
    for(ri i = 1; i <= m; i ++) 
        re(lx), re(ly), mmp[lx][ly] = 1;
    for(ri i = 1; i <= n; i ++)
        for(ri j = 1; j <= n; j ++)
            for(ri k = 1; k <= n; k ++)
                if(mmp[i][k] + mmp[k][j] == 2)//处理出所有点之间的到达关系 
                    mmp[i][j] = 1;
    init();
    while(bfs())
        while(ret = dfs(0, 1000000007))
            ans += ret; 
    printf("%d\n", n - ans);
}

【洛谷P1447】能量采集

这个题开始我还想用些奇奇怪怪的方法水过去,然后失败了,看了题解发现是一道莫比乌斯反演的题目,以后会用latex以后再填上具体推论过程这个坑吧qwq
这个题我们先这么想,假如横纵坐标互质,那么它一定是一个直线上经过的第一个非原点的点,那么横纵坐标各_2,_3……那么我们就可以得出,一个点对答案的贡献是(gcd(x,y)-1)*2+1
那么也就是说,枚举xy,然后就能计算答案了,但是这样是n^2的,那么我们换个思路求答案,因为枚举gcd是o(n)的,那么我们可以设g[i]表示有g[i]个最大公因数为i,但是我们没法直接求g[i],所以再引入一个函数f[i]表示有f[i]个数公因数为i,那么g[i] = f[i] – f[2 * i] – f[3 * i] – …… – f[k * i](k * i <= min(n, m))(这里其实是莫比乌斯反演的思想)
那么我们根据这个思路做就好,时间复杂度大概在nlogn左右qwq,菜鸡不会证明

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector> 
#include<cmath>
#include<stack>
#include<queue>
#include<map>
#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), t == h)) ? EOF : *h ++;
}

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

lo n, m, mi, dp[100010], ans;

int main()
{
    re(n), re(m);
    mi = (n > m) ? m : n;
    for(ri i = mi; i >= 1; i --)
    {
        dp[i] = (n / i) * (m / i);
        for(ri j = 2; j * i <= mi; j ++)
            dp[i] -= dp[j * i];
        ans += (i + i - 1) * dp[i];
    }
    printf("%lld", ans);
}

【洛谷P2403】所驼门王的宝藏

这个题贼恶心,首先很容易就可以想到缩环跑个dp,但是这个题难点在于,你要怎么建图,才能避免一行全是1这种门或者一列全是2这种情况,防止mle
所以我们将每一行中的1以及每一列当中2按行/列连成一个大环,然后再从这个环上建边即可,至于3,我们开一个二维map然后判断下它四周的点,然后建边即可
不知道为啥,洛谷的评测姬吼像对stl并不友好,我在bzoj上时间空间均无压力,但是到了洛谷各种被卡空间卡时间,最后手写了个栈,开了个真2维map(因为两个维度上都在动态开点),把一堆中间变量全加上register,才算是在洛谷稳定通过

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

using namespace std;

const int mx = 1000000007;

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), t == h)) ? 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 << 3) + (x << 1) + a - '0', a = gch();
    if(b == 1)
        x *= -1;
}

bool flag[100010];

int tail, he[100010], head[100010], sta[100010];

int dfn[100010], scc[100010], v[100010], low[100010];

int n, r, c, ta, cnt, ans, tot = -1, x[100010], y[100010], t[100010];

vector <int> h[1000010], l[1000010];

map <int, map <int, int> > mmp;

int dx[8] = {0, 0, -1, -1, -1, 1, 1, 1}, dy[8] = {1, -1, 0, 1, -1, 0, 1, -1};

struct in
{
    int fr, to, ne;
}ter[1000020], es[1000020];

int dp[100010];

inline void build(ri f, ri l)
{
    if(f == l)
        return;
    ter[++ tot] = (in){f, l, head[f]}, head[f] = tot;
}

void DP(ri no)
{
    flag[no] = 1;
    for(ri i = he[no]; i >= 0; i = es[i].ne)
    {
        ri to = es[i].to;
        if(flag[to] == 0)
            DP(to);
        dp[no] = max(dp[no], dp[to]);
    }
    dp[no] += v[no];
    ans = max(ans, dp[no]);
}


void dfs(ri no)
{
    dfn[no] = low[no] = ++ ta;
    sta[++ tail] = no;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        ri to = ter[i].to;
        if(dfn[to] == 0)
            dfs(to), low[no] = low[no] > low[to] ? low[to] : low[no];
        else if(scc[to] == 0)
            low[no] = low[no] > dfn[to] ? dfn[to] : low[no]; 
    }
    if(dfn[no] == low[no])
    {
        cnt ++;
        while(233)
        {
            ri qaq = sta[tail --];
            scc[qaq] = cnt, v[cnt] ++;
            if(qaq == no)
                break;
        }
    }
}

inline void rebuild(ri f, ri l)
{
    if(f == l)
        return;
    es[++ tot] = (in){f, l, he[f]}, he[f] = tot;
}

int main()
{
    memset(head, -1, sizeof(head));
    re(n), re(r), re(c);
    for(ri i = 1; i <= n; i ++)
        re(x[i]), re(y[i]), re(t[i]), mmp[x[i]][y[i]] = i, h[x[i]].push_back(i), l[y[i]].push_back(i);
    for(ri i = 1; i <= r; i ++)
    {
        int no = 0;
        for(ri j = 0; j < h[i].size(); j ++)
            if(t[h[i][j]] == 1)
            {
                no = h[i][j]; break;
            }
        for(ri j = 0; j < h[i].size(); j ++)
        {
            build(no, h[i][j]);
            if(t[h[i][j]] == 1)
                build(h[i][j], no);
        }
    }
    for(ri i = 1; i <= c; i ++)
    {
        int no = 0;
        for(ri j = 0; j < l[i].size(); j ++)
            if(t[l[i][j]] == 2)
            {
                no = l[i][j]; break;
            }
        for(ri j = 0; j < l[i].size(); j ++)
        {
            build(no, l[i][j]);
            if(t[l[i][j]] == 2)
                build(l[i][j], no);
        }
    }
    for(ri i = 1; i <= n; i ++)
        if(t[i] == 3)
            for(ri lx, ly, j = 0; j < 8; j ++)
            {
                lx = x[i] + dx[j], ly = y[i] + dy[j];
                if(mmp[lx][ly])
                    build(i, mmp[lx][ly]);
            }
    for(ri i = 1; i <= n; i ++)
        if(dfn[i] == 0)
            dfs(i);
    tot = -1;
    memset(he, -1, sizeof(he));
    for(ri i = 1; i <= n; i ++)
        for(ri j = head[i]; j >= 0; j = ter[j].ne)
            if(scc[i] != scc[ter[j].to])
                rebuild(scc[i], scc[ter[j].to]);
    for(ri i = 1; i <= cnt; i ++)
        if(flag[i] == 0)
            DP(i);
    printf("%d", ans);
}

【洛谷P1772】物流运输

这个题开始我在想,一个时间点转移到下一个时间点怎么办,比如我在1这个时间有一条长度为1的最短路,然后2这个时间,最短路就变为3了(之前3这整个路径不通),那么说明需要改变线路,但是改变一次的代价是1000000,还有一个为4的路,但是它一直可以通行,那么答案为4
后来看了题解发现担心是不必要的,我们可以求出一整个时间段的最短路,这样然后设dp[i]为从1~n的最小代价,然后枚举切换路径的时间点就吼了

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

using namespace std;

const int mx = 1000000007;

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), t == h)) ? EOF : *h ++;
}

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

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

int n, m, k, e, d, ta, he, lx, ly, lz, head[30], tot = -1;

int su[22][110], co[110][110], dis[25], q[1000010], dp[110];
/*
设dp[i]表示在1~n这个时间段里的最小花费
然后我们预处理出所有时间段的花费(不改变线路)
所以转移方程为dp[i] = min(dp[i], dp[j] + cost[j + 1][i] + k)
cost不改变线路时一段时间的花费 
*/ 

bool flag[22][110], vis[25];

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], c}, head[l] = tot;
}

inline void spfa(int f, int l)
{
    memset(dis, 63, sizeof(dis)), memset(vis, 0, sizeof(vis));
    ta = he = 0;
    q[he] =  1, dis[1] = 0;
    while(he <= ta)
    {
        int qaq = q[he ++];
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(dis[to] > dis[qaq] + ter[i].co && su[to][l] - su[to][f - 1] == 0)
            {
                dis[to] = dis[qaq] + ter[i].co;
                if(vis[to] == 0)
                    vis[to] = 1, q[++ ta] = to;
            }
        }
        vis[qaq] = 0;
    }
    co[f][l] = dis[m];
    if(co[f][l] < dis[0])
        co[f][l] *= (l - f + 1);
}

int main()
{
    memset(head, -1, sizeof(head));
    re(n), re(m), re(k), re(e);
    for(ri i = 1; i <= e; i ++)
        re(lx), re(ly), re(lz), build(lx, ly, lz);
    re(d);
    for(ri i = 1; i <= d; i ++)
    {
        re(lx), re(ly), re(lz);
        for(ri j = ly; j <= lz; j ++)
            flag[lx][j] = 1;
    }
    for(ri i = 1; i <= m; i ++)//通过求前缀和,判断这个点是否能在一段时间内使用 
        for(ri j = 1; j <= n; j ++)
            su[i][j] = su[i][j - 1] + (int)flag[i][j];
    for(ri i = 1; i <= n; i ++)//预处理所有时间段内的最短路 
        for(ri j = i; j <= n; j ++)
            spfa(i, j);
    for(ri i = 1; i <= n; i ++)
        dp[i] = co[1][i];
    for(ri i = 2; i <= n; i ++)
        for(ri j = 1; j < i; j ++)
            dp[i]= min(dp[i], dp[j] + co[j + 1][i] + k);
    printf("%d", dp[n]);
}