本文共 8526 字，大约阅读时间需要 28 分钟。

问题 A: 特殊立方数

题目描述

存在一个n位数M，它的立方数K的最后n位也是M，我们可以称这样的K为特殊立方数。 例如：15625 = 25 * 25 * 25，因此15625是一个特殊立方数。 请计算[a, b]之间有多少个特殊立方数，如果一个都没有则输出0。

输入

单组输入。 输入两个正整数a和b，1<=a<=b<=10^9。

输出

输出在[a,b]之间（包含a和b）有多少个特殊立方数，如果一个都没有则输出0。

样例输入

1 200

样例输出

3

提示

在1到200之间，存在1、64和125三个特殊立方数。

分析： 直接暴力，遍历1到1000，按照题意模拟。

代码：

#include
   
    #define ll long long#define INF 0x7f7f7f7fusing namespace std;int main(){       int a,b;    while(~scanf("%d %d",&a,&b)){           int num=0;        for(int i=1;i<=1000;i++){               if(i*i*i
    
     b)break;            int x=i,t=1;            while(x)x/=10,t*=10;            if(i*i*i%t==i)num++;        }        cout<
     
      <
     
    
   

问题 B: 进制转换

题目描述

写出一个程序，接受一个十六进制的数，输出该数值的十进制表示。（多组同时输入 ）

输入

多组输入，每组数据不会超过50条 每组输入一个十六进制的数值字符串n(3<=N<=1e3，N表示字符串长度)。 题目保证十六进制数中的英文字母为大写

输出

输出该数值的十进制字符串。

样例输入

0xA

样例输出

10

分析： 模拟，因为字符串长度1e3，数字很大，所以用到了高精度。每一次先读取一个字符，转换成十进制数，然后每次还需要乘以每一位的权值。具体模拟过程对照代码查看。

代码：

#include
   
    #define ll long long#define INF 0x7f7f7f7fusing namespace std;int ans[10005],k;void fun2(int m){       ans[0]+=m;    for(int i=0;i<=k;i++){           ans[i+1]+=ans[i]/10;        ans[i]%=10;    }    while(ans[k+1]){           k++;        ans[k+1]+=ans[k]/10;        ans[k]%=10;    }}void fun1(){       for(int i=0;i<=k;i++)ans[i]*=16;    for(int i=0;i<=k;i++){           ans[i+1]+=ans[i]/10;        ans[i]%=10;    }    while(ans[k+1]){           k++;        ans[k+1]+=ans[k]/10;        ans[k]%=10;    }}int main(){       string s;    while(cin>>s){           memset(ans,0,sizeof(ans));        int n=s.size();        k=0;        for(int i=2;i
    
     ='A'&&s[i]<='Z')                t=s[i]-'A'+10;            if(s[i]>='0'&&s[i]<='9')                t=s[i]-'0';            fun2(t);//先加上该数        }        for(int i=k;i>=0;i--)            printf("%d",ans[i]);        printf("\n");    }}
    
   

问题 C: 小易喜欢的数列

题目描述

小易非常喜欢拥有以下性质的数列: 1、数列的长度为n 2、数列中的每个数都在1到k之间(包括1和k) 3、对于位置相邻的两个数A和B(A在B前),都满足(A <= B)或(A mod B != 0)(满足其一即可) 例如,当n = 4, k = 7 那么{1,7,7,2},它的长度是4,所有数字也在1到7范围内,并且满足第三条性质,所以小易是喜欢这个数列的 但是小易不喜欢{4,4,4,2}这个数列。小易给出n和k,希望你能帮他求出有多少个是他会喜欢的数列。

输入

多组输入 输入包括两个整数n和k(1 ≤ n ≤ 10, 1 ≤ k ≤ 10^5)。

输出

输出一个整数,即满足要求的数列个数,因为答案可能很大,输出对1,000,000,007取模的结果。

样例输入

2 2

样例输出

3

分析： 动态规划，dp[i][j]表示整个状态空间，dp[i][j]表示数列长度为i且以j结尾

递推关系：dp[i][j]+=dp[i-1][m] (1≤m≤k,且是合法序列)，如果直接判断序列是否合法，那么三层循环会超时，这时我们可以先将dp[i-1]中的所有合法序列求和记作sum，然后对于dp[i][j]（1≤j≤k）减去非法序列的个数即可。

代码：

#include
   
    #define ll long long#define INF 0x7f7f7f7fusing namespace std;const int mod=1e9+7;int dp[15][100005];int main(){       int n,k;    while(~scanf("%d %d",&n,&k)){           for(int i=1;i<=k;i++)dp[1][i]=1;//第一层的每个数字都能放        for(int i=2;i<=n;i++){               int sum=0;            for(int j=1;j<=k;j++)sum=(sum+dp[i-1][j])%mod;//上一层所有的合法序列            for(int j=1;j<=k;j++){                   int temp=j*2;                dp[i][j]=sum;                while(temp<=k){                       dp[i][j]=(dp[i][j]-dp[i-1][temp]+mod)%mod;//减去不合法的序列，可能是负数所以加mod取余                    temp+=j;                }            }        }        int sum=0;        for(int i=1;i<=k;i++)sum=(sum+dp[n][i])%mod;        cout<
    
     <
    
   

