3n+1 問(wèn)題(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ù)推測(cè)，對(duì)于任何輸入值，上述算法都將終止。盡管算法很簡(jiǎn)單，但不知道這個(gè)猜想是否正確。
給定輸入 n，可以確定輸出的數(shù)字（包括 1）。對(duì)于給定的 n，這稱(chēng)為 n 的循環(huán)長(zhǎng)度。在上面的例子中，22 的循環(huán)長(zhǎng)度是 16。
對(duì)于任何兩個(gè)數(shù)字 i 和 j，您將確定 i 和 j 之間（包括 i 和 j）所有數(shù)字的最大循環(huán)長(zhǎng)度。

Input

輸入將由一系列整數(shù) i 和 j 組成（i ≤ j），每行一對(duì)整數(shù)（輸入保證不超過(guò) 10 行）。所有整數(shù)將小于 100000 且大于 0。您應(yīng)該處理所有整數(shù)對(duì)，并且對(duì)于每對(duì)確定 i 和 j 之間（包括 i 和 j）的所有整數(shù)的最大循環(huán)長(zhǎng)度。

Output

對(duì)于每對(duì)輸入整數(shù) i 和 j，您應(yīng)該輸出 i，j，i 和 j 之間的最大循環(huán)長(zhǎng)度。這三個(gè)數(shù)字應(yīng)由一個(gè)空格分隔，一行中三個(gè)數(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ù)說(shuō) CGY 家里的喵星人很聰明，會(huì)計(jì)算十以?xún)?nèi)的加法。例如：現(xiàn)有數(shù)字 1，2，喵星人會(huì)用“Mia~Mia~Mia~”來(lái)表達(dá)答案是 3。
現(xiàn)在有請(qǐng)你來(lái)寫(xiě)一個(gè)程序，模擬這個(gè)過(guò)程。

Input

輸入在一行中給出兩個(gè)區(qū)間在 [1,9] 的正整數(shù) A 和 B，用空格分隔

Output

在一行中輸出有 A+B 個(gè)“Mia~”(不包含引號(hào))。

Sample Input

2 1

Sample Output

Mia~Mia~Mia~

Hint

思路：

題解？！//大家都過(guò)了，沒(méi)什么好說(shuō)啦

#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

開(kāi)學(xué)的第一節(jié)課是高數(shù)課，由于翁哥第一節(jié)課講的東西實(shí)在是太無(wú)聊了，F(xiàn)S 開(kāi)始了“釣魚(yú)”模式。SLF 看 FS 實(shí)在是太困了，就給了他一個(gè)問(wèn)題：現(xiàn)在黑板有一個(gè)數(shù)字 N，那么將這個(gè)數(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 玩了十分鐘后覺(jué)得太無(wú)聊了，于是把這個(gè) easy problem 交給你。

Input

輸入一行，N，M，其中 N 為不超過(guò) 100 位的正整數(shù)，N 為十進(jì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ù)相加，即獲得一個(gè)數(shù)反轉(zhuǎn)過(guò)來(lái)相加即可
方法二：用JAVA得BigInteger輸入，然后reserve相加完事
題目都說(shuō)了最大有100位的非負(fù)整數(shù)，當(dāng)然是用大數(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;
}

簡(jiǎn)單的問(wèn)題(15)

Problem Description

現(xiàn)在給你一個(gè)包含 0~9 和 A~F 的字符串，你需要求出在這個(gè)字符串中出現(xiàn)次數(shù)最多的字符，然后你需要求出這個(gè)字符串組成的十六進(jìn)制轉(zhuǎn)換為十進(jìn)制的數(shù)。

Input

第一行讀入一個(gè)整數(shù) T(1≤T≤10)，代表數(shù)據(jù)組數(shù)。
接下來(lái)給出 T 行，
每行給出這個(gè)字符串
輸入保證數(shù)組長(zhǎng)度 ≤ 15

Output

每組輸出兩行
第一行表示出現(xiàn)次數(shù)最多的字符和出現(xiàn)的次數(shù)，用空格隔開(kāi)。若有相同的次數(shù)，則輸出字典序最小的。
第二行表示轉(zhuǎn)換的十進(jìn)制數(shù)

Sample Input

1
22011

Sample Output

4884

Hint

思路：

按題意模擬，注意一下輸出的數(shù)字要用long long來(lái)存

#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開(kāi)始學(xué)習(xí)編程了，今天是他上的第一課，老師讓他把輸入的數(shù)字照著原樣輸出。

Input

輸入一個(gè)實(shí)數(shù)

Output

輸出輸入的數(shù)字N

Sample Input

123.88

Sample Output

123.88

Hint

思路：

實(shí)數(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)在正準(zhǔn)備用他的超能力轟炸一片區(qū)域，在這片區(qū)域中有 N 座建筑，每個(gè)建筑的血量都是 M，SLF 攜帶的炮彈只能對(duì)一座建筑造成 X 點(diǎn)傷害，但發(fā)射炮彈需要消耗他的能量,第一發(fā)炮彈的能量為 3 點(diǎn),并且發(fā)射炮彈需要的能量每次遞增兩點(diǎn)，即下一發(fā)的能量=上一發(fā)的能量+2，幸運(yùn)的是每當(dāng) SLF 摧毀了一座建筑，他都可以獲得 Y 點(diǎn)能量，SLF 一開(kāi)始共有 Z 點(diǎn)能量，現(xiàn)在 SLF 想知道他最多可以炸掉多少建筑。

Input

第一行讀入一個(gè)整數(shù) T，代表數(shù)據(jù)組數(shù)。
接下來(lái)給出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點(diǎn)能量，所以總能量變?yōu)?0-15+1=6，第四發(fā)炮彈發(fā)射需要能量為9點(diǎn)，無(wú)法再次發(fā)射，所以總共摧毀一座建筑

