周末训练9.5

拓补排序:https://blog.csdn.net/qq_41713256/article/details/80805338

链式前向星:https://blog.csdn.net/sugarbliss/article/details/86495945

邻接表单向链表->传送门

邻接表:(vector)


1
2
3
4
5
6
7
8
vector<int> G[N];

int u,v;
scanf("%d%d",&u,&v);
G[u].push_back();

for(int i=0;i<G[p].size();i++)
{ int y=G[p][i]; }

快速幂:(模板)


1
2
3
4
5
6
7
8
9
10
11
ll ksm(ll a,ll b)
{
    ll x=1,s=a;
    while(b)
    {
        if(b%2==1) x=(x*s)%m;
        s=(s*s)%m;
        b/=2;
    }
    return x;
}

拓补排序:(有向无环图)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//↓T:旅行计划
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,INF=1e9;
int n,m;
vector<int> G[N];//邻接表
int rd[N];
queue<int> q;
int ans[N];
int main()
{
//  freopen("plan.in","r",stdin);
//  freopen("plan.out","w",stdout);
   
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);//邻接表
        rd[v]++;//记录入度
    }
    for(int i=1;i<=n;i++) if(rd[i]==0) q.push(i),ans[i]=1;//入度为0的入队
    while(!q.empty())
    {
        int p=q.front();q.pop();
        for(int i=0;i<G[p].size();i++)
        {
            int y=G[p][i];//找下一个点
            ans[y]=max(ans[y],ans[p]+1);//DP
            rd[y]--;//入度减一
            if(rd[y]==0) q.push(y);//如果入度为0就入队
        }
    }
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
   
    return 0;
}

 

比赛:

1.排序问题

题解:过两遍sort,注意mod后的赋值

2.阶乘取模

题解:快速幂

3.旅行计划

题解:拓补排序,注意每个点的初值为为1

4.城市重建

题解:邻接表Dijkstra(只能80分)

长乐7.15集训

又是艰难的一天,生活不易,淇淇叹气

 


1.并查集:https://www.bilibili.com/video/BV13t411v7Fs?from=search&seid=18163582992417912843

模板:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;

const int N=10005;

int n,m;
int fa[N];

void Init()
{
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
    }
}

int Find(int x)
{
    if(fa[x]!=x) return fa[x]=Find(fa[x]);
    return fa[x];
}

void Merge(int x,int y)
{
    int x_root=Find(x);
    int y_root=Find(y);
    if(x_root!=y_root)
        fa[x_root]=y_root;
}

int main()
{
    cin>>n>>m;
    Init();
    for(int i=1;i<=m;i++)
    {
        int z,x,y;
        cin>>z>>x>>y;
        if(z==1) Merge(x,y);
        if(z==2)
        {
            if(Find(x)==Find(y)) cout<<"Y"<<endl;
            else cout<<"N"<<endl;
        }
    }

    return 0;
}

 


2.最小生成树:https://www.bilibili.com/video/BV1Eb41177d1?from=search&seid=12623132578193160421

模板:

Prim:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;

const int N=1005;
const int INF=1e9;

int n,m;
int f[N][N];
int dis[N];
int vst[N];
int ans;

void Init()
{
    for(int i=1;i<=n;i++)
    {
        dis[i]=INF;
        for(int j=1;j<=n;j++)
        {
            if(i!=j) f[i][j]=INF;
        }
    }
}

void Prim(int x)
{
    ans=0;
    int minn,k;
    dis[x]=0;
    for(int i=1;i<=n;i++)
    {
        minn=INF;
        for(int j=1;j<=n;j++)
        {
            if(vst[j]==0 && minn>dis[j])
            {
                minn=dis[j];
                k=j;
            }
        }
        ans+=dis[k];
        vst[k]=1;
        for(int j=1;j<=n;j++)
        {
            if(vst[j]==0 && dis[j]>f[k][j])
            {
                dis[j]=f[k][j];
            }
        }
    }
}

int main()
{
    cin>>n>>m;
    Init();
    for(int i=1;i<=m;i++)
    {
        int u,v,c;
        cin>>u>>v>>c;
        f[u][v]=f[v][u]=c;
    }
    Prim(1);
    cout<<ans;

    return 0;
}

 

