题解:洛谷P1955:[NOI2015]程序自动分析

题解:洛谷P1955:[NOI2015]程序自动分析

算法:并查基、离散化、文件读入与写出。

题目描述

在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本:假设 $x_1,x_2,x_3\dots$代表程序中出现的变量,给定 $n$ 个形如$x_i=x_j$或$x_i \neq x_j$的变量相等/不等的约束条件,请判定是否可以分别为每一个变量赋予恰当的值,使得上述所有约束条件同时被满足。例如,一个问题中的约束条件为:$x_1=x_2,x_2=x_3,x_3=x_4,x_4\neq x_1$,这些约束条件显然是不可能同时被满足的,因此这个问题应判定为不可被满足。

现在给出一些约束满足问题,请分别对它们进行判定。

输入格式

从文件prog.in中读入数据。

输入文件的第 $1$ 行包含 $1$ 个正整数 $t$,表示需要判定的问题个数。注意这些问题之间是相互独立的。

对于每个问题,包含若干行:

第 $1$ 行包含 $1$ 个正整数 $n$ ,表示该问题中需要被满足的约束条件个数。接下来 $n$ 行,每行包括 $3$ 个整数 $i,j,e$,描述 $1$ 个相等/不等的约束条件,相邻整数之间用单个空格隔开。若 $e=1$,则该约束条件为 $xi=xj$;若 $e=0$,则该约束条件为 $xi\neq xj$;

输出格式

输出到文件 prog.out 中。

输出文件包括 $t$ 行。

输出文件的第 $k$ 行输出一个字符串“ YES” 或者“NO”(不包含引号,字母全部大写),“YES” 表示输入中的第 $k$ 个问题判定为可以被满足,“NO” 表示不可被满足。

输入输出样例

输入 #1

1
2
3
4
5
6
7
2
2
1 2 1
1 2 0
2
1 2 1
2 1 1

输出 #1

1
2
NO
YES

输入 #2

1
2
3
4
5
6
7
8
9
10
2
3
1 2 1
2 3 1
3 1 1
4
1 2 1
2 3 1
3 4 1
1 4 0

输出 #2

1
2
YES
NO

说明/提示

【样例解释1】

在第一个问题中,约束条件为:$x1=x2,x1\neq x2$。这两个约束条件互相矛盾,因此不可被同时满足。

在第二个问题中,约束条件为:$x1=x2,x1=x2$。这两个约束条件是等价的,可以被同时满足。

【样例说明2】

在第一个问题中,约束条件有三个:$x1=x2,x2=x3,x3=x1$。只需赋值使得$x1=x1=x1$,即可同时满足所有的约束条件。

在第二个问题中,约束条件有四个:$x1=x2,x2=x3,x3=x4,x4\neq x1$。由前三个约束条件可以推出$x1=x2=x3=x4$,然而最后一个约束条件却要求$x1\neq x4$,因此不可被满足。

【数据范围】

img

【时限2s,内存512M】

题目传送门:🚪

文件读入与写出

虽说题干写着从文件读入,写出到文件,但其实这个题完全不需要……直接标准读入读出就可以……可怜我太实诚……酿造了如下惨状:

1564486633365

既然提到了就说说这个……

C的方法

  • fopen()函数

    使用方式:fp = fopen("input.in", "r")

    • 第一个参数为打开文件的文件名;
    • 第二个参数为文件方式,是文件的类型和操作要求,有如下几种(组合):
      • r:只读(read),要求文件必须已经存在;
      • w:只写(Write),若文件不存在则自动创建,如果已存在则删除原文件后新建;
      • a:追加(Append),保留文件中已有内容,从文件尾开始写;
      • t:文本文件(Text),可忽略;
      • b:二进制文件(Binary);
      • +:读写。
    • 返回值为文件指针,为FILE类型的指针变量。

    在具体使用此方法写入时,使用fscanf(fp, "%d", &n)来读取:

    • 第一个参数为文件指针名,即使用fopen返回的指针;
    • 第二个参数为格式控制符,同scanf()的使用方式;
    • 第三及以后的参数为传入变量的指针。

    使用fprintf(fp, "%d\n", n)来写入文件:

    • 第一个参数为文件指针名,即使用fopen返回的指针;
    • 第二个参数为格式控制符,同printf()的使用方式;
    • 第三及以后的参数为输出变量。

    结束使用该函数使用:fclose(fp)

  • freopen()函数

    使用方式:freopen("input.in", "r", stdin);freopen("output.out", "w", stdout);

    • 第一个参数为打开文件的文件名;
    • 第二个参数为文件方式,同fopen()函数;
    • 第三个参数为文件指针,通常使用标准流文件(stdin/stdout/stderr)。

    使用freopen()函数,并使用了标准流文件后,就可以直接使用scanf()printf()来读入和写出。

    结束使用fclose(stdin);fclose(stdout)

