GDUFS 2018信息学院程序设计新手赛（正式赛）题解
緊張刺激的新手賽結束了……有驚無險啊啊啊，雖然中途OJ炸了一次……很快就修復，感謝大家耐心的等待！
謝謝大家！！！
題解開始前，先向大家道個歉，題目還是很多誤導人的地方，測評機崩了，導致很多人題沒過。接下來都會一一解釋……希望大家能理解……不過題目區分度還是達到了預期，有的同學表現也很搶眼。
?
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.5Sample Output
No難易度：?
題解：直接判斷即可
坑點：注意字符數組判斷要用strcmp，不能直接==，如果要直接==就用string類
#include<iostream> using namespace std; int main(){string url;cin>>url;if(url=="222.201.101.7")cout<<"Yes";else cout<<"No";return 0; }?
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 10Sample Output
樣例輸出1： 0樣例輸出2： 1樣例輸出3： 81?
難易度：?
題解：三角形定理，任意兩邊之和大于第三遍即可。
坑點：無
#include<bits/stdc++.h> using namespace std; const int MAXN=100005; typedef long long ll;int a[3];int main(){scanf("%d%d%d",&a[0],&a[1],&a[2]);sort(a,a+3);if(a[0]+a[1]>a[2]){cout<<0<<endl;}else{cout<<a[2]-a[0]-a[1]+1<<endl;}return 0; }?
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： 4Sample Output
樣例輸出1： 0樣例輸出2： 3樣例輸出3： 2?
難易度：?
題解：思維題，偶數輸出N/2，奇數輸出N，1輸出0
坑點：樣例都給出來了，無坑點
#include <bits/stdc++.h> using namespace std; int main(){int N;scanf("%d",&N);if(N==1)cout<<0<<endl;else if(N%2==1)cout<<N<<endl;elsecout<<N/2<<endl;return 0; }?
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 10Sample Output
樣例輸出1： 1樣例輸出2： 2樣例輸出3： 9?
難易度：??
題解：簡單思維，實際上，平均走是最優的，所以我們只要算出中點，然后直接計算即可。
坑點：看你能不能想得出來。
#include <iostream> #include <algorithm> #include <string.h> #include <vector> #include <memory.h> #include <bitset> #include <map> #include <deque> #include <math.h> #include <stdio.h> using namespace std; int main() {int a,b;cin>>a>>b;int m=(a+b)/2;if(a>b)swap(a,b);long long int ans=0;for(int i=1;i<1000;i++){if(a==m)break;ans+=i;a++;}for(int i=1;i<1000;i++){if(b==m)break;ans+=i;b--;}cout<<ans<<endl;return 0; }?
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 2Sample Output
樣例輸出1： shunzi樣例輸出2： jingang樣例輸出3： hulu樣例輸出4： lanpai?
難易度：??
題解：無
坑點：仔細讀題，另外善用排序。
#include <iostream> #include <algorithm> #include <string.h> #include <vector> #include <memory.h> #include <set> #include <map> #include <deque> #include <math.h> #include <stdio.h> using namespace std; int main() {int a[5];for(int i=0;i<5;i++)scanf("%d",&a[i]);sort(a,a+5);map<int,int> s;for(int i=0;i<5;i++)s[a[i]]++;if((a[0]==a[1]-1&&a[1]==a[2]-1&&a[2]==a[3]-1&&a[3]==a[4]-1)||(a[0]==1&&a[1]==10&&a[2]==11&&a[3]==12&&a[4]==13))printf("shunzi\n");else if(s.size()==2&&(s.begin()->second==2||s.begin()->second==3))printf("hulu\n");else if(s.size()==2&&(s.begin()->second==1||s.begin()->second==4))printf("jingang\n");elseprintf("lanpai\n");return 0; }?
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 5Sample Output
樣例輸出1： 3 9 15樣例輸出2： 100 99 3 300 101難易度：???
題解：很多人以為是簡單題，然后直接算，其實這樣的時間復雜度是不可以接受的，所以很多人都收到了Runtime Error和Time Limited? Exceed錯誤。所以我們要優化我們的算法。這里引入一個前綴和的概念。假設前i項的和為sum[i]，那么我們要計算L~R的和就只需要一個公式，sum[R] - sum[L-1] 即可。為啥這樣可以，自己思考。然后對于每一個sum[i]我們預處理出來即可。
坑點：暴力算會超時
#include<bits/stdc++.h> using namespace std; int a[1000005]; int sum[1000005]; int main() {int N,Q;scanf("%d%d",&N,&Q);for(int i=1;i<=N;i++){scanf("%d",&a[i]);sum[i]=sum[i-1]+a[i];}int L,R;while(Q--){scanf("%d%d",&L,&R);printf("%d\n",sum[R]-sum[L-1]);}return 0; }?
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 0Sample Output
樣例輸出1： 2樣例輸出2： 2樣例輸出3： 1難易度：???
題解：邏輯題，實際上我在樣例解釋中已經解釋得很清楚了。我們只需要計算缺了多少個數和多了多少個數即可。
坑點：注意非負整數包括0.
#include<bits/stdc++.h> using namespace std; int a[200]; int main(){int n,m;cin>>n>>m;for(int i=0;i<n;i++)cin>>a[i];int i;int num=0;//計算集合里比M小的數有多少個，直接枚舉每一個數看看集合里有沒有for(i=0;i<m;i++){for(int j=0;j<n;j++){if(a[j]==i){num++;}}}//看看有沒有跟M大小一個的數，有的話需要一個刪除操作。這里aaa要么0要么1.int aaa=0;for(int j=0;j<n;j++){if(a[j]==m){aaa++;}}//答案cout<<m-num+aaa<<endl;return 0; }?
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 1Sample Output
樣例輸出1： 4樣例輸出2： 5難易度：??
題解：小學數學題，直接算即可。
坑點：注意取整問題，和變量名字別搞錯
#include<bits/stdc++.h> using namespace std; int k,n,s,p; int main() {cin>>k>>n>>s>>p;cout<<(int)(ceil((int)(ceil(n/(double)(s)))*k/(double)(p)))<<endl;return 0; }?
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： ababSample Output
樣例輸出1： 1樣例輸出2： 10樣例輸出3： 20HINT
?
對于aba他的所有不同的子串有
?
a（出現了兩次）
?
b（出現了一次）
?
ab（出現了一次）
?
ba（出現了一次）
?
aba（出現了一次）
?
所以總的答案為 1*2+1*1+2*1+2*1+3*1 = 10
?
?
?
對于abab，他的所有不同的子串有
?
a（出現了兩次）
?
b（出現了兩次）
?
ab（出現了兩次）
?
ba（出現了一次）
?
aba（出現了一次）
?
bab（出現了一次）
?
abab（出現了一次）
?
所以答案為 1*2+1*2 +2*2+2*1+3*1+3*1+4*1 = 20
?
難易度：????
題解：題目要求的是，一個字符串中，所有不同的子串出現的次數乘以他的長度的和。乍一看很難的樣子，實際上我們只需要稍作分析，就會發現其實是一個簡單題。我們把不同的子串出現的次數這個限制去掉，改成所有子串出現的次數乘以他的長度的和。那么我們就會發現，每一個子串出現的次數都是1次。所以答案就會變成一個很簡單的公式了。我們假設原字符串長度為N，那么答案就是，長度為N的子串有一個，長度為N-2的子串有兩個，長度為N-3的子串有三個。。。然后直接計算出和即可。
#include <iostream> #include <algorithm> #include <string.h> #include <vector> #include <memory.h> #include <set> #include <map> #include <deque> #include <math.h> #include <stdio.h> using namespace std; int main() {string str;cin>>str;int N=str.length();int sum=0;for(int i=1;i<=N;i++){sum+=i*(N-i+1);}printf("%d\n",sum);return 0; }?
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： 1000000000Sample Output
樣例輸出1： 1樣例輸出2： 2樣例輸出3： 5樣例輸出4： 181?
難易度：????????
解題思路：這實際上是一道數學題，直接百度1/X + 1/Y = 1/N 即可找到詳細題解。https://www.cnblogs.com/GHzz/p/8644625.html
坑點：要會因式分解公式
#include<iostream> using namespace std; typedef long long int ll; int main(){ll n;cin>>n;n=n*n;ll sum = 1;for(ll i = 2; i*i <= n; i++){int cou = 0;if(n%i==0){cou = 1;n /= i;while(n%i==0){cou++;n /= i;}}if(cou != 0){sum = sum*(cou+1);}}if(n != 1){sum = sum*2;//剩下一個質數(1+1)}if(sum==1 && n==1){sum = 1;}cout<<(sum-1)/2+1<<endl;return 0; }?
總結
以上是生活随笔為你收集整理的GDUFS 2018信息学院程序设计新手赛（正式赛）题解的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： php顺序结构例题,php顺序结构就象一
- 下一篇： 什么是CMM