Kruskal :


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;

const int N=10005;

int n,m;
int fa[N];
int ans;

struct node
{
    int u;
    int v;
    int w;
}e[N*2];

bool cmp(node x,node y)
{
    return x.w<y.w;
}

int Find_root(int x)
{
    if(fa[x]!=x) return fa[x]=Find_root(fa[x]);
    return fa[x];
}

bool Merge(int x,int y)
{
    int x_root=Find_root(x);
    int y_root=Find_root(y);
    if(x_root!=y_root)//判断 且 合并集合
    {
        fa[x_root]=y_root;
        return 1;
    }
    return 0;
}

void Kruskal()
{
    ans=0;
    int k=0;
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        if(Merge(e[i].u,e[i].v))
        {
            ans+=e[i].w;
            k++;
        }
        if(k==n-1) break;
    }
    if(k==n-1) cout<<ans;
    else cout<<-1;
   
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>e[i].u>>e[i].v>>e[i].w;
    }
    sort(e+1,e+m+1,cmp);
    Kruskal();

    return 0;
}

 


3.繁忙城市:http://noip.ybtoj.com.cn/contest/32/problem/1

题解:纯Prim或纯Kruskal都可

 


4.新的开始:http://noip.ybtoj.com.cn/contest/32/problem/2

题解:设置虚拟节点(即0号节点)为超级电源,在矿井上建立发电站相当于让它与0号节点连边。

 


5.公路建设:http://noip.ybtoj.com.cn/contest/32/problem/3

题解:貌似写Kruskal会好一点,可是我写的Prim,样例过了,ojwa,不想改了

 


6.连接云朵:http://noip.ybtoj.com.cn/contest/33/problem/1

题解:用Kruskal,当子集等于k的时候就是最小值了

 


The end.

【纪中】Day10+

【C】
题意:求无向图中两点之间的路径数。
水题。由于每个点只在一个简单环上,所以缩点以后图就变成一颗树了,而只要进过一个环,就有两条路。
于是用tarjin缩点再跑lca即可。缩点也可以用dfs,写完tarjin结果忘了无向图怎么处理,只好改dfs。。。
【棋盘游戏】
题意:从一个点走到(0,0),一步可往左、下、左下三个方向走任意步,询问先手的输赢情况。
明显的博弈论,正解是威佐夫博弈,公式很简单:
记w=(int)[((sqrt(5)+1)/2)*z ];
若w=x,则先手必败,否则先手必胜。
来讲讲部分分的做法。
30%:显然,若起点为(0,0)则先手必输,那么,从(0,0)右、上、右上的点便是先手必胜。接着,从(0,0)开始一层一层地找,若没有被标记过先手必胜,则就是先手必败。
60%:既然可以从上述方法得知输赢情况,那么,可以发现先手必败的情况特别少,打表发现,每一个必败点(x, y),(x - 1)(y - 2)、(x - 2)(y - 3)其中一个一定是必败点,可以找规律求解(反正我没找到)。
【偷窃】
题意:在一堆正方体中拿走最多的数量,并且使其三视图不改变。
正解是二分图匹配,对于行和列的最高点建边,再分别连向源点和汇点,流量是其最大值的数值,跑网络流求最大匹配。
但是,水水就能过去的题为什么要打网络流。要使三视图不改变,只要最高的不少,其余的全搬走只剩一个即可。那么,对于列上的最大值,去找行上有没有与其想等的,如果有,在一个位置就可满足行列的要求,如果没有,就随便找一个比它大的放。
代码如下:
继续阅读【纪中】Day10+

Day11

