【Cf Edu #47 G】Allowed Letters
2024-10-21 05:49:12
这个题大概就是每一个位置都有一个能填字符的限制(一个点集),给出已有的$n$个字符,问能填出的最小字典序的字符串。
总体思路是贪心,每一位尽量选最小的字符。
关键在于判断在某位选了一个字符后,接下来的位置能否满足限制。
考虑怎么判断有解,这里有一种网络流的思路:
- 有$6$个点,代表了$a - f$$6$个字符,有源点向这些点连边,流量为该字符的个数。
- 另有$2^{6}$个点,代表了各个点集,这些点向汇点连边,流量为该点集在所有限制中出现的次数。
- 如果某个点在一个点集中,则由该点向该点集连流量为$INF$的边。
易得,当流量满流时,有合法解。
当然,用网络流这个模型虽然很容易理解,但如果每一次检验都跑一边的话效率不行,出题人有一种基于调整法的网络流做法,在已知流网络上进行修改,但是我不是很懂,代码也较长,在此不做累述。
此处所用的做法十分简洁。有以下结论:
- 接下来仅考虑某位置选了某个字符后,判断剩下的一个后缀是否有解。
- 定义$cnt_{i}$表示字符$i$的剩余数量,$num_{s}$表示与集合$s$有交的位置(该位置上限制的字符集与$s$有交)。
- 枚举$2^{6}$个集合,当所有的集合都准合法时才有解。
- 准合法的定义是:$\sum_{i = a}^{f} (其中 i \in s) <= num_{s}$。
显然,如果$|s|=1$,即$s$中只有一个字符,那$s$准合法就是$s$合法(存在合法解)。
这里用于说明$s$是合法的当且仅当所有$s$的子集是合法的,且$s$是准合法的。
由于我们从小到大枚举所有集合,可以保证所有之前已经枚举过的集合已经合法了,即它的子集都合法,故只要判断该集合是否准合法。
关于这个条件的必要性:
- 如果$s$不是准合法的,显然$s$不会是合法的,因为没有足够位置放。
- 如果$s$的某一个子集$s_{i}$不合法,也就是$s_{i}$的有关位置$num_{s_{i}}$不够调计,那在$s$的有关位置$num_{s}$中并不会有更多的供$s_{i}$中的字符放置的位置,那$s$也将是不合法的。
关于这个条件的充分性:
- 如果所有它的子集都合法了,并且$s$准合法,就不会存在某一个集合中的元素占用了过多的公共位置,因为那样会导致另一个子集不合法,即产生矛盾。
这样的话就能在$O(nA2^{A})$解决问题了,其中$A$是字符集大小。
$\bigodot$技巧与套路:
- 利用网络流的模型
- 集合的枚举以及使用
#include <cstdio>
#include <cstring>
#include <algorithm> const int N = , ST = ; int n, m, bit[N], ans[N], cnt[], num[ST + ][N];
char s[N], ssr[]; inline int Check(int x) {
for (int st = ; st <= ST; ++st) {
int cnum = ;
for (int i = ; i < ; ++i) {
if ((st >> i) & ) cnum += cnt[i];
}
if (num[st][n] - num[st][x] < cnum) return ;
}
return ;
} int main() {
scanf("%s%d", s + , &m);
n = strlen(s + );
for (int i = ; i <= n; ++i) {
bit[i] = ST; ans[i] = -;
++cnt[s[i] - 'a'];
}
for (int i = , x; i <= m; ++i) {
scanf("%d%s", &x, ssr);
int le = strlen(ssr), st = ;
for (int j = ; j < le; ++j) {
st |= << (ssr[j] - 'a');
}
bit[x] &= st;
} for (int st = ; st <= ST; ++st) {
for (int i = ; i <= n; ++i) {
num[st][i] = num[st][i - ] + (bool)(bit[i] & st);
}
} for (int i = ; i <= n; ++i) {
for (int j = ; j < ; ++j) {
--cnt[j];
if (((bit[i] >> j) & ) && Check(i)) {
ans[i] = j; break;
}
++cnt[j];
}
if (ans[i] == -) {
puts("Impossible");
return ;
}
}
for (int i = ; i <= n; ++i) {
putchar(ans[i] + 'a');
} return ;
}
最新文章
- fstream文件操作
- HD1160FatMouse&#39;s Speed(最长单调递增子序列)
- linux 下面 jdk1.7 rpm 包的安装
- 使用JAVA反射初始化数组(转)
- HTML5入门7---";session的会话缓存";和";localStorage的cookie";缓存数据
- poj 3279 Fliptile
- gdb图形化调试工具总结
- boost::bind的使用方法
- 基于visual Studio2013解决C语言竞赛题之0518回文数
- linux权限和ntfs知识文件系统权限
- JS自动化测试 单元测试之Qunit
- 使用CLR Profiler分析.NET程序
- 2013 ACM/ICPC Asia Regional Chengdu Online hdu4731 Minimum palindrome
- 20190320xlVBA_考场座位设置
- ubuntu诸软件安装
- 【消灭代办】第2周 - 数组判断、开发工具、transform:matrix、Grid
- Forward团队-爬虫豆瓣top250项目-团队编程项目开发环境搭建过程
- flask再学习-重构!启动!
- 树莓派(Raspberry Pi)USB无线网卡自动连接,二代B
- 基于Ubuntu16.04搭建WordPress
热门文章
- 求二维数组最大子数组的和。郭林林&;胡潇丹
- 服务治理->; Spring Cloud Eureka
- 【Go】累加器的测试问题记录
- OpenFastPath(2):原生态Linux Socket应用如何移植到OpenFastPath上?
- python-两个筛子数据可视化(直方图)
- HTML和JS自解码机制
- IIS 无法加载 CSS,JS的问题
- Tomcat java zabbix 监控
- Python基础_可迭代的/迭代器/生成器
- Aspose.words Java基于模板生成word之循环图片