本站现已归档

本站内容的文章主要为早年的算法学习笔记, 日常日记和其它琐碎记录.

查看我的主页和新博客请**点击这里**

一种基于数值的dp遍历方法 Codeforces1475G Strange Beauty|题解

原题: 1475G - Strange Beauty

显然, 读题后我们可以发现: 对于一个beauty array, 将其从小到大排序后, 每一个元素(除第一个)必然能被其前一个元素整除.

将其抽象为图: 对于一条链, 每一个结点(除第一个)都能被其上一个结点整除.

于是, 我们可以轻易得到这样一个树形dp的思路:

新增一个值为1的虚拟点作为根结点, 形成一颗有根树. 将数组a从小到大排序后依次插入树中. 对于一个准备加入树的结点, 其可选择的父结点即树中所有可以将其整除的结点. 对于所有可选择的父结点, 找出距离根结点最远的一个, 将新结点挂载为其子结点.

完成所有插入操作后, 选择从根到叶最长的一条链, 这条链即最后留下的beauty array

这个思路显然是正确的, 但在这道题中行不通. 因为这道题的数据规模是$2\times 10^5$, 而这种做法的最坏复杂度可达到$n^2$

如何处理这个规模的问题? 注意到数据范围中的不寻常之处: 数据大小也为$2\times 10^5$, 而非通常的$10^9$. 这启发我们应当使用一种基于数值的方法进行优化.

注意到, 插入操作是dp中寻找最优子结构的过程. dp的另一种做法是根据子结构更新”父结构”, 也即:

将”对于一个新结点, 寻找可将新结点整除的父结点” 改为”对于已在树上的一个结点, 寻找能被其整除, 挂载到其下的子结点”

这个过程即, 遍历该结点的所有倍数. 类似于埃氏筛, 这个过程的复杂度是$N/1+N/2+…+N/N$, 约为$NlogN$, 满足本题的需求.

于是, 我们得到了官方题解所使用的方法:

Let’s calculate for each number $x$ how many times it occurs in the array $a$. Let’s denote this number as $cnt[x]$.

Let’s use the dynamic programming method. Let $dp(x)$ be equal to the maximum number of numbers not greater than $x$ such that for each pair of them one of the conditions above is satisfied. More formally, if $dp(x)=k$, then there exists numbers $b_1,b_2,…,b_k (b_i\leq x)$ from the array $a$ such that for all $1 \leq i, j \leq k$ one of the conditions above is satisfied.

Then to calculate $dp(x)$ you can use the following formula:

$dp(x) = cnt(x) + \max \limits_{y = 1,\ x\ mod\ y = 0}^{x-1} dp(y)$

Note that to calculate $dp(x)$ you need to go through the list of divisors of $x$. For this, we use the sieve of Eratosthenes.

一种基于该方法的实现:

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#define LL long long
using namespace std;
LL T;
LL n, arr[300000], cnt[300000], dp[300000];
int main (){
    cin >> T;
    while (T--){
        scanf("%lld", &n);
        for (LL i = 1; i <= 200000; ++ i)
            cnt[i] = 0;
        for (LL i = 1; i <= n; ++ i){
            scanf("%lld", &arr[i]);
            cnt[arr[i]] ++;
        }
        for (LL i = 1; i <= 200000; ++ i)
            dp[i] = cnt[i];
        sort(arr + 1, arr + 1 + n);
        LL m = unique(arr + 1, arr + 1 + n) - arr - 1;
        for (LL k = 1;k <= m; ++ k){
            LL i = arr[k];
            for (LL j = i * 2; j <= 200000; j += i){
                dp[j] = max(dp[j], dp[i] + cnt[j]);
            }
        }
        printf("%lld\n", n - *max_element(dp + 1, dp + 200001));
    }
    return 0;
}

恋旧事

“那时，荔枝林后边的小水沟边闪现了两条银光…只浮游在空中，一晃一晃…待那对情侣定睛一看，却是…”

“”“却是？？”“”

“是阿哲校服上的反光带！”

朋友们编造着全新的校园传说，笑闹在一片。我也跟着一起，只是略有收敛。因为我还知道另一个校园传说。

那是不知多久之前的某届，一个女高中生。高考后那一夜，她哭得涕泪俱下。

“我不想毕业！我还想留在高中！永远永远！我不想要分别…”

临别校园的那个晚上，她许下了这样的愿望。

糟糕的是，这个愿望实现了。

不知是遭遇了什么意外，少女没有活着上了大学。她成了校园里的地缚灵，看着学弟学妹们，一届又一届。

