1001 数组中和等于K的数对
基准时间限制：1 秒 空间限制：131072 KB 分值: 5 难度：1级算法题
给出一个整数K和一个无序数组A，A的元素为N个互不相同的整数，找出数组A中所有和等于K的数对。例如K = 8，数组A：{-1,6,5,3,4,2,9,0,8}，所有和等于8的数对包括(-1,9)，(0,8)，(2,6)，(3,5)。
Input
第1行：用空格隔开的2个数，K N，N为A数组的长度。(2 <= N <= 50000，-10^9 <= K <= 10^9)
第2 - N + 1行：A数组的N个元素。（-10^9 <= A[i] <= 10^9)
Output
第1 - M行：每行2个数，要求较小的数在前面，并且这M个数对按照较小的数升序排列。
如果不存在任何一组解则输出：No Solution。
Input示例
8 9
-1
6
5
3
4
2
9
0
8
Output示例
-1 9
0 8
2 6
3 5
排序后线扫差不多吧，简单贪心。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<map>
using namespace std; const int NN=; int n,k;
int a[NN];
bool boo=;
map<int,int>p; int main()
{
scanf("%d%d",&k,&n);
for (int i=;i<=n;i++)
{
scanf("%d",&a[i]);
p[a[i]]++;
}
sort(a+,a+n+);
for (int i=n;i>=;i--)
{
int x=k-a[i];
if (x>=a[i]) break;
if (p[x]) {printf("%d %d\n",x,a[i]);boo=;}
}
if (!boo) printf("No Solution\n");
}
1002 数塔取数问题
一个高度为N的由正整数组成的三角形，从上走到下，求经过的数字和的最大值。
每次只能走到下一层相邻的数上，例如从第3层的6向下走，只能走到第4层的2或9上。
5
8 4
3 6 9
7 2 9 5
例子中的最优方案是：5 + 8 + 6 + 9 = 28
Input
第1行：N，N为数塔的高度。(2 <= N <= 500)
第2 - N + 1行：每行包括1层数塔的数字，第2行1个数，第3行2个数......第k+1行k个数。数与数之间用空格分隔（0 <= A[i] <= 10^5) 。
Output
输出最大值
Input示例
4
5
8 4
3 6 9
7 2 9 5
Output示例
28
一道dp的水题吧。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std; const int NN=,INF=1e8+;; int n;
int f[NN][NN]; int main()
{
scanf("%d",&n);
for (int i=;i<=n;i++)
for (int j=;j<=i;j++)
scanf("%d",&f[i][j]);
for (int i=;i<=n;i++)
for (int j=;j<=i;j++)
f[i][j]=max(f[i][j]+f[i-][j-],f[i][j]+f[i-][j]);
int ans=-INF;
for (int i=;i<=n;i++)
ans=max(ans,f[n][i]);
printf("%d\n",ans);
}
1003 阶乘后面0的数量
n的阶乘后面有多少个0？
6的阶乘 = 1*2*3*4*5*6 = 720，720后面有1个0。
Input
一个数N(1 <= N <= 10^9)
Output
输出0的数量
Input示例
5
Output示例
1
发现2一定比5多，所以只要找5的倍数即可除一除就好了。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<map>
using namespace std; int n,ans=; int main()
{
scanf("%d",&n);
for (long long x=;x<=n;x*=)
ans+=(n/x);
printf("%d\n",ans);
}
1004 n^n的末位数字
给出一个整数N，输出N^N（N的N次方）的十进制表示的末位数字。
Input
一个数N（1 <= N <= 10^9）
Output
输出N^N的末位数字
Input示例
13
Output示例
3
水题吧，最后一位乘一乘，取模即可。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std; int n;
bool boo[]={};
int flag[]={}; int main()
{
scanf("%d",&n);
int y=n%;
int x=n%,ci=;
while()
{
if (boo[x]) break;
ci++,boo[x]=,flag[x]=ci;
x=x*y%;
}
x=n%ci;
if (x==) x=ci;
for (int i=;i<=;i++)
if (flag[i]==x)
{
printf("%d\n",i);
break;
}
}
1009 数字1的数量
给定一个十进制正整数N，写下从1开始，到N的所有正数，计算出其中出现所有1的个数。
例如：n = 12，包含了5个1。1,10,12共包含3个1，11包含2个1，总共5个1。
Input
输入N(1 <= N <= 10^9)
Output
输出包含1的个数
Input示例
12
Output示例
5
这道题可以计算每个位置出现1的次数，一个简单的数学归纳+计算，具体看代码。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std; int n; int main()
{
scanf("%d",&n);
int ans=,tail=,mi=;
while (n!=)
{
int x=n%;
n/=;
ans+=n*mi;
if (x==) ans+=tail+;
if (x>) ans+=mi;
tail=tail+x*mi,mi*=;
}
printf("%d",ans);
}
应该还是可以理解的，比较快。