題意：
? ? ? 給你n個(gè)字符串，讓你在里面找到一個(gè)字符串集合使得這些字符串中所有的字母出現(xiàn)的次數(shù)和為偶數(shù)，輸出集合的最大個(gè)數(shù)，和ASCII最小的解。


思路：
? ? ? 考慮到每個(gè)字符串中所有的字符都是有大寫字母組成的，我們可以把每個(gè)字符串都用一個(gè)26位長(zhǎng)的二進(jìn)制數(shù)表示，比如第一位表示A,那么當(dāng)?shù)谝晃粸?的時(shí)候就是說明A出現(xiàn)了偶數(shù)次，1表示出現(xiàn)了奇數(shù)次（直接異或），那么我們要找到滿足題意的集合也就是可以轉(zhuǎn)化成我們?cè)趎個(gè)26位長(zhǎng)的二進(jìn)制數(shù)中找到最多的數(shù)字，使得他們異或一起最后等于0（等于0表示所有的字母都是偶數(shù)次），這樣我們有兩種方式，一種是我自己寫的暴搜，時(shí)間復(fù)雜度O(2^n)沒有超時(shí)，如果是要完全的暴力建議去寫搜索，不要寫for循環(huán)枚舉，因?yàn)閒or的枚舉在判斷的時(shí)候時(shí)間復(fù)雜度還要*n，這樣估計(jì)就超時(shí)了，寫搜索可以在狀態(tài)轉(zhuǎn)換的時(shí)候把值算出來，這樣最后的時(shí)候不用可以去算什么，直接if判斷，減少了一個(gè)n,時(shí)間復(fù)雜度應(yīng)該是妥妥的O(2^n),還有就是再說下白書上的方法，用的是中途相遇法，這個(gè)方法感覺很好，讓我想起了雙向廣搜，這個(gè)題目我想是不是應(yīng)該叫雙向深搜，大體思路就是把要枚舉的東西分成兩部分分別枚舉，然后在結(jié)合一起去判斷，時(shí)間復(fù)雜度可以降低不少，白書給的時(shí)間復(fù)雜度我感覺算的有問題，我算的是O(1.44^n*n/2),兩個(gè)方法我都試了，中途相遇法的時(shí)間復(fù)雜度優(yōu)化了很多，下面是兩個(gè)方法的AC代碼。






直接暴力深搜 時(shí)間復(fù)雜度
O（2^n） ?runtime ?2.292?


#include<map>
#include<string>
#include<stdio.h>
#include<string.h>


using namespace std;


int num[30];
char str[1100];
int Ans ,Anszt;


void DFS(int nowid ,int nows ,int nownum ,int nowzt)
{
? ?if(nowid == 0)
? ?{
? ? ? if(nownum == 0)
? ? ? {
? ? ? ? ?if(Ans <= nows)
? ? ? ? ?{
? ? ? ? ? ? Ans = nows;
? ? ? ? ? ? Anszt = nowzt;
? ? ? ? ?}
? ? ? }
? ? ? return ;
? ?}
? ?DFS(nowid - 1 ,nows ,nownum ,nowzt * 2);
? ?DFS(nowid - 1 ,nows + 1 ,nownum ^ num[nowid] ,nowzt * 2 + 1);
}


int main ()
{
? ?int n ,i ,j ,now;
? ?while(~scanf("%d" ,&n))
? ?{
? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? {
? ? ? ? ?scanf("%s" ,str);
? ? ? ? ?now = 0;
? ? ? ? ?int l = strlen(str) - 1;
? ? ? ? ?for(j = 0 ;j <= l ;j ++)
? ? ? ? ?now = now ^ (1 << (str[j] - 'A'));
? ? ? ? ?num[i] = now;
? ? ? }
? ? ? Ans = Anszt = 0;
? ? ? DFS(n ,0 ,0 ,0);
? ? ? printf("%d\n" ,Ans);
? ? ? int nowid = 1 ,mk = 0;
? ? ? while(Anszt)
? ? ? {
? ? ? ? ?if(Anszt&1)?
? ? ? ? ?{
? ? ? ? ? ? if(mk) printf(" %d" ,nowid);
? ? ? ? ? ? else printf("%d" ,nowid);
? ? ? ? ? ? mk = 1;
? ? ? ? ?}
? ? ? ? ?Anszt /= 2;
? ? ? ? ?nowid ++;
? ? ? }
? ? ? printf("\n");
? ?}
? ?return 0;
}
? ?


中途相遇法 ?時(shí)間復(fù)雜度
O(2^(n/2)*n/2) => 1.44^n*n/2 ?runtime 0.029
#include<map>
#include<string>
#include<stdio.h>
#include<string.h>


using namespace std;


map<int ,int>mark;
int num[30];
char str[1100];


int bitcount(int x)
{
? ?return x == 0 ? 0 : bitcount(x / 2) + (x & 1);
}?


int main ()
{
? ?int n ,i ,j ,now ,l;
? ?while(~scanf("%d" ,&n))
? ?{
? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? {
? ? ? ? ?scanf("%s" ,str);
? ? ? ? ?now = 0 ,l = strlen(str) - 1;
? ? ? ? ?for(j = 0 ;j <= l ;j ++)
? ? ? ? ?now = now ^ (1 << (str[j] - 'A'));
? ? ? ? ?num[i] = now;
? ? ? }
? ? ? mark.clear();
? ? ? int n1 = n / 2;
? ? ? int n2 = n - n1;
? ? ? for(i = 0 ;i < (1 << n1) ;i ++)
? ? ? {
? ? ? ? ?int x = 0;
? ? ? ? ?for(j = 1 ;j <= n1 ;j ++)
? ? ? ? ?if(i & (1 << (j-1))) x ^= num[j];
? ? ? ? ?if(!mark.count(x) || bitcount(i) > bitcount(mark[x]))
? ? ? ? ?mark[x] = i;
? ? ? }
? ? ? int Ans = 0;
? ? ? for(i = 0 ;i < (1<<n2) ;i ++)
? ? ? {
? ? ? ? ?int x = 0;
? ? ? ? ?for(j = 1 ;j <= n2 ;j ++)
? ? ? ? ?if(i & (1 << (j-1))) x ^= num[n1 + j];
? ? ? ? ?if(mark.count(x) && bitcount(i) + bitcount(mark[x]) > bitcount(Ans))
? ? ? ? ?Ans = (i << n1) ^ mark[x];
? ? ? }
? ? ? printf("%d\n" ,bitcount(Ans));
? ? ? int mk = 0,Anszt = Ans ,nowid = 1;
? ? ? while(Anszt)
? ? ? {
? ? ? ? ?if(Anszt&1)?
? ? ? ? ?{
? ? ? ? ? ? if(mk) printf(" %d" ,nowid);
? ? ? ? ? ? else printf("%d" ,nowid);
? ? ? ? ? ? mk = 1;
? ? ? ? ?}
? ? ? ? ?Anszt /= 2;
? ? ? ? ?nowid ++;
? ? ? }
? ? ? printf("\n");
? ? ??
? ? ? ? ?
? ?}
? ?return 0;
}
? ? ??
? ? ? ? ?
? ? ??

總結(jié)

以上是生活随笔為你收集整理的LA2965侏罗纪（异或和为0的最大数字个数）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。