「所以，值得吗？永远留在学校，和糟糕的校服和五三之类的东西作伴？我问她。

『那时还不这么糟糕。她把弄着自己一头长发，思绪游离地说着。至少那时候没有这样的校服。

「但你所爱的也非这些。你的同学和朋友，他们都不在这个学校了。和那些人日夜相处的日子，和他们一起生活的日子，已经走了。

『有的没走。她说。像是老师们，像是宿管养的大黄。还有走不了的，这座荔枝林就不会走，我们文学社也不会走。这里的高中生永远十八岁，不会变老。我喜欢这些，很喜欢很喜欢。

「总归还是会寂寞的吧？即使它们是你所爱，但你在这里已经很久了。

少女低下眉眼，用力地纠扯着自己的头发，很是凌乱。她脸上确实有些落寞。

『好吧，我承认…谢谢你陪我说这么多话。

那是我第一次见到她的时候了。

“不要走~嘛！你走了的话…就又没人陪我了！”少女梨花带雨。不，我当初认识的幽灵学姐不是这样的啊…

现在已经是据高考仅剩一个月的时候了，距离我认识这位幽灵学姐也已经半年过去了。虽说第一次见面时是个优雅的黑长直学姐，其实熟络之后彼此都不是严肃的人。

“我也不能一直留在学校啊。”我无奈地说。“说起来今年高考已经延期一个月了。”

“你走了我又超~孤单的了！”

所以说你不要当地缚灵啊。

“明明荔枝林里天天有一对又一对的小情侣…”

说起来地缚灵怎么离开学校啊？

“好羡慕啊好羡慕啊！我以前也有过男朋友…”

近一点说，我是怎么发现这个幽灵学姐的啊…

“人家现在都已经结婚了也说不定，而我…”

‘听我说！忘了这座学校吧！’

“咦？”

‘忘了学校，你应该就能离开这里了。’

“真的吗？不，你为什么这么肯定啊…”

虽然有点心虚，但我还是故作自信地说，’直觉。我就是靠直觉找到你的啊。’

”找到我…这么说来你为什么能找到我啊，明明是个幽灵…“

糟糕！她在往很不妙的方向思考！

“地缚灵…什么嘛！其实你也很留念学校吧！见到我的那天晚上，其实也在想不要毕业对吧！”

‘…才不是！’

“不然，你怎么会见到身为地缚灵的我呢？嘴上说着学校不好不好，其实也不是不喜欢嘛。”

‘…你哪有资格说我啦！明明自己成了地缚灵，现在却又哭着想要走…

秋。今天是我的大学生涯第一天。

那天之后，我就再也没碰见她了。大概成功离开学校了吧。

石桌上刻下一行字

“某年月日 再见 我的母校

相逢只有一刻 离别则是永恒”

她走的时候还是很不舍吧。

其实挺想知道她现在如何，不过既然是幽灵的话，应该是升天了吧？

“hello！好久不见啦学弟！”

…这样的话我刚刚的怀念情绪会非常难为情诶！

学姐的长发比之前更长了，她穿着清凉的秋装…而且身体毫无虚幻之感，无疑是活生生的人类。

『那之后我从医院里醒来的，据说当时已经治好了外伤，但一直都昏迷不醒…

『大学的话因为办的是因病休学的手续，学籍还是好好保留着，所以现在可以以大一新生的身份入学…

『学校已经不太能想起来了，不过现在看来也不算太糟糕…

『怎么和你在同一所大学？不不，好好想想，是你问的我怎么报志愿哦…

「其实我一直很想问的…你现在几岁了啊？如果前男友都结婚了的话…

『…十八岁哦！因为幽灵不会生长所以就是十八岁！！

「我想问的是户籍上…

『十八岁！！！

…

本文采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可

void Tarjan(int u){
    //...
    if (dfn[v]){
        low[u] = min(low[u], dfn[v]);
    }
    else{
        Tarjan(v);
        low[u] = min(low[u], low[v]);
    }
    //...
}

前两天, 学弟hjk问了我这么一个问题:为什么在Tarjan中第4行代码不能写成这样

low[u] = min(low[u], low[v]);

看着他求知的面庞, 我不禁想起了曾经young的自己, 同样向自己提出过这个问题..

于是我打算写篇文章来讲讲这个

这个问题并不奇怪. 因为在缩点板子题中, 显然点$u$和$low[u]$和$low[low[u]]$祖孙三代所表示的三个点最后会合并成同一个点, 那为什么不直接把$u$的$low$值设定成最远的祖父呢?

于是我尝试把这样修改的代码交上去, 很顺利, 它a过了. 但是我把它交到了割点板子题上, 它就wa得很惨.

