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

 

【[NOIP2009】靶形数独 题解(大概)

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

题目再怎么看也就只是简单的数独(sudoku)而已,其实没比基本的数独难到哪去。

先从最基本的数独开始讲,在程序中做数独最经常还是用深搜(Depth First Search),在进行剪枝后再对种种可能进行一一搜索。对于剪枝的方法还是要从数独的规则入手:满足每一行、每一列、每一个粗线宫(3*3)内的数字均含1-9,不重复。在此我们可以用数组通过统计每一行、每一列、每一个粗线宫中存在的数字在讨论剩余空格中数字的可能。个人在在每次dfs时会先找出可能的数字最少的点优先进行搜索,这样可以减少不少时间(也算是个不小的优化吧)。

在此题中我们用上述做法找到所以可能并把最大的ANS找出进行输出即是答案。

 



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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int L[10][10],H[10][10],A[10][10]; //列 行 area
int map[10][10],ANS=0;
 
int Area(int x,int y)  
{  
    return  (x-1)/3*3+(y+2)/3;  
}

int Abs(int x)  
{  
    return x > 0 ? x : -x;  
}
 
int Score(int x,int y)  
{  
     return 10-max(Abs(x-5),Abs(y-5));  
}

int boom = 0;
void start()
{
        for (int i = 1; i <= 9; i++)
        {
                for (int j = 1; j <= 9; j++)
                {
                        int k = Area(i, j);
                        if (map[i][j])
                        {
                                if (!H[i][map[i][j]]&&!L[j][map[i][j]]&&!A[k][map[i][j]])
                                {
                                        H[i][map[i][j]]=L[j][map[i][j]]=A[k][map[i][j]]=1;
                                }else
                                {
                                        boom = 1; return;
                                }
                        }
                }
        }
}


void dfs(int now)
{
        int g_max=0, minn=10, px, py;
        for (int i = 1; i <= 9; i++)
        {
                for (int j = 1; j <= 9; j++)
                {
                        if (map[i][j]) continue;
                        int num = 0, sd=0;
                        for (int k = 1; k <= 9; k++)
                        {
                                if (H[i][k] || L[j][k] || A[Area(i, j)][k]) continue;
                                num++; sd=k;
                        }
                        if (num == 0) return;
                        if (num < minn)
                        {
                                minn = num;
                                px=i; py =j;
                        }
                        g_max += sd*Score(i,j);
                }
        }
       
        if(g_max+now <= ANS)  return ;  
    if(g_max == 0)  
    {  
        boom=1;  
        ANS = max(ANS,now);  
        return ;  
    }  
       
        for (int k = 1; k <= 9; k++)
        {
                if (H[px][k] || L[py][k] || A[Area(px, py)][k]) continue;
               
                H[px][k] = L[py][k] = A[Area(px, py)][k] =1;
                map[px][py] = k;
               
                dfs(now+k*Score(px, py));
               
                map[px][py] = 0;
                H[px][k] = L[py][k] = A[Area(px, py)][k] =0;
        }
        return;
}

int main(void)
{
       
        for (int i = 1; i <= 9; i++)
          for (int j = 1; j <= 9; j++)
          {
                scanf("%d", &map[i][j]);
                ANS+=map[i][j]*Score(i,j);
          }
        start();
        if (boom)
        {
                printf("-1");
                return 0;
        }
        dfs(ANS);
        if (boom) printf("%d", ANS);
        else printf("-1");
}


	

矩阵填数

题意:

给出一些有限制的矩阵,求出满足要求的方案数。

可以发现,如果将每个矩形的四条边延长,可以将大矩形划分成不多于400个的小矩形。

对于每个有限制的矩形,只有两种情况:达到要求和未达到要求。最多有2^10种状态。

由于状态少,可以用状压DP来解决。

设f[tot][k]为第i个小矩形达到状态k的方案数,state[i][j]为小矩形tot满足要求每个有限制的矩形的状态

就有

  1. f[tot + 1][k|sta[i][j]] += (long long)f[tot][k] * (power(V[i][j], num[i][j]) -power(V[i][j] - 1, num[i][j]))
  2. f[tot + 1][k] += (long long)f[tot][k] * (power(V[i][j] - 1, num[i][j])

最后f[tot][(1<<n) - 1](tot是小矩形数,(1<<n) - 1是状态数)为答案

继续阅读矩阵填数

BZOJ【1857】传送带

描述

在平面上给出两条线段AB,CD,再给出在线段、平面的速度,求出从A走到D最短的时间。

从题意上看,我们很(ping)容(zhi)易(jue)得出答案是单峰的,也就是对于AB上的点E,在从A到B的过程中,答案是先变小,再变大。于是就用三分来求峰值。

单峰证明:对于AB上的点E,到CD上的点F。当EF⊥CD时,E到CD的距离最短,而时间也最短。 否则的话E到CD的距离一定大于EF。


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

using namespace std;

struct node
{
    double x, y;
}A, B, C, D, T;

double p, r, q;
double ans = INT_MAX;

double dir(node a, node b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

node tri(node a, node b, int t)
{
    T.x = a.x + (b.x - a.x) * t *1.0 / 3;
    T.y = a.y + (b.y - a.y) * t *1.0 / 3;
    return T;
}

double ANS(node a, node b)
{
    return dir(a, A) / p + dir(b, D) / q + dir(a, b) / r;
}

double Ans(node t)
{
    node c = C, d = D, x, y;
    double time_x, time_y, times = INT_MAX;
    do
    {
       x = tri(c, d, 1);
       time_x = ANS(t, x);
       y = tri(c, d, 2);
       time_y = ANS(t, y);
       times = min(times, min(time_x, time_y));
       if (time_x > time_y) c = x;
       else d = y;
    }while (dir(c, d) >= 0.0000001);
    return times;
}

int main(void)
{
    freopen("walk.in","r",stdin);
    freopen("walk.out","w",stdout);
   
    cin >> A.x >> A.y >> B.x >> B.y >> C.x >> C.y >> D.x >> D.y;
    cin >> p >> q >> r;
    node x, y;
    double time_x, time_y;
    do
    {
       x = tri(A, B, 1);
       time_x = Ans(x);
       y = tri(A, B, 2);
       time_y = Ans(y);
       ans = min(ans, min(time_x, time_y));
       if (time_x > time_y) A = x;
       else B = y;
    }while (dir(A, B) >= 0.0000001);
    printf("%.2f", ans);
   
    fclose(stdin);
    fclose(stdout);
    return 0;
}

BZOJ【2338】画矩形

这题要求找出一个最大面积的矩形,学过数学的都知道:矩形对角线交于一点,而且两条对角线相等。于是我们就可以枚举每一条线段,按长度排序,取长度相等的判断他们的中点是否重合,重合的话就可以构成一个矩形。

按照上面的方法,枚举线段要n^2, 排序要n^2log(n^2),所以时间大概为O(n^2log(n^2))。

但是这题的数据有10^8,如果用两点之间距离公式和中点公式有可能被卡精度,于是可以在求距离是不开根号,直接用long long存,中点公式也不除2,这样可以避免精度的影响。

最后,在求面积时用叉积求即可。