思路：

按題意模擬計(jì)算。注意考慮可摧毀數(shù)量大于n的時(shí)候。

#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終于開(kāi)始學(xué)英語(yǔ)了，然而他的記憶力有限，每當(dāng)他看完一段文章，他最多記住每個(gè)字母開(kāi)頭對(duì)應(yīng)的一個(gè)單詞?！凹热恢荒苡涀∫粋€(gè)單詞，那么當(dāng)然記住最大的那個(gè)啊”——LXY。然而怎么定義最大這個(gè)概念呢，LXY決定按照字典順序，記住最大的那個(gè)單詞。
現(xiàn)在我們知道LXY即將會(huì)看到的文本，你能確定他會(huì)記住哪些單詞么？
注：輸入文本中的所有不同單詞不計(jì)大小寫(xiě)，比如“Apple”，“aPPle”或“APPLE”都被視為相同的單詞apple

Input

輸入一串文本，直至文件結(jié)束。

Output

按照每個(gè)字母開(kāi)頭對(duì)應(yīng)的字典序最大的單詞，沒(méi)有則不輸出，單詞統(tǒng)一由小寫(xiě)字母組成，一行輸出一個(gè)。
注：任何不屬于字母的符號(hào)都會(huì)區(qū)分單詞，包括回車(chē)、數(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

思路：

方法一：直接按題意模擬，注意輸入格式的問(wèn)題
方法二：用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 老是說(shuō)自己是垃圾，于是有一天，CGY 做夢(mèng)夢(mèng)到了自己真的變成了垃圾，而且是很多很多的垃圾。
眾所周知 LXY 是一個(gè)環(huán)保主義者，于是學(xué)院重點(diǎn)垃圾 CGY 的回收處理工作就交由 LXY 來(lái)全權(quán)負(fù)責(zé)。
垃圾 CGY 分為三類(lèi)：棕色 CGY、綠色 CGY 和透明 CGY。LXY 分別從宿舍、課室和機(jī)房收集來(lái)三個(gè)箱子（畢竟垃圾 CGY 只會(huì)被丟在這幾個(gè)地方），每個(gè)箱子都包含指定數(shù)量的棕色、綠色和透明 CGY。LXY 需要移動(dòng)這些垃圾 CGY，使得每個(gè)箱子里僅包含一種 CGY，這樣才方便迫害回收再利用。
問(wèn)題在于 LXY 太胖了，每次移動(dòng) CGY 都需要消耗一定的力氣，于是他想盡量減少移動(dòng)的數(shù)量。//雖然 LXY 把 CGY 丟下樓的難度比吃生菜還簡(jiǎn)單（甚至能一次丟好幾個(gè)）
出于此目的，可以假設(shè)每個(gè)箱子都足夠大（畢竟 CGY 體積小而且還算是限定版垃圾）。

Input

輸入包括多行，每行包含由空格分隔的 ⑨ 個(gè)整數(shù)。每三個(gè)整數(shù)表示第 i 個(gè)箱子中的棕色、綠色和透明 CGY 的數(shù)量。例如：

表示第一個(gè)箱子有 20 個(gè)透明 CGY，第二個(gè)箱子有 12 個(gè)綠色 CGY，第三個(gè)箱子有 15 個(gè)棕色 CGY。
垃圾 CGY 總數(shù)不會(huì)超過(guò) 2^31。

Output

對(duì)于每行輸入，應(yīng)輸出每個(gè)箱子裝的 CGY 的種類(lèi)和最少的 CGY 移動(dòng)數(shù)量。
大寫(xiě)字母 'B'，'G'，'C' 分別表示棕色、綠色和透明，字符串中的第 i 個(gè)字符表示第 i 個(gè)箱子中裝的 CGY 的種類(lèi)。
CGY 移動(dòng)數(shù)量應(yīng)在種類(lèi)字符串后面，用空格隔開(kāi)。
如果有多個(gè)解，則應(yīng)輸出字典序最小的種類(lèi)字符串。

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

思路：

題目意思是三個(gè)混合裝有三種不同物品的箱子，移動(dòng)物品使得三個(gè)箱子只裝同一種東西并要求移動(dòng)的總數(shù)量最少。
因?yàn)橹挥蠦CG三種情況，枚舉情況為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)絡(luò)修復(fù)(25)

