Solution

提供一种新思路。

首先考虑如何判断一个状态是否合法。

考虑把所有十进制长度一样的数缩成一个点。

这样的点的个数 \(\le 5\)。

蒟蒻猜了一个结论:只要满足对于所有缩出来的点的子集的点的个数 > 子集内边的个数,那么就是有解的。

这时 \(\tt \color{black}{S}\color{red}{egmentTree}\) 会下凡告诉你:这是对的!卡不掉!

但是这样只能判断可不可行啊,不能输出方案啊。。。

发现这个东西判断的时间复杂度很小,可以多次判断。

那么我们可以对于每一条边尝试一下可不可以删,然后连边(在原图上,让最后每一个长度只剩下一个点,剩下的特殊处理)。

Code

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = j, i##E = k; i <= i##E; i++)
#define R(i, j, k) for(int i = j, i##E = k; i >= i##E; i--)
#define ll long long
#define db double
#define pii pair<int, int>
#define mkp make_pair
using namespace std;
const int N = 100;
const int M = 2e6 + 7;
const int inf = 1e9;
int n, m, mx, p[N], minn[N], D[M][2], sum = 0;
int a[N][N];
bool check() {
L(t, 0, (1 << mx) - 1) {
int ds = 0, bs = 0;
L(i, 1, mx) if(t & (1 << (i - 1))) ds += p[i];
if(!ds) continue;
L(i, 1, mx) if(t & (1 << (i - 1))) L(j, 1, mx) if(t & (1 << (j - 1))) bs += a[i][j];
if(bs >= ds) return 0;
}
return 1;
}
int Cnt(int x) { return x == 0 ? 0 : Cnt(x / 10) + 1; }
char sa[N], sb[N];
bool get() {
L(x, 1, mx) L(i, 1, mx) if(a[x][i]) {
if(p[x] > 1) {
a[x][i] --, p[x] --;
if(check()) return printf("%d %d\n", minn[x] + p[x], minn[i]), 1;
a[x][i] ++, p[x] ++;
}
if(p[i] > 1) {
a[x][i] --, p[i] --;
if(check()) return printf("%d %d\n", minn[x], minn[i] + p[i]), 1;
a[x][i] ++, p[i] ++;
}
}
return 0;
}
int main() {
scanf("%d", &n), mx = Cnt(n);
L(i, 1, n) p[Cnt(i)]++;
minn[1] = 1;
L(i, 2, mx) minn[i] = minn[i - 1] * 10;
L(i, 1, n - 1) scanf("%s%s", sa, sb), D[i][0] = strlen(sa), D[i][1] = strlen(sb), a[D[i][0]][D[i][1]] ++;
if(!check()) return puts("-1"), 0;
while(get()) sum ++;
L(x, 1, mx) L(i, 1, mx) if(a[x][i]) printf("%d %d\n", minn[x] + p[x] - 1, minn[i] + p[i] - 1), sum ++ ;
if(sum != n - 1) assert(0);
return 0;
}

祝大家学习愉快!


不过怎么证明那个结论是对的啊,蒟蒻思考了好久还是不懂,求解 /kel

最新文章

  1. Android(Logcat、Monitors)
  2. Android中的跨进程调用技术AIDL
  3. js 递归下的循环
  4. Hibernate关联关系配置(一对多、一对一和多对多)
  5. 锋利的JQuery(六)
  6. [翻译]观察变换View Transform (Direct3D 9)
  7. mvc的一些知识点
  8. CLR via C# - Char_String
  9. ionic2 跳转子页面隐藏底部导航栏
  10. CBO 基于成本的优化器[基础]
  11. Java读取文件存储到mysql
  12. bzoj2655calc 容斥+dp
  13. Mac OS X 10.8.4下面XZ Utils(*.tar.xz)压缩解压缩命令工具的安装
  14. ITU-T E.800 有关服务质量(QoS)的术语定义
  15. Qt如何去掉按钮等控件的虚线框(焦点框)
  16. 学习了clipboard复制剪切插件的使用
  17. Introducing XAML Standard and .NET Standard 2.0
  18. Linux 系统 TCP优化
  19. 使用idea生成maven项目的jar包(转)
  20. Javascript高级编程学习笔记(7)—— 函数

热门文章

  1. Android10_原理机制系列_Activity窗口添加到WMS过程
  2. php(tp5)生成条形码
  3. BUUCTF 不一样的flag writeup
  4. 金九银十已到!Cookie 和 Session的这些知识你必须知道,面试必问!
  5. Druid配置和初始化参数 转发地址图片有
  6. IDM下载器的自定义设置
  7. Guitar Pro吉他指弹入门——双手泛音
  8. 【ACwing 100】InDec序列——差分
  9. Java继承的两道实验题目
  10. CentOS下搭建禅道Bug反馈系统