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;
}