题目链接

C

核心思路

这个思路说实话有点玄学，也就是我们前面的数位按照l或者r的相同数位来填补，后面就填相同的数字也就是比如l是2345

我们可以是2999,2888,23111,23777.

这样构造好像肯定是最小的。

但是好好巩固下数位dp来做这道题还是更好的。

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;

int main(){

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    auto get = [&](LL x){
        int mn = 10, mx = -1;
        while(x){
            mn = min(1LL * mn, x % 10);
            mx = max(1LL * mx, x % 10);
            x /= 10;
        }
        return mx - mn;
    };

    int T;
    cin >> T;
    while(T--){
        LL l, r;
        cin >> l >> r;
        if (l < 10 || l == r){
            cout << l << '\n';
            continue;
        }

        int a[20], b[20];
        int len1 = 0, len2 = 0;
        LL num = l;
        while(num) a[++len1] = num % 10, num /= 10;
        num = r;
        while(num) b[++len2] = num % 10, num /= 10;
        int ans = 10;
        LL val = -1; 
        {
            int res = get(l);
            if (res < ans){
                ans = res;
                val = l;
            }
        }
        {
            int res = get(r);
            if (res < ans){
                ans = res;
                val = r;
            }
        }
        {
            LL x = 0;
            for(int i = len1; i >= 1; i--){
                for(int j = 0; j <= 9; j++){
                    LL t = x;
                    for(int k = i; k >= 1; k--)
                        t = t * 10 + j;
                    if (t < l || t > r) continue;
                    int res = get(t);
                    if (res < ans){
                        ans = res;
                        val = t;
                    }
                }
                x = x * 10 + a[i];
            }
        }
        {
            LL x = 0;
            for(int i = len2; i >= 1; i--){
                for(int j = 0; j <= 9; j++){
                    LL t = x;
                    for(int k = i; k >= 1; k--)
                        t = t * 10 + j;
                    if (t < l || t > r) continue;
                    int res = get(t);
                    if (res < ans){
                        ans = res;
                        val = t;
                    }
                }
                x = x * 10 + b[i];
            }
        }
        cout << val << '\n';
    }

}

D

核心思路

这个其实很明显是一个贡献题，我们可以先计算出来最坏的情况，就是每一个都需要修改。也就是\(ans=(n-k+1)*(k/2)\).然后如果发现有匹配的那么我们就ans--就好了。这又有个性质就是与某个点x匹配的点y必然是奇偶性相同的。

然后我们就是找对于任意一个数val看其左边有多少位置可以和它匹配。

然后就是经典的按照约束条件添加不等式就好了。

首先假设左端点是i，那么就有\((val+i)/2-k>=1\),\((val+i)/2+k<=n\).这是让我们的左右端点属于\([1,n]\).

然后就是 val和i的距离不可以超过k所以有\(val-i+1<=k\).还有一个就是\(1\leq i \leq val\).

接下来只需要把这些不等式联立就好了，然后再在我们预处理出来的数组中使用二分查询就好了。

// Problem: D. Petya, Petya, Petr, and Palindromes
// Contest: Codeforces - Codeforces Round 861 (Div. 2)
// URL: https://codeforces.com/contest/1808/problem/D
// Memory Limit: 256 MB
// Time Limit: 1500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long 


const int N=2e5+10,mod=1e9+7;
int n,k;
vector<int> pos[N][2];

int cal(vector<int> &v,int l,int r)
{
	return upper_bound(v.begin(),v.end(),r)-lower_bound(v.begin(),v.end(),l);
}



signed main()
{
cin>>n>>k;
if(k==1)
{
	cout<<0<<endl;
	return 0;
}
int ans=(n-(k-1))*(k/2);
int x;
for(int i=1;i<=n;i++)
{
	cin>>x;
	pos[x][i&1].push_back(i);
}
int maxx=2e5;
int res=0;
for(int val=0;val<=maxx;val++)
{
	for(int odd=0;odd<2;odd++)
	{
		for(auto i:pos[val][odd])
		{
		 int l = max(max(1ll*1, i - (k - 1)), 2 + k / 2 * 2 - i);
                int r = min(i - 1, 2 * n - k / 2 * 2 - i);
                if(l <= r)
                    ans -= cal(pos[val][odd], l, r);
		}
	}
}
cout<<ans<<endl;
return 0;

}