問題 A: 努力的蟲子

題目描述
一只蟲子掉到枯井里，它每天白天都會向上爬n厘米，但是晚上休息時會下降若干厘米，通過分析發現，第1天晚上蟲子會下降n/2厘米，第2天晚上蟲子會下降(n/2+n/4)厘米，第3天晚上蟲子會下降(n/2+n/4+n/8)厘米，…，以此類推，
如果井的深度為m米，請問這只努力的蟲子第幾天能夠爬出枯井？

輸入
每組輸入資料占1行，
每行輸入兩個正整數n和m，且50m<n<100m，

輸出
輸出一個正整數，即蟲子第幾天爬出枯井，
資料保證有解

樣例輸入

60 1

樣例輸出

3

分析： 一個簡單的模擬題，注意單位的轉換，還有一點，如果白天已經爬上去了，那么就不用考慮晚上會掉落了，

代碼

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n,m,t=0;scanf("%d %d",&n,&m);m*=100;//米轉換成厘米
    double sum=0;
    while(1){
        t++,sum+=n;
        if(sum>=m){
            cout<<t<<endl;
            return 0;
        }
        sum-=n*(1.0-pow(0.5,t*1.0));
    }
    return 0;
}

問題 B: 六位數

題目描述
請撰寫一個程式統計在M和N之間（M<N，且包含M和N）有多少個六位數ABCDEF滿足以下要求：
(1) ABCDEF這六個數字均不相同，即A、B、C、D、E和F表示六個不同的數字，
(2) AB+CD=EF，即將這個六位數拆成三個兩位數，使得第1個和第2個兩位數的和等于第3個兩位數，

輸入
單組輸入，
輸入兩個六位正整數M和N（M<N），兩者之間用空格隔開，

輸出
輸出在M到N之間（包含M和N）滿足要求的六位數的個數，

樣例輸入

100000 110000

樣例輸出

0

分析： 模擬，列舉m,n之間的每一個數，判斷該數是不是滿足要求，沒有什么復雜的地方，題意理清就好了，

代碼

#include <bits/stdc++.h>

using namespace std;
bool check(int x){
    int p[10],cnt=0;
    while(x){
        p[cnt++]=x%10;
        x/=10;
    }
    if(cnt!=6)return 0;
    int a=p[0]+p[1]*10,b=p[2]+p[3]*10,c=p[4]+p[5]*10;//EF,CD,AB
    sort(p,p+cnt);//判斷是否重復
    for(int i=1;i<6;i++){
        if(p[i]==p[i-1])return 0;
    }
    if(b+c==a)return 1;
    else return 0;
}
int main()
{
    int m,n,num=0;scanf("%d %d",&m,&n);
    for(int i=m;i<=n;i++){
        if(check(i))num++;
    }
    printf("%d\n",num);
    return 0;
}

問題 C: 小h的工具人

題目描述
小h有一個工具人，把它放在一個大小為n*m的迷宮，

迷宮里’.‘表示空地，’*'表示陷阱，

當小H的工具人按照當前指令操作，無法進行下一步移動（即會遇到陷阱，邊界，訪問過的位置)，工具人將會右轉(順時針旋轉90度)，

否則，工具人只會按照當前指令方向移動，

請注意，小h的工具人無法移動到訪問過的方格，且同一位置只能旋轉一次，移動后方可再次旋轉，

請問小h的工具人最多可以經過多少個方格，

例如：
5 5
R…
…
…
…
…
小h的工具人最多可經過25個格子
2 3
…L
…
小h的工具人最多可經過3個格子，

輸入
多組輸入，
第一行兩個整數n和m，表示迷宮的行和列(1≤n,m≤10)
接下來n行，每行m個字符描述迷宮，
‘.’表示空地，表示可以通過的方格，‘*’表示陷阱，表示不能通過的方格，
迷宮中有一個英文字母，表示機器人的位置及其初始指令，
英文字母只有’U’,’D’,’L’,’R’四種，分別表示機器人的初始指令是向上，向下，向左，向右，

輸出
每組輸入，輸出一個答案，表示小h的工具人最多可訪問的方格數目，

樣例輸入

2 3
U…
.*.
4 4
R…
..
..
…

樣例輸出

4
12

分析： 模擬題，因為工具人只會按照當前指令的方向移動，直到無法繼續往前走，工具人轉彎只能右轉，所以我們定義的方向陣列是按照下左上右的順序，在一個方向上走到無法往前時，更換方向，當連續兩次更換方向時，不符合題意了，此時可以退出，輸出結果，

代碼