【虚】
题意:从数轴的原点开始,有1/4的概率往左或往右走,有1/2的概率被-1s(站在原地不动)。询问t时到p点的概率。
把一个点拆成两个点,则题目可化成有1/2的概率往左或往右走,询问2t时到2p点的概率。可用排列组合求解。
【传送】
题意:一张n*m的图,从(1,1)开始,可以往左或往下走,在一些点有传送门,可以传送到另一个点,询问最大收益。
tarjin缩点+spfa即可。(为什么说的那么简单?因为我还没写出来)。
【串】
题意:n次操作,有p的概率出现1,否则为0。每个长度为x的1可以获得x^3的分数,求答案的期望。
假设在i之前已经出现了x个1,那么如果新加入的是1,对答案的贡献是(x + 1)^3 - x^3, 化简得3x^2 + 3x + 1。
所以,现在只需要维护x^2、x的期望即可。
x的期望:x1[i] = (x1[i - 1] + 1) * x
x^2的期望:x2[i] = (x2[i - 1] + 2 * x1[i - 1] + 1) * x
答案期望:sum += (3 * x2[i - 1] + 3 * x1[i - 1] + 1) * x

7月21日备战Noip2017暑假集训6(A) 接力【最短路,优先队列(存疑)】

接力

【问题描述】

接力共有n名队员(编号1-n)参加,在同一时刻赛道上允许有任意多名选手同时赛跑。比赛开始前,所有交警在起跑线等待起跑。

在t=0时刻,编号为1的选手开始赛跑,L1秒后跑完一圈回到起点。当选手i跑完一圈他会示意Mi名选手开始接力。(选手可能被多次示意,只算最早的示意)每个选手只跑一圈。

接力的总时间为最后一个选手结束赛跑的时间。求接力的总时间。

【输入格式】

第一行一个单独的整数n,表示有n名选手。

接下来n行,每行开始有2个整数Li,Mi,接下来有Mi个整数,表示示意选手的编号。

【输出格式】

一行一个整数,表示接力的总时间。

【输入样例】

5

4 2 2 4

3 3 1 3 4

7 1 5

4 2 3 5

1 0

【输出样例】

14

数据范围与约定

对于30%的数据:n <= 10。

对于60%的数据:n <= 300。

对于100%的数据:n <= 1000。

继续阅读7月21日备战Noip2017暑假集训6(A) 接力【最短路,优先队列(存疑)】

7月21日备战Noip2017暑假集训6(A) 单词 【拓扑排序】

单词

【问题描述】

在一种未知语言中,很多单词被发现了,但是他们的字母的字典序我们是不知道的。我们知道的是,这些单词是按照字典序从小到大排列的。

或者找出这种语言唯一的字母的字典序,或者得出这种方案是不存在的,或者得出有很多种这样的方案。

【输入格式】

第一行包括一个正整数n(1 <= n <= 100),表明单词的数量。

接下来n行,每行一个单词,每个单词最多包含10个小写的英文字母。保证单词以未知语言的字典序给出。

【输出格式】

有且仅有一行,输出包含所有字母的字典序。如果没有这种字典序,则输出“!”,如果有多种方案则输出“?”。

【输入样例1

5

ula

uka

klua

kula

al

【输出样例1

luka

【输入样例2

4

jaja

baba

baja

beba

【输出样例2

【输入样例3

3

marko

darko

zarko

【输出样例3

数据范围与约定

对于30%的数据:n <= 20。

对于100%的数据:n <= 100。

继续阅读7月21日备战Noip2017暑假集训6(A) 单词 【拓扑排序】

Day5

【匹配】
简单的模拟题,这里略过。

【矩形】
题意:给出n条直线,求组成的矩形个数。
60%的做法,先枚举两条平行的直线,再枚举垂直于前两条直线且有交点的线,用排列组合求出答案。这个做法是O(n^3)。
由数据范围可知O(n^3)的时间复杂度刚好超时,考虑优化上面的算法,用bitset记录每两条直线是否相交,那么,求垂直于两条直线且相交就变成了求两条直线bitset的和(&)。由于直线分为两种,垂直于x轴与平行于x轴,可以枚举直线少的来进行&操作。时间复杂的为O(n^3/128)。
正解为树状数组(线段树)来维护两条平行直线间共有的相交直线数。时间复杂度O(n^2longn)。

