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 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     东海集训

 

【NOIP2010】关押罪犯 题解(大概→_→)

题目传送门:!点我传送!

刚开始做的时候看到最小值这几个字,我们就应想到用贪心的想法,我们应该尽量的把先影响力高的两的犯人关到不同的监狱,直到发现有两个犯人已经被分配到相同的监狱,这两个犯人之间的影响力就是这题的答案。

二分法

二分法大家肯定都不陌生,这题只要对影响力进行二分,对于在二分出来的影响力X,只要是犯人之间的影响力小于X就判断在可容忍范围内,可将其关到同一监狱内,反之则必须分到不同监狱。时间最多应是O(log1,000,000,000),应还在时间范围内。

以下代码来自http://blog.csdn.net/cynthia_wjyi/article/details/47125015


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
#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<algorithm>  
using namespace std;  
struct Node{  
    int y,z,next;  
}e[200020];  
int tot,item,n,m;  
int head[20005],b[20005],a[100005];  
bool pd;  
int cmp(int a,int b){return a<b;}  
void insert(int x,int y,int z)  
{  
    e[++tot].y=y;  
    e[tot].z=z;  
    e[tot].next=head[x];  
    head[x]=tot;  
}  
void dfs(int x,int data)  
{  
    if(pd==false)return;  
    b[x]=data;  
    for(int i=head[x];i!=0;i=e[i].next)  
    {  
        if(e[i].z>item)  
        {  
            if(b[e[i].y]==-1)dfs(e[i].y,1-data);  
            else  
            if(b[e[i].y]==data){pd=false;return;}  
        }  
    }  
}  
bool work(int midd)  
{  
    memset(b,-1,sizeof(b));  
    pd=true;  
    item=a[midd];  
    for(int i=1;i<=n;i++)  
    if(b[i]==-1)dfs(i,0);  
    return pd;  
}  
int main()  
{  
    scanf("%d%d",&n,&m);  
    memset(head,0,sizeof(head));  
    int x,y,z;  
    tot=0;  
    for(int i=1;i<=m;i++)  
    {  
        scanf("%d%d%d",&x,&y,&z);  
        insert(x,y,z);  
        insert(y,x,z);  
        a[i+1]=z;  
    }  
//  for(int i=1;i<=tot;i++)cout<<e[i].y<<' '<<e[i].z<<' '<<e[i].next<<endl;  
    a[1]=0;  
    sort(a+1,a+1+m,cmp);  
//  for(int i=1;i<=m+1;i++)cout<<a[i]<<' ';  
//  cout<<endl;  
    int l=1,r=m+1,mid;  
    while(l<r)  
    {  
        mid=(l+r)/2;  
//      cout<<l<<' '<<r<<' '<<mid<<endl;  
        if(work(mid)==true)r=mid;  
        else l=mid+1;  
    }  
    printf("%d\n",a[l]);  
}

并查集

这题我乍一看以为是二分图,其实用并查集的思想就可以做。

  1. 对于并查集的判断顺序,通过贪心的思想得出是要从大到小,保证答案最小。所以要先对于影响力对每一对犯人进行排序。
  2. 对于每个犯人我们可以创造一个他的镜像,比如犯人X和犯人Y,我们需加入犯人Px和犯人Py。
  3. 在操作过程中我们只需不断将X、Py并入一个集合,同样将Y、Px也并入一个集合。在发现X,Y已处于同一集合时就说明他们已经被分配到相同的监狱,这时他们之间的影响力即是答案。

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

struct sd
{
    int x,y,z;
}hate[100100];

int father[50000];

bool com (sd a, sd b)
{
    return a.z > b.z;
}

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

int xfind(int x)
{
    return father[x] == x ? x : xfind(father[x]);
}

void un(int a, int b)
{
    father[xfind(a)] = xfind(b);
}

int main(void)
{
    int i,n,m;
   
    scanf("%d%d", &n, &m);
    start(n*2);
   
    int po=m;
    while (m--) scanf("%d%d%d",&hate[m].x,&hate[m].y,&hate[m].z);
   
    sort(hate+1,hate+po+1,com);
   
    int ans=0;
    for (i=1;i<=po;i++)
    {
        if (xfind(hate[i].x)==xfind(hate[i].y))
        {
            ans=hate[i].z;
            break;
        }
       
        un(hate[i].x,hate[i].y+n);
        un(hate[i].y,hate[i].x+n);
    }
   
    printf("%d", ans);
    return 0;
}

[BZOJ 3624] [APIO 2008] 免费道路

并查集。

题意:求把 N 个点用 N-1 条边连成一棵树,且其中恰有 K 条边为 0 边的一种方案。

第一反应:先连 0 边再连 1 边。

但可能会有这么一种情况:所有的 1 边都连上之后仍然整个图仍然是不联通的。这意味着有一些 0 边是必选的。但如果像上面那样直接做的话可能选不到这些边,从而得不出答案。

于是可以这样做:

先把所有 1 边端点合并,然后接着枚举 0 边,若两顶点不在同一集合中,则把这条边端点所在集合合并,并加入答案中。

接着把并查集重置成只有答案集合中的边的情况,加入能加的 0 边直到答案中的 0 边数量达到 K。最后加入 1 边。

这题还要判断方案是否存在,判断方法为 1. 选取的 0 边边数恰为 K。 2. 选取的总边数为 N-1

代码如下(BZOJ 有点诡异,endl 交上去会 RTE,而 '\n' 就没问题):

继续阅读[BZOJ 3624] [APIO 2008] 免费道路