C++的方法

1
2
3
4
5
6
ifstream inputFL("input.in");
ofstream outputFL("putput.out");
inputFL >> n;
outputFL << n << endl;
inputFL.close();
outputFL.close();

正式题解

基本题意就是给你几个约束条件看他们能不能共存成立。而相等关系的约束条件我们可以很容易地想到将其转换为一个图,出现相等关系就说明它们在一个个图上 $\Rightarrow$ 两个值的最终祖先节点相同。而出现不等关系就说明它们没在一个图上,所以这个问题就可以转换成一个并查集问题。在这里贴上并查基常用的板子:

  • 得到最终祖先:

    1
    2
    3
    4
    5
    int get(int x){
    if(x == fa[x]){
    return x;
    }else return fa[x] = get(fa[x]);
    }
  • 合并两棵树:

    1
    2
    3
    4
    5
    6
    7
    void merge(int a, int b){
    int faOa = get(a);
    int faOb = get(b);
    if(faOa != faOb){
    fa[b] = a;
    }
    }

而注意到题目数据量很大,$i$、$j$ 的范围到了 $10^9$,无法开那么大的数组,所以我们使用到了离散化。我的离散化的博文的传送门:🚪

基本思想就是看输入的两个值是否相同,如果相同就保留到一棵树上。如果不相同的话检查两个点的根结点是否相同,如果相同则说明这两个值已经相同,出现矛盾,则输出“NO”。为了实现这个思想,我们首先要对输入进行排序,将相等关系放在前面预先判断。

AC代码如下:

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>
#define inputFL cin
#define outputFL cout
using namespace std;
struct Node{
int x;
int y;
bool e;
}Nodes[100005];
bool cmp(Node a, Node b){
return a.e > b.e;
}
int dict[1000005];
int fa[1000005];
int cnt, uqcnt;
int n;
int get(int x){
if (x == fa[x]) {
return x;
}else return fa[x] = get(fa[x]);
}
// void merge(int x, int y){
// fa[get(x)] = get(y);
// }
int main(){
// ifstream inputFL("prog.in"); // C++方式, C使用freopen()
// ofstream outputFL("prog.out");
int T;
inputFL >> T;
while(T--){
inputFL >> n;
memset(dict, 0, sizeof(dict));
memset(fa, 0, sizeof(fa));
uqcnt = cnt = 0;
for (int i = 0; i < n; i++) {
inputFL >> Nodes[i].x >> Nodes[i].y >> Nodes[i].e;
dict[cnt++] = Nodes[i].x;
dict[cnt++] = Nodes[i].y;
}
sort(dict, dict + cnt);
uqcnt = unique(dict, dict + cnt) - dict;
for (int i = 0; i < n; i++) {
Nodes[i].x = lower_bound(dict, dict + uqcnt, Nodes[i].x) - dict;
Nodes[i].y = lower_bound(dict, dict + uqcnt, Nodes[i].y) - dict;
}
for (int i = 0; i < uqcnt; i++) {
fa[i] = i;
}
bool check = 1;
sort(Nodes, Nodes + n, cmp);
for (int i = 0; i < n; i++) {
int a = get(Nodes[i].x);
int b = get(Nodes[i].y);
if (Nodes[i].e) {
fa[a] = b;
}else{
if (a == b) {
check = 0;
outputFL << "NO" << endl;
break;
}
}
}
if (check)
outputFL << "YES" << endl;
}
}

特别提醒:一定要分清离散化中各个变量的具体含义与用处,否则就会出现以下的状况而无从下手:

1564489428381

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×