UVa 1326 - Jurassic Remains(枚举子集+中途相遇法)
2024-09-04 14:42:00
训练指南p.59
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map> using namespace std; const int MAXN = ; int N;
int A[MAXN];
char str[];
map<int , int> table; int bitcount( int x )
{
int res = ;
while ( x )
{
if ( x & ) ++res;
x >>= ;
}
return res;
} int main()
{
while ( scanf( "%d", &N ) == )
{
for ( int i = ; i < N; ++i )
{
scanf( "%s", str );
A[i] = ;
for ( int j = ; str[j]; ++j )
A[i] |= ( << ( str[j] - 'A' ) );
} table.clear(); int n1 = N / , n2 = N - n1;
for ( int i = ; i < ( << n1 ); ++i )
{
int tmp = ;
for ( int j = ; j < n1; ++j )
if ( i & ( << j ) )
tmp ^= A[j];
if ( !table.count(tmp) || bitcount(i) > bitcount( table[tmp] ) ) table[tmp] = i;
} int ans = ;
for ( int i = ; i < ( << n2 ); ++i )
{
int tmp = ;
for ( int j = ; j < n2; ++j )
if ( i & ( << j ) ) tmp ^= A[ n1 + j ];
if ( table.count(tmp) && bitcount(ans) < bitcount(i) + bitcount(table[tmp]) )
ans = ( i << n1 ) | table[tmp];
} printf("%d\n", bitcount(ans) );
bool first = false;
for ( int i = ; i < N; ++i )
if ( ans & ( << i ) )
{
if ( first ) putchar(' ');
printf("%d", i + );
first = true;
}
puts("");
}
return ;
}
最新文章
- [原创.数据可视化系列之二]使用cesium三维地图展示美国全球军事基地分布
- JSch - Java实现的SFTP(文件下载详解篇)
- javascript 中的 true 或 false
- static 变量
- linux普通用户权限设置为超级用户权限方法、sudo不用登陆密码
- JS调用android逻辑方法
- 性能测试之LoardRunner 手动关联二
- Java爬虫,信息抓取的实现(转)
- Python 入门介绍
- 分布式缓存Memcached/memcached/memcache详解及区别
- 过程 sp_addextendedproperty, 对象无效。不允许有扩展属性,或对象不存在。
- Android开发中碰到的一个ANR问题。
- Zabbix3.4监控平台部署
- jq通过对象获取其ID值
- LeetCode(59):螺旋矩阵 II
- SqlServer添加触发器死锁的原因
- InnoDB Lock浅谈
- 无需Java代码通过JHipster生成有安全验证的微服务应用
- 禁用表单元素 &;&; 禁止选中
- POJ 1442 splay
热门文章
- ABP学习 解决:Update-Database : 无法将“Update-Database”项识别为 cmdlet、函数、脚本文件或可运行程序的名称的问题
- data-ng-repeat 指令
- 【Java】多线程相关复习—— 线程的创建、名字、运行情况以及顺序控制(join方法) 【一】
- 基于java开发的开源代码GPS北斗位置服务监控平台
- HTML语义化的重要性
- phpstorm 安装XeDbug
- php结合redis实现高并发下的抢购、秒杀功能【转】
- [Hdu4825]Xor Sum(01字典树)
- python-9-IO编程
- python开发基础之字符编码、文件处理和函数基础