【历史】
题意:每次连一条边,询问两个点是否在t之前不联通,在当前时刻联通,强制在线。
由于强制在线的是连接的边,对于询问并没有要求强制在线,那么,先将询问存下来,对于t之前的状态可在t时记录,t的状态可直接得到。
正解是可持久化并查集, 用可持久化线段树维护可持久化数组,由于修改的只能是一个数,所以合并并查集时不能用路径压缩,需要用启发式合并,那么,对于每个询问只需查找当前数组和前t的数组即可。

代码如下(可持久化并查集代码明天补充)

继续阅读Day5

Day1:A+组

【元素】
题意:将n个整数分组,使组数最少且元素最多的组的元素个数尽量少。
数据范围给出提示,n<=15,符合这个范围的算法有深搜、状压DP。这里考虑深搜,枚举组数N,对于每一个数枚举其所在的组。时间复杂度为O(刚好能过)。
状压DP时间复杂度较为严谨,为O(2 ^ n * n ^ 2)。 令f[i]为状态i时最少需要的组数,对于两个状态opt、nav。若能合并,则f[opt ^ nav] = min(f[opt], f[nav])。若不能合并,则需讨论。

【反击】
题意:在n个数中找出最多满足条件的完美对数。
n <= 1000,可以暴力判断每两个数是否能符合条件,由于不能重复选取,联想到二分图。二分图求最大匹配方法有许多,这里使用网络流求二分图。将每个点拆成两点,每个点与另一边能与自己匹配的点连一条流量上限为1的边。源点s与一半的点连边,流量上限为正无穷。汇点t与另一半的点连边,流量上限为正无穷。
时间复杂度为O(nlogn).

【最小】
题意:将n点m边图中的点分为白点和黑点。 删除一些边,使剩下的边代价尽量小,且白点与最近的黑点仍按原先的最短路连接。
答案要求按最短路连接,于是先删除不在最短路上的边,再求最小生成树。最短路用spfa求解,由于有多个源点,先将所有黑点入队再求最短路。删边后只需满足白点与黑点由最短路连接,因此可能出现删边后成为森林的现象,在求最小生成树是将所有黑点先行合并。

主要代码如下

继续阅读Day1:A+组

POJ 3169 Layout(差分约束)

题目:传送门

题目大意:

当排队等候喂食时,奶牛喜欢和它们的朋友站得靠近些。FJ有N(2<=N<=1000)头奶牛,编号从1到N,沿一条直线站着等候喂

食。奶牛排在队伍中的顺序和它们的编号是相同的。因为奶牛相当苗条,所以可能有两头或者更多奶牛站在同一位置上。即使说,

如果我们想象奶牛是站在一条数轴上的话,允许有两头或更多奶牛拥有相同的横坐标。

一些奶牛相互间存有好感,它们希望两者之间的距离不超过一个给定的数L。另一方面,一些奶牛相互间非常反感,它们希望两者间

的距离不小于一个给定的数D。给出ML条关于两头奶牛间有好感的描述,再给出MD条关于两头奶牛间存有反感的描述。

(1<=ML,MD<=10000,1<=L,D<=1000000)

你的工作是:如果不存在满足要求的方案,输出-1;如果1号奶牛和N号奶牛间的距离可以任意大,输出-2;否则,计算出在满足所有要求的情况下,1号奶牛和N号奶牛间可能的最大距离。

 

刚开始看一脸懵逼😐,上网搜了题解发现是差分约束(不要问我为什么一直搜题解,题目好难)发现这东西大概是一些特定的不等式组

继续阅读POJ 3169 Layout(差分约束)

网络流/费用流

【流模型】
如同我们可以把一个实际的道路地图抽象成一个有向图来计算两点之间的最短路径,我们也可以将一个有向图看作一个网流络来解决另一类型的问题。网络流比较适合用来模拟液体流经管道、 电流在电路网络中的运动、 信息网络中信息的传递等等类似的过程。
我们可以将网络流类比成水流, 如下图给出一个有向图 G =(V, E).图中的边可以想象成管道, 顶点则是管道的连接点。 边上的权值我们称之为这条边的流量上限, 可以把它想象成这条管道能通过的水流的多少。 对于图中每条边e我们记它的流量上限为 c(e) .

