蓝桥（杂题3）

整数拼接

Description
给定义个长度为 n 的数组 A1, A2, · · · , An。你可以从中选出两个数 Ai 和Aj(i 不等于 j)，然后将 Ai 和 Aj 一前一后拼成一个新的整数。例如 12 和 345 以拼成 12345 或 34512。注意交换 Ai 和 Aj 的顺序总是被视为 2 种拼法，即便是 Ai = Aj 时。
请你计算有多少种拼法满足拼出的整数是 K 的倍数。

Input

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

Output

一个整数代表答案。

Sample Input

4 2
1 2 3 4

Sample Output

6

思路：

因此本题就相当于求Ai和Aj 满足 (Ai + Aj * 10 ^ len(Ai)) % k = 0 这一等式（len(Ai)是Ai的位数）

转化 (Aj * 10 ^ len(Ai)) %k = -Ai % k

即首先枚举Ai，然后求有几个Aj * 10 ^ len(Ai) % k = -Ai % k

最后，注意每次算结果的时候需要判重

ps. 利用 to_string(a[i]).size(); // 得到数字的长度

#include
#include
using namespace std;

const int  N = 100010;

int s[11][N];

int  main(){
    int n,k;
    long long a[N];
    long long res;
    cin >> n >> k;
    for(int i=0;i<n;i++){
        cin >> a[i]; 
    }
    
    for(int i=0;i<n;i++){
        int temp = a[i]%k;
        for(int j=0;j<11;j++){
            s[j][temp]++; 
            temp = temp*10%k;
        }
    }
    
    for(int i=0;i<n;i++){
        int t = a[i]%k;
        int len = to_string(a[i]).size();  // 得到数字的长度
        res += s[len][(-t+k)%k];
        
        // 去重
        int r=t;
        while(len--) r=r*10%k;
        if(r == (-t+k)%k) res--;
    }
    
    cout << res << endl;
    
    return 0;
}
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

1207. 大臣的旅费

https://www.acwing.com/problem/content/description/1209/

问题描述

很久以前，T王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。

为节省经费，T国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。

J是T国重要大臣，他巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了J最常做的事情。他有一个钱袋，用于存放往来城市间的路费。

聪明的J发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第x千米到第x+1千米这一千米中（x是整数），他花费的路费是x+10这么多。也就是说走1千米花费11，走2千米要花费23。

J大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？

输入格式

输入的第一行包含一个整数n，表示包括首都在内的T王国的城市数

城市从1开始依次编号，1号城市为首都。

接下来n-1行，描述T国的高速路（T国的高速路一定是n-1条）

每行三个整数Pi, Qi, Di，表示城市Pi和城市Qi之间有一条高速路，长度为Di千米。

输出格式

输出一个整数，表示大臣J最多花费的路费是多少。

输入样例

5
1 2 2
1 3 1
2 4 5
2 5 4

输出样例

135

TEL代码，直接采用 Floyd求最短路 算法
由于时间复杂度为 O3，所以直接TEL

#include
#include
#include
using namespace std;
const int N = 10010, INF = 1e9;
int n,m;
int d[N][N];

void folyd(){
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                 d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
}

int main(){
    cin >> n;
    m = n-1;
    
    if(n==1){
		printf("0");
		return 0;
	}
	
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i==j) d[i][j] = 0;        // 自环
            else d[i][j] = INF;
        
    while(m--){
        int a,b,c;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b],c);    // 重边
        d[b][a] = min(d[b][a],c);
    }
    
    folyd();
    
    int maxx=0;
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(maxx < d[i][j]){
                maxx = d[i][j];
            }
        }
        
    cout << 10*maxx+((1+maxx)*maxx)/2 << endl;
    return 0;
}

//原状态是：f[i, j, k]表示从i走到j的路径上除了i, j以外不包含点k的所有路径的最短距离。
//那么f[i, j, k] = min(f[i, j, k - 1), f[i, k, k - 1] + f[k, j, k - 1]。
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
50
51
52
53

AC code：

本题主要考察的内容即 树的直径

任何一颗树都是二分图，都有以上的性质

#include
using namespace std;

const int N = 100010;

int maxu, maxx;
int w[N],e[N],ne[N],h[N],idx;

void add(int a ,int b ,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int u,int fa, int d){
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        int t = w[i];
        if(j == fa) continue;
        if(maxx < d+t){
            maxx = d+t;
            maxu = j;
        }
        dfs(j,u,d+t);
    }
}

int n;

int main(){
    cin >> n;
    memset(h,-1,sizeof h);
    int k = n - 1;
    while(k--){
        int a , b , c ;
        //cin >> a >> b >> c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    
    dfs(1,-1,0);
    
    dfs(maxu,-1,0);
    
    cout << maxx*10+(maxx + 1ll)*maxx/2 << endl;
    return 0;
}

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