Problem Description

這個(gè)學(xué)期以來(lái)，信息中心301的有線(xiàn)網(wǎng)絡(luò)一直用不了，LXY和CGY為此很苦惱。在院長(zhǎng)一聲令下修好了燈之后，網(wǎng)絡(luò)中心的人終于來(lái)301修復(fù)網(wǎng)絡(luò)了。老師經(jīng)過(guò)排查告訴LXY：301的交換機(jī)有多余的回路存在，導(dǎo)致局域網(wǎng)不能正常的工作。為了解決這個(gè)問(wèn)題，必須拆掉多余的線(xiàn)路，保證任意兩臺(tái)交換機(jī)之間只有一條聯(lián)通路存在。同時(shí)，由于網(wǎng)線(xiàn)的材質(zhì)不同，每一條網(wǎng)線(xiàn)的延遲也不一樣，LXY希望最后留下來(lái)的線(xiàn)路的延遲最小。
然而CGY在垃圾的夢(mèng)中，LXY在撿垃圾，你能告訴他們?cè)摿粝碌木€(xiàn)路延遲最小是多少么？

Input

第一行兩個(gè)正整數(shù)n(n<=100),k(k<=n^2)
接下來(lái)的k行每行三個(gè)正整數(shù)i j m，表示i,j兩臺(tái)交換機(jī)之間有網(wǎng)線(xiàn)聯(lián)通，延遲為m。

Output

最后留下的網(wǎng)線(xiàn)的最小延遲。

Sample Input

5 5
1 2 8
1 3 1
1 5 3
2 4 5
3 4 2

Sample Output

11

Hint

思路：

最小生成樹(shù)模板題