【最大流模型】
对于有源点s和汇点t的图,则称为网络流图。在这样的图中,源点入度为 0 且可以产生无穷大的流量,汇点出度为 0 且可以吸
收无穷大的流量。
称一条从源点到汇点的,并使除源汇之外所有结点满足流量平衡,所有边满足流量约束的流方案为有源汇网络的可行流。(这里的流方案并不一定只沿一条路流,也可能在多个结点上出现支路,但要保证满足流量约束与流量平衡条件。)
最大的可行流方案为最大流。求解最大流的问题称为最大流问题。

【求解最大流/Dinic算法】
Dinic 算法的主要思想就是每次寻找最短的增广路,并沿着它增广。因为最短增广路的长度在增广过程中始终不会变短,所以无需每次都通过广搜来寻找最短增广路。我们可以先进行一次广搜,然后考虑由近距离顶点指向远距离顶点的边所组成的分层图,在上面进行深搜寻找最短增广路(这里一次深搜就可以完成多次增广的工作)。每增广一条边,就要在其反向边上加上流入的流量,在这条边上减去流入的流量,这样,在找到一条更优的增广路后,便可以直接从反向边进行修改。
如果在分层图上找不到新的增广路了(此时我们得到了分层图所对应的阻塞流),则说明最短增广路的长度变长了或不存在增广路了,于是重新构造新的分层图。
注: 建边时一般从2开始建,这样便于正、反边的互换,只要(^1)便能得到另一条边。
构建分层图的代码:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
queue<int> q;

int bfs()  {
    int v, now;
    for (int i = s;i <= t; i++) cnt[i] = en[i], dir[i] = -1;
    dir[s] = 0;
    while (!q.empty()) q.pop();
    q.push(s);
    while (!q.empty())  {
        for (int e = en[now = q.front()]; e ; e = next[e])
            if (val[e] > 0 && dir[v = gt[e]] == -1)  {
                dir[v] = dir[now] + 1;
                q.push(v);
                if (v == t) return 1;
            }
        q.pop();
    }
    return 0;
}

Dinic代码:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int Dinic(int u, int flow)  {
    if (u == t) return flow;
    int acc = 0, v, del;
    for (int &e = cnt[u]; e ; e = next[e])  
        if (val[e] > 0 && dir[u] + 1 == dir[v = gt[e]] && dir[v] > 0)  {
            del = Dinic(v, min(val[e], flow - acc));
            if (del)  {
                val[e] -= del;
                val[e ^ 1] += del;
                acc += del;
                if (acc == flow) break;
            }
        }
    if (acc != flow) dir[u] = -1;
    return acc;
}

【费用流】
费用流则是在网络流的基础上给每条边多加了个属性,即单位流量的费用,一般在费用流的可行方案中,要求费用与流量平衡。
注意到,在网络流的求解中,每次都是随便选取一条边来进行增广,费用流中由于边多了一个权值,选边的顺序就需要确定了。显而易见,可以贪心地在残余网络上选最小费用的路径进行增广。多了个权值,在建边时反向边的权值便是负值,所以不能Dijkstra来求最小值,要用队列优化的 Bellman-Ford 算法。
实际上,费用流与网络流的差别也就在选取边的顺序上;


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
queue<int> q;

int spfa()  {
    memset(vis, 0, sizeof vis);
    for (int i = 1;i <= 2 * N; i++) dir[i] = INF;
    int nxt, now;
    dir[s] = 0;
    q.push(s);
    vis[s] = 1;
    while (!q.empty())  {
        vis[now = q.front()] = 0;
        for (int e = beg[now]; e ;e = next[e])
            if (cap[e] > 0 && dir[now] + cost[e] < dir[nxt = gt[e]])  {
                dir[nxt] = dir[now] + cost[e];
                if (!vis[nxt])  {
                    vis[nxt] = 1;
                    q.push(nxt);
                }
            }
            q.pop();
    }
    if (dir[t] < INF) return 1;
    return 0;
}

【网络流题目】(两题代码相同)

【POJ】2186Popular Cows

【QZYZ】1238草地排水

继续阅读网络流/费用流