#include <bits/stdc++.h>
#define INF 0x7f7f7f7f
#define ll long long
using namespace std;
char mp[15][15];
int vis[15][15];
int d[4][2]={1,0,0,-1,-1,0,0,1};//下左上右
int x,y,op;//初始位置和初始方向
int main()
{
    int n,m;
    while(~scanf("%d %d",&n,&m)){
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n;i++){
            scanf("%s",mp[i]);
            for(int j=0;j<m;j++){
                if(mp[i][j]!='.'&&mp[i][j]!='*'){
                    x=i,y=j;
                    if(mp[i][j]=='U')op=2;//記錄初始指令方向
                    if(mp[i][j]=='R')op=3;
                    if(mp[i][j]=='D')op=0;
                    if(mp[i][j]=='L')op=1;
                }
            }
        }
        vis[x][y]=1;
        int ans=1,flag=0;
        while(1){
            while(1){
                int dx=x+d[op][0],dy=y+d[op][1];
                if(dx<0||dx>=n||dy<0||dy>=m||vis[dx][dy]||mp[dx][dy]=='*'){//要轉彎了
                    flag++;
                    break;
                }
                vis[dx][dy]=1;
                ans++;
                flag=0;
                x=dx,y=dy;
            }
            if(flag==2)break;//當在某一個點旋轉了兩次，不符合題意，退出
            op=(op+1)%4;
        }
        cout<<ans<<endl;
    }
    return 0;
}

問題 D: 小h的禮物

題目描述
在一個大小為n*m的迷宮里，藏著許多禮物，每個禮物有它們的價值aij
小h來到迷宮，準備拿禮物，
在迷宮，拿禮物有如下規則：
如果你拿了某一區域的禮物，左邊，右邊，上一行，下一行的禮物都不能拿了，
請問：小h可獲取的最大禮物價值和是多少？

輸入
多組輸入，

每組資料，第一行兩個整數n,m，分別表示迷宮的行和列(1≤n,m≤200)
接下來n行,每行m個整數，表示迷宮每個區域的禮物價值aij(0≤aij≤1000)

輸出
每組資料，輸出一個整數，表示小h可獲取的最大禮物價值和是多少，

樣例輸入

4 6
11 0 7 5 13 9
78 4 81 6 22 4
1 40 9 34 16 10
11 22 0 33 39 6

樣例輸出

242

分析： 動態規劃問題，這個問題如果上來就找狀態轉移方程是很麻煩的，條件限制太多導致找起來會很麻煩，其實這道題可以拆開來看，行和列，先對每一行做動態規劃，可以得出這一行能夠挖到的最大數量的金幣，再對每一行的最優解做動態規劃，求出整體最優解，兩次的規則是一樣的，
對每一行，dp[i][j]=max(dp[i][j-1],dp[i][j-2]+a[i][j])，表示第i行第j列的最優價值等于第i行第j-1列的值和第i行第j-2列的值加上當前位置的值的最大值，
求總體的最優價值同理，

代碼

#include <bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f

using namespace std;
int dp[205][205];
int ans[205];
int a[205][205];
int main()
{
    int n,m;
    while(~scanf("%d %d",&n,&m)){
        memset(dp,0,sizeof(dp));
        memset(ans,0,sizeof(ans));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                scanf("%d",&a[i][j]);
            }
        }
        //求出每一行的最有價值和
        for(int i=1;i<=n;i++)dp[i][1]=a[i][1],dp[i][2]=max(a[i][1],a[i][2]);
        for(int i=1;i<=n;i++){
            for(int j=3;j<=m;j++){
                dp[i][j]=max(dp[i][j-1],dp[i][j-2]+a[i][j]);
            }
        }
        //求整體的最優價值和
        ans[1]=dp[1][m],ans[2]=max(dp[1][m],dp[2][m]);
        for(int i=3;i<=n;i++)ans[i]=max(ans[i-1],ans[i-2]+dp[i][m]);
        printf("%d\n",ans[n]);
    }
    return 0;
}

問題 E: 小h的書桌

題目描述
強迫癥小h在整理書庫，準備把書全部擺放在書桌上，擺放若干堆，

小h要求：書桌上的每堆書必須按照書本厚度從小到到大排序（也就是每堆書下面的不能比上面的薄，可以一樣），

小h會從書庫里一本一本地拿書出來，然后進行擺放，請問小h最少需要擺放多少堆，才能擺好所有書籍，

輸入
第一行一個整數，表示書庫書本總數量(1≤n≤10^5)
第二行個整數，表示書本厚度ai(1≤ai≤30000)

輸出
輸出一個整數，表示小h最少需要擺放堆數，

樣例輸入

8
389 207 155 300 299 170 158 65

樣例輸出

2

提示
最少需要擺放兩堆

第一堆：398-207-155-65

第二堆：300-299-170-158

