2020 第十一届 蓝桥杯 整数拼接

发表于 分类于 阅读次数： 本文字数： 953 阅读时长 ≈ 3 分钟

此题为2020年第十一届蓝桥杯省赛第一场B组第九题

时间限制: 1.0s 内存限制: 256.0MB 本题总分：25 分
问题：
给定义个长度为 n 的数组 A1, A2, · · · , An。你可以从中选出两个数 Ai (i 不等于 j)，然后将 Ai 和 Aj 一前一后拼成一个新的整数。例如 12 和 以拼成 12345 或 34512。注意交换 Ai 和 Aj 的顺序总是被视为 2 种拼法，是 Ai = Aj 时。
请你计算有多少种拼法满足拼出的整数是 K 的倍数。

输入：
第一行包含 2 个整数 n 和 K。
第二行包含 n 个整数 A1, A2, · · · , An。

输出：
一个整数代表答案。

样例输入：
4 2
1 2 3 4

样例输出：
6

评测用例规模与约定：
对于 30% 的评测用例，1 ≤ n ≤ 1000, 1 ≤ K ≤ 20, 1 ≤ Ai ≤ 10的四次方。
对于所有评测用例，1 ≤ n ≤ 10的五次方，1 ≤ K ≤ 10的五次方，1 ≤ Ai ≤ 10的九次方。

思路： 直接暴力肯定超时。我们可以先进行一次操作，对所有数字进行遍历。求出对于每个数，后数为多少时满足题目要求。因为所有数都小于等于十的九次方，即最多为10位数，所以我们只需要求每个数在后数为1位数到10位数时对后数的余数要求即可。然后再遍历一次判定满足要求的后数，总答案加上对该后数的需求即可。数据接收数组选择long long，防止运算中数据超限。答案也选择long long，防止储存不下。

具体思路如下：

  • 整式为 （数一*10^数二的位数^+数二）%k == 0 即数一数二满足要求
  • 我们遍历整个数组，按 （k - 数一*10^1-10^%k）%k 求出数一在1-10次方的情况下对后数余数的要求。这次遍历统计的是数一对于数二的需求。
  • 用一个二维数组 mymap[位数][余数需求] 来储存对于 特定数二 的需求数量。
  • 再次遍历整个数组，对数组元素的位数与余数进行计算，如果位数与余数满足需求，总答案则加上上一步中统计的需求数量。这次遍历是为了寻找数二。
  • 在遍历中，我们需要进行去重判定。如果一个数跟自己组合也满足条件，说明上面多加了一次，总答案减去1。

AC代码： OJ链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;

long long myarray[100001];//存数 
int mymap[11][100001];//存不同幂情况下对余数的需求 mymap[幂][需求]=数量 
long long ans=0;//答案 

void func1(int n,int k)//将各个位数可组合数的需求进行统计 
{
	for(int now=0;now<n;now++)
	{
		for(int temp=1;temp<=10;temp++)
		{
			
			int times=(long long)pow(10,temp)%k;
			mymap[temp][(k-myarray[now]*times%k)%k]++;//在temp次幂的情况下  对后数余数为 k-array[now]*times%k 的需求加一 
			//即后数为temp位数 并且余数为 k-array[now]*times%k 即可成功组合 
			//因为 array[now]*times%k 可能等于0 所以k减它可能等于k 所以需要总体%k一下 
		} 
	}
}

void func2(int n,int k)//遍历所有数 答案加上需求数 顺便去重 
{
	for(int now=0;now<n;now++)
	{
		int times=(int)log10(myarray[now])+1;//当前数位数 
		ans+=mymap[times][myarray[now]%k];//加上所有可以组合的 
		if((myarray[now]*(int)pow(10,times)%k+myarray[now]%k)%k==0)//去重  
		{
			ans--;//如果一个数跟自己组合也满足条件 说明上面多加了一次 减去它 
		}
	}
} 

int main()       
{
    int n,k; 
    memset(mymap,0,sizeof(mymap));
    scanf("%d %d",&n,&k);
    for(int now=0;now<n;now++)
    {
    	scanf("%lld",&myarray[now]);
	}
	func1(n,k);
	func2(n,k);
	printf("%lld",ans);
    return 0;
}