GDUFS 2018信息学院程序设计新手赛（正式赛）Java版题解
Problem A: HELLO
Description
《絕地求生》(PUBG) 是一款戰術競技型射擊類沙盒游戲 。 該游戲中，玩家需要在游戲地圖上收集各種資源，并在不斷縮小的安全區域內對抗其他玩家，讓自己生存到最后。游戲《絕地求生》除獲得G-STAR最高獎項總統獎以及其他五項大獎 ，還打破了7項吉尼斯紀錄。小洪是這個游戲的狂熱愛好者，就在他今天準備“吃雞”的時候他的舍友小權突然提醒他今天是新手賽！他果斷停止游戲，沖向實驗室，輸入了今天的比賽地址222.201.101.7，但是他發現登不上網站！于是他向你求救！
Input
輸入只有一行，由不超過20個字符組成字符串，字符串僅由數字和字符“.”組成，判斷其是否是今天的比賽網址。
Output
如果是輸入的字符串是 “222.201.101.7” （不包括雙引號），那么輸出"Yes"，否則輸出 “No”
Sample Input
222.201.101.5
Sample Output
No
簡單的字符串比較題，但是用“==”比較是不行的，這樣比較的是兩個字符串對象的引用，需要使用“equals”函數比較。
import java.util.Scanner;public class Main {static String pa = "222.201.101.7";public static void main(String[] args) {Scanner reader = new Scanner(System.in);String in = reader.next();if(in.equals(pa)) {System.out.println("Yes");} else {System.out.println("No");}} }Problem B: ORZ
Description
《英雄聯盟》(簡稱LOL)是由美國拳頭游戲(Riot Games)開發、中國大陸地區騰訊游戲代理運營的英雄對戰MOBA競技網游。游戲里擁有數百個個性英雄，并擁有排位系統、符文系統等特色養成系統。《英雄聯盟》還致力于推動全球電子競技的發展，除了聯動各賽區發展職業聯賽、打造電競體系之外，每年還會舉辦“季中冠軍賽”“全球總決賽”“All Star全明星賽”三大世界級賽事，獲得了億萬玩家的喜愛，形成了自己獨有的電子競技文化。小洪是英雄聯盟的狂熱愛好者，今天他決定學習三角形打野法。現在給你三條邊，小洪可以花費一點法力讓某一條邊的長度增加1，請問要使得這三條邊能組成三角形，最少需要多少法力？
Input
輸入只有一行，三個數字A,B,C，分別代表三條邊的長度。
所有數字范圍為 （1~100）
Output
一個整數，代表最少需要多少法力，才能使得這三條邊能組成一個三角形。
Sample Input
樣例輸入1：
3 4 5
樣例輸入2：
2 3 5
樣例輸入3：
100 10 10
Sample Output
樣例輸出1：
0
樣例輸出2：
1
樣例輸出3：
81
三角形兩邊之和大于第三邊，如果最小的兩邊相加都大于第三邊，直接輸出0即可，如不符合則計算出差了多少。
import java.util.Arrays; import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner reader = new Scanner(System.in);int[] tri = new int[3];for (int i = 0; i < 3; i++) {tri[i] = reader.nextInt();}Arrays.sort(tri);if(tri[0] + tri[1] > tri[2]) {System.out.println(0);return;}System.out.println(tri[2] - (tri[0] + tri[1]) + 1);} }Problem C: NIGHTMARE
Description
《陰陽師》是由中國網易移動游戲公司自主研發的3D日式和風回合制RPG手游。2016年6月1日11：00，《陰陽師》開放安卓首測 ；同年9月2日，登陸ios平臺于App Store首發 ；同年9月9日，陰陽師全平臺公測 。游戲中的和風元素是以《源氏物語》的古日本平安時代為背景設計的。游戲劇情以日本平安時代為背景，講述了陰陽師安倍晴明于人鬼交織的陰陽兩界中，探尋自身記憶的故事 。小洪是陰陽師的狂熱愛好者，今天他十連抽的時候抽到了3個SSR！于是他決定開個Party慶祝。在party中，有一個大Pizza~小洪要把它平均的分給N個小伙伴（包括他自己），那么小洪最少要切多少刀呢？我們假設 Pizza是圓的，并且不能傷害自己的小伙伴-_-||
Input
輸入只有一行，一個數字N，代表Party中有N個小伙伴。
所有數字范圍為 （1~100）
Output
要平均分的最少刀數
Sample Input
樣例輸入1：
1
樣例輸入2：
3
樣例輸入3：
4
Sample Output
樣例輸出1：
0
樣例輸出2：
3
樣例輸出3：
2
為什么要說不能切小伙伴呢？
以樣例2為例，1塊披薩分給3個小伙伴，只需要砍死兩個小伙伴即可平均分配，顯然比切比薩更優。
但是，披薩只能一刀刀切，小伙伴卻可以一刀砍死兩個，那么這里是輸出1還是2呢？
出于這一層考慮，禁止大家考慮切小伙伴的策略。
（魔鬼的胡說八道）
好吧，只考慮切披薩，那么偶數人只需要切一半人數的刀，奇數人則需要剛好切人數刀，只有一個人時不需要切。
至于為什么是這樣，請不明白的同學自己切切切。
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner reader = new Scanner(System.in);int in = reader.nextInt();if(in == 1) {System.out.println(0);return;}if(in % 2 == 0) {System.out.println(in / 2);}else {System.out.println(in);}} }Problem D: GAME
Description
《糖果傳奇》是由King開發的一款微策略消除手游，于2014年8月發行。游戲設置了超過500關的關卡，在游戲中，玩家可以通過三個或三個以上的糖果以不同方式的連接消除得分，碰撞開不同的障礙物完成任務。小洪是糖果傳奇的狂熱愛好者。他和他的女朋友都特別喜歡這個游戲，現在他們相約在某個地方一起玩這個游戲。我們假設他們的家在一個X軸上。小洪的家在 X1=a的位置，他女朋友在X2=b的位置。每個人都可以在X軸上行走任意多次。當一個人移動一次的時候，他的疲勞值會改變，疲勞值改變的規則如下：
第一次移動疲勞值增加1，第二次移動疲勞值增加2，第三次移動疲勞值增加3……舉個例子，小洪往右走了一步，再往左走了一步（回到初始位置），再往右走了一步，那么他一共走了三步，那么他的疲勞值為 1+2+3=6.
他們倆人會在某個整點相遇，請你幫他們計算，他們要相遇的最少的疲勞值之和。
Input
輸入有兩行，第一行1數字 a，代表小洪的初始位置
第二行一個數字b，代表他女朋友的初始位置
所有的數字范圍為 （1~1000）
Output
讓他們相遇的最少的疲勞值之和。
Sample Input
樣例輸入1：
3
4
樣例輸入2：
101
99
樣例輸入3：
5
10
Sample Output
樣例輸出1：
1
樣例輸出2：
2
樣例輸出3：
9
顯然你走一步我走一步是最優的，于是我們模擬這個過程就完事了。
先檢查一下輸入是不是左小右大，如果不是就交換一下，方便我們左走一下右走一下。
Problem E: ROAL
Description
《osu!》是一款基于《押忍！戰斗！應援團》、《精英節拍特工》和《太鼓達人》等商業游戲改編的免費同人音樂游戲，由Peppy （Dean Herbert）開發制作。小洪是osu狂熱愛好者。但是他今天想打鋤大地，在他的世界中。牌是沒有花色的。現在給你5張牌（1~13），要你判這五張牌能否組成順子，葫蘆，金剛
順子：五張牌是連續的，如1 2 3 4 5，5 6 7 8 9，9 10 11 12 13，10 11 12 13 1是順子，但是11 12 13 1 2和 12 13 1 2 3和13 1 2 3 4 不算順子。
葫蘆：三張帶一對。如，1 1 1 2 2,5 5 5 6 6,11 11 11 13 13.
金剛：四張帶一個。如1 1 1 1 2,13 13 13 13 1.
Input
輸入只有一行，每行5個數字，代表5張牌，數字的范圍為（1~13）題目保證數字出現的次數不會超過4次。
Output
如果是順子輸出“shunzi”
如果是葫蘆輸出“hulu”
如果是金剛輸出“jingang”
如果都不是輸出“lanpai”
Sample Input
樣例輸入1：
10 11 12 1 13
樣例輸入2：
5 5 5 5 4
樣例輸入3：
5 5 5 4 4
樣例輸入4：
11 12 13 1 2
Sample Output
樣例輸出1：
shunzi
樣例輸出2：
jingang
樣例輸出3：
hulu
樣例輸出4：
lanpai
我佛了，這題不用map這些庫類去寫純用if真的難寫。
為了讓諸位能看得懂，我就用if寫吧…
沒啥好說的這題，判斷就完事了。
但是要跟Java的同學說一聲抱歉，學校oj的java性能實在是太垃圾了，我這份代碼也會超時，這樣寫是沒有問題的，唯一一位用Java過的同學使用了BufferedReader，希望沒過的同學去了解一下。
import java.util.Arrays; import java.util.Scanner;public class Main {static int[] in = new int[5];public static void main(String[] args) {Scanner reader = new Scanner(System.in);for (int i = 0; i < 5; i++) {in[i] = reader.nextInt();}Arrays.sort(in);if(in[0] == 1 && in[1] == 10 && in[2] == 11 && in[3] == 12 && in[4] == 13) {System.out.println("shunzi");return;}boolean flag = false;for (int i = 0; i < 4; i++) {if(in[i] + 1 != in[i + 1]) {flag = true;break;}}if(!flag) {System.out.println("shunzi");return;}if(in[0] == in[1] && in[1] == in[2]) {if(in[2] != in[3] && in[3] == in[4]) {System.out.println("hulu");return;}if(in[2] == in[3] && in[3] != in[4]) {System.out.println("jingang");return;}}if(in[4] == in[3] && in[3] == in[2]) {if(in[2] != in[1] && in[1] == in[0]) {System.out.println("hulu");return;}if(in[2] == in[1] && in[1] != in[0]) {System.out.println("jingang");return;}}System.out.println("lanpai");} }Problem F: OMG
Description
《中國式家長》是一款由墨魚玩游戲開發的模擬養成游戲，游戲已經上架steam、wegame于2018年9月29日正式發售。
《中國式家長》是一款現實主義的模擬游戲，游戲模擬從出生到高考的整段過程，探討中國孩子與家長之間的關系。2018年10月，《中國式家長》的游戲在網絡上引發熱議。該游戲銷售剛滿一個月，已經在一家知名游戲商城上取得全球周銷量排行第2名。小洪是中國式家長的狂熱愛好者。今天他決定讓他的孩子小洲上清華！已知小洲高考的分數，請你計算一下他某幾科科目的分數和！我們假設在游戲的世界中，高考科目有很多，然后小洪會讓你查詢某個區間的分數和。
Input
輸入有多行，第一行兩個數字N和Q，代表游戲世界中有N個科目和小洪會問你Q個問題。第二行包括N個數字，由空格隔開，每個數字代表小洲一科的高考分數Ai。
接下來有Q行，每行包括兩個數字L和R，代表小洪要你告訴他這N個科目中，從第L個到第R個科目的分數的和
（1<=Ai<=100）
（1<=N<=100000）
(1<=Q<=100000)
(1<=L<=R<=N)
Output
對于每個查詢，輸出一個數字，代表該次查詢的分數和。每個數字占一行。
Sample Input
樣例輸入1：
5 3
1 2 3 4 5
1 2
2 4
1 5
樣例輸入2：
5 5
100 99 98 1 2
1 1
2 2
4 5
1 5
3 5
Sample Output
樣例輸出1：
3
9
15
樣例輸出2：
100
99
3
300
101
這題很快樂的，現場有很多人來問我為什么過不了。
（我樣例都過了交上去又是tle又是wa的怎么回事啊.jpg）
看看題目的數據范圍，數組長度十萬！查詢個數10萬！10萬個1到10萬的的累加不超時才怪。
有些精明的小朋友選擇了先求總數，然后根據查詢來決定是累加求和還是求出不需要求的部分再減掉，可喜可賀，贊賞這些小朋友！
但是如果我給你10萬個3萬到7萬的，那還是gg。
所以這題需要用到一個簡單的小算法，前綴和，前綴和每個位置都是前面所有數跟自己的累加，在區間查詢的時候，只需要用r位置減去l - 1位置，即可瞬間求出。
這題沒有2018學號開頭的做出來，一年的差距2333
import java.util.Scanner;public class Main {static int[] num = new int[100005];public static void main(String[] args) {Scanner reader = new Scanner(System.in);int n = reader.nextInt();int q = reader.nextInt();for (int i = 1; i <= n; i++) {num[i] += reader.nextInt();num[i + 1] += num[i];}int l, r;while (q-- > 0) {l = reader.nextInt();r = reader.nextInt();System.out.println(num[r] - num[l - 1]);}} }Problem G: CRAWLING
Description
《太吾繪卷》是ConchShip Games研發的一款以神話和武俠為題材的獨立游戲。玩家將扮演神秘的“太吾氏傳人”。
在《太吾繪卷》的世界中，你除了需要扮演神秘的“太吾氏傳人”，還將以不同的處世立場——或善、或惡、或中庸——投身于紛繁復雜的江湖之中。你不僅可以拜訪世界各地的武林門派，學習種類繁多的功法絕藝；還可以與人義結金蘭，或結下血海深仇；不僅可以興建自己的村莊，經營各種產業；還可以與自己的摯愛生兒育女，緣定三生；直到你終于面對太吾氏的宿敵，擊敗相樞劍冢，決定世界的命運！小洪是太吾繪卷的狂熱愛好者，同時他也很喜歡研究集合問題，最近他在研究邪惡集合，所謂邪惡集合，就是如果這個集合里不存在的最小的非負整數是X，那么這個集合就是邪惡的。現在小洪手里有一個集合，他想把他變成邪惡集合，每一步小洪可以刪掉集合里一個數，或者往集合里添加添加一個數，請問小洪最少需要多少步，才能使得這個集合變成邪惡集合！
Input
輸入有兩行，第一行兩個數字 N,X，代表初始集合的大小 ，和題目中的X
第二行包括N個各不相同的數字，代表集合初始的N個數字
所有的數字范圍為 （1~10000）
Output
要把這個集合變成邪惡集合的最少步數
Sample Input
樣例輸入1：
5 3
0 4 5 6 7
樣例輸入2：
5 1
1 2 3 4 5
樣例輸入3：
1 0
0
Sample Output
樣例輸出1：
2
樣例輸出2：
2
樣例輸出3：
1
快樂的循環求最小非負，簡單題，沒過太可惜了。
import java.util.Scanner;public class Main {static boolean[] vis = new boolean[205];public static void main(String[] args) {Scanner reader = new Scanner(System.in);int n, x, g = 0, cnt = 0;n = reader.nextInt();x = reader.nextInt();for (int i = 0; i < n; i++) {vis[reader.nextInt()] = true;}while (g != x) {while (vis[g] && g < x) {++g;}if (g != x) {++cnt;++g;}}if(vis[x]) {++cnt;}System.out.println(cnt);} }Problem H: KINGDOM
Description
《王者榮耀》是由騰訊游戲天美工作室群開發并運行的一款運營在Android、IOS、NS平臺上的MOBA類手機游戲，于2015年11月26日在Android、IOS平臺上正式公測。小洪是王者榮耀的狂熱愛好者，但是他最近玩膩了，決定返璞歸真，折紙飛機玩。他還邀請了他的ACM的小伙伴們一起玩耍。已知每張紙能夠折S個紙飛機，現在有K個小伙伴，每個小伙伴要折N個紙飛機。但是紙只能一包一包的買，已知每包紙有包含P張紙。現在要把紙分給每一個小伙伴，使得每個小伙伴都有足夠的紙去折屬于他的N個紙飛機，那么請問，他們最少要買多少包紙？注意，紙是不能共享的喔~
Input
輸入只有一行，每行4個數字，用空格隔開，分別為 K,N,S,P，每個數字所代表的的意思見上述題面。
所有數字范圍為 （1~10000）
Output
一個數字，代表最少要買多少包紙。
Sample Input
樣例輸入1：
5 3 2 3
樣例輸入2：
5 3 100 1
Sample Output
樣例輸出1：
4
樣例輸出2：
5
小學數學啊，快樂就完事了。
ceil是向上取整。
聽說奇奇哥哥和鴻鴻哥哥出過這題作為作業，好吧，其實這題來自codeforce。
Problem I: NECKLACE
Description
Codeforces是一家為計算機編程愛好者提供在線評測系統的俄羅斯網站。該網站由薩拉托夫國立大學的一個團體創立并負責運營。
小洪是Codeforces的狂熱愛好者，今天他決定打CF，今天CF的簽到題非常簡單，他決定讓你們來做~幸運的是，小洪已經幫你們翻譯好題目了。已知一個字符串，讓你求這個字符串的所有不同的非空子串的長度乘以該子串出現的次數的和。以下是具體解釋
子串：串中任意個連續的字符組成的子序列稱為該串的子串，比如有一個串 ababacab，以下串都是他的子串
ab（出現了三次），a（出現了四次），aba（出現了兩次），bab，ababcab（出現了一次）等
不同的子串：比如有一個串 ababcab，以下串都是他不同的子串
ab，a，aba，bab，ababcab，c等
子串的長度：即該子串的字符個數，如aba的長度為3，a的長度為1.
Input
輸入只有一行，包括一個只由小寫字母組成的字符串
字符串的長度為 （1~1000）
Output
這個字符串的所有不同的非空子串的長度乘以該子串出現的次數的和
Sample Input
樣例輸入1：
a
樣例輸入2：
aba
樣例輸入3：
abab
Sample Output
樣例輸出1：
1
樣例輸出2：
10
樣例輸出3：
20
HINT
對于aba他的所有不同的子串有
a（出現了兩次）
b（出現了一次）
ab（出現了一次）
ba（出現了一次）
aba（出現了一次）
所以總的答案為 12+11+21+21+3*1 = 10
對于abab，他的所有不同的子串有
a（出現了兩次）
b（出現了兩次）
ab（出現了兩次）
ba（出現了一次）
aba（出現了一次）
bab（出現了一次）
abab（出現了一次）
所以答案為 12+12 +22+21+31+31+4*1 = 20
聰哥：題目要求的是，一個字符串中，所有不同的子串出現的次數乘以他的長度的和。乍一看很難的樣子，實際上我們只需要稍作分析，就會發現其實是一個簡單題。我們把不同的子串出現的次數這個限制去掉，改成所有子串出現的次數乘以他的長度的和。那么我們就會發現，每一個子串出現的次數都是1次。所以答案就會變成一個很簡單的公式了。我們假設原字符串長度為N，那么答案就是，長度為N的子串有一個，長度為N-2的子串有兩個，長度為N-3的子串有三個。。。然后直接計算出和即可。
哈哈哈哈哈但是我是用后綴自動機過的啊哈哈哈好快樂啊不要阻止我。
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner reader = new Scanner(System.in);String in = reader.next();int sum = 0;for (int i = 0; i < in.length(); i++) {sum += i * (in.length() - i + 1);}System.out.println(sum);} }然后給你們感受一下后綴自動機的代碼：
#include<bits/stdc++.h> using namespace std; const int maxn = 1005; char s[maxn];struct Sam {int next[maxn << 1][26];int link[maxn << 1], step[maxn << 1];int endpos[maxn << 1];int a[maxn], b[maxn << 1];int sz, last, root;void init() {//如多次建立自動機，加入memset操作root = sz = last = 1;}void add(int c) {int p = last;int np = ++sz;last = np;endpos[np] = 1;step[np] = step[p] + 1;while(!next[p][c] && p) {next[p][c] = np;p = link[p];}if(p == 0) {link[np] = root;} else {int q = next[p][c];if(step[p] + 1 == step[q]) {link[np] = q;} else {int nq = ++sz;memcpy(next[nq], next[q], sizeof(next[q]));step[nq] = step[p] + 1;link[nq] = link[q];link[q] = link[np] = nq;while(next[p][c] == q && p) {next[p][c] = nq;p = link[p];}}}}void build() {init();for(int i = 0; s[i]; i++) {add(s[i] - 'a');}for(int i = 1; i <= sz; i++) {a[step[i]]++;}for(int i = 1; i <= step[last]; i++) {a[i] += a[i - 1];}for(int i = 1; i <= sz; i++) {b[a[step[i]]--] = i;}for(int i = sz; i > 1; i--) {int e = b[i];endpos[link[e]] += endpos[e];}}void solve() {build();int ans = 0;for(int i = 1; i <= sz; i++) {ans += ((step[link[i]] + 1) + step[i]) * (step[i] - step[link[i]]) / 2 * endpos[i];}printf("%d\n", ans);}} sam;int main() {scanf("%s", s);sam.solve();return 0; }真長，好處是根本不需要動腦子啊23333，大力ac就完事了。
Problem J: BECAUSE
Description
CTF（Capture The Flag）中文一般譯作奪旗賽，在網絡安全領域中指的是網絡安全技術人員之間進行技術競技的一種比賽形式。CTF起源于1996年DEFCON全球黑客大會，以代替之前黑客們通過互相發起真實攻擊進行技術比拼的方式。發展至今，已經成為全球范圍網絡安全圈流行的競賽形式，2013年全球舉辦了超過五十場國際性CTF賽事。小洪是ACM的狂熱愛好者，但是他也業余打打CTF，CTF涉及密碼學，在密碼學中素數是非常重要的一個東西，今天小洪在打CTF的時候，遇到了一個非常有意思的題目，他決定用ACM的方法去解決它，題目大意是這樣的，給你一個正整數N，要你求出所有滿足方程 1/X + 1/Y = 1/N 的正整數解的個數，即X>0，Y>0的解的個數。小洪已經解出了這道題目，他決定考考你，看看你是否也能解出來~
Input
輸入有包括一行，一個正整數N
所有的數字范圍為 （1<=N<=1000000000）（1后面9個0）
Output
滿足方程 1/X + 1/Y = 1/N 的正整數解的個數，其中X<=Y
Sample Input
樣例輸入1：
1
樣例輸入2：
3
樣例輸入3：
20180101
樣例輸入4：
1000000000
Sample Output
樣例輸出1：
1
樣例輸出2：
2
樣例輸出3：
5
樣例輸出4：
181
聰哥：這實際上是一道數學題，直接百度1/X + 1/Y = 1/N 即可找到詳細題解。我們最后可以把公式化簡為 N^2 = (N - X) * (N - Y) 所以答案就是求N^2的約數組合數。
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner reader = new Scanner(System.in);long n = reader.nextLong();n *= n;long sum = 1;for (long i = 2; i * i <= n; i++) {int check = 0;if(n % i == 0) {check = 1;n /= i;while (n % i == 0) {check++;n /= i;}}if(check != 0) {sum = sum * (check + 1);}}if(n != 1) {sum = sum * 2;}System.out.println((sum - 1) / 2 + 1);} }總結
以上是生活随笔為你收集整理的GDUFS 2018信息学院程序设计新手赛（正式赛）Java版题解的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 很好看的宇宙人404模板源码
- 下一篇： 【LaTex】3.2 数据结构(TikZ