1042 数字0-9的数量 1050 循环数组最大子段和 1062 序列中最大的数 1067 Bash游戏 V2 1092 回文字符串

1042 数字0-9的数量
基准时间限制：1 秒 空间限制：131072 KB 分值: 10 难度：2级算法题　

给出一段区间a-b，统计这个区间内0-9出现的次数。

 
比如 10-19，1出现11次（10,11,12,13,14,15,16,17,18,19,其中11包括2个1)，其余数字各出现1次。

Input

两个数a,b（1 <= a <= b <= 10^18)

Output

输出共10行，分别是0-9出现的次数

Input示例

10 19

Output示例

1

11

1

1

1

1

1

1

1

1
这道题和有一题统计数字，差不多的，只不过这里统计所有，0的细节稍微特殊考虑一下。

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 #include<cmath>

 #include<cstring>

 using namespace std;

 typedef long long LL;

 LL st,ed,ans[]={};

 LL make(LL num,int now)

 {

     LL res=,tail=,mi=;

     if (num<&&now==) return ;

     while (num!=)

     {

         if (now==&&num<) break;

         int x=num%;

         num/=;

         res+=(num-(now==))*mi;

         if (x>now) res+=mi;

         if (x==now) res+=tail+;

         tail=(LL)x*mi+tail,mi*=;

     }

     return res;

 }

 int main()

 {

     scanf("%lld%lld",&st,&ed);

     for (int i=;i<=;i++)

     {

         ans[i]=make(ed,i)-make(st-,i);

         printf("%lld\n",ans[i]);

     }

 }

1050 循环数组最大子段和
基准时间限制：1 秒 空间限制：131072 KB 分值: 10 难度：2级算法题

N个整数组成的循环序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的连续的子段和的最大值（循环序列是指n个数围成一个圈，因此需要考虑a[n-1],a[n],a[1],a[2]这样的序列）。当所给的整数均为负数时和为0。
例如：-2,11,-4,13,-5,-2，和最大的子段为：11,-4,13。和为20。
 

Input

第1行：整数序列的长度N（2 <= N <= 50000)

第2 - N+1行：N个整数 (-10^9 <= S[i] <= 10^9)

Output

输出循环数组的最大子段和。

Input示例

6

-2

11

-4

13

-5

-2

Output示例

20
直接爆力+剪枝就过了，普通最大字段和不行，不过可以从前面的非0出发，因为有长度限制。

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 #include<cmath>

 #include<cstring>

 using namespace std;

 typedef long long LL;

 const int NN=;

 int n;

 int a[NN*];

 int main()

 {

     scanf("%d",&n);

     for (int i=;i<=n;i++)

     {

         scanf("%d",&a[i]);

         a[i+n]=a[i];

     }

     LL ans=,x;

     for (int i=;i<=n;i++)

     {

         x=;

         for (int j=i;j<i+n;j++)

              {

                 if (x+a[j]<) break;

                 else x+=a[j];

                 ans=max(x,ans);

             }

     }

     printf("%lld\n",ans);

 }

1062 序列中最大的数
题目来源： Ural 1079
基准时间限制：1 秒 空间限制：131072 KB 分值: 10 难度：2级算法题

 收藏
 关注

有这样一个序列a：
a[0] = 0
a[1] = 1
a[2i] = a[i]
a[2i+1] = a[i] + a[i+1]
 
输入一个数N，求a[0] - a[n]中最大的数。
a[0] = 0, a[1] = 1, a[2] = 1, a[3] = 2, a[4] = 1, a[5] = 3, a[6] = 2, a[7] = 3, a[8] = 1, a[9] = 4, a[10] = 3。
例如：n = 5，最大值是3，n = 10，最大值是4。
 

Input

第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10)

第2 - T + 1行：T个数，表示需要计算的n。（1 <= n <= 10^5)

Output

共T行，每行1个最大值。

Input示例

2

5

10

Output示例

3

4
预处理+输出

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #include<iostream>

 #include<cstring>

 using namespace std;

 typedef long long LL;

 const int NN=;

 LL a[NN],ans[NN];

 int main()

 {

     a[]=ans[]=;

     a[]=ans[]=;

     for (int i=;i<NN;i++)

     {

         if (i%==) a[i]=a[i/];

         else a[i]=a[i/]+a[i/+];

         ans[i]=max(ans[i-],a[i]);

     }

     int T,x;

     scanf("%d",&T);

     while (T--)

     {

         scanf("%d",&x);

         printf("%lld\n",ans[x]);

     }

 }

1067 Bash游戏 V2
基准时间限制：1 秒 空间限制：131072 KB 分值: 10 难度：2级算法题

 收藏
 关注

有一堆石子共有N个。A B两个人轮流拿，A先拿。每次只能拿1，3，4颗，拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出N，问最后谁能赢得比赛。
例如N = 2。A只能拿1颗，所以B可以拿到最后1颗石子。
 

Input

第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000)

第2 - T + 1行：每行1个数N。(1 <= N <= 10^9)

Output

共T行，如果A获胜输出A，如果B获胜输出B。

Input示例

3

2

3

4

Output示例

B

A

A
发现一个循环的规律吧，然后%一下，输出就可以了

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 const int ans[]={,,,,,,,};

 int main()

 {

     int T,x;

     scanf("%d",&T);

     while (T--)

     {

         scanf("%d",&x);

         x=x%;

         if (x==) x=;

         printf("%c\n",ans[x]+'A');

     }

 }

1092 回文字符串
基准时间限制：1 秒 空间限制：131072 KB 分值: 10 难度：2级算法题

 收藏
 关注

回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。每个字符串都可以通过向中间添加一些字符，使之变为回文字符串。
例如：abbc 添加2个字符可以变为 acbbca，也可以添加3个变为 abbcbba。方案1只需要添加2个字符，是所有方案中添加字符数量最少的。
 

Input

输入一个字符串Str，Str的长度 <= 1000。

Output

输出最少添加多少个字符可以使之变为回文字串。

Input示例

abbc

Output示例

2
水题，正和反求一次lcs就差不多了。

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #include<cstring>

 #include<iostream>

 using namespace std;

 const int NN=;

 char a[NN],b[NN];

 int dp[NN][NN];

 int main()

 {

     char temp;

     int n,i,j;

     scanf("%s",a);

     n=strlen(a);

     i=;j=n-;

     while(i<n) b[i++]=a[j--];

     for(i=;i<=n;i++)

         for(j=;j<=n;j++)

             if(a[i-]==b[j-]) dp[i][j]=max(dp[i-][j-]+,max(dp[i-][j],dp[i][j-]));

             else dp[i][j]=max(dp[i-][j-],max(dp[i-][j],dp[i][j-]));

     int ans=n-dp[n][n];

     printf("%d\n",ans);

 }  

1042 数字0-9的数量 1050 循环数组最大子段和 1062 序列中最大的数 1067 Bash游戏 V2 1092 回文字符串的相关教程结束。