Preface
这场感觉都是一个礼拜前补题打的了，但由于上周末事情比较多都没来得及写题解
因此可能题意都记得不是很清楚了，就简略地谈一谈吧
A. Lucky Numbers
不难想到直接暴力从左端点枚举到右端点并对每个数进行暴力判断
一个很naive的结论就是当答案为\(9\)时直接输出即可，然后我们发现无论从哪个点开始显然都不用经过很久就能找到一个答案为\(9\)的数
证明略感觉很simple
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int t,l,r;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j; scanf("%d%d",&l,&r); int ans=-1,num;
for (i=l;i<=r&&ans!=9;++i)
{
int x=i,mi=9,mx=0;
while (x) mi=min(mi,x%10),mx=max(mx,x%10),x/=10;
if (mx-mi>ans) ans=mx-mi,num=i;
}
printf("%d\n",num);
}
return 0;
}
B. Playing in a Casino
不难想到先做每一列的贡献和原来是等价的，而且此时问题变得十分容易
我们只需要排序后就能把绝对值去掉了，然后就非常trivial了
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=300005;
int t,n,m,x; vector <int> v[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=m;++i) v[i].resize(n);
for (i=0;i<n;++i) for (j=1;j<=m;++j) scanf("%d",&v[j][i]);
long long ans=0; for (i=1;i<=m;++i)
{
long long pfx=0; sort(v[i].begin(),v[i].end());
for (j=0;j<n;++j) ans+=1LL*v[i][j]*j-pfx,pfx+=v[i][j];
}
printf("%lld\n",ans);
}
return 0;
}
C. Unlucky Numbers
A题的反面题，感觉还是挺有趣的说
一个很直觉的方法就是数位DP了，但一般的数位DP都是记\(f(x)\)表示\(1\sim x\)的答案，然后用\(f(r)-f(l-1)\)来得到\([l,r]\)的答案的，但这题显然没有这种可减性
那怎么处理比较好呢，考虑原来我们在一般的数位DP中会针对不超上界在状态中记录一个信息表示从高位到这一位的所有数是否都卡在上界上，因此我们仿照这个对下界也做同样的处理
但是如果直接上手DP可能会有点不好设计状态，我们可以考虑枚举两个数字\(i,j\)表示所有使用的数必须在区间\([i,j]\)内部，此时我们强制令极差为\(j-i\)
然后此时我们的DP只要考虑可行性即可，设\(f_{i,0/1,0/1}\)表示做到从高到低的第\(i\)位，上界是否卡死，下界是否卡死的状态是否有解，若有解由于只要输出一个解可以直接记录下
但是直接这样做会有一个问题，那就是如果\(l,r\)在十进制下的位数不同，那么\(l\)前面的前导\(0\)会对DP产生影响
不过我们稍加分析后发现\(l,r\)位数不同的情况是很trivial的，因为我们总可以构造一个位数和\(l\)位数相同的全为\(9\)的数，它的答案就已经是\(0\)了
因此这题就做完了，感觉是最近做过的几场比赛里最难的一个C了，单次询问复杂度\(O(9^3\log n)\)
#include<cstdio>
#include<iostream>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=20;
int t,L[N],R[N],cur[N],ans[N],mi,c1,c2; long long l,r; bool vis[N][2][2];
inline bool DP(CI now,CI LB,CI RB,CI FL,CI FR)
{
if (!now) return 1; if (vis[now][FL][FR]) return 0;
for (RI i=LB;i<=RB;++i)
{
if (FL&&i<L[now]) continue;
if (FR&&i>R[now]) continue;
if (DP(now-1,LB,RB,FL&&(i==L[now]),FR&&(i==R[now])))
return cur[now]=i,1;
}
return vis[now][FL][FR]=1,0;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j,k; scanf("%lld%lld",&l,&r); c1=c2=0;
while (l) L[++c1]=l%10,l/=10;
while (r) R[++c2]=r%10,r/=10;
if (c1!=c2)
{
for (i=1;i<=min(c1,c2);++i)
putchar('9'); putchar('\n'); continue;
}
for (mi=10,i=0;i<=9;++i) for (j=i;j<=9;++j)
{
bool flag=0; memset(vis,0,sizeof(vis));
for (k=i;k<=j;++k) if (L[c1]<=k&&k<=R[c1])
if (cur[c1]=k,DP(c1-1,i,j,k==L[c1],k==R[c1])) { flag=1; break; }
if (flag&&j-i<=mi) mi=j-i,memcpy(ans,cur,sizeof(ans));
}
for (i=c1;i;--i) putchar(ans[i]+'0'); putchar('\n');
}
return 0;
}
D. Petya, Petya, Petr, and Palindromes
这题真是过了快一周我草稿纸上都更新了二三十页的新内容了，翻了半天才把当时的想法翻出来
一个显然的想法在考虑回文串的对应位置时，只有下标奇偶性相同的位置之间可能可以产生贡献
我们不妨这样考虑原问题，先假设对于所有的回文串每对对应位置上的数均不相同，然后容斥算出相同的部分减去即可
一个很naive的想法就是把所有值相同的数的下标放在一起处理，那么现在就是要讨论两个下标是否会在某次计算中配对了
首先正着考虑，假设对应的下标差是\(i\)，满足\(i\in[2,k-1]\and 2|i\)，经过简单计算得到此时合法的起始比较下标为\(j\)，满足\(a_j=a_{j+i}\)且\(j\in [\frac{k+1-i}{2},n-\frac{k+1-i}{2}+1]\)
然后考虑我们枚举的某个下标\(y\)，以它作为右端点（即\(j+i\)）考虑找出所有满足要求的\(x\)（即\(j\)）的个数
但是不要忘记还有个隐含条件\(x+y\ge k+1\)，我们把上面的式子用\(x,y\)表示出来就有\(x\in[\max(k+1-y,y-k+1),2n-k+1-y]\)
很显然这左右端点对应的值的个数都可以直接通过二分来找到，也许通过一定技巧也可以用two points，不过里面有\(\max\)感觉不太方便的说
总复杂度\(O(m\log n)\)
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,k,x; long long ans; vector <int> v[N][2];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j,p; for (scanf("%d%d",&n,&k),i=1;i<=n;++i)
scanf("%d",&x),v[x][i&1].push_back(i);
for (ans=1LL*(k-1)/2*(n-k+1),i=1;i<=200000;++i) for (j=0;j<2;++j)
{
int len=v[i][j].size(); for (p=0;p<len;++p)
{
int LB=lower_bound(v[i][j].begin(),v[i][j].end(),max(k+1-v[i][j][p],v[i][j][p]-k+1))-v[i][j].begin();
int RB=upper_bound(v[i][j].begin(),v[i][j].end(),2*n-k+1-v[i][j][p])-v[i][j].begin()-1;
ans-=max(0,min(p-1,RB)-LB+1);
}
}
return printf("%lld",ans),0;
}
E1. Minibuses on Venus (easy version)
第一次见到分了三个难度级的题目，被狠狠地震撼到了
不过这个Easy难度的直接暴力DP就行了，首先一眼枚举所有数的和\(s\)，考虑求出所有和为\(s\)的合法序列的个数
很显然此时我们枚举每一个\([0,k-1]\)的数\(p\)，若\(2p\bmod k=s\)则只要此时\(p\)出现就一定合法
但直接计算合法的方案数有点不太好下手，我们可以容斥一下用不加任何限制的情况减去只用不合法的\(p\)时的情况数
那么直接上DP，\(f_{i,j,0/1}\)表示处理了前\(i\)个位置，和对\(k\)取模为\(j\)，是否有禁用限制的方案数，转移是很trivial的
总复杂度\(O(n\times k^3)\)
#include<cstdio>
#include<iostream>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
int n,k,mod,f[105][35][2],ans;
inline void inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
int main()
{
RI i,j,p,q; for (scanf("%d%d%d",&n,&k,&mod),p=0;p<k;++p)
{
int cur=0; for (memset(f,0,sizeof(f)),q=0;q<k;++q) if (q*2%k==p) cur|=(1<<q);
for (f[0][0][0]=f[0][0][1]=i=1;i<=n;++i)
for (j=0;j<k;++j) for (q=0;q<k;++q)
{
int pre=(j-q+k)%k; inc(f[i][j][1],f[i-1][pre][1]);
if (!((1<<q)&cur)) inc(f[i][j][0],f[i-1][pre][0]);
}
inc(ans,(f[n][p][1]-f[n][p][0]+mod)%mod);
}
return printf("%d",ans),0;
}
E2. Minibuses on Venus (medium version)
点开E2一看好家伙\(n\)直接爆炸增长成\(10^{18}\)了，那么不难想到应该用类似于矩阵快速幂那样的科技优化下DP
但这里的状态转移怎么想感觉和矩阵也没关系的说，不过其实能用快速幂优化的除了矩阵其实还有一个，那就是循环卷积
首先考虑无限制的情况，如果我们用一个多项式\(a_0\cdot x^0+a_1\cdot x^1+a_2\cdot x^2+\cdots+a_{k-1}\cdot x^{k-1}\)来表示状态，\(x_i\)的系数\(a_i\)表示和在模\(k\)后为\(i\)的方案数
那么一次转移显然就是做一个循环卷积，其中转移多项式\(A=x^0+x^1+x^2+\cdots+x^{k-1}\)，因此我们只要求\(A^n\)即可，这个是可以用快速幂加速的
那么接下来有禁用的也很明显了，我们把所有能用的位置对应的系数置为\(1\)，不能用的置为\(0\)，然后设这个转移多项式为\(B\)，求出\(B^n\)后减一减即可
这题一个很大的启发就是加速DP的科技除了矩乘之外还有循环卷积，算是学到了
总复杂度是\(O(k^4\log n)\)的，可以通过此题
#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=105;
int k,ans,mod; long long n;
inline vector <int> Mul(vector <int>& A,vector <int>& B)
{
vector <int> C(k);
for (RI i=0;i<k;++i) for (RI j=0;j<k;++j)
(C[(i+j)%k]+=1LL*A[i]*B[j]%mod)%=mod;
return C;
}
inline vector <int> Pow(vector <int> A,long long p)
{
vector <int> tmp(k); tmp[0]=1;
for (;p;p>>=1,A=Mul(A,A)) if (p&1) tmp=Mul(tmp,A);
return tmp;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j; for (scanf("%lld%d%d",&n,&k,&mod),i=0;i<k;++i)
{
vector <int> A(k),B(k);
for (j=0;j<k;++j) if (A[j]=1,2*j%k!=i) B[j]=1;
(ans+=(Pow(A,n)[i]-Pow(B,n)[i]+mod)%mod)%=mod;
}
return printf("%d",ans),0;
}
E3. Minibuses on Venus (hard version)
这种难度快直逼3000的题我肯定是写不动的
看了眼dalao的博客发现原来有技术可以直接推出一个封闭解的说，还是太恐怖了
Postscript
这场没打也可惜，看起来这场CD难度挺大的而且都是合我胃口的题，早知道翘课去打了
标签：CI,861,Codeforces,int,Div,include,RI,DP,define From： https://www.cnblogs.com/cjjsb/p/17289105.html