柚子快報激活碼778899分享：藍(lán)橋杯刷題第四天

http://yzkb.51969.com/

思路：

? ? ? ?這道題很容易即可發(fā)現(xiàn)就是簡單的暴力即可完成題目，我們只需滿足所有數(shù)的和為偶數(shù)即可保證有滿足條件的分法，同時也不需要存下每個輸入的數(shù)據(jù)，只需要知道他是偶數(shù)還是奇數(shù)即可，因為我們只需要偶數(shù)個奇數(shù)搭配在一塊看成是偶數(shù)即可，然后對應(yīng)到上面我們就可以統(tǒng)計一組數(shù)據(jù)中奇數(shù)的個數(shù)就不需要多余的計算一個數(shù)據(jù)和，當(dāng)奇數(shù)個數(shù)為0時，情況就是取和不取問題組合情況為2的偶數(shù)的個數(shù)次方，當(dāng)奇數(shù)個數(shù)為奇數(shù)時，必不可能有滿足條件的情況，當(dāng)奇數(shù)個數(shù)為偶數(shù)且不為0時，每兩個奇數(shù)即可配合成一個偶數(shù)，奇數(shù)的組合數(shù)為2的（奇數(shù)的個數(shù)-1）次方。ps：可以理解為先取出一個奇數(shù)，其余奇數(shù)為取或者不取那么其中一個子集有奇數(shù)個數(shù)的奇數(shù)另一個必有偶數(shù)個數(shù)的奇數(shù)，只需把這些排列組合（有2的（奇數(shù)的個數(shù)-1）次方種情況）列出并把取出的奇數(shù)放到只有奇數(shù)個數(shù)的奇數(shù)那個子集即可滿足條件。

還有說因為奇數(shù)得成對出現(xiàn)所以2的n次方除2這個我理解不了我個人想法寫到了上面的ps上

核心代碼段：

代碼：

import java.util.*;

public class Main {

public static void main (String []args) {

int T;

Scanner a = new Scanner(System.in);

T=a.nextInt();

int sum[] = new int[T];

int n1=T;

while(T-->0){

int n;

n = a.nextInt();

//統(tǒng)計數(shù)量

int b;

//統(tǒng)計奇數(shù)和偶數(shù)的數(shù)目

int nj,no;

nj=no=0;

for(int i=0;i

b=a.nextInt();

if(b%2==0) {

++no;

}

else {

++nj;

}

}

if(nj%2==0) {

//將兩個奇數(shù)合并為一個偶數(shù)，而n個奇數(shù)共有n-1種組合然后就是排列組合問題了最多有2的n次方種情況

int num =nj+no;

if(nj!=0) {

num--;

}

sum[T]=1;

// for(int i=0;i

// sum[T]=sum[T]*2%1000000007;

// }

sum[T]=(int) (Math.pow(2,num)%1000000007);

}

else {

sum[T]=0;

}

}

a.close();

for(T=n1-1;T>=0;T--) {

System.out.println(sum[T]);

}

}

}

做題反思：

1.蜜汁報錯

藍(lán)橋杯代碼執(zhí)行結(jié)果為段錯誤即有越界行為

2.題目有多組數(shù)據(jù)要輸出下面兩種都是可以的1.把數(shù)據(jù)存下來然后一起輸出2.算出一個就輸出。

fig：情況1

fig：情況2

3.pow返回值為double，先進(jìn)行（int）會導(dǎo)致精度受損，固要先取余（藍(lán)橋杯很多時候都要先取余輸出低位的數(shù)值）再數(shù)據(jù)轉(zhuǎn)換。

eg：

sum[T]=(int) (Math.pow(2,nj)%1000000007);和

sum[T]=(int) Math.pow(2,nj)%1000000007;

的區(qū)別在第一個是先取余再轉(zhuǎn)int精度沒有丟失，后者是先轉(zhuǎn)int再取余精度在大范圍數(shù)的時候double變int會精度丟失導(dǎo)致在數(shù)值比較大的情況下二者的計算結(jié)果有所區(qū)別。

上者可以20個結(jié)果都對，后者只對4個結(jié)果（數(shù)據(jù)范圍小沒損失精度）

前者：

后者：

4.區(qū)分好continue和break的區(qū)別

continue是結(jié)束該輪循環(huán)，但并沒有跳出

break是結(jié)束循環(huán)即跳出循環(huán)

? ? ? ? 我一開始直接這樣導(dǎo)致一直找不到問題，因為就是遇到不滿足情況的就跳出循環(huán)了，后面的組使用都沒有去做，有點逆天了，敲得還是太少了

代碼其實十幾分鐘就敲完了但一直沒找出來問題，從晚上7.30到9.20才真正把這道題寫完有點ass了

官網(wǎng)一個我覺得寫得比較簡潔的版本（內(nèi)核是差不多的我進(jìn)行了模仿去debug上面的代碼而已）：

import java.util.*;

public class Main {

public static void main (String []args) {

int T;

Scanner a = new Scanner(System.in);

T=a.nextInt();

long sum[] = new long[T];

int n1=T;

while(T-->0){

int n;

n = a.nextInt();

//統(tǒng)計數(shù)量

int b;

//統(tǒng)計奇數(shù)和偶數(shù)的數(shù)目

int nj,no;

nj=no=0;

for (int j = 0; j < n; ++j) {

int e = a.nextInt();

if (e % 2 == 0) ++no;

else ++nj;

}

if (nj % 2 == 0)

sum[T] = (int) (Math.pow(2, no) * Math.pow(2, nj == 0 ? 0 : nj - 1) % 1000000007);

else sum[T] = 0;

}

a.close();

for(T=n1-1;T>=0;T--) {

System.out.println(sum[T]);

}

}

}

柚子快報激活碼778899分享：藍(lán)橋杯刷題第四天

http://yzkb.51969.com/

參考文章