您好,登錄后才能下訂單哦!
這篇文章主要介紹如何使用Java實(shí)現(xiàn)藍(lán)橋杯G將軍,文中介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們一定要看完!
G將軍有一支訓(xùn)練有素的軍隊(duì),這個(gè)軍隊(duì)除開G將軍外,每名士兵都有一個(gè)直接上級(jí)(可能是其他士兵,也可能是G將軍)?,F(xiàn)在G將軍將接受一個(gè)特別的任務(wù),需要派遣一部分士兵(至少一個(gè))組成一個(gè)敢死隊(duì),為了增加隊(duì)員的獨(dú)立性,要求如果一名士兵在隊(duì)中,他的直接上級(jí)不能在隊(duì)中。
請(qǐng)問,G將軍有多少種派出隊(duì)的方法。注意,G將軍也可以作為一個(gè)士兵進(jìn)入隊(duì)。
輸入格式
輸入的第一行包含一個(gè)整數(shù)n,表示包括G將軍在內(nèi)的軍隊(duì)的人數(shù)。軍隊(duì)的士兵從1至n編號(hào),G將軍編號(hào)為1。
接下來n-1個(gè)數(shù),分別表示編號(hào)為2, 3, …, n的士兵的直接上級(jí)編號(hào),編號(hào)i的士兵的直接上級(jí)的編號(hào)小于i。
輸出格式
輸出一個(gè)整數(shù),表示派出隊(duì)的方案數(shù)。由于數(shù)目可能很大,你只需要輸出這個(gè)數(shù)除10007的余數(shù)即可。
樣例輸入1
3
1 1
樣例輸出1
4
樣例說明
這四種方式分別是:
選1;
選2;
選3;
選2, 3。
樣例輸入2
7
1 1 2 2 3 3
樣例輸出2
40
數(shù)據(jù)規(guī)模與約定
對(duì)于20%的數(shù)據(jù),n ≤ 20;
對(duì)于40%的數(shù)據(jù),n ≤ 100;
對(duì)于100%的數(shù)據(jù),1 ≤ n ≤ 100000。
資源約定:
峰值內(nèi)存消耗(含虛擬機(jī)) < 256M
CPU消耗 < 2000ms
請(qǐng)嚴(yán)格按要求輸出,不要畫蛇添足地打印類似:“請(qǐng)您輸入…” 的多余內(nèi)容。
所有代碼放在同一個(gè)源文件中,調(diào)試通過后,拷貝提交該源碼。
注意:不要使用package語句。不要使用jdk1.7及以上版本的特性。
注意:主類的名字必須是:Main,否則按無效代碼處理。
import java.util.ArrayList; import java.util.Scanner; public class Main { public static int n; public static int MOD = 10007; public static ArrayList<Integer>[] list; public static long[][] dp; public void dfs(int root) { dp[root][0] = 1; dp[root][1] = 1; for(int i = 0;i < list[root].size();i++) { int child = list[root].get(i); dfs(child); dp[root][0] = dp[root][0] * (dp[child][0] + dp[child][1]) % MOD; dp[root][1] = dp[root][1] * dp[child][0] % MOD; } } @SuppressWarnings("unchecked") public static void main(String[] args) { Main test = new Main(); Scanner in = new Scanner(System.in); n = in.nextInt(); list = new ArrayList[n + 1]; for(int i = 1;i <= n;i++) list[i] = new ArrayList<Integer>(); for(int i = 2;i <= n;i++) { int father = in.nextInt(); list[father].add(i); } dp = new long[n + 1][2]; test.dfs(1); long result = (dp[1][0] + dp[1][1] - 1) % MOD; System.out.println(result); } }
以上是“如何使用Java實(shí)現(xiàn)藍(lán)橋杯G將軍”這篇文章的所有內(nèi)容,感謝各位的閱讀!希望分享的內(nèi)容對(duì)大家有幫助,更多相關(guān)知識(shí),歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。