#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 是一個(gè)三人組隊(duì)的電子競(jìng)技比賽，只有三人齊心協(xié)力優(yōu)勢(shì)互補(bǔ)才能在比賽中 AC 盡可能多的題目。
香農(nóng)先修班選出了 ⑨ 位優(yōu)秀的 JBer，由他們進(jìn)行組隊(duì)參加新一年的 JB-ICPC 區(qū)域賽，爭(zhēng)取為 SCNUSE 拿下盡可能多的獎(jiǎng)，甚至是 World Final 名額。
SLF 和 FS 作為新一屆先修班的負(fù)責(zé)人犯難了，因?yàn)樗恢廊绾螌⑦@幾個(gè)人分成三個(gè)組，畢竟有些人的優(yōu)勢(shì)是重疊的導(dǎo)致總共能 AC 的題目數(shù)量較少。
又或者說(shuō)有些人根本不想和某些人一起組隊(duì)，畢竟人和人之間的關(guān)系總是要比算法難處理得多，對(duì)吧……
老前輩 LXY 給出戰(zhàn)術(shù)指導(dǎo)換家，把所有能組合在一起的三人組合得出的 AC 題數(shù)統(tǒng)計(jì)起來(lái)，選出不重合的三組隊(duì)員使得三隊(duì)的 AC 數(shù)最高，就可以保證三隊(duì)都能穩(wěn)定打鐵拿獎(jiǎng)了。
SLF 和 FS 只得照辦，統(tǒng)計(jì)出所有可能的組合，然后丟給決策自動(dòng)機(jī) CGY 來(lái)處理。問(wèn)題在于，CGY 還在變成垃圾的夢(mèng)里沒(méi)醒來(lái)，那你懂我意思了吧？

Input

輸入包含最多 100 個(gè)測(cè)試樣例。
每個(gè)樣例第一行是一個(gè)整數(shù) n（0 < n < 81），即可能的組合數(shù)。
接下來(lái)的 n 行，每行包含 4 個(gè)正整數(shù) a,b,c,s（1 ≤ a < b < c ≤ 9,0 < s < 10000），這意味著（a,b,c）這個(gè)組合可以 AC s 道題。（輸入保證不會(huì)有重復(fù)出現(xiàn)的組合）
最后一組樣例只有一個(gè) 0，不需要處理。

Output

對(duì)于每個(gè)測(cè)試樣例，輸出樣例編號(hào)和最高分。如果組不成三支隊(duì)，輸出 -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暴力搜索，因?yàn)樗阉鞔螖?shù)最大為C(3,80),不會(huì)超時(shí)。
用DFS列出所有的組合的可能性，最后判斷當(dāng)前組合是否符合題意即沒(méi)有重復(fù)的隊(duì)員，符合就更新一下最大值即可。

#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正在為他的英語(yǔ)考試做準(zhǔn)備，為此他給自己寫(xiě)了一個(gè)電子字典，字典含有以下功能：

1. 添加
   添加操作的格式為：insert 單詞 頻次
   例如：insert helpful 5
   意思是添加helpful這個(gè)單詞，頻次為5。如果再次執(zhí)行insert helpful 5 操作時(shí)，helpful的頻次變?yōu)?0。
2. 刪除
   刪除格式為：delete 單詞
   例如：delete helpful
   意思是刪除字典中helpful這個(gè)單詞。
   若當(dāng)前版本的電子字典中沒(méi)有要?jiǎng)h除的單詞，則輸出”Empty”(不含引號(hào))。
3. 查詢(xún)
   查詢(xún)的格式為：query 單詞
   例如：query ful
   意思是查詢(xún)當(dāng)前版本的電子字典中以ful結(jié)尾的所有單詞詞頻總和，然后輸出結(jié)果。

Input

第一行讀入一個(gè)整數(shù) T，代表數(shù)據(jù)組數(shù)。
每組數(shù)據(jù)的第一行讀入一個(gè)整數(shù) N 代表操作數(shù)。
接下來(lái) N 行，每行形容一個(gè)操作。
保證數(shù)據(jù)滿(mǎn)足 1≤T≤10， 1≤N≤1000，insert操作的字符串總長(zhǎng)度之和≤30000，所有字符串長(zhǎng)度≤10000
輸入只有小寫(xiě)字母

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

思路：

按題意模擬，把輸入的每一個(gè)單詞都取出其所有后綴，然后插入map中。查詢(xún)時(shí)直接查后綴的個(gè)數(shù)。
注意：某單詞有可能是另外一個(gè)單詞的后綴，例如單詞e是Apple的后綴，所以刪除某單詞所有后綴的時(shí)候要注意有可能會(huì)把另外一個(gè)單詞給刪掉。
比較好想的辦法就是采用兩個(gè)map，一個(gè)dic記錄后綴，一個(gè)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

