CSP 模拟 19
It started off so well
They said we made a perfect pair
I clothed myself in your glory and your love
How I loved you
How I cried
The years of care and loyalty
Were nothing but a sham it seems
The years belie we lived the lie
I love you 'til I die
Save me, Save me, Save me
I can't face this life alone
Save me, Save me, Save me
I'm naked and I'm far from home
The slate will soon be clean
I'll erase the memories
To start again with somebody new
Was it all wasted
All that love
I hang my head and I advertise
A soul for sale or rent
I have no heart, I'm cold inside
I have no real intent
Save me, Save me, Save me
I can't face this life alone
Save me, Save me, Save me
Oh I'm naked and I'm far from home
Each night I cry and still believe the lie
I love you 'til I die
Save me, Save me, Save me
Yea, yeah
Save me yeah Save me oh Save me
Don't let me face my life alone
Save me, Save me
Oh I'm naked and I'm far from home
\(\text{zxs round}\)
T1 十年之约
原题：CodeForces-1542C Strange Function *1600
考虑如何判断一个数 \(x\) 是在 \([1,k]\) 中所有数的倍数，容易发现只要找到每个质数的最高次幂 \(p_i^{c_i}\)，判断 \(\prod_{i} p_i^{c_i}\) 是否整除 \(x\) 即可。
那么对于值域 \([1,n]\)，从 \(2\) 开始枚举，发现 \(n-\left\lfloor\dfrac{n}{2}\right\rfloor\) 个数答案为 \(2\)。设 \(n'=\left\lfloor\dfrac{n}{2}\right\rfloor\)，那么现在考虑的 \(i\in[1,n']\) 中实际代表 \(2\) 的 \(i\) 倍，且 \(3\) 处有 \(n'-\left\lfloor\dfrac{n'}{3}\right\rfloor\) 个数答案为 \(3\)。再设 \(n''=\left\lfloor\dfrac{n'}{3}\right\rfloor\)，\(4\) 处有 \(\left\lfloor\dfrac{n''}{2}\right\rfloor\) 个数答案为 \(4\)。这里只除以 \(2\) 是因为 \([1,3]\) 到 \([1,4]\) 中 \(\prod_{i} p_i^{c_i}\) 只增加了 \(2\)。
于是算法流程应当只在质数幂出进行，容易发现处理 \(O(\log n)\) 级别即可。
点击查看代码
int pr[105];
inline void linear_sieve(){
pr[1]=1;
for(int i=2;i<=100;++i){
for(int j=2;j<=i;++j){
if(i%j==0){
pr[i]=j;
break;
}
}
int tmp=i;
while(tmp%pr[i]==0) tmp/=pr[i];
if(tmp!=1) pr[i]=1;
}
}
int t;
ll n;
int ans;
int main(){
linear_sieve();
scanf("%d",&t);
while(t--){
scanf("%lld",&n);
ans=0;
for(int i=1;i<=100;++i){
if(pr[i]==1) continue;
ans=(ans+1ll*(n-n/pr[i])%mod*i%mod)%mod;
n/=pr[i];
if(!n) break;
}
printf("%d\n",ans);
}
return 0;
}
T2 可爱三小只
原题：CodeForces-446B DZY Loves Modification *2000
注意到一次选择造成的影响形如：使这一行或列减少 \(mp\) 或 \(np\)，同时使所有列或行减少 \(p\)。
发现影响只存在两个信息交替，也就是无论列怎么选择，行内部选择的先后顺序一定，可以用大根堆先求出 \(f_i,g_i\) 分别表示选择 \(i\) 行或 \(i\) 列的最大答案。
之后枚举选择操作 \(i\) 行 \(k-i\) 列，每个选择的实际减少值是前面另一种选择个数乘 \(p\)，考虑把行操作都放在最前，这时只有列操作有减少，减少值是 \(i(k-i)p\)，注意到如果把列操作都放在最前也是这个答案。
考虑任意一种选择顺序，把列操作通过交换相邻项，从行靠前列靠后改变成这种选择顺序，例如 \(\texttt{rcrrcr}\) 就是从 \(\texttt{rrrrcc}\) 移动第一个到 \(\texttt{rcrrrc}\)，再到 \(\texttt{rcrrcr}\)，每次交换都是一个行一个列交换。相邻交换说明此外的所有减少都没有变化，而二者相对影响从行使列减少 \(p\) 变成列使行减少 \(p\)，那么无论以怎样顺序结果都相同。
点击查看代码
int n,m,k,p;
int a[maxn][maxn];
ll f[maxk],g[maxk],ans;
priority_queue<ll> q;
int main(){
n=read(),m=read(),k=read(),p=read();
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
a[i][j]=read();
}
}
for(int i=1;i<=n;++i){
ll sum=0;
for(int j=1;j<=m;++j){
sum+=a[i][j];
}
q.push(sum);
}
for(int i=1;i<=k;++i){
ll now=q.top();
q.pop();
f[i]=f[i-1]+now;
q.push(now-1ll*m*p);
}
while(!q.empty()) q.pop();
for(int j=1;j<=m;++j){
ll sum=0;
for(int i=1;i<=n;++i){
sum+=a[i][j];
}
q.push(sum);
}
for(int i=1;i<=k;++i){
ll now=q.top();
q.pop();
g[i]=g[i-1]+now;
q.push(now-1ll*n*p);
}
ans=-llinf;
for(int i=0;i<=k;++i){
ans=max(ans,f[i]+g[k-i]-1ll*p*i*(k-i));
}
printf("%lld\n",ans);
return 0;
}
T3 蛋糕塌了
原题：CodeForces-1316F Battalion Strength *2800
一个不如标算的做法。
考虑 \(p\) 数组升序。
设 \(f_i\) 为 \(i\) 前缀结果的期望，那么转移需要知道上一个数的期望，于是设 \(g_i\) 为 \(i\) 前缀最后一个数的期望。
就有：
写成矩阵是：
维护有序 \(p\) 需要平衡树，复杂度 \(O(k^3n\log n)\)，也可以离线用权值线段树。
标算是考虑每个点对的贡献概率，离线下来线段树维护。
点击查看代码
const int seed=20070528;
mt19937 mt((unsigned long long)&seed);
inline int rand(int l,int r){
return uniform_int_distribution<int>(l,r)(mt);
}
inline int read(){
int x=0,w=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
return x*w;
}
int n,q;
int p[maxn],id[maxn];
struct Matrix{
ll a[3][3];
Matrix(){
a[0][0]=a[0][1]=a[0][2]=0;
a[1][0]=a[1][1]=a[1][2]=0;
a[2][0]=a[2][1]=a[2][2]=0;
}
Matrix operator*(const Matrix &rhs)const{
Matrix res;
for(int i=0;i<3;++i){
for(int j=0;j<3;++j){
for(int k=0;k<3;++k){
res.a[i][j]=(res.a[i][j]+a[i][k]*rhs.a[k][j]);
}
res.a[i][j]%=mod;
}
}
return res;
}
};
struct fhq_Treap{
int rt,tot;
int ch[maxn<<1][2],val[maxn<<1],pri[maxn<<1];
Matrix prod[maxn<<1],mat[maxn<<1];
inline void push_up(int x){
prod[x]=mat[x];
if(ch[x][0]) prod[x]=prod[ch[x][0]]*prod[x];
if(ch[x][1]) prod[x]=prod[x]*prod[ch[x][1]];
}
inline int new_node(int k,bool type,int l,int r){
++tot;
val[tot]=k,pri[tot]=rand(l,r);
if(!type){
mat[tot].a[0][0]=mat[tot].a[1][1]=mat[tot].a[2][2]=1;
}
else{
mat[tot].a[0][0]=1;
mat[tot].a[1][0]=1ll*inv2*k%mod,mat[tot].a[1][1]=inv2;
mat[tot].a[2][1]=1ll*inv2*k%mod,mat[tot].a[2][2]=1;
}
prod[tot]=mat[tot];
return tot;
}
inline int build(int l,int r,int last){
if(l>r) return 0;
if(l==r){
int x=new_node(p[id[l]],(id[l]<=n),last+1,last+100000);
return x;
}
int mid=(l+r)>>1;
int x=new_node(p[id[mid]],(id[mid]<=n),last+1,last+100000);
ch[x][0]=build(l,mid-1,pri[x]);
ch[x][1]=build(mid+1,r,pri[x]);
push_up(x);
return x;
}
int merge(int x,int y){
if(!x||!y) return x+y;
if(pri[x]<pri[y]){
ch[x][1]=merge(ch[x][1],y);
push_up(x);
return x;
}
else{
ch[y][0]=merge(x,ch[y][0]);
push_up(y);
return y;
}
}
void split(int p,int k,int &x,int &y){
if(!p) x=0,y=0;
else{
if(val[p]<=k) x=p,split(ch[p][1],k,ch[x][1],y);
else y=p,split(ch[p][0],k,x,ch[y][0]);
push_up(p);
}
}
inline void insert(int k){
int x,y;
split(rt,k,x,y);
rt=merge(merge(x,new_node(k,1,1,1000000000)),y);
}
inline void erase(int k){
int x,y,z;
split(rt,k,x,z),split(x,k-1,x,y);
y=merge(ch[y][0],ch[y][1]);
rt=merge(merge(x,y),z);
}
}T;
int main(){
n=read();
for(int i=1;i<=n;++i){
p[i]=read();
}
p[n+1]=-inf,p[n+2]=inf;
for(int i=1;i<=n+2;++i) id[i]=i;
sort(id+1,id+n+2+1,[&](int x,int y){
return p[x]<p[y];
});
T.rt=T.build(1,n+2,0);
printf("%lld\n",T.prod[T.rt].a[2][0]);
q=read();
for(int i=1;i<=q;++i){
int x=read(),k=read();
T.erase(p[x]);
p[x]=k;
T.insert(p[x]);
printf("%lld\n",T.prod[T.rt].a[2][0]);
}
return 0;
}
T4 西安行
原题：AtCoder-AGC013E Placing Squares
\(a_i^2\) 的组合意义是在 \(a_i\) 个位置有顺序填入两个本质不同的数的方案数，可以重复。
考虑设 \(f_{i,j}\) 为前 \(i\) 个位置最后一段已经填了 \(j\) 个数的方案数，转移 \(i\) 时，讨论 \(i-1\) 能不能作为一段的结尾。
如果可以，那么有：
反之就是：
改成矩阵快速幂加速。
点击查看代码
struct Matrix{
ll a[3][3];
Matrix(){
a[0][0]=a[0][1]=a[0][2]=0;
a[1][0]=a[1][1]=a[1][2]=0;
a[2][0]=a[2][1]=a[2][2]=0;
}
Matrix operator*(const Matrix &rhs)const{
Matrix res;
for(int i=0;i<3;++i){
for(int j=0;j<3;++j){
for(int k=0;k<3;++k){
res.a[i][j]=(res.a[i][j]+a[i][k]*rhs.a[k][j]);
}
res.a[i][j]%=mod;
}
}
return res;
}
}I,M1,M2;
inline Matrix q_pow(Matrix A,int B){
Matrix res=I;
while(B){
if(B&1) res=res*A;
A=A*A;
B>>=1;
}
return res;
}
int n,m;
int a[maxn],vis[maxn];
int f[maxn][3];
int main(){
I.a[0][0]=I.a[1][1]=I.a[2][2]=1;
M1.a[0][0]=1,M1.a[0][1]=2,M1.a[0][2]=1;
M1.a[1][0]=0,M1.a[1][1]=1,M1.a[1][2]=1;
M1.a[2][0]=1,M1.a[2][1]=2,M1.a[2][2]=2;
M2.a[0][0]=1,M2.a[0][1]=2,M2.a[0][2]=1;
M2.a[1][0]=0,M2.a[1][1]=1,M2.a[1][2]=1;
M2.a[2][0]=0,M2.a[2][1]=0,M2.a[2][2]=1;
n=read(),m=read();
for(int i=1;i<=m;++i) a[i]=read();
Matrix ans;
if(!m) ans=q_pow(M1,n);
else{
ans=I;
for(int i=1;i<=m;++i){
if(i==1) ans=ans*q_pow(M1,a[i]);
else ans=ans*q_pow(M1,a[i]-a[i-1]-1);
ans=ans*M2;
}
ans=ans*q_pow(M1,n-a[m]-1);
}
printf("%lld\n",ans.a[0][2]);
return 0;
}
反思
T2 为啥没想到最后一个顺序不影响答案？