【纪中】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草地排水

继续阅读网络流/费用流

POJ - 3255 Roadblocks

困扰了两天的次短路问题终于在大佬 @C2013ZDX 的帮助下AC了。激动人心😂

传送门:戳我

题目大意:一张无向图,n个点,r条边,求起点1到终点n的次短路。

 

看到题目的时候就懵逼了,最短路好打,可是次短路是什么东东。

后来看了网上的题解,次短路应该是在一段最短路的基础上再加上一段次短路,证明过程不详讲,只要用spfa或dijkstra在记录最短路的时候顺便更新每个点的次短路即可。

 

早上打了个spfa,有时间可以尝试下dijkstra;

由于是无向图所以可以来回走,刚开始没注意到这么gay的条件导致次短路挂掉。。

 

下为code+手打注释

 


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
74
75
76
77
78
79
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;

const int R=100010;
const int N=5010;

struct dist
{
    int first,second;
    dist()  {
        first = (int)1e9;
        second = (int)1e9;
    }
}dis[N];

int num[2*R],next[2*R],val[2*R],f[N],to[2*R],tot;

queue <int> q;

void adde(int u,int v,int w)    //邻接表
{
    next[++tot]=f[u];
    f[u]=tot;
    to[tot]=v;
    val[tot]=w;
}

void spfa(void)
{
    dis[1].first=0; //1的最短路清零,次短路不能
    q.push(1);
    while (!q.empty())
    {
        int nxt;
        int now=q.front();
        q.pop();
        for (int i=f[now];i;i=next[i])
        {
            int com=dis[now].first+val[i];  //1.起点到now点最短路+到to[i]的距离
            if (com<dis[nxt = to[i]].first)     //更新最短路
            {
                int tem=dis[nxt].first;
                dis[nxt].first=com;
                dis[nxt].second=tem;    //原最短路更新为次短路
                q.push(nxt);
            }
            if (com>dis[nxt].first && com<dis[nxt].second)  //更新次短路
            {
                dis[nxt].second=com;
                q.push(nxt);
            }
            com=dis[now].second+val[i]; //2.起点到now点的次短路加上到to[i]点的距离
            if (com>dis[nxt].first && com<dis[nxt].second)  //更新次短路*2
            {
                dis[nxt].second=com;
                q.push(nxt);
            }
        }
    }
}

int main(void)
{
    int n,m,u,v,w;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        adde(u,v,w);
        adde(v,u,w);    //无向图
    }
    spfa();
    printf("%d\n",dis[n].second);
    return 0;
}

 

看到图论就脸黑,还是太过年轻🤣

 

岂曰无衣,与子同袍。

Y.W.             2017/7/11       东海集训

POJ 1182 / NOI 2001 详解

题目    https://cn.vjudge.net/contest/164366#problem/C

http://poj.org/problem?id=1182

 

题目描述:
动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B, B吃C,C吃A。
现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述:
第一种说法是"1 X Y",表示X和Y是同类。
第二种说法是"2 X Y",表示X吃Y。
此人对N个动物,用上述两种说法,一句接一句地说出K句话,这K句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。
1) 当前的话与前面的某些真的话冲突,就是假话;
2) 当前的话中X或Y比N大,就是假话;
3) 当前的话表示X吃X,就是假话。
你的任务是根据给定的N(1 <= N <= 50,000)和K句话(0 <= K <= 100,000),输出假话的总数。

Input

第一行是两个整数N和K,以一个空格分隔。
以下K行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中D表示说法的种类。
若D=1,则表示X和Y是同类。
若D=2,则表示X吃Y。

Output

只有一个整数,表示假话的数目。

Sample Input

100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5

Sample Output

3

 

 

题目的解法为带权并查集,这题算得上是对并查集应用情况最好的考察。

不过题目确实很难,自己并没有什么思路。

后来看了大佬的题解后才懂得解法,并自己手打了一遍,发现WA了,仔细检查发现在处理寻找父节点时写成了找爷爷节点。。绝望🤣🤣

因版权原因,此处给出博客的网址:http://blog.csdn.net/c0de4fun/article/details/7318642/

 

写得很棒😃

最令我惊叹的还是对于关系的处理,异常精妙。。

 

下面是自己打的code加注释


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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

struct animal
{
    int num;
    int parent;
    int relation;   //编号,父节点,关系
};
animal ani[500010];

int n,k;
int same=0;
int enemy=1;
int food=2; //关系定义
int ans;

void init(void)
{
    for (int i=1;i<=n;i++)
    {
        ani[i].num=i;
        ani[i].parent=i;
        ani[i].relation=0;  //初始化,编号与父节点==i,关系为同类
    }
}

int findfa(int node)
{
    int t;
    if (ani[node].parent==ani[node].num)
        return ani[node].parent;        //直到找到父节点是自身,返回;
    t=ani[node].parent;     //记录父节点
    ani[node].parent=findfa(t); //将父节点更新为爷爷节点
    ani[node].relation=(ani[node].relation + ani[t].relation)%3; //通过父节点的关系计算出与爷爷节点的关系
    return ani[node].parent;    //返回新的父节点
}

void Union(int x,int y,int a,int b,int d)
{
    ani[b].parent = a;  
    ///rootY.parent = rootX.parent;  
    ani[b].relation =( (3 - ani[y].relation) + (d - 1) + ani[x].relation) % 3;
    //由b与y的关系和y与x的关系和x对a的关系推出b与a的关系;
}

int main(void)
{
    scanf("%d%d",&n,&k);
    init();
    for (int q=1;q<=k;q++)
    {
        int d,x,y;
        scanf("%d%d%d",&d,&x,&y);
        if (x>n || y>n || x<=0 || y<=0) //编号不正确
            ans++;
        else
        {
            if (x==y && d==2)
                ans++;      //自己吃自己
            else
            {
                int a=findfa(x);
                int b=findfa(y);    //根节点
                if (a!=b)
                {
                    Union(x,y,a,b,d);   //不在同一集合就合并
                }
                else
                {
                    if (d==1)       //同类
                    {
                        //若集合中关系不为同类,ans++;
                        if (ani[x].relation != ani[y].relation)
                        {
                            ans++;
                        }
                    }
                    if (d==2)       //敌人
                    {
                        //若集合中关系不为敌人,ans++;
                        if ((ani[y].relation+3-ani[x].relation)%3 != 1)
                        {
                            ans++;
                        }
                    }
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

 

一上午的成果,感觉还是收获颇丰。😀😀

 

 

心情有低谷,人生从未有低谷!

Y.W.            2017/7/10     东海集训