1001 数组中和等于K的数对 1002 数塔取数问题 1003 阶乘后面0的数量 1004 n^n的末位数字 1009 数字1的数量

时间：2021-07-03 09:12:38
　　　　　　　　　　　　　　　　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);

 }




应该还是可以理解的，比较快。


 








相关文章