所以这是怎么回事？为什么这种写法可以过缩点不能过割点？缩点和割点有什么区别？

点双和边双的区别

我copy一下有关点双连通分量和边双连通分量的定义

点连通度

一张图的点连通度的大小等于最小点割集的大小。

边连通度

一张图的边连通度的大小等于最小边割集的大小。

点双连通分量

点连通度大于等于$2$的分量

边双连通分量

边连通度大于等于$2$的分量

换句话说:

点双上任意删去一个点 剩下的图形依然连通.

边双上任意删去一个边 剩下的图形依然连通.

再看看缩点问题: 它实质上就是求边双. 一个边双可以缩成一个点, 缩完点之后的图形中每一条边都是割边.

于是要研究缩点和割点的区别, 就是研究点双和边双的区别. 当燃啦, 从定义上看两者就不一样.

那我能不能整个图形 它是个边双而不是点双？

这个图形不难构造, 它长这个样子

嗯 这个图中${1,2,3,4}$和${4,5,6,7}$这两个分量, 它们就是个普通的环, 所以既是点双, 又是边双.

如果两个分量由一个点$5$连接, 通过这个点 ${1,2,3,4,5,6,7}$连接成了一个大的边双, 但是它并不是个点双, 因为这个连接点$5$本身就成了那个割点.

更普通地说, 如果两个边双之间有至少一个点连接两者, 那么就可以合并成一个大的边双; 如果两个点双之间有至少两个点连接两者, 那么就可一合并成一个大的点双. 但如果有且只有一个点连接两个点双, 情况就会变成: 两者形成了一个大的边双, 但这个边双并不是点双.

我不清楚这个图有没有名字, 总之我管它叫糖葫芦图

啊放错图了. 应该是这个

言归正传

为什么用$low[v]$更新$low[u]$的写法能过缩点不能过割点? 还是看这张图

设$1$是出发点

如果依照$dfn[v]$来更新$low[u]$, 那么这张图跑一遍Tarjan会得到$low[4]=1,low[7]=dfn[4]$, 也就是说该算法会得到”$1$和$4$在一个连通分量中, $4$和$7$在一个连通分量中”. 不论我们所求是边双还是点双, 这种说法都是没错的.

但如果如果依照$low[v]$来更新$low[u]$, 那么这张图跑一遍Tarjan会得到$low[7]=low[4]=1$, 也就是说该算法会得到”$1$和$4$和$7$在一个连通分量中”, 但事实上它们三个在同一个边双中, 却不是在同一个点双中, 所以求缩点时这种算法是正确的, 求割点时就是错误的.

综上所述, 之所以这种写法在割点问题和缩点问题中的表现不同, 原因就在于点双和边双的传递性不同.

文结于CSP-J/S2019day1.

NOIP2017d1t3逛公园题解

策策同学特别喜欢逛公园。公园可以看成一张N个点M条边构成的有向图，且没有 自环和重边。其中1号点是公园的入口，N号点是公园的出口，每条边有一个非负权值， 代表策策经过这条边所要花的时间。

策策每天都会去逛公园，他总是从1号点进去，从N号点出来。

策策喜欢新鲜的事物，它不希望有两天逛公园的路线完全一样，同时策策还是一个 特别热爱学习的好孩子，它不希望每天在逛公园这件事上花费太多的时间。如果1号点 到N号点的最短路长为d，那么策策只会喜欢长度不超过d + K的路线。

策策同学想知道总共有多少条满足条件的路线，你能帮帮它吗？

为避免输出过大，答案对P取模。

如果有无穷多条合法的路线，请输出-1。

AFO时长一年后难得又写了一道题.

这个题看起来有些复杂. 我们不妨先考虑弱些的情况

保证公园的地图是一张DAG

这个情形就很显然是个树形dp. 不难设计出状态转移方程

设$dis[u]$是”从$u$到终点的最短路”, $moew(u,hp)$表示”策策处在$u$点, 体力为$dis[u]+hp$时, 恰好耗尽体力走到终点的方案数”, 容易得到转移方程:
$$
meow(u,hp)=\sum_{v} meow(v,dis[u]+hp-edge[u\ to\ v].length-dis[v])
$$
其中$v$是所有$u$可以直接连向的点

由于$0\leq hp\leq k\leq$, 故复杂度为$O(n\times hp)$

地图中存在环, 但保证不存在零环

这个时候上述转移方程还是否适用呢?

笔者在这里陷入了一个误区: 如果存在环的话, 策策就可以多次走到同一个点. 这样一个点就会被多次处理, 看起来不具备无后效性啊

