题目

https://www.luogu.com.cn/problem/P8708

思路

题目本身对数字顺序没有要求的，排序之后往往会好做一些。

排序之后，数组满足一个单调性。对于题目中的“拼接”，利用单调性就可以使用双指针算法求解。

具体地，比如排序之后的数字序列为 $a_1,…,a_i,a_j,…,a_n$。固定一个 $a_i$，对于它后面的 $a_j$，无论是将 $a_i$ 接在 $a_j$ 后面还是将 $a_j$ 接在 $a_i$ 后面，都满足的性质是：数字 $a_j$ 的值越大，拼接之后得到的数字越大。

比如：

1,1,2,3,4,4,5,6

固定 $a_i=1$，那么 $a_j$ 接在 $a_i$ 后面：12, 13, 14都是递增的；
$a_i$ 接在 $a_j$ 后面：21, 31, 41…也是递增的。

所以，利用以上的性质，使用 对撞指针 进行求解。
for 循环控制指针 l移动，另一个指针 r 从最右边出发，两个指针相向移动，不回退。

对于每一个指针 l ，找到一个满足条件的最大元素 r，因为数字是排序的，所以如果 r 都满足，那么 l—r 中间的所有数字元素都可以进行拼接，那么直接加上贡献即可。

这里为什么指针 r 不用回退呢？
仔细思考之后就会发现，只有当前 l 和 r 拼接之后大于 k ，r指针才会移动。由于单调性，确保了结果的不重不漏。

这里因为调换拼接顺序也算新的方案，所以要跑两遍双指针。一遍是 l+r，一遍是 r+l。

使用字符串维护“拼接”非常方便，所以直接读入到string变量即可。

使用 for+while() 模式，枚举+寻找边界，实现对撞指针。

Code

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N = 100010;
string k,a[N];
int n;

bool cmp(string a, string b)//判断是否有a<=b
{
    if(a.size() == b.size())
    {
        if(a <= b)
            return true;
        else
            return false;
    }
    else
    {
        if(a.size() > b.size())
            return false;
        else
            return true;
    }
}

int main()
{
    cin >> n >> k;
    for(int i = 0; i < n; i ++)
        cin >> a[i];

    sort(a,a+n,[](string &a,string &b)
    {
        if(a.size() == b.size())
            return a<b;
        else
            return a.size()<b.size();
    });

    ll cnt = 0;
    //l拼r
    for(int l = 0,r = n-1; l < n; l ++)
    //对于每一个l，确定r满足条件的最大下标
    {
        while(r>l && cmp(a[l]+a[r],k)==false)
            r --;
        //直到找到符合位置的r
        if(r > l)
            cnt += r-l;
    }

    //r拼l
    for(int l = 0,r = n-1; l < n; l ++)
    {
        while(r>l && cmp(a[r]+a[l], k)==false)
            r --;
        if(r > l)
            cnt += r-l;
    }
    printf("%lld",cnt);
    return 0;
}

技巧有：字符串数字判断大小、sort()函数的自定义排序。

一个是理解“贡献”的妙用，另一个是理解指针 r 不用回退的妙用。