版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

仓库源文，站点原文

title: "题解 - [Luogu P5042] [UOJ 100] [集训队互测2015] 丢失的题面（ydc的题面）" categories:

题目链接

<!-- more -->

原始题面

曾经, 有一个题面摆在 ydc 的面前没有珍惜, 直到失去时才后悔莫及,

如果上天再给他一次机会, ydc 一定会牢牢的记住这个题面

没办法, 已经失去了, 所以这道题只能让你帮 ydc 做了

已知的信息只有, 这道题是传统题, 采用全文比较的方式, 时间限制 $1\texttt{s}$, 空间限制 $256\texttt{MB}$

ydc 还给你提供了这道题的所有数据

数据下载: https://pan.baidu.com/s/1kT8Al0r 密码: cb5y

不方便用百度网盘的可以在这边下载 lost.zip

—— Tifa

该题在比赛时显示的成绩就是最终成绩

来源

中国国家集训队互测 2015 - By 于纪平

题意简述

看数据猜程序

解题思路

首先根据输入数据风格分为 4 类

  1. 1-3 组: 输入 1 个数, 让你构造一个序列
  2. 4-6 组: 输入一个数组, 输出一个和输入数组构造方式差不多的数组
  3. 7-9 组: 输入一个图, 还有若干次查询
  4. 第 10 组: 送分的

首先说下第 10 组, 直接输出输出文件那一堆就行

接下来是第 1 类

  1. 第 1 组: 不难发现是 Thue-Morse 序列, OEIS: A010060
  2. 第 2 组: 不难发现是用类似 Fibonacci 数列构造方式构造的
  3. 第 3 组: 三进制版的 POJ 1780, 输出数据即为恰好包含全部 12 位三进制数的字典序最小的序列, 做法为以 n-1 位三进制数为结点建图然后从 00000000000 出发找 Euler 回路, 不难发现构造出来的序列长度正好为 $3^{12}+12-1=531452$

然后是第 2 类

  1. 第 4 组: 不难发现是组合数的数列, 关键在于求模数, 观察第 4 行即可得到为 104857601, 后面两组数据均以此为模数
  2. 第 5 组: 就是把第 4 组的输入输出反过来
  3. 第 6 组: 按前两组构造方式猜测与组合数有关, 这里猜测和二项式展开有关

或者这样 (注意到 $104857601 = 25\times 2^{22}+1$)

  1. 第 4 组: 给出一个多项式, 对其平方
  2. 第 5 组: 给出一个多项式, 对其开方
  3. 第 6 组: 给出一个多项式, 对其开立方

但是写 NTT 显然没有写组合数简单, 所以这个看看就好

最后是第 3 类

  1. 第 7 组: 观察输出数据发现, 输出只有 0 和 0x7f7f7f7f, 猜测是判断两点是否连通, 故直接并查集即可
  2. 第 8 组: 观察输出数据发现, 输出均和边权差不多, 而且输入的是树, 这里猜测为输出两点路径中的最大边权, 直接倍增一下即可
  3. 第 9 组: 观察输出数据发现其特点综合了以上两种情况, 猜测为求两点路径中边权最大值的最小值, 用 Kruskal 找最小生成森林之后倍增即可 (就是把前两种情况都复制过来改改就行)

代码参考

<details open> <summary><font color='orange'>Show code</font></summary> {% icodeweb cpa_cpp title:Luogu_P5042 Luogu/P5042/0.cpp %} </details>