#2408. 精准预测

    ID: 2408 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>PROV赛事:contest890来源:qoj.ac数据:公开样例并查集

精准预测

精准预测

题目描述

预览输出 JSOI2019 Round 2 精准预测(predict) 精准预测(predict) 【题目背景】 JYY 和他的火星探险队再次登录火星小镇,并且打算把机器学习的知识传授给火 星人,从而提高火星人的生活效率。但智力有限的火星人纷纷表示不相信计算机科学。 为了让火星人彻底信服,JYY 的探险队找到了他们之前关于火星详细的数据记录,并且 训练了一个预测模型,这个模型能准确地预测出火星人在未来的生死情况。 【题目描述】 目前,火星小镇上有n 个居民(编号1, 2, . . . , n)。机器学习算法预测出这些居民在 接下来T 个时刻(编号1, 2, . . . , T)的生死情况,每条预测都是如下两种形式之一: • .难.兄.难.弟0 t x y: 在t 时刻,如果x 是死亡状态,那么在t + 1 时刻,y 是死亡 状态。(注意, 当x 在t 时刻是生存状态时,该预测也被认为是正确的) • .死.神.来.了1 t x y: 在t 时刻,如果x 是生存状态,那么在t 时刻,y 是死亡状 态。(注意, 当x 在t 时刻是死亡状态时,该预测也被认为是正确的) (注意本题是对某个时刻进行生死状态的预测, 如果某个人在t 时刻是生存状态, 在 t + 1 时刻是死亡状态, 你可以认为是在t 到t + 1 这段时间内发生了某个事件导致其死 亡.) 虽然JYY 对自己从大数据中统计得到的模型非常自信,但火星人看到这些预测吓 了一跳,表示实在难以接受这种设定,更是认为计算机科学是可怕的邪教,打破了他们 平静的生活。为了安抚火星人的情绪,JYY 打算从这些预测结果中推导出一些火星人更 容易接受的事实,从而安抚火星人的情绪。 具体来说,JYY 首先.假.设.对.火.星.人.生.死.的.预.测.全.部.正.确。在此基础上,JYY 希望 为小镇上的每个居民k .分.别.计.算.有.多.少.个.火.星.人.有.可.能.和.他.一.起.活.到.第T +1 .时.刻。换 言之,JYY 希望为每个火星人k 计算 ∑ 1≤i≤n,i̸=k Live(k, i), 其中Live(i, j) = 1 表示编号为i 和j 的火星人可以同时在第T + 1 时刻处于生还状态, 否则Live(i, j) = 0。 注意火星人是不能够复活的。一个火星人可能在时刻1 就处于死亡状态,也有可能 有.预.测.未.覆.盖.的.死.亡情况发生(火星人在任何时候都可能死亡,但任意时刻观察到火星 人的状态要么活着,要么死亡)。最后,注意到Live 是为每一对火星人分别定义的,因 此Live(x, y) = Live(y, z) = 1 并不意味着Live(x, z) = 1。 【输入格式】 从文件predict.in 中读入数据。 第2 页 共9 页

预览输出 JSOI2019 Round 2 精准预测(predict) 输入第一行包含三个整数T, n, m。 接下来有m 行,每行表示一条预言,每条预言第一个整数c 表示预言的类型: • c = 0:接下来读入t, x, y • c = 1:接下来读入t, x, y 输入数据保证1 ≤t ≤T、1 ≤x, y ≤n。.本.题.内.存.限.制1024MiB .包.含.进.程.中.运.行 .库、.堆.栈.等.所.有.内.存,.请.特.别.留.意。 【输出格式】 输出到文件predict.out 中。 输出n 个数表示答案,用空格分割. 【样例1 输入】 1 3 3 2 2 0 2 1 3 3 1 1 2 3 【样例1 输出】 1 2 1 1 【样例1 解释】 如果编号为2 的火星人活到T + 1 时刻, 意味着在1 时刻他也是活着的, 由于第二 条预言, 会观察到编号为3 的火星人在时刻1 是死亡状态, 所以编号为2 和3 的火星人 不能同时活到T + 1 时刻, 所以Live(2, 3) = 0. 而编号为1 的火星人能和其他两人的某一个活到T + 1 时刻. 注意当1 和3 同时活 着的时候, 第一条预言是正确的. 所以有Live(1, 2) = 1, Live(1, 3) = 1. 【样例2】 见选手目录下的predict/predict2.in 与predict/predict2.ans。 第3 页 共9 页

预览输出 JSOI2019 Round 2 精准预测(predict) 【子任务】 测试点 T n m 1 ≤2 ≤10 ≤10 2,3 ≤102 ≤102 ≤200 4 ≤106 ≤3, 000 ≤6, 000 5,6 ≤4 × 104 ≤104 ≤2 × 104 7 ≤106 ≤3 × 104 ≤6 × 104 8 ≤4 × 104 ≤8 × 104 9,10 ≤5 × 104 ≤105 第4 页 共9 页

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 3 2
0 2 1 3
1 1 2 3
2 1 1

样例 2

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