题目链接:uva 1326 - Jurassic Remains
题目大意:给出n个字符串,每个字符串由大写字母组成(每个字母最多出现一次),问说找出尽量多的字符串,使得这些字符串中任意字母出现的次数均为偶数。
解题思路:
方法1:暴力枚举,o(2^24)的复杂度18s还是hold的住得。
#include <stdio.h>
#include <string.h>
const int N = 105;
int n, k[N], c[N], v[N], ans;
int handle(char* s) {
int len = strlen(s), k = 0;
for (int i = 0; i < len; i++)
k = k ^ (1<<(s[i]-'A'));
return k;
}
void init () {
ans = 0;
memset(v, 0, sizeof(v));
memset(c, 0, sizeof(c));
char word[N];
for (int i = 0; i < n; i++) {
scanf("%s", word);
k[i] = handle(word);
}
}
void dfs (int d, int s, int cnt) {
if (d >= n) {
if (s == 0 && cnt > ans) {
memcpy(v, c, sizeof(c));
ans = cnt;
}
return;
}
c[d] = 0;
dfs (d + 1, s, cnt);
c[d] = 1;
dfs (d + 1, s ^ k[d], cnt + 1);
c[d] = 0;
}
void put () {
printf("%d\n", ans);
int x = 0;
for (int i = 0; i < 24; i++) if (v[i]) {
if (x++) printf(" ");
printf("%d", i + 1);
}
printf("\n");
}
int main () {
while (scanf("%d", &n) == 1) {
init();
dfs(0, 0, 0);
put();
}
return 0;
}
方法2:中间相遇法,首先如果对于一个字符串用一个二进制数来表示的话,对应选出若干个字符串既可以用这些二进制数取亦或所得到的数来表示,如果为0即为满足。中间相遇法即将n差分成两部分来枚举,当两个状态相同的话,相亦或肯定为0.
#include <stdio.h>
#include <string.h>
#include <map>
using namespace std;
const int N = 105;
int n, k[N], ans;
map<int, int> g;
int bitCount(int x) {
return x == 0 ? 0 : bitCount(x >> 1) + (x&1);
}
int handle(char* s) {
int len = strlen(s), k = 0;
for (int i = 0; i < len; i++)
k ^= (1<<(s[i]-'A'));
return k;
}
void init () {
ans = 0;
g.clear();
char word[N];
for (int i = 0; i < n; i++) {
scanf("%s", word);
k[i] = handle(word);
}
}
void solve () {
int mid = n >> 1;
for (int i = 0; i < (1<<mid); i++) {
int s = 0;
for (int j = 0; j < mid; j++) if (i & (1<<j)) {
s ^= k[j];
}
if (!g[s] || bitCount(g[s]) < bitCount(i)) g[s] = i;
}
int t = n - mid;
for (int i = 0; i < (1<<t); i++) {
int s = 0;
for (int j = 0; j < t; j++) if (i & (1<<j)) {
s ^= k[mid + j];
}
if (g[s] && bitCount(g[s]) + bitCount(i) > bitCount(ans)) {
ans = (i<<mid) ^ g[s];
}
}
}
void put () {
int x = 0;
printf("%d\n", bitCount(ans));
for (int i = 0; i < n; i++) if (ans & (1<<i)) {
if (x++) printf(" ");
printf("%d", i + 1);
}
printf("\n");
}
int main () {
while (scanf("%d", &n) == 1) {
init();
solve();
put();
}
return 0;
}
分享到:
相关推荐
侏罗纪时代的POV尿仙人掌python游戏-具有更多资产ig的Google Chrome Dino游戏的模仿产品?还没做完。您仍然可以玩它!
Jurassic
Jurassic库 c#后台执行js库,可子线程执行不需要ui线程
jurassic, 用于解析和执行JavaScript代码的.NET 库 什么是侏罗纪?Jurassic是ECMAScript语言和运行时的实现。 它旨在为. NET 提供最佳的性能和标准兼容的实现。 Jurassic不是面向最终用户的;而是打算集成到. NET ...
Jurassic Pack 1 2.2 与unity官方的模型差不多,有一丢丢差别
Jurassic Pack Vol I.rar
Hi! boys!Do you like to play game for cs?Yes?Oh!Free downlods the map,you can play games in the JURASSIC PARK!!!Please to free downlods NOW!
write a "C" program which estimates the probability that an explorer will safely escape from a dinosaur- and volcano-infested island ("Jurassic Island") by taking random walks across it. As well as ...
#h1 jurassic-park此应用程序已开发为SpringBoot应用程序。 该应用程序的要求是 Grails-2.4.5 MySQL的 #h3数据库配置数据库配置可用于在'jurassic-park / grais-app / conf / config.groovy'文件中进行修改 在该...
侏罗纪世界进化新标签扩展为您的Chrome浏览器带来了新外观。 安装侏罗纪世界进化新标签页主题,并享受精选的侏罗纪世界进化高清图像。 它带有一些很酷的属性,这些属性可以改善您的“新标签页”体验,例如:-每个新...
语言:Bahasa Indonesia,Bahasa Melayu,Deutsch,English,Filipino,Français,Kiswahili,Nederlands,Norsk,Tiếng Việt,Türkçe,català,dansk,eesti,español,hrvatski,italiano,latviešu,lietuvių,magyar,polski...
Jurassic Pack Vol. III Dinosaurs 侏罗纪包卷恐龙三Unity游戏模型资源unitypackage 版本2022 支持Unity版本2020.3.37或更高 侏罗纪包包含第三卷生物。 13 个游戏就绪的可玩生物,带有控制器、脚本和预制件。所有...
高二英语外研选修六 Module Jurassic ParkPPT课件.pptx
Jurassic Pack Vol. II Dinosaurs 侏罗纪包卷恐龙二号Unity游戏模型资源unitypackage 版本2022 支持Unity版本2020.3.37或更高 侏罗纪包包含第二卷生物。 13 个游戏就绪的可玩生物,带有控制器、脚本和预制件。所有...
带有高清侏罗纪世界堕落王国壁纸的新标签主题,专为侏罗纪世界堕落王国的恐龙迷制作。 侏罗纪世界堕落王国新标签-由FreeAddon提供安装我的侏罗纪世界堕落王国新标签页主题,每次您打开一个新标签页,即可享受侏罗纪...
Create React App入门该项目是通过引导的。可用脚本在项目目录中,可以运行:yarn start 在开发模式下运行应用程序。 打开在浏览器中查看它。 如果您进行编辑,则页面将重新加载。 您还将在控制台中看到任何棉绒错误...
侏罗纪世界演变的高清背景 带有打开的每个新标签的新墙纸。 有了我们的扩展程序,您每次打开一个新选项卡,都可以享受不同的侏罗纪世界进化论高清壁纸。 新标签不再是以前的样子。 现在,空白的起始页不在等式中。...
侏罗纪公园高清壁纸和新标签主题为最佳浏览体验 如何使用: - 通过单击“添加到Chrome”按钮,安装此扩展,将自动添加。扩展加载时等待几秒钟,最好的遵循! - 在左上角,“齿轮”。加载设置面板,您可以在其中使用...