问题 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;
}