题目背景
给你一张 n 个点的简单无向图。
接下来有 q 次操作,每次操作为添加一条边或删去一条边,请在每次操作后判断图中是否有四元环。
等等,题面放错了。
并非呃呃。
在「呃呃 / ee」一题中,如何构造数据成为了一个难题。
当初始边数过小时,可能会让一些 O(mm) 的做法得以通过,而初始边数过大时又随机不出一张无四元环的初始图。
给你一道呃呃,输出一组足够强力的数据。
题目描述
给你一个整数 n,有一集合 U={1,2,…,n}。
你需要构造 n 个集合 S1,2,…,n,满足条件:
- 对所有 1≤i≤n,Si⊆U;
- 对所有 1≤i<j≤n,∣Si∩Sj∣≤1。
为了不让暴力通过,你希望 i=1∑n∣Si∣ 尽量大。
输入格式
一行两个整数 n,L,关于 L 的信息见「数据规模与约定」部分。
输出格式
输出 n 行,每行一个长为 n 的 01 字符串。
若第 i 行第 j 列的字符为 1,代表 j∈Si,否则 j∈/Si。
3 5
111
010
100
提示
数据规模与约定
为了衡量你的构造强度,你将会得到一个整数 L。
对于每个数据点,你需要构造出一组解使得 ∑i=1n∣Si∣≥L。
数据点编号 |
n= |
L= |
1 |
4 |
8 |
2 |
10 |
23 |
3 |
2333 |
4666 |
4 |
6996 |
5 |
104 |
6 |
2×104 |
7 |
4×104 |
8 |
6×104 |
9 |
8×104 |
10 |
105 |
对于所有数据,保证 4≤n≤2333。
提示
构造一张左右部点数均为 n 的二分图,对于所有 1≤i,j≤n,左侧点 i 与右侧点 j 之间有边当且仅当 j∈Si。容易验证,此时构造出的图中无四元环。