3n+1 問題(10)
Problem Description
考慮以下算法：
1. input n
2. print n
3. if n == 1 then STOP
4. if n is odd then n = 3 * n + 1
5. else n = n / 2
6. GOTO 2.
給定輸入 22，將輸出以下數(shù)字序列
據(jù)推測，對于任何輸入值，上述算法都將終止。盡管算法很簡單，但不知道這個猜想是否正確。
給定輸入 n，可以確定輸出的數(shù)字（包括 1）。對于給定的 n，這稱為 n 的循環(huán)長度。在上面的例子中，22 的循環(huán)長度是 16。
對于任何兩個數(shù)字 i 和 j，您將確定 i 和 j 之間（包括 i 和 j）所有數(shù)字的最大循環(huán)長度。
Input
輸入將由一系列整數(shù) i 和 j 組成（i ≤ j），每行一對整數(shù)（輸入保證不超過 10 行）。所有整數(shù)將小于 100000 且大于 0。您應該處理所有整數(shù)對，并且對于每對確定 i 和 j 之間（包括 i 和 j）的所有整數(shù)的最大循環(huán)長度。
Output
對于每對輸入整數(shù) i 和 j，您應該輸出 i，j，i 和 j 之間的最大循環(huán)長度。這三個數(shù)字應由一個空格分隔，一行中三個數(shù)字，每行輸入一行輸出。整數(shù) i 和 j 必須以與它們出現(xiàn)在輸入中相同的順序出現(xiàn)在輸出中（在同一行上）。
Sample Input
1 10
100 200
201 210
900 1000
Sample Output
1 10 20
100 200 125
201 210 89
900 1000 174
Hint
思路：
暴力打表or直接模擬
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int num[100010];
int cnt(int n)
{
int ans=0;
while(n!=1)
{
if(n%2==1)
n=3*n+1;
else
n/=2;
ans++;
}
return ans+1;
}
void init()
{
for(int i=1;i<=100000;i++)
num[i]=cnt(i);
}
int main()
{
init();
int n,m;
while(~scanf("%d%d",&n,&m))
{
int maxx=-1;
for(int i=n;i<=m;i++)
maxx=max(maxx,num[i]);
printf("%d %d %d\n",n,m,maxx);
}
return 0;
}
喵星人(5)
Problem Description
據(jù)說 CGY 家里的喵星人很聰明，會計算十以內(nèi)的加法。例如：現(xiàn)有數(shù)字 1，2，喵星人會用“Mia~Mia~Mia~”來表達答案是 3。
現(xiàn)在有請你來寫一個程序，模擬這個過程。
Input
輸入在一行中給出兩個區(qū)間在 [1,9] 的正整數(shù) A 和 B，用空格分隔
Output
在一行中輸出有 A+B 個“Mia~”(不包含引號)。
Sample Input
2 1
Sample Output
Mia~Mia~Mia~
Hint
思路：
題解？！//大家都過了，沒什么好說啦
#include <iostream>
using namespace std;
int main()
{
int a,b;
string mia="Mia~";
cin>>a>>b;
for(int i=0;i<a+b;i++)
cout<<mia;
cout<<endl;
return 0;
}
變換數(shù)字(20)
Problem Description
開學的第一節(jié)課是高數(shù)課，由于翁哥第一節(jié)課講的東西實在是太無聊了，F(xiàn)S 開始了“釣魚”模式。SLF 看 FS 實在是太困了，就給了他一個問題：現(xiàn)在黑板有一個數(shù)字 N，那么將這個數(shù)字反轉(zhuǎn)相加M次之后的數(shù)字是多少？例如現(xiàn)在的數(shù)字 N=87，M=4，那么 87+78 = 165，165+561=726，726+627=1353，1353+3531=4884，最后的答案為 4884。
FS 玩了十分鐘后覺得太無聊了，于是把這個 easy problem 交給你。
Input
輸入一行，N，M，其中 N 為不超過 100 位的正整數(shù)，N 為十進制數(shù)，M 為整數(shù)且 0<=M<=30
Output
輸出一行 ans，其中 ans 代表最后的答案
Sample Input
87 4
Sample Output
4884
Hint
87+78 = 165
165+561 = 726
726+627 = 1353
1353+3531=4884
思路：
方法一：C++模擬大數(shù)相加，即獲得一個數(shù)反轉(zhuǎn)過來相加即可
方法二：用JAVA得BigInteger輸入，然后reserve相加完事
題目都說了最大有100位的非負整數(shù)，當然是用大數(shù)啦，不然怎么可能是道20分題:)
#include <iostream>
#include <cmath>
using namespace std;
string get_add(string s,int n){
int len = s.size();
string t = s;
for(int i = 0;i < ceil((double)len);i++){
s[i] = (char) (s[i]+t[len-i-1]-'0');
}
for(int i = len-1;i >= 1;i--){
if(s[i]-'0'>=n){
s[i-1] = (char) (s[i-1]+1);
s[i] = (char) (s[i]-n);
}
}
t = "";
if(s[0]-'0'>=n){
t = "1";
s[0] = (char)(s[0]-n);
}
return t+s;
}
int main(){
string n;
int m;
cin>>n>>m;
while(m--){
n = get_add(n,10);
}
cout<<n;
return 0;
}
簡單的問題(15)
Problem Description
現(xiàn)在給你一個包含 0~9 和 A~F 的字符串，你需要求出在這個字符串中出現(xiàn)次數(shù)最多的字符，然后你需要求出這個字符串組成的十六進制轉(zhuǎn)換為十進制的數(shù)。
Input
第一行讀入一個整數(shù) T(1≤T≤10)，代表數(shù)據(jù)組數(shù)。
接下來給出 T 行，
每行給出這個字符串
輸入保證數(shù)組長度 ≤ 15
Output
每組輸出兩行
第一行表示出現(xiàn)次數(shù)最多的字符和出現(xiàn)的次數(shù)，用空格隔開。若有相同的次數(shù)，則輸出字典序最小的。
第二行表示轉(zhuǎn)換的十進制數(shù)
Sample Input
1
22011
Sample Output
4884
Hint
思路：
按題意模擬，注意一下輸出的數(shù)字要用long long來存
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
int main()
{
int T;
cin>>T;
while(T--)
{
string str;
cin>>str;
int n=str.length(),cnt[20];
long long number=0;
memset(cnt,0,sizeof(cnt));
for(int i=n-1;i>=0;i--)
{
if('A'<=str[i]&&str[i]<='F')
{
cnt[str[i]-'A'+10]++;
number+=pow(16,n-1-i)*(str[i]-'A'+10);
}
else
{
cnt[str[i]-'0']++;
number+=pow(16,n-1-i)*((str[i]-'0'));
}
}
int maxx=-1,pos;
char maxxc;
for(int i=0;i<16;i++)
{
if(maxx<cnt[i])
{
maxx=cnt[i];
pos=i;
}
}
if(pos<10)
maxxc=(char)('0'+pos);
else
maxxc=(char)('A'+pos-10);
cout<<maxxc<<" "<<maxx<<endl;
cout<<number<<endl;
}
return 0;
}
CGY 的第一課(5)
Problem Description
CGY開始學習編程了，今天是他上的第一課，老師讓他把輸入的數(shù)字照著原樣輸出。
Input
輸入一個實數(shù)
Output
輸出輸入的數(shù)字N
Sample Input
123.88
Sample Output
123.88
Hint
思路：
實數(shù)包括所有小數(shù)和整數(shù)，所以要用字符串輸入輸出
#include <iostream>
using namespace std;
int main()
{
string in;
cin>>in;
cout<<in<<endl;
return 0;
}
轟炸(10)
Problem Description
SLF 現(xiàn)在正準備用他的超能力轟炸一片區(qū)域，在這片區(qū)域中有 N 座建筑，每個建筑的血量都是 M，SLF 攜帶的炮彈只能對一座建筑造成 X 點傷害，但發(fā)射炮彈需要消耗他的能量,第一發(fā)炮彈的能量為 3 點,并且發(fā)射炮彈需要的能量每次遞增兩點，即下一發(fā)的能量=上一發(fā)的能量+2，幸運的是每當 SLF 摧毀了一座建筑，他都可以獲得 Y 點能量，SLF 一開始共有 Z 點能量，現(xiàn)在 SLF 想知道他最多可以炸掉多少建筑。
Input
第一行讀入一個整數(shù) T，代表數(shù)據(jù)組數(shù)。
接下來給出T行，
每行給出N,M,X,Y,Z
1≤T≤10，1≤N≤100，1≤M≤100，1≤X≤M，1≤Y≤100，1≤Z≤100
Output
每組數(shù)據(jù)輸出一行，代表最多可以炸掉多少建筑
Sample Input
1
5 5 2 1 20
Sample Output
1
Hint
摧毀一座建筑需要3發(fā)炮彈，需要的能量為3+5+7=15，摧毀一座建筑后獲得1點能量，所以總能量變?yōu)?0-15+1=6，第四發(fā)炮彈發(fā)射需要能量為9點，無法再次發(fā)射，所以總共摧毀一座建筑
思路：
按題意模擬計算。注意考慮可摧毀數(shù)量大于n的時候。
#include <iostream>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n,m,x,y,z,t;
cin>>n>>m>>x>>y>>z;
if(m%x) t = (m/x)+1;
else t = m/x;
int s1 = t*t + 2*t;
m = n;
while(n>0){
z-=s1;
if(z<0) break;
n--;
s1+=t*t*2;
z+=y;
}
cout<<m-n<<endl;
}
}
LXY 背單詞(20)
Problem Description
LXY終于開始學英語了，然而他的記憶力有限，每當他看完一段文章，他最多記住每個字母開頭對應的一個單詞?！凹热恢荒苡涀∫粋€單詞，那么當然記住最大的那個啊”——LXY。然而怎么定義最大這個概念呢，LXY決定按照字典順序，記住最大的那個單詞。
現(xiàn)在我們知道LXY即將會看到的文本，你能確定他會記住哪些單詞么？
注：輸入文本中的所有不同單詞不計大小寫，比如“Apple”，“aPPle”或“APPLE”都被視為相同的單詞apple
Input
輸入一串文本，直至文件結(jié)束。
Output
按照每個字母開頭對應的字典序最大的單詞，沒有則不輸出，單詞統(tǒng)一由小寫字母組成，一行輸出一個。
注：任何不屬于字母的符號都會區(qū)分單詞，包括回車、數(shù)字。
Sample Input
Adventures in Disneyland
Two blondes were going to Disneyland when they came to a fork in the
road. The sign read: "Disneyland Left."
So they went home.
Sample Output
adventures
blondes
came
disneyland
fork
going
home
in
left
road
so
two
when
Hint
思路：
方法一：直接按題意模擬，注意輸入格式的問題
方法二：用sstream將非字符賦值為空格，分割出單詞之后模擬即可
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
string word[30];
void init()
{
for(int i=0;i<26;i++)
word[i]="0";
}
int main()
{
string in;
init();
while(getline(cin,in))
{
transform(in.begin(),in.end(),in.begin(),::tolower);
int n=in.length();
string thisword="";
for(int i=0;i<=n;i++)
{
if((in[i]>='a'&&in[i]<='z')&&i!=n)
{
thisword+=in[i];
}
else if(thisword.length()>0)
{
int pos=(thisword[0]-'a');
if(thisword>word[pos])
word[pos]=thisword;
thisword="";
}
}
}
for(int i=0;i<26;i++)
if(word[i]!="0")
cout<<word[i]<<endl;
return 0;
}
垃圾裝箱(15)
Problem Description
CGY 老是說自己是垃圾，于是有一天，CGY 做夢夢到了自己真的變成了垃圾，而且是很多很多的垃圾。
眾所周知 LXY 是一個環(huán)保主義者，于是學院重點垃圾 CGY 的回收處理工作就交由 LXY 來全權負責。
垃圾 CGY 分為三類：棕色 CGY、綠色 CGY 和透明 CGY。LXY 分別從宿舍、課室和機房收集來三個箱子（畢竟垃圾 CGY 只會被丟在這幾個地方），每個箱子都包含指定數(shù)量的棕色、綠色和透明 CGY。LXY 需要移動這些垃圾 CGY，使得每個箱子里僅包含一種 CGY，這樣才方便迫害回收再利用。
問題在于 LXY 太胖了，每次移動 CGY 都需要消耗一定的力氣，于是他想盡量減少移動的數(shù)量。//雖然 LXY 把 CGY 丟下樓的難度比吃生菜還簡單（甚至能一次丟好幾個）
出于此目的，可以假設每個箱子都足夠大（畢竟 CGY 體積小而且還算是限定版垃圾）。
Input
輸入包括多行，每行包含由空格分隔的 ⑨ 個整數(shù)。每三個整數(shù)表示第 i 個箱子中的棕色、綠色和透明 CGY 的數(shù)量。例如：
表示第一個箱子有 20 個透明 CGY，第二個箱子有 12 個綠色 CGY，第三個箱子有 15 個棕色 CGY。
垃圾 CGY 總數(shù)不會超過 2^31。
Output
對于每行輸入，應輸出每個箱子裝的 CGY 的種類和最少的 CGY 移動數(shù)量。
大寫字母 'B'，'G'，'C' 分別表示棕色、綠色和透明，字符串中的第 i 個字符表示第 i 個箱子中裝的 CGY 的種類。
CGY 移動數(shù)量應在種類字符串后面，用空格隔開。
如果有多個解，則應輸出字典序最小的種類字符串。
Sample Input
1 2 3 4 5 6 7 8 9
5 10 5 20 10 5 10 20 10
Sample Output
BCG 30
CBG 50
Hint
思路：
題目意思是三個混合裝有三種不同物品的箱子，移動物品使得三個箱子只裝同一種東西并要求移動的總數(shù)量最少。
因為只有BCG三種情況，枚舉情況為321=6種，所以直接枚舉所有箱子可能的情況即可，然后取最小值，順帶要注意題目中的字典序要求。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
string part[6]={"BCG","BGC","CBG","CGB","GBC","GCB"};
int part_sum[6],r[3][3];
int main()
{
while(~scanf("%d",&r[0][0]))
{
scanf("%d%d",&r[0][1],&r[0][2]);
for(int i=1;i<3;i++)
for(int j=0;j<3;j++)
scanf("%d",&r[i][j]);
memset(part_sum,0,sizeof(part_sum));
part_sum[0]=r[1][0]+r[2][0]+r[0][1]+r[1][1]+r[0][2]+r[2][2];
part_sum[1]=r[1][0]+r[2][0]+r[0][1]+r[2][1]+r[0][2]+r[1][2];
part_sum[2]=r[0][0]+r[2][0]+r[0][1]+r[1][1]+r[1][2]+r[2][2];
part_sum[3]=r[0][0]+r[1][0]+r[0][1]+r[2][1]+r[1][2]+r[2][2];
part_sum[4]=r[0][0]+r[2][0]+r[1][1]+r[2][1]+r[0][2]+r[1][2];
part_sum[5]=r[0][0]+r[1][0]+r[1][1]+r[2][1]+r[0][2]+r[2][2];
int minn=99999999,pos=-1;
for(int i=0;i<6;i++)
{
if(part_sum[i]<minn)
{
minn=part_sum[i];
pos=i;
}
}
cout<<part[pos]<<" "<<minn<<endl;
}
return 0;
}
301 網(wǎng)絡修復(25)
Problem Description
這個學期以來，信息中心301的有線網(wǎng)絡一直用不了，LXY和CGY為此很苦惱。在院長一聲令下修好了燈之后，網(wǎng)絡中心的人終于來301修復網(wǎng)絡了。老師經(jīng)過排查告訴LXY：301的交換機有多余的回路存在，導致局域網(wǎng)不能正常的工作。為了解決這個問題，必須拆掉多余的線路，保證任意兩臺交換機之間只有一條聯(lián)通路存在。同時，由于網(wǎng)線的材質(zhì)不同，每一條網(wǎng)線的延遲也不一樣，LXY希望最后留下來的線路的延遲最小。
然而CGY在垃圾的夢中，LXY在撿垃圾，你能告訴他們該留下的線路延遲最小是多少么？
Input
第一行兩個正整數(shù)n(n<=100),k(k<=n^2)
接下來的k行每行三個正整數(shù)i j m，表示i,j兩臺交換機之間有網(wǎng)線聯(lián)通，延遲為m。
Output
最后留下的網(wǎng)線的最小延遲。
Sample Input
5 5
1 2 8
1 3 1
1 5 3
2 4 5
3 4 2
Sample Output
11
Hint
思路：
最小生成樹模板題
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
struct temp{
int i,j,c;
}a[10010];
int f[110];
int find_father(int x){ return f[x]==x?x:f[x] = find_father(f[x]);}
bool cmp(temp&s1,temp&s2){return s1.c<s2.c;}
int main(){
int n,m,total = 0;
cin>>n>>m;
for(int i = 1;i<=n;i++) f[i] = i;
for(int i = 0;i<m;i++) cin>>a[i].i>>a[i].j>>a[i].c;
sort(a,a+m,cmp);
for(int i = 0;i<m;i++){
int x = a[i].i,y = a[i].j,c = a[i].c;
if(find_father(x) != find_father(y)){
f[find_father(x)] = find_father(y);
total+=c;
}
}
cout<<total;
return 0;
}
Best match(25)
Problem Description
總所周知，大名鼎鼎的 JB-ICPC 是一個三人組隊的電子競技比賽，只有三人齊心協(xié)力優(yōu)勢互補才能在比賽中 AC 盡可能多的題目。
香農(nóng)先修班選出了 ⑨ 位優(yōu)秀的 JBer，由他們進行組隊參加新一年的 JB-ICPC 區(qū)域賽，爭取為 SCNUSE 拿下盡可能多的獎，甚至是 World Final 名額。
SLF 和 FS 作為新一屆先修班的負責人犯難了，因為他不知道如何將這幾個人分成三個組，畢竟有些人的優(yōu)勢是重疊的導致總共能 AC 的題目數(shù)量較少。
又或者說有些人根本不想和某些人一起組隊，畢竟人和人之間的關系總是要比算法難處理得多，對吧……
老前輩 LXY 給出戰(zhàn)術指導換家，把所有能組合在一起的三人組合得出的 AC 題數(shù)統(tǒng)計起來，選出不重合的三組隊員使得三隊的 AC 數(shù)最高，就可以保證三隊都能穩(wěn)定打鐵拿獎了。
SLF 和 FS 只得照辦，統(tǒng)計出所有可能的組合，然后丟給決策自動機 CGY 來處理。問題在于，CGY 還在變成垃圾的夢里沒醒來，那你懂我意思了吧？
Input
輸入包含最多 100 個測試樣例。
每個樣例第一行是一個整數(shù) n（0 < n < 81），即可能的組合數(shù)。
接下來的 n 行，每行包含 4 個正整數(shù) a,b,c,s（1 ≤ a < b < c ≤ 9,0 < s < 10000），這意味著（a,b,c）這個組合可以 AC s 道題。（輸入保證不會有重復出現(xiàn)的組合）
最后一組樣例只有一個 0，不需要處理。
Output
對于每個測試樣例，輸出樣例編號和最高分。如果組不成三支隊，輸出 -1。
Sample Input
3
1 2 3 1
4 5 6 2
7 8 9 3
4
1 2 3 1
1 4 5 2
1 6 7 3
1 8 9 4
0
Sample Output
Case 1: 6
Case 2: -1
Hint
思路：
n最大81，所以直接DFS暴力搜索，因為搜索次數(shù)最大為C(3,80),不會超時。
用DFS列出所有的組合的可能性，最后判斷當前組合是否符合題意即沒有重復的隊員，符合就更新一下最大值即可。
#include <iostream>
#include <cstring>
using namespace std;
int n,a[100][4],t[3],res;
bool f[100];
void dfs(int curn){
if(curn == 3){
int curac = 0,tt;
bool flag[10] = {false};
for(int i = 0;i<3;i++){
tt = t[i];
curac+=a[tt][3];
for(int j = 0;j<3;j++)
flag[a[tt][j]] = true;
}
for(int i = 1;i<=9;i++)
if(!flag[i]) return;
res = max(res,curac);
return;
}
for(int i = 0;i<n;i++){
if(!f[i]){
f[i] = true;
t[curn] = i;
dfs(curn+1);
f[i] = false;
}
}
}
int main(){
int k = 0;
while(cin>>n &&n!=0){
for(int i = 0;i<n;i++)
cin>>a[i][0]>>a[i][1]>>a[i][2]>>a[i][3];
memset(f,false,sizeof(f));
res = -1;
dfs(0);
cout<<"Case "<<++k<<": "<<res<<endl;
}
return 0;
}
電子字典(25)
Problem Description
slf正在為他的英語考試做準備，為此他給自己寫了一個電子字典，字典含有以下功能：
- 添加
添加操作的格式為：insert 單詞 頻次
例如：insert helpful 5
意思是添加helpful這個單詞，頻次為5。如果再次執(zhí)行insert helpful 5 操作時，helpful的頻次變?yōu)?0。 - 刪除
刪除格式為：delete 單詞
例如：delete helpful
意思是刪除字典中helpful這個單詞。
若當前版本的電子字典中沒有要刪除的單詞，則輸出”Empty”(不含引號)。 - 查詢
查詢的格式為：query 單詞
例如：query ful
意思是查詢當前版本的電子字典中以ful結(jié)尾的所有單詞詞頻總和，然后輸出結(jié)果。
Input
第一行讀入一個整數(shù) T，代表數(shù)據(jù)組數(shù)。
每組數(shù)據(jù)的第一行讀入一個整數(shù) N 代表操作數(shù)。
接下來 N 行，每行形容一個操作。
保證數(shù)據(jù)滿足 1≤T≤10， 1≤N≤1000，insert操作的字符串總長度之和≤30000，所有字符串長度≤10000
輸入只有小寫字母
Output
根據(jù)題目要求輸出
Sample Input
1
6
insert helpful 8
query ful
insert careful 9
query ful
delete helpful
query ful
Sample Output
8
17
9
Hint
思路：
按題意模擬，把輸入的每一個單詞都取出其所有后綴，然后插入map中。查詢時直接查后綴的個數(shù)。
注意：某單詞有可能是另外一個單詞的后綴，例如單詞e是Apple的后綴，所以刪除某單詞所有后綴的時候要注意有可能會把另外一個單詞給刪掉。
比較好想的辦法就是采用兩個map，一個dic記錄后綴，一個com記錄完整單詞。
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
map<string,int> dic,com;//dic記錄后綴，com記錄完整單詞，用于del
void ins(string str,int key);
void del(string str);
int que(string str);
int main()
{
int t,n;
cin>>t;
while(t--)
{
cin>>n;
while(n--)
{
string op,str;
cin>>op>>str;
if(op=="insert")
{
int key;
cin>>key;
ins(str,key);
}
else if(op=="delete")
{
del(str);
}
else
{
cout<<que(str)<<endl;
}
}
dic.clear();
com.clear();
}
return 0;
}
void ins(string str,int key)
{
if(com.count(str)==0)
com.insert(map<string,int>::value_type(str,key));
else
com[str]+=key;
int n=str.length();
for(int i=0;i<n;i++)
{
string insstr=str.substr(n-i-1);
if(dic.count(insstr)==0)
dic.insert(map<string,int>::value_type(insstr,key));
else
dic[insstr]+=key;
}
}
void del(string str)
{
if(com.count(str)==0)
cout<<"Empty"<<endl;
else
{
int num=com[str],n=str.length();
for(int i=0;i<n;i++)
{
string delstr=str.substr(n-i-1);
dic[delstr]-=num;
}
com.erase(str);
}
}
int que(string str)
{
if(dic.count(str)==0)
return 0;
return dic[str];
}
體育老師的煩惱(25)
Problem Description
學期結(jié)束了，學校準備將學生的體育成績進行一個排名，具體排名規(guī)則如下。
首先按照學生的期末成績進行排序，成績高的在前。
其次是按照學生的期中成績 40% 和平時成績 60% 相加后的成績進行排序，成績高的在前。
最后是按照學生的學號進行排序，學號小的在前。
PS：所有學生的學號長度一致，數(shù)字小的在前。
數(shù)學不好的體育老師找到了 CGY 來幫他解決這個問題，CGY 覺得太簡單的于是丟給背鍋俠 FS 來做。由于這段時間 FS 實在是太忙了，于是將問題拋給了你。
Input
輸入 n 表示學生人數(shù)(n<=10000)，接下來的 n 行，每行從前往后給出學生的學號(位數(shù)為 11 位)，學生姓名(不大于 10 位的字符串，無空格)，期末成績(不大于 100 的非負整數(shù))，期中成績(不大于 100 的非負整數(shù))，平時成績(不大于 100 的非負整數(shù))。
Output
輸出 n 行，一人一行，輸出格式與輸入格式相同
Sample Input
6
20152000100 Tim 60 60 60
20052001323 Su 90 60 100
20173999099 Lily 90 90 80
20163334123 Ming 90 90 80
20143727429 Boy 90 80 90
20184732198 Tom 100 90 90
Sample Output
20184732198 Tom 100 90 90
20143727429 Boy 90 80 90
20052001323 Su 90 60 100
20163334123 Ming 90 90 80
20173999099 Lily 90 90 80
20152000100 Tim 60 60 60
Hint
思路：
本題考察結(jié)構(gòu)體排序，不過有個注意點是要注意浮點數(shù)的精度誤差。
最佳的做法就是采用整數(shù)來存，然后將期中成績4，平時成績6再來比較即可。
//float精度比double低所以會丟失一些精度，用float反而會AC，用double不考慮精度問題的話肯定是會WA的。
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
struct Student{
string snumber;
string sname;
int ends;
int mid;
int pin;
int quan;
};
bool cmp(Student student1,Student student2)
{
if(student1.ends==student2.ends)
{
if(student1.quan==student2.quan)
{
return student1.snumber<student2.snumber;
}
else
{
return student1.quan>student2.quan;
}
}
else
return student1.ends>student2.ends;
}
Student student[10010];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>student[i].snumber>>student[i].sname>>student[i].ends>>student[i].mid>>student[i].pin;
student[i].quan=student[i].mid*4+student[i].pin*6;
}
sort(student,student+n,cmp);
for(int i=0;i<n;i++)
{
cout<<student[i].snumber<<" "<<student[i].sname<<" "<<student[i].ends<<" "<<student[i].mid<<" "<<student[i].pin<<endl;
}
return 0;
}
避銃(30)
Problem Description
我們希望在一塊 n × n 的棋盤上放置 n 個象棋中的車，但受到以下限制：
· 第 i 個車只能放置在一個給定的左上角為 (xl[i],yl[i]) 和右下角為 (xr[i],yr[i]) 的矩形內(nèi)，其中 1 ≤ i ≤ n，1 ≤ xl[i] ≤ xr[i] ≤ n，1 ≤ yl[i] ≤ yr[i] ≤ n。
· 任意兩個車都不可以相互攻擊，也就是不能放銃（迫真），也就是說，沒有兩個車可以占據(jù)同一列或同一行。
你的任務是找到有沒有滿足上述條件的車的放置。
Input
輸入包含幾個測試用例。每個的第一行包含一個整數(shù) n（n ≤ 5000），即棋盤的大小。然后是 n 行，其中的第 i 行給出了 xl[i]，yl[i]，xr[i] 和 yr[i]。輸入最后是一個 0，不需要處理。
Output
如果有這種放置 play，輸出 "Tenpai"，反之輸出 "Ron"。
Sample Input
8
1 1 2 2
5 7 8 8
2 2 5 5
2 2 5 5
6 3 8 6
6 3 8 5
6 3 8 8
3 6 7 8
0
Sample Output
Tenpai
Hint
思路：
因為車是只能攻擊同一行或同一列的車，所以可以將這個二維問題分解為兩個一維問題。
是否能在x上的若干個區(qū)域內(nèi)選出n個不同的x值，在y上的若干個區(qū)域內(nèi)選出n個不同的y值。(每個區(qū)域只能選一個值)
若都能滿足則輸出"Tenpai"，不能則輸出"Ron"。
可以用貪心法來處理這個一維問題。
設若干個區(qū)域為[l,r]，對r值進行升序排序，如果r值相同則根據(jù)l值進行升序排序。
排完序之后從前往后遍歷，再從li遍歷取第一個沒有被標記的值，如果這個值大于ri，則表明沒有解，小于等于ri則將這個值標記。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
struct temp{
int x1,x2;
int y1,y2;
}a[5010];
bool cmp1(const temp&s1,const temp&s2){
if(s1.x2==s2.x2)
return s1.x1<s2.x1;
else
return s1.x2<s2.x2;
}
bool cmp2(const temp&s1,const temp&s2){
if(s1.y2==s2.y2)
return s1.y1<s2.y1;
else
return s1.y2<s2.y2;
}
bool visx[5010],visy[5010],flag;
int main(){
int n;
while(cin>>n && n!=0){
memset(visx,false,sizeof(visx));
memset(visy,false,sizeof(visy));
flag = true;
struct temp t;
for(int i = 0;i<n;i++){
cin>>t.x1>>t.y1>>t.x2>>t.y2;
a[i] = t;
}
if(flag){
sort(a,a+n,cmp1);
for(int i = 0;i<n;i++){
t = a[i];
int curx = t.x1,x2 = t.x2;
while(visx[curx]){//尋找第一個未標記值
curx++;
}
if(curx>x2){//判斷是否這個值是否超過當前區(qū)間最大值
flag = false;
break;
}
visx[curx] = true;
}
}
if(flag){
sort(a,a+n,cmp2);
for(int i = 0;i<n;i++){
t = a[i];
int cury = t.y1,y2 = t.y2;
while(visy[cury]){
cury++;
}
if(cury>y2){
flag = false;
break;
}
visy[cury] = true;
}
}
if(flag)
cout<<"Tenpai"<<endl;
else
cout<<"Ron"<<endl;
}
return 0;
}
總結(jié)：
//這次比賽涌現(xiàn)了好多meng男，tqltql