分析： 典型的LIS升級版，n有10^5， 如果用n^2的方法求LIS肯定會超時，
為什么是求LIS呢，書桌上的書必須厚度從小到大，厚度可以相等，說明每一堆書的厚度最大的那本形成了一個最長非遞減子序列，所以我們求這個序列的最長非遞減子序列即可，

簡單說下怎么O(nlogn)弄一個最長遞增子序列吧，最長非遞減子序列考慮相等就好了，
考慮一個數列3 4 1 2 5
首先，把3加入答案序列中，然后加4，發現4>3所以顯然可以將4直接加入，那么答案序列就是{3,4},然后加1，發現1<4,1<3，然后將1替換3，此時的答案序列{1,4},然后加入2，將2替換4，此時答案序列為{1,2}，然后加入5，5>2，直接加入，答案序列為{1,2,5}，為什么這么做不會影響結果呢？你可以這么想，我們當前已經求出了一個當前最優的序列，如果我們用1替換3，然后后面來一個數字替換了4，那么我們就可以得到一個更優的序列，而如果沒有數字替換4，那么這個1替換3也就是沒有貢獻的，不會影響我們結果的最優性，然后，如何找到一個最小的但是大于某個數字的數字，就可以進行二分查找了，因為我們的答案序列是有序的，

代碼

#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f

using namespace std;
int ans[100005],k=0;
int main()
{
    int n,a;scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a);
        if(i==1)ans[k++]=a;
        else{
            int id=lower_bound(ans,ans+k,a)-ans;
            if(id>=k)ans[k++]=a;
            else ans[id]=a;
        }
    }
    cout<<k<<endl;
    return 0;
}

問題 F: 河畔軍訓

題目描述
河畔鎮是一個景色秀麗，氣候宜人的度假勝地，每天都會有很多的游客來這里游玩，但奇怪的是這里總會出現一些潛伏者，果不其然，通過保衛者的跟蹤，發現在河畔鎮的地下隱藏著Blitz的秘密武器實驗室，最危險的地方也是最安全的地方，這里人多，所以只能采用狙擊作戰，一場“無聲無息“的戰斗即刻打響，
每到周末小z，小y便開始在河畔軍訓小h(當然有時也會被反軍訓)，
不過他們軍訓采用刀戰(即相遇時才可軍訓)
每當小z，小y，小h三人在河畔整相遇時，小z和小y便可軍訓小h
由于小h有兔耳朵buff加成，小h每秒最多可以移動3步，且可以選擇上/下/左/右/左上/左下/右上/右下8個方向移動
小z，小y每秒均只能移動1步，只能上/下/左/右4個方向移動，
當然，三人均可選擇保持原地不動，
三人移動始終在地圖范圍內，
下面，給你河畔的地圖以及小z，小y，小h的初始坐標，
請你求出最快軍訓小h的時間(即3人相遇的最短時間)，如果無法軍訓小h則輸出“lack of junxun”

輸入
多組資料
每組資料第一行兩個整數N,M(1<=N,M<=1000)代表河畔地圖的行和列
接下來是N*M大小的地圖
其中“z”，“y”，“h”分別代表小z，小y，小h的初始坐標
“#”代表障礙物，“.”表示可以正常通過的位置

輸出
對于每組資料
如果能軍訓小h，則輸出最快軍訓小h所需的時間
否則，輸出“lack of junxun”

樣例輸入

2 4
z…h
#y#.
2 3
z#y
#h.

樣例輸出

1
lack of junxun

分析： 一道稍微復雜一點的BFS，因為要求最短時間，我們使用BFS，小z，小y每次只能移動一步，小h每次能走三步，三個人每次都可以不走，那么我們可以想到，每一次行動（小z，小y移動一步，小h移動三步），我們都標記他們走過的點，如果其中某一個人走到的點，發現其余兩個人都來過，那么說明三人可以在這個點匯合，
好像以前寫過一個類似的題，但是忘了是啥了…

代碼

#include <bits/stdc++.h>

