QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 22 MB Total points: 100 Interactive

# 4913. 子集匹配

统计

题目背景

小 P 本来想投个很有意思的改编题,但是它被原题做法直接爆过去了。

小 P 心态非常爆炸,于是他决定投一个简单题送温暖。

题目描述

小 P 学了 Hall 定理,感觉很有意思。

小 P 发现 Hall 定理的一个直接推论是,如果左部点集合 $L$ 的大小不超过右部点集合 $R$ 的大小,且左部点度数相等、右部点度数相等,且边集不为空,那么一定存在大小为 $|L|$ 的匹配。

小 P 发现 Hall 定理的一个问题是,它只给了存在性而没给构造。

小 P 随机了一道题,想让你帮他做:

给定 $n,K$ ,保证 $2K>n$ 。设 $[n]=\{0,1,2,\cdots,n-1\}$ 。设 $\mathcal L$ 为所有 $[n]$ 的大小为 $K$ 的子集组成的集合, $\mathcal R$ 为所有 $[n]$ 的大小为 $K-1$ 的子集组成的集合,并且对于 $S\in \mathcal L,T\in \mathcal R$ , $S,T$ 之间有边当且仅当 $T\subset S$ 。请你求出一组大小为 $|\mathcal L|$ 的匹配。

为了减小 IO 所用时间,本题采用交互的形式评测。

请不要尝试 hack 交互库!

实现细节

你必须引用 hall.h 头文件。

你需要实现下面的过程:

int solve(int n,int K,int s);

其中 $s$ 表示一个 $[n]$ 的子集 $S$ , $x\in S$ 当且仅当 $s$ 的二进制从低到高的第 $x$ 位为 $1$ 。保证 $|S|=K$ 。你需要返回一个非负整数 $t$ ,以同样的格式表示集合 $T$ ,并满足 $T\subset S,|T|=K-1$ 。

solve 函数可能被调用多次,请注意变量的初始化。保证每次调用时给出的 $n,K$ 都不变,且同一个 $s$ 只会被询问一次。

评测方式

样例评测库将读入如下格式的输入数据:

一行,两个正整数,表示 $n,K$ 。

样例评测库将输出如下格式的输出数据:

设样例评测库调用了 $q$ 次 solve 函数,那么会输出 $q+1$ 行,第 $i$ 行 $(1\le i\le q)$ 形如 s -> t ,其中 $s,t$ 是由 $01$ 组成的长度为 $n$ 的字符串,表示 solve 函数的参数和返回值,从左到右依次为低位至高位。第 $q+1$ 行会输出 OKWA ,表示匹配是否合法。

样例数据

input

5 3

output

00111 -> 00101
01011 -> 00011
01101 -> 01100
01110 -> 01010
10011 -> 10010
10101 -> 10001
10110 -> 00110
11001 -> 01001
11010 -> 11000
11100 -> 10100
OK

数据规模与约定

保证 $1\le n\le 27$ 、 $2K>n$ 。

对于 $20\%$ 的数据,保证 $n\le 15$ 。

对于 $40\%$ 的数据,保证 $n\le 19$ 。

对于 $60\%$ 的数据,保证 $n\le 23$ 。

对于 $80\%$ 的数据,保证 $n\le 25$ 。

请注意本题的空间限制。

保证交互库消耗时间不超过 $\texttt{0.3s}$ ,消耗空间不超过 $\texttt{18MB}$ (其中包括 #include<bits/stdc++.h>using namespace std;)。

时间限制: $\texttt{3s}$

空间限制: $\texttt{22MB}$