请注意: **我们所设计的状态不是 “策策处在$u$点” , 而是 “体力为$dis[u]+hp$的策策处在$u$点” **

如果不存在零环的话, 策策虽然可以多次走到$u$点, 但是每次走到$u$点时的$hp$是一定不同的. 永远只有一个“处在$u$点的体力为$dis[u]+hp$的策策”.

也就是说$meow(u,hp)$的值一定只会被计算一次, 满足无后效性. 上述方程仍然成立. 时间复杂度依然为$O(n\times hp)$

(AFO久了脑子就不太好使了.)

地图中存在零环

顺着上面的思路, 没有零环时每次走到$u$点时的$hp$是一定不同的. 那么也就是说”有零环时会有两次走到$u$点时$hp$是相同的”. 通过这个性质就可以轻松地判断$u$点上是否在一个零环上.

值得注意的特殊情况:

$meow(终点,0)=1$是dp的边界条件, 那么使用上述的判零环方法会忽略”终点在一个零环上”的情况. 因为这种情况发生时$moew(终点,0)=+\infty$, dp的边界条件被破坏了.

特判”终点在一个零环上”的情况也不难. 只要在做dijkstra的过程中发现有一条指向终点的长度为$0$的最短路, 那么这条最短路就是终点上的零环.

(实话说这个情况要不是样例有我就真的忽略了)

总之代码如下

#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL n, m, k, p, T;
//gragh beg
struct edge{
    LL v, cs;
    edge *nxt;
    edge (const LL &be, const LL &ge, edge *de){
        v = be, cs = ge, nxt = de;
        return ;
    }
}*G[200000], *G_[200000];
void del_g(edge **g, LL n){
    for (LL i = 1;i <= n;++ i){
        for (edge *j = g[i], *k;j;k = j, j = j->nxt, delete(k));
        g[i] = NULL;
    }
    return ;
}
//gragh end
//dijkstra beg
LL dis[200000];
bool vis[200000], zero_1;
struct qwq{
    LL v, dis;
    bool operator < (const qwq &al)const{
        return dis > al.dis;
    }
};
void dijkstra(LL s){
    priority_queue<qwq> q;
    q.push((qwq){1, 0});
    while(q.size()){
        qwq al = q.top();
        q.pop();
        if (vis[al.v])
            continue;
        dis[al.v] = al.dis;
        vis[al.v] = 1;
        for (edge *i = G[al.v]; i; i = i->nxt){
            if (vis[i->v]){
                if (i->v == 1 && dis[al.v] + i->cs == 0){
                    //node1 on a zero circle
                    zero_1 = 1;
                    return ;
                }
                continue;
            }
            q.push((qwq){i->v, al.dis + i->cs});
        }
    }
    return ;
}
//dijkstra end
//dp
LL dp[100010][60];
bool sta[100010][60];
LL meow(LL u, LL hp){
    if (sta[u][hp])
    //a zero circle on this road
        return -1;
    if (dp[u][hp] != -1)
        return dp[u][hp];
    sta[u][hp] = 1;
    LL al = 0, hp_;
    for (edge *i = G_[u];i;i = i->nxt){
        hp_ = hp + dis[u] - i->cs - dis[i->v];
        if (hp_ < 0 || hp_ > k)
            continue;
        LL tmp = meow(i->v, hp_);
        if (tmp == -1)
            return -1;
        al = (al + tmp) % p;
    }
    sta[u][hp] = 0;
    return dp[u][hp] = al;
}
//dp end
int main (){
    cin >> T;
    while (T--){
        //initialization
        memset(dis, 0, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        memset(dp, -1, sizeof(dp));
        memset(sta, 0, sizeof(sta));
        zero_1 = 0;
        LL al, be, ge;
        scanf("%lld%lld%lld%lld", &n, &m, &k, &p);
        for (LL i = 1;i <= m;++ i){
            scanf("%lld%lld%lld", &al, &be, &ge);
            G[al] = new edge(be, ge, G[al]);
            G_[be] = new edge(al, ge, G_[be]);
        }
        //main
        LL ans = 0;
        dijkstra(1);
        if (zero_1){
            ans = -1;
        }
        else{
            dp[1][0] = 1;
            for (LL i = 0;i <= k;++ i){
                LL tmp = meow(n, i);
                if (tmp == -1){
                    ans = -1;
                    break;
                }
                ans = (ans + tmp) % p;
            }
        }
        printf("%lld\n", ans);
        //initialization
        del_g(G, n);del_g(G_, n);
    }
    return 0;
}

文结.