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);
}
有这样一个序列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);
}