Solution -「CF 1586F」Defender of Childhood Dreams
2024-09-07 20:26:16
\(\mathcal{Description}\)
Link.
定义有向图 \(G=(V,E)\),\(|V|=n\),\(\lang u,v\rang \in E \Leftrightarrow u<v\)。求一个对 \(E\) 的染色 \(f\),使得 \(\not\exist \lang v_1,v_2,\cdots,v_{k+1} \rang, |\{f(v_i,v_{i+1})\mid i\in[1,k]\}|=1\),同时最小化 \(f\) 的值域大小。
\(2\le k<n\le10^3\)。
\(\mathcal{Solution}\)
设 \(f\) 的值域大小为 \(c\),断言:\(c\ge\lceil\log_k n\rceil\)。
证明 该结论的等价表述是,若 \(f\) 值域大小为 \(c\),则 \(n\le k^c\)。当 \(c=0\) 时显然成立。接下来对 \(c\) 进行归纳:
任取一个 \(f\) 值域大小为 \(c\) 的,被合法染色的图 \(G\),并任取某种颜色 \(x\),据此将点集 \(V\) 划分为 \(V_1,V_2,\cdots,V_t\),使得 \(V_i\) 的导出子图中不存在颜色为 \(x\) 的边。这些点集之间的连边颜色全部为 \(x\),所以 \(t\le k\)。而仅考虑某个 \(V_i\) 的导出子图,它至多用 \(c-1\) 中颜色染色,由归纳假设,\(|V_i|\le k^{c-1}\),继而 \(|V|=\sum |V_i|\le k\cdot k^{c-1}=k^c\)。 \(\square\)
模仿归纳方法得到构造方法:划分点集,将点集之间的边染色,而后递归处理。复杂度上限为 \(\mathcal O(n^2)\)。
\(\mathcal{Code}\)
/*+Rainybunny+*/
#include <bits/stdc++.h>
#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )
#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )
const int MAXN = 1e3;
int n, k, mxc, ans[MAXN + 5][MAXN + 5];
inline void solve( const int l, const int r, const int clr ) {
if ( l == r ) return ;
if ( clr > mxc ) mxc = clr;
int s = ( r - l + k ) / k;
for ( int i = l; i <= r; i += s ) {
solve( i, std::min( i + s - 1, r ), clr + 1 );
rep ( u, l, i - 1 ) rep ( v, i, std::min( i + s - 1, r ) ) {
ans[u][v] = clr;
}
}
}
int main() {
scanf( "%d %d", &n, &k );
solve( 1, n, 1 );
printf( "%d\n", mxc );
rep ( i, 1, n ) rep ( j, i + 1, n ) printf( "%d ", ans[i][j] );
putchar( '\n' );
return 0;
}
最新文章
- Maven 的插件和生命周期的绑定
- 使用Navicat修改SQLite数据库提示:no such collation sequence: LOCALIZED
- Struct2
- Codeforces 543D. Road Improvement (树dp + 乘法逆元)
- 用imagemagick和tesseract-ocr破解简单验证码
- 安装tomcat 证书
- KEIL 伪指令
- php的引用
- BZOJ-1923-外星千足虫-SDOI2010
- OC语法7——内存管理之@property参数
- Block使用的简单总结
- <;select>;设置multiple=";multiple";属性后 下拉框全部展开了 不再是折叠的怎么回事
- 【Linux】 升级CentOS6的内核到3.10
- there was no endpoint listening at net.pipe://localhost/PreviewProcessingService/ReportProcessing
- Spring Boot SSL
- mysqlfrm初步使用
- redux的源码解析
- BZOJ 1232 安慰奶牛题解
- xubuntu无法进图形界面问题
- 自定义Write节点的afterrender属性
热门文章
- spring boot 启动警告 WARN 15684 --- [ restartedMain] c.n.c.sources.URLConfigurationSource : No URLs will be polled as dynamic configuration sources. 解决
- Zabbix监控报警Lack of free swap space on Zabbix server解决办法
- MASA Framework - 整体设计思路
- 《手把手教你》系列技巧篇(五十六)-java+ selenium自动化测试-下载文件-上篇(详细教程)
- 【Java】main方法的理解
- 学习javaScript必知必会(4)~事件、事件绑定、取消事件冒泡、事件对象
- 进程池与线程池基本使用、协程理论与实操、IO模型、前端、BS架构、HTTP协议与HTML前戏
- 【记录一个问题】android ndk下设置线程的亲缘性,总有两个核无法设置成功
- unity3d百度语音合成mp3流转换byte[]失败
- Collection类集