using namespace std;
struct node{
    int x,y;
};
queue<node>p[3];
char mp[1005][1005];
int vis[1005][1005][3];
int d[8][2]={1,0,0,1,-1,0,0,-1,1,1,1,-1,-1,-1,-1,1};
int zx,zy,yx,yy,hx,hy,n,m;
void init(){
    memset(vis,0,sizeof(vis));
    while(!p[0].empty())p[0].pop();
    while(!p[1].empty())p[1].pop();
    while(!p[2].empty())p[2].pop();
    p[0].push((node){zx,zy});
    p[1].push((node){yx,yy});
    p[2].push((node){hx,hy});
    vis[zx][zy][0]=1,vis[yx][yy][1]=1,vis[hx][hy][2]=1;
}
bool check(int x,int y,int k){
    if(x<0||x>=n||y<0||y>=m)return 0;
    if(mp[x][y]=='#'||vis[x][y][k])return 0;
    return 1;
}
bool bfs(int k){
    int num=p[k].size();//每一次只把上一步存的點往后走一步
    while(num--){
        node now=p[k].front();p[k].pop();
        int x=now.x,y=now.y;
        for(int i=0;i<8;i++){
            if(i==4&&(k==0||k==1))break;//小h才能走8個方向
            int dx=x+d[i][0],dy=y+d[i][1];
            if(!check(dx,dy,k))continue;
            vis[dx][dy][k]=1;
            if(vis[dx][dy][0]&&vis[dx][dy][1]&&vis[dx][dy][2])return 1;//如果三個人都走過這個位置，說明可以同時到達某個點了，
            p[k].push((node){dx,dy});
        }
    }
    return 0;
}
void adie(){
    int step=0;
    init();//初始化
    while(!p[0].empty()||!p[1].empty()||!p[2].empty()){
        step++;
        if(bfs(0)){cout<<step<<endl;return;}
        if(bfs(1)){cout<<step<<endl;return;}
        if(bfs(2)){cout<<step<<endl;return;}//小h可以走三步
        if(bfs(2)){cout<<step<<endl;return;}
        if(bfs(2)){cout<<step<<endl;return;}
    }
    cout<<"lack of junxun"<<endl;
    return ;
}
int main()
{
    while(~scanf("%d %d",&n,&m)){
        for(int i=0;i<n;i++)scanf("%s",mp[i]);
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(mp[i][j]=='z')zx=i,zy=j;//記錄三人的初始位置
                if(mp[i][j]=='y')yx=i,yy=j;
                if(mp[i][j]=='h')hx=i,hy=j;
            }
        }
        adie();
    }
    return 0;
}

問題 G: 小A的煩惱

題目描述
小A生活在一個神奇的國家，這個國家有N（N<=100000）個城市，還有M（M<=5000000）條道路連接兩城市，道路連接的兩個城市可以直接免費到達，小A比較煩惱，因為他想知道每個城市能直接到達哪些城市，你能幫幫他嗎？保證每個城市都有道路與其連接，（注：按照輸入的道路順序輸出每個城市直接連接的城市,若有城市出現多次，則按最小出現次序輸出）

輸入
第1行包含兩個整數N和M；接下來M行，每行兩個整數描述一條道路連接的兩個城市的編號，

輸出
輸出N行，每行若干個用一個空格隔開的整數；第I行輸出的是與城市I直接相連城市編號，保證城市的出現按照道路輸入的先后順序出現，

樣例輸入

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

樣例輸出

3 4 2
3 4 1
2 1
1 2

分析： 用vector存每一個城市與其相連的城市，注意去重即可，

代碼

#include <bits/stdc++.h>

using namespace std;
vector<int>mp[100005];
int main()
{
    int n,m;
    while(~scanf("%d %d",&n,&m)){
        for(int i=1;i<=n;i++)mp[i].clear();
        for(int i=1;i<=m;i++){
            int u,v;scanf("%d %d",&u,&v);
            if(find(mp[u].begin(),mp[u].end(),v)!=mp[u].end())continue;//如果u到v已經有了一條路，就不用添加了
            mp[u].push_back(v);
            if(find(mp[v].begin(),mp[v].end(),u)!=mp[v].end())continue;//如果v到u已經有了一條路，也不用添加了
            mp[v].push_back(u);
        }
        for(int i=1;i<=n;i++){
            for(auto x:mp[i])cout<<x<<" ";
            cout<<endl;
        }
    }
    return 0;
}

問題 H: l/n不分的小波

題目描述
小波非常羨慕普通話好的同學，因為自己經常l/n不分，遇到非常下飯的事情時，小波有時候會情不自禁的說聲nb，但是很有可能說成了lb，
現有一只含大小寫字母的字串s，表示小波說的話，問其中包含多少個nb和NB，nB，Nb，假設其中所有的lb(LB，lB，Lb)都是因為小波l/n不好的緣故，

輸入
單組輸入，一個只含小寫字母的字串s，長度<1e5 ，

輸出
一個整數，表示字串中包含多少個nb和NB，nB，Nb，

樣例輸入

wcnb

樣例輸出

1

分析： 按照題意模擬，

代碼

#include <bits/stdc++.h>

using namespace std;

int main()
{
    string s;cin>>s;
    int num=0;
    for(int i=1;i<s.size();i++){//模擬所有情況
        if((s[i-1]=='N'||s[i-1]=='n')&&(s[i]=='b'||s[i]=='B'))num++;
        if((s[i-1]=='L'||s[i-1]=='l')&&(s[i]=='b'||s[i]=='B'))num++;
    }
    cout<<num<<endl;
    return 0;
}