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诚啃。您應(yīng)該處理所有整數(shù)對，并且對于每對確定 i 和 j 之間（包括 i 和 j）的所有整數(shù)的最大循環(huán)長度私沮。

Output

對于每對輸入整數(shù) i 和 j始赎，您應(yīng)該輸出 i，j仔燕，i 和 j 之間的最大循環(huán)長度极阅。這三個數(shù)字應(yīng)由一個空格分隔，一行中三個數(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

開學(xué)的第一節(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開始學(xué)習(xí)編程了围小，今天是他上的第一課昵骤，老師讓他把輸入的數(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終于開始學(xué)英語了枪芒，然而他的記憶力有限彻况，每當他看完一段文章，他最多記住每個字母開頭對應(yīng)的一個單詞病苗×贫猓“既然只能記住一個單詞，那么當然記住最大的那個啊”——LXY硫朦。然而怎么定義最大這個概念呢贷腕，LXY決定按照字典順序，記住最大的那個單詞。
現(xiàn)在我們知道LXY即將會看到的文本泽裳，你能確定他會記住哪些單詞么瞒斩？
注：輸入文本中的所有不同單詞不計大小寫，比如“Apple”涮总，“aPPle”或“APPLE”都被視為相同的單詞apple

Input

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

Output

按照每個字母開頭對應(yīng)的字典序最大的單詞瀑梗，沒有則不輸出烹笔，單詞統(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)保主義者妓蛮，于是學(xué)院重點垃圾 CGY 的回收處理工作就交由 LXY 來全權(quán)負責(zé)。
垃圾 CGY 分為三類：棕色 CGY叛复、綠色 CGY 和透明 CGY仔引。LXY 分別從宿舍扔仓、課室和機房收集來三個箱子（畢竟垃圾 CGY 只會被丟在這幾個地方）褐奥，每個箱子都包含指定數(shù)量的棕色、綠色和透明 CGY翘簇。LXY 需要移動這些垃圾 CGY撬码，使得每個箱子里僅包含一種 CGY，這樣才方便迫害回收再利用版保。
問題在于 LXY 太胖了呜笑，每次移動 CGY 都需要消耗一定的力氣，于是他想盡量減少移動的數(shù)量彻犁。//雖然 LXY 把 CGY 丟下樓的難度比吃生菜還簡單（甚至能一次丟好幾個）
出于此目的叫胁，可以假設(shè)每個箱子都足夠大（畢竟 CGY 體積小而且還算是限定版垃圾）。

Input

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

表示第一個箱子有 20 個透明 CGY输钩，第二個箱子有 12 個綠色 CGY豺型，第三個箱子有 15 個棕色 CGY。
垃圾 CGY 總數(shù)不會超過 2^31买乃。

Output

對于每行輸入姻氨，應(yīng)輸出每個箱子裝的 CGY 的種類和最少的 CGY 移動數(shù)量。
大寫字母 'B'剪验，'G'肴焊，'C' 分別表示棕色、綠色和透明功戚，字符串中的第 i 個字符表示第 i 個箱子中裝的 CGY 的種類抖韩。
CGY 移動數(shù)量應(yīng)在種類字符串后面，用空格隔開疫铜。
如果有多個解茂浮，則應(yīng)輸出字典序最小的種類字符串。

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)絡(luò)修復(fù)(25)

Problem Description

這個學(xué)期以來属桦，信息中心301的有線網(wǎng)絡(luò)一直用不了，LXY和CGY為此很苦惱他爸。在院長一聲令下修好了燈之后聂宾，網(wǎng)絡(luò)中心的人終于來301修復(fù)網(wǎng)絡(luò)了。老師經(jīng)過排查告訴LXY：301的交換機有多余的回路存在诊笤，導(dǎo)致局域網(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 作為新一屆先修班的負責(zé)人犯難了睡毒，因為他不知道如何將這幾個人分成三個組，畢竟有些人的優(yōu)勢是重疊的導(dǎo)致總共能 AC 的題目數(shù)量較少冗栗。
又或者說有些人根本不想和某些人一起組隊演顾，畢竟人和人之間的關(guān)系總是要比算法難處理得多，對吧……
老前輩 LXY 給出戰(zhàn)術(shù)指導(dǎo)換家隅居，把所有能組合在一起的三人組合得出的 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 道題撒遣。（輸入保證不會有重復(fù)出現(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列出所有的組合的可能性宠纯，最后判斷當前組合是否符合題意即沒有重復(fù)的隊員，符合就更新一下最大值即可层释。

#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正在為他的英語考試做準備婆瓜，為此他給自己寫了一個電子字典，字典含有以下功能：

1. 添加
   添加操作的格式為：insert 單詞 頻次
   例如：insert helpful 5
   意思是添加helpful這個單詞贡羔，頻次為5廉白。如果再次執(zhí)行insert helpful 5 操作時，helpful的頻次變?yōu)?0乖寒。
2. 刪除
   刪除格式為：delete 單詞
   例如：delete helpful
   意思是刪除字典中helpful這個單詞猴蹂。
   若當前版本的電子字典中沒有要刪除的單詞，則輸出”Empty”(不含引號)楣嘁。
3. 查詢
   查詢的格式為：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

學(xué)期結(jié)束了，學(xué)校準備將學(xué)生的體育成績進行一個排名权纤，具體排名規(guī)則如下钓简。
首先按照學(xué)生的期末成績進行排序乌妒，成績高的在前。
其次是按照學(xué)生的期中成績 40% 和平時成績 60% 相加后的成績進行排序外邓，成績高的在前撤蚊。
最后是按照學(xué)生的學(xué)號進行排序，學(xué)號小的在前损话。
PS：所有學(xué)生的學(xué)號長度一致拴魄，數(shù)字小的在前。
數(shù)學(xué)不好的體育老師找到了 CGY 來幫他解決這個問題席镀，CGY 覺得太簡單的于是丟給背鍋俠 FS 來做匹中。由于這段時間 FS 實在是太忙了，于是將問題拋給了你豪诲。

Input

輸入 n 表示學(xué)生人數(shù)(n<=10000)顶捷，接下來的 n 行，每行從前往后給出學(xué)生的學(xué)號(位數(shù)為 11 位)屎篱，學(xué)生姓名(不大于 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ù)同一列或同一行届吁。
你的任務(wù)是找到有沒有滿足上述條件的車的放置错妖。

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"节榜。
可以用貪心法來處理這個一維問題。
設(shè)若干個區(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