问题 D: 幸运数

题目描述

众所周知，不管是人还是熊都需要人品。于是乎，为了给自己找一个幸运数字，Mavis 学习了人类的阿拉伯数字，并不知从哪儿弄来了一串序列和一个 S，Mavis 说：“长度最短且和大于等于 S 的连续子段的长度， 就是俺的幸运数字”！

但是 Mavis 只会喊口号，不会解决问题，所以这个问题就交给你了。

输入

输入文件共三行。

第一行输入仅一个正整数 n，意义如题所述。（ n ≤ 4000000, ai ≤ 10^9)

第二行输入 n 个正整数 ai，表示序列中的元素。

第三行输入仅一个正整数 S，意义如题所述。

每两个输入的数之间都用一个空格隔开。

输出

输出文件仅一行一个整数，表示幸运数。

样例输入

8

4 12 10 18 17 10 17 17

40

样例输出

3

分析： 尺取法模拟出每一个子段和，记录最短的长度。最初l，r都为1，开始模拟，r先不断右移，直到sum＞=s，记录长度，然后l开始右移，直到sum<s重新开始移动r。像一把尺子不断的移动，可对照代码理解。（我觉得代码可能比我写的这些容易看懂…）

代码：

#include
   
    #define ll long long#define INF 0x7f7f7f7fusing namespace std;int a[4000005];int main(){       int n;scanf("%d",&n);    for(int i=1;i<=n;i++)scanf("%d",&a[i]);    int s;scanf("%d",&s);    ll sum=0,l=1,r,ans=n;    for(r=1;r<=n;){           if(sum
    
     =s)ans=min(r-l,ans),sum-=a[l++];    cout<
     
      <
     
    
   

问题 E: 小h上学路

题目描述

小h的位置是,学校的位置是。 小h上学有三种移动方式： 1：走路，可以从位置a移动到a+1或a-1 2：公交，可以从位置移动到nextprime(a) 3：打的，可以从位置a移动到或2a或3a nextprime(a)表示第一个大于a的素数 每种方式所需时间都是1min，请问到达学校的最短时间是多少。

输入

输入的包含两个整数a,b(0≤a,b≤1e5)，分别表示小h位置和学校位置。

输出

输出小h到达学校所需最短时间。

样例输入

4 21

样例输出

3

提示

走路：4->5 公交：5->7 打的：7->21 最少花3min

代码： bfs搜索，先打素数表，之后按照题目意思开始搜索。详见代码