學(xué)期結(jié)束了，學(xué)校準(zhǔn)備將學(xué)生的體育成績(jī)進(jìn)行一個(gè)排名，具體排名規(guī)則如下。
首先按照學(xué)生的期末成績(jī)進(jìn)行排序，成績(jī)高的在前。
其次是按照學(xué)生的期中成績(jī) 40% 和平時(shí)成績(jī) 60% 相加后的成績(jī)進(jìn)行排序，成績(jī)高的在前。
最后是按照學(xué)生的學(xué)號(hào)進(jìn)行排序，學(xué)號(hào)小的在前。
PS：所有學(xué)生的學(xué)號(hào)長(zhǎng)度一致，數(shù)字小的在前。
數(shù)學(xué)不好的體育老師找到了 CGY 來(lái)幫他解決這個(gè)問(wèn)題，CGY 覺(jué)得太簡(jiǎn)單的于是丟給背鍋俠 FS 來(lái)做。由于這段時(shí)間 FS 實(shí)在是太忙了，于是將問(wèn)題拋給了你。

Input

輸入 n 表示學(xué)生人數(shù)(n<=10000)，接下來(lái)的 n 行，每行從前往后給出學(xué)生的學(xué)號(hào)(位數(shù)為 11 位)，學(xué)生姓名(不大于 10 位的字符串，無(wú)空格)，期末成績(jī)(不大于 100 的非負(fù)整數(shù))，期中成績(jī)(不大于 100 的非負(fù)整數(shù))，平時(shí)成績(jī)(不大于 100 的非負(fù)整數(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)體排序，不過(guò)有個(gè)注意點(diǎn)是要注意浮點(diǎn)數(shù)的精度誤差。
最佳的做法就是采用整數(shù)來(lái)存，然后將期中成績(jī)4，平時(shí)成績(jī)6再來(lái)比較即可。
//float精度比double低所以會(huì)丟失一些精度，用float反而會(huì)AC，用double不考慮精度問(wèn)題的話(huà)肯定是會(huì)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 的棋盤(pán)上放置 n 個(gè)象棋中的車(chē)，但受到以下限制：
· 第 i 個(gè)車(chē)只能放置在一個(gè)給定的左上角為 (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。
· 任意兩個(gè)車(chē)都不可以相互攻擊，也就是不能放銃（迫真），也就是說(shuō)，沒(méi)有兩個(gè)車(chē)可以占據(jù)同一列或同一行。
你的任務(wù)是找到有沒(méi)有滿(mǎn)足上述條件的車(chē)的放置。

Input

輸入包含幾個(gè)測(cè)試用例。每個(gè)的第一行包含一個(gè)整數(shù) n（n ≤ 5000），即棋盤(pán)的大小。然后是 n 行，其中的第 i 行給出了 xl[i]，yl[i]，xr[i] 和 yr[i]。輸入最后是一個(gè) 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

思路：

因?yàn)檐?chē)是只能攻擊同一行或同一列的車(chē)，所以可以將這個(gè)二維問(wèn)題分解為兩個(gè)一維問(wèn)題。
是否能在x上的若干個(gè)區(qū)域內(nèi)選出n個(gè)不同的x值，在y上的若干個(gè)區(qū)域內(nèi)選出n個(gè)不同的y值。(每個(gè)區(qū)域只能選一個(gè)值)
若都能滿(mǎn)足則輸出"Tenpai"，不能則輸出"Ron"。
可以用貪心法來(lái)處理這個(gè)一維問(wèn)題。
設(shè)若干個(gè)區(qū)域?yàn)閇l,r]，對(duì)r值進(jìn)行升序排序，如果r值相同則根據(jù)l值進(jìn)行升序排序。
排完序之后從前往后遍歷，再?gòu)膌i遍歷取第一個(gè)沒(méi)有被標(biāo)記的值，如果這個(gè)值大于ri，則表明沒(méi)有解，小于等于ri則將這個(gè)值標(biāo)記。

#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]){//尋找第一個(gè)未標(biāo)記值
                    curx++;
                }
                if(curx>x2){//判斷是否這個(gè)值是否超過(guò)當(dāng)前區(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