Codeforces Round 861 (Div. 2)
C题直接数位dp即可
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#include<cmath>
#include<set>
#include<unordered_map>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define A puts("Yes")
#define B puts("No")
using namespace std;
typedef double db;
typedef long long ll;
//typedef __int128 i128;
const int N=1e6+5;
const int S=1e5+5;
const ll inf=1ll<<60;
const ll mo=1e9+7;
ll l,r,d1[N],d2[N],t,l1,l2,u,d,ans;
ll f[20][2][2][2],flag,c[100];
void check(){
memset(f,-1,sizeof(f));
f[l1][1][1][1]=0;
int aa,bb,ne;
fd(i,l1-1,0) {
fo(le,0,1) fo(a,0,1) fo(b,0,1) fo(dig,d,u) {
if (a && dig<d1[i]) continue;
if (b && dig>d2[i]) continue;
if (f[i+1][le][a][b]<0) continue;
aa=a&(dig==d1[i]);
bb=b&(dig==d2[i]);
ne=le&(dig==0);
f[i][ne][aa][bb]=f[i+1][le][a][b]+dig*c[i];
}
}
fo(a,0,1) fo(b,0,1) {
if (f[0][0][a][b]>0) {
flag=1;
ans=f[0][0][a][b];
return;
}
}
}
void solve(){
flag=0;
fo(i,0,9) {
fo(j,0,9) {
d=j;
u=j+i;
if (u>9) break;
check();
if (flag) return;
}
}
}
int main()
{
// freopen("data.in","r",stdin);
c[0]=1;
fo(i,1,18) c[i]=c[i-1]*10ll;
int T;
scanf("%d",&T);
while (T--) {
scanf("%lld %lld",&l,&r);
l1=l2=0;
t=l;
while (t) {
d1[l1++]=t%10;
t/=10;
}
t=r;
while (t) {
d2[l2++]=t%10;
t/=10;
}
if (l1<l2) {
ll z=0;
while (z<l) z=z*10ll+9ll;
printf("%lld\n",z);
continue;
}
solve();
printf("%lld\n",ans);
}
return 0;
}
D
题意：一个长度为k的序列的价值定义为将其修改为回文的最少步数。求一个串所有长度为k的字串的价值和。
首先注意到一个pair(i,j)产生了贡献，i，j的奇偶性一定相同。
然后问题转化为询问一段区间[l,r]（只考虑与i奇偶性相同的）中有多少个数和a[i]相同
那么我们可以离线处理，从左往右扫，利用前缀相减就能得到。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#include<cmath>
#include<set>
#include<unordered_map>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define A puts("Yes")
#define B puts("No")
using namespace std;
typedef double db;
typedef long long ll;
//typedef __int128 i128;
const int N=1e6+5;
const int S=1e5+5;
const ll inf=1ll<<60;
const ll mo=1e9+7;
struct node{
ll x,op;
};
vector<node> v[N];
ll n,a[N],k,ans,l,r;
ll f[N],g[N];
int main()
{
// freopen("data.in","r",stdin);
scanf("%lld %lld",&n,&k);
if (k==1) {
printf("%d\n",0);
return 0;
}
fo(i,1,n) scanf("%lld",&a[i]);
fo(i,k/2+2, n) {
l=max(2*(1+k/2)-i, i+1-k);
r=min(i-2, 2*(n-k/2)-i);
if ((i-l)&1) l++;
if ((r-i)&1) r--;
ans+=(r-l)/2+1ll;
// printf("%lld %lld %lld\n",i,l,r);
if (l-2>0) v[l-2].push_back((node){a[i], +1});
v[r].push_back((node){a[i], -1});
}
fo(i,1,n) {
if (i&1) {
f[a[i]]++;
for (int j=0;j<(int)v[i].size();j++) {
ans+=v[i][j].op*f[v[i][j].x];
}
}
else {
g[a[i]]++;
for (int j=0;j<(int)v[i].size();j++) {
ans+=v[i][j].op*g[v[i][j].x];
}
}
}
printf("%lld",ans);
return 0;
}
E题：
数的范围是在k进制下的n位数
一个数是lucky的当且仅当在k进制下，存在一个数位上的数，等于其他数位上的数在模k意义下的和。
利用减法原理
假设一个数的数位和为s，如果存在一个数，那么有
s-x%k=x%k -> s%k=2x%k
那么我们找到这样的x，就是说在计算和为s的方案数是不能使用这些x
easy直接dp即可
mid可以将其看作是一个卷积。