#include
   
    #define ll long long#define INF 0x7f7f7f7fusing namespace std;int a,b,prime[300005],pos_ne,x=0;bool ju[300005],vis[300005];struct node{       int pos,time;    bool operator <(const node &a) const{           return a.time
    
     300002)break;            ju[i*prime[j]]=true;            if(i%prime[j]==0)break;        }    }}void bfs(){       priority_queue
     
      p;    p.push((node){   a,0});    while(!p.empty()){           node now=p.top();p.pop();        int pos=now.pos,time=now.time;        if(vis[pos])continue;        vis[pos]=1;        if(pos==b){               cout<
      <
       
        0)p.push((node){   pos-1,time+1});        pos_ne=upper_bound(prime,prime+x,pos)-prime;        p.push((node){   prime[pos_ne],time+1});        if(pos
       
     
    
   

问题 F: 小h的地图

题目描述

小h有一幅奇怪的地图，地图上只列出了n个点，m条路，小h处于s点，含浦家苑是d点。

小h的地图有点奇怪：

在奇数编号、偶数编号的点，分别需要等待1、2分钟才会提示下一步怎么走。

现在告诉你地图的具体情况，小h想知道他能不能在M分钟内赶到含浦家苑。

输入

多组输入。

每组输入第一行有5个整数n,m,s,dM，含义见题目描述。

接下来M行，每行三个数字u,v,t，分别代表每条路的两个点和步行时间。

题目保证：1≤n≤m≤1000

输出

对于每组输入数据，输出一行。

如果小h能在M分钟内赶到含浦家苑，输出YES和最少花费的时间。

否则输出NO。

样例输入

4 3 1 4 10

1 2 1

3 2 2

3 4 3

5 4 2 4 7

1 2 5

5 4 2

3 5 1

2 3 1

样例输出

YES 10

NO

分析： bfs搜索，存图的时候可以先考虑好等待的时间，bfs用优先队列存点。

代码：

#include
   
    #define ll long long#define INF 0x7f7f7f7fusing namespace std;int n,m,s,d,M;int mp[1005][1005];int vis[1005];struct node{       int pos,time;    bool operator<(const node &a)const{           return a.time
    
     p;    memset(vis,0,sizeof(vis));    p.push((node){   s,0});    while(!p.empty()){           node now=p.top();p.pop();        int pos=now.pos,time=now.time;        if(vis[pos])continue;        vis[pos]=1;        if(time>M){               cout<<"NO"<
    
   

问题 G: 小h的题目

题目描述

每个人都在担心考试的难度。 小h有一个规则来出题目，他会在写问题之前写一个随机字符串 只要可以按顺序在此字符串中找到四个字母E，A，S，Y。 他的题目会很容易。 现在你有这个字符串，请告诉我测试题的难度。

输入

输入数据有多组，每组占用一行，由一个字符串组成（1≤len(str)≤1000）

输出

对于每组输入，输出一行。

题目很容易输出easy，否则输出difficult。

样例输入

eAsy

SEoAtSNY

样例输出

difficult

easy

分析： 简单模拟，一个字母一个字母搜，若全部找到则输出easy。反之输出difficult

代码：

#include
   
    #define ll long long#define INF 0x7f7f7f7fusing namespace std;char t[]={   'E','A','S','Y'};int main(){       string s;    while(cin>>s){           int k=0;        for(int i=0;i
   

问题 H: 有趣的树上问题

问题描述

小波发现了一道比较有趣的树上问题。现有一个由n个节点组成的树（也可认为是一个连通的无环无向图），这棵树共有n-1条边，节点从1开始编号，且根节点为1。有趣的点在于树上的每个节点都有一个tag标签，题目保证每个标签都只可能是小写字母中的某一个。现在需要求出每个节点的子树中有多少个与当前结点标签相同的个数（子树包含其自身）。

输入

第一行输入n，表示共有n个结点(n<=1e5)。 第二行到第n行，每行输入两个数字u，v，表示u、v之间存在一条边。 第n+1行输入一个字符串s，表示每个节点的tag标签值。

输出

一行，每个节点的子树中有多少个与当前结点标签相同的个数（子树包含其自身），两个数字之间用空格隔开。

样例输入

7

1 2

1 3

2 5

2 6

3 4

3 7

abaedcd

样例输出

2 1 1 1 1 1 1

分析： dfs搜索，一路深搜，搜完每一个节点的子树后记录该节点的26个字母的tag值是多少。最后用ans数组维护该节点的子树中有多少个与当前结点标签相同的个数。

代码：

#include 
   
    #define INF 0x7f7f7f7f#define ll long longusing namespace std;vector
    
     mp[100005];int tag[100005][30],n;int ans[100005];string s;void dfs(int x,int pre){       tag[x][s[x-1]-'a']++;    for(int i=0;i
     
      >s;    dfs(1,0);    for(int i=1;i<=n;i++)cout<
      
       <<" ";    cout<
      
     
    
   

问题 I: 堆棋子

题目描述

小易将n个棋子摆放在一张无限大的棋盘上。第i个棋子放在第x[i]行y[i]列。同一个格子允许放置多个棋子。每一次操作小易可以把一个棋子拿起并将其移动到原格子的上、下、左、右的任意一个格子中。小易想知道要让棋盘上出现有一个格子中至少有i(1 ≤ i ≤ n)个棋子所需要的最少操作次数。

输入

多组输入 输入包括三行,第一行一个整数n(1 ≤ n ≤ 50),表示棋子的个数 第二行为n个棋子的横坐标x[i](1 ≤ x[i] ≤ 10^9) 第三行为n个棋子的纵坐标y[i](1 ≤ y[i] ≤ 10^9)

输出

输出n个整数,第i个表示棋盘上有一个格子至少有i个棋子所需要的操作数,以空格分割。行末无空格

如样例所示:

对于1个棋子: 不需要操作 对于2个棋子: 将前两个棋子放在(1, 1)中 对于3个棋子: 将前三个棋子放在(2, 1)中 对于4个棋子: 将所有棋子都放在(3, 1)中

样例输入

4

1 2 4 9

1 1 1 1

样例输出

0 1 3 10

分析： n最大只有50，我们可以枚举每一个点作为那个摆放i个棋子的点，每次枚举，记录其他点到该点的距离，因为我们要求最少的操作次数，所以我们将距离从小到大排序，优先移动距离小的。每次维护一个sum记录最小的移动次数。

代码：

#include 
   
    #define INF 0x7f7f7f7f#define ll long longusing namespace std;int x[55],y[55];ll ans[55],sum[55];int main(){       int n;    while(~scanf("%d",&n)){           for(int i=1;i<=n;i++)sum[i]=1e12;        for(int i=1;i<=n;i++)scanf("%d",&x[i]);        for(int i=1;i<=n;i++)scanf("%d",&y[i]);        for(int i=1;i<=n;i++){   //枚举所放位置的行            for(int j=1;j<=n;j++){   //枚举所放位置的列                for(int k=1;k<=n;k++)ans[k]=abs(x[i]-x[k])+abs(y[j]-y[k]);//枚举每一个棋子的移动步数                sort(ans+1,ans+n+1);                ll sum_temp=0;                for(int k=1;k<=n;k++)sum_temp+=ans[k],sum[k]=min(sum[k],sum_temp);            }        }        for(int i=1;i<=n;i++)printf("%lld ",sum[i]);        printf("\n");    }    return 0;}