#P679. 无标号图编码

无标号图编码

本题没有可用的提交语言。

你现在要把一个由 01 组成的比特串编码为一张 $M=100$ 个顶点的无标号无向图,并且需要在图的点和边随机打乱之后仍然恢复出这个比特串。此外,你需要让这个比特串尽可能长。

评测方式

你需要提交一个程序。你的程序需要支持三个运行模式 N, A, B,分别表示输出比特串长度、加密、解密。每次加密或解密时,你的程序都会被重新执行。

首先评测程序会将单个字母 N 作为输入运行你的程序,你需要输出一个正整数 $n$,表示你能编码的比特串最长有多长。出于一些原因,我们知道这个长度不会超过 $5000$。

然后,以下过程会被执行若干次:

  • 评测程序会运行你的程序,输入两行,第一行是单个字母 A,第二行是一个长度为 $n$ 的比特串。你需要输出一张 $M$ 个顶点的无向图,具体格式见下文。
  • 评测程序会打乱这张无向图的点标号和边标号。
  • 评测程序会重新运行你的程序,输入若干行,第一行是单个字母 B,第二行及以后表示一张 $M$ 个顶点的无向图。你的程序需要输出一个长度为 $n$ 的比特串,且输出串需要和这一轮最开始输入的串相同。

上述的无向图的格式如下:首先一行一个整数 $e$,表示图的边数(我们知道图的点数固定为 $M=100$);此后 $e$ 行每行两个整数 $u_i, v_i$,表示一条无向边。我们不允许 $u_i=v_i$。图的下标从 $1$ 开始。

范例代码与执行过程

例如,假设你写了这样的程序:

#include <bits/stdc++.h>
using namespace std;
int main() {
  int n = 1;
  string s;
  cin >> s;
  if (s == "N") {
    cout << n << endl;
  } else if (s == "A") {
    string z;
    cin >> z;
    if (z == "0") {
      cout << 0 << endl;
    } else {
      cout << 1 << endl;
      cout << 1 << ' ' << 2 << endl;
    }
  } else if (s == "B") {
    int e;
    cin >> e;
    if (e == 0) {
      cout << "0" << endl;
    } else if (e == 1) {
      cout << "1" << endl;
    }
  }
}

这个程序会把长度为 $1$ 的两个比特串 01 分别加密为空图和只有一条 $(1,2)$ 边的图。上述算法按照下面的给分方式可以获得 $1$ 分。

交互库会先运行该程序,将 N 输入进去,得到长度 $n=1$,然后会运行若干次,每次把以下两个输入:

A
0

A
1

输入该程序,该程序会分别输出

0

1
1 2

对于这两种图,评测器会试图将它们点边打乱;当然打乱空图毫无意义。该程序会再次被执行,以下面的内容为输入:

B
0

B
1
11 45

或者一些别的什么数字;该程序当然会正确恢复出原来的两个一位比特串。

给分方式

该题目与常见算法竞赛题目有显著不同,因此有奇妙的给分方式。首先,我们鼓励你写保证正确性的算法,因此在这些测试中,解密错误哪怕一次都会有较高的惩罚;其次,你能加密的比特串越长越好。

假设在 $100$ 组测试中你犯错了 $u$ 次,且你的程序能加密的比特串长度为 $n$,则你的分数

$$ \mathrm{score} = \left\lfloor\frac{f(u)}{f(0)}g(x)\right\rfloor, $$

其中

$$ f(u)=\max{\left(\frac{1}{1+u}-\frac{1}{51},0\right)} $$

是对你的解密犯错的惩罚次数:换言之,你哪怕犯错一次都会让分数下降大约一半。

$$ g(x)= \begin{cases} x,&0 < x\le10\\ 2\sqrt{x-9}+8,&10 < x\le130\\ 2\sqrt[3]{x-103}+24,&130 < x\le2300\\ -6\log_2\left(4348-x\right)+116,&2300 < x\le4092\\ \frac{x}{8}-\frac{887}{2},&4092 < x\le4348\\ 100,&4348 < x\le4355\\ x-4255,&x > 4355 \end{cases} $$

是对你能加密的比特串的长度的奖励。注意,不要被这个式子的长度给吓到;这是一个单调的函数,这里有几个特殊值可以给你参考:$g(10)=10,g(130)=30,g(2300)=50,g(4092)=68,g(4348)=100$。在 $[0,4355]$ 这个范围内,它大概长这样:

函数图像

自测程序

你可以使用这份程序来在本地对你的代码进行测试。

致谢

这道题目归功于 kczno1 同学。感谢 mcfx 同学提供的打爆标程的题解。感谢 UOJ 各位管理员群友帮我按后台的按钮。