title:
date: 2022-11-05 14:48:50
tags: []
catagories: [测试]
今天测试打挂了
来写个题解
A
题面大意
长度 \(n (n\le 10^5)\) 序列，支持区间加 \(c\ (|c|\le10^4)\) ，区间除以 \(d\ (2\le d \le 10^9)\)，区间询问最小值，区间询问和.
题解
第一眼看就是线段树板子题嘛ww
如果只需要支持区间除，一个数最多除 log 次 就会变成 1， 所以暴力做复杂度是对的
但是我打完线段树代码才发现他需要支持区间加
注意到如果暴力除的话，最坏情况小
啊那这我就不会了tt
但是一想随机数据应该有 60 分吧. 结果没有（寄）
正解我也不知道是怎么想到的，但是姑且作为一个套路记下来吧
做法
我们在原来的基础上加一个小优化，就是当 \(min-\lfloor \frac{min}{d} \rfloor=max-\lfloor \frac{max}{d}\rfloor\) 的时候，说明区间内所有数除完之后差值是相等的，这时候，就可以直接当区间减法做.
具体代码（注意 C++ 的除法是向零取整）：
void change_dv(int p, int l, int r, ll v)
{
if(t[p].mx<=0 and t[p].mn>=-1) return;
int amx=Div(t[p].mx,v),amn=Div(t[p].mn,v);
if(t[p].l==l and t[p].r==r and t[p].mx-amx==t[p].mn-amn)
{
t[p].sum-=(t[p].r-t[p].l+1)*(t[p].mx-amx);
t[p].lz-=t[p].mx-amx;
t[p].mx=amx,t[p].mn=amn;
return ;
}
if(t[p].l==t[p].r) { t[p].mn=Div(t[p].mn,v); t[p].mx=Div(t[p].mx,v); t[p].sum=Div(t[p].sum,v); return ; }
spread(p);
int mid=(t[p].l+t[p].r)>>1;
if(r<=mid) change_dv(ls,l,r,v);
else if(l>mid) change_dv(rs,l,r,v);
else change_dv(ls,l,mid,v),change_dv(rs,mid+1,r,v);
pushup(t[p],t[ls],t[rs]);
}
时间复杂度
\(O(可过)\) 但为什么呢？这做法感觉很玄学
考虑势能分析，这是一个很不错的分析复杂度技巧，但我不太会
直接搬网上题解
我们考虑用势能分析解决这个问题。定义一个代表 \([l,r]\) 区间的节点的势能为 \(\log(\max_{l,r}-\min_{l,r})\)。整棵树的势能就是所有节点的势能之和。
查询操作并不引起势能变化，而且复杂度是显然的，不在我们的考虑范围之内。
对于区间修改，暂时先考虑不完全被 \([l,r]\) 覆盖的区间的节点的势能变化：单个节点最坏情况增加 \(\log V\) 的势能（\(V\) 是值域），这样的区间等价于分别包含 \(l,r\) 端点的区间，所以是 \(\log n\) 级别的。那么总共只会增加 \(q\cdot \log n\log V\) 的势能。
对于完全被 \([l,r]\) 覆盖的区间的节点，考虑一棵二叉树的节点个数大概是二倍值域大小，所以完全被 \([l,r]\) 覆盖的区间的节点个数在 \(r-l+1\) 级别。需要分两种操作讨论：
- 区间加。显然势能是不变的。总时间复杂度 \(\mathcal O(q\log n)\)。
- 区间除。
- \(\max_{L,R}-\min_{L,R}\le 1\)。设满足此条件的节点个数为 \(t\)。此时势能极小而且基本不变了，而且它大概率满足上文优化的条件。所以我们认为它是 \(\mathcal O(\log n)\) 级别的。
- \(\max_{L,R}-\min_{L,R}> 1\)。由于 \(d>1\)，那么 \(\max_{L,R}-\min_{L,R}\) 至少减半，也即势能至少减 \(1\)。修改这部分节点复杂度是 \(\mathcal O(r-l+1-t)\) 级别的，但同时势能至少减少 \(r-l+1-t\)。当减少到 \(\max_{L,R}-\min_{L,R}\le 1\) 时，就又变成了上面的问题。
所以总复杂度应该也就是积蓄的最大势能：\(\mathcal O(q\cdot \log n\log V)\)。
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+5;
int n,q;
ll a[N];
inline ll Div(ll a, ll b)
{
if(a<0) return -((-a-1)/b+1);
else return a/b;
}
struct Sagiri
{
int l,r;
ll mn,mx,sum,lz;
} t[N<<2];
#define ls (p<<1)
#define rs (p<<1)|1
void pushup(Sagiri &c, Sagiri a, Sagiri b)
{
c.mn=min(a.mn,b.mn);
c.mx=max(a.mx,b.mx);
c.sum=a.sum+b.sum;
}
void build(int p, int l, int r)
{
t[p].l=l,t[p].r=r,t[p].lz=0;
if(l==r) { t[p].mn=a[l],t[p].sum=a[l],t[p].mx=a[l]; return ; }
int mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
pushup(t[p],t[ls],t[rs]);
}
void spread(int p)
{
int z=t[p].lz;
if(z)
{
t[ls].lz+=z; t[rs].lz+=z;
t[ls].sum+=(t[ls].r-t[ls].l+1)*z;
t[rs].sum+=(t[rs].r-t[rs].l+1)*z;
t[ls].mn+=z; t[rs].mn+=z;
t[ls].mx+=z; t[rs].mx+=z;
t[p].lz=0;
return ;
}
}
Sagiri query(int p, int l, int r)
{
if(t[p].l==l and t[p].r==r) return t[p];
spread(p);
int mid=(t[p].l+t[p].r)>>1;
if(r<=mid) return query(ls,l,r);
else if(l>mid) return query(rs,l,r);
else
{
Sagiri res;
pushup(res,query(ls,l,mid),query(rs,mid+1,r));
return res;
}
}
void change(int p, int l, int r, int v)
{
if(t[p].l==l and t[p].r==r)
{
t[p].mn+=v; t[p].mx+=v;
t[p].sum+=(t[p].r-t[p].l+1)*v; t[p].lz+=v;
return ;
}
spread(p);
int mid=(t[p].l+t[p].r)>>1;
if(r<=mid) change(ls,l,r,v);
else if(l>mid) change(rs,l,r,v);
else change(ls,l,mid,v),change(rs,mid+1,r,v);
pushup(t[p],t[ls],t[rs]);
}
void change_dv(int p, int l, int r, ll v)
{
if(t[p].mx<=0 and t[p].mn>=-1) return;
int amx=Div(t[p].mx,v),amn=Div(t[p].mn,v);
if(t[p].l==l and t[p].r==r and t[p].mx-amx==t[p].mn-amn)
{
t[p].sum-=(t[p].r-t[p].l+1)*(t[p].mx-amx);
t[p].lz-=t[p].mx-amx;
t[p].mx=amx,t[p].mn=amn;
return ;
}
if(t[p].l==t[p].r) { t[p].mn=Div(t[p].mn,v); t[p].mx=Div(t[p].mx,v); t[p].sum=Div(t[p].sum,v); return ; }
spread(p);
int mid=(t[p].l+t[p].r)>>1;
if(r<=mid) change_dv(ls,l,r,v);
else if(l>mid) change_dv(rs,l,r,v);
else change_dv(ls,l,mid,v),change_dv(rs,mid+1,r,v);
pushup(t[p],t[ls],t[rs]);
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=0; i<n; i++) scanf("%lld",&a[i]);
build(1,0,n-1);
int op,l,r; ll x;
while(q--)
{
scanf("%d%d%d",&op,&l,&r);
if(op==1) scanf("%lld",&x),change(1,l,r,x);
else if(op==2) scanf("%lld",&x),change_dv(1,l,r,x);
else if(op==3) printf("%lld\n",query(1,l,r).mn);
else printf("%lld\n",query(1,l,r).sum);
for(int i=0; i<n; i++) printf("%lld ",query(1,i,i).sum);
puts("");
}
return 0;
}
B
题目大意
有一个 \(n \times n\) 的黑白矩阵，一次操作把一行赋值到一列上，将整个矩阵全部变成黑色，输出最少步数，否则输出 \(-1\) .
题解
测试的时候大概想出了做法，但是写不出 \(O(n^2)\) 的代码.
具体做法就是如果有一个 \((i,i)\) 黑色，就可以把 \(i\) 这一行赋值到列上，这样就一定可以把 \(i\) 这一行全部变成黑色，有了一行全部是黑色之后，就可以拿它把所有列赋值完.
如果不存在一个 \((i,i)\) 黑色，可以多花一步或两步把蓝点移到 \((i,i)\).
代码其实很短，只需要记录一下每一行每一列有几个黑色的
算贪心吧，但我也不太会证.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1005;
int n,cc[N],cr[N];
char a[N][N];
int work(int x)
{
int res=2*(n-cr[x]); //白色的点一定会被赋值两次
//下面这行是处理 (x,x) 是白色的情况的，注意到如果从同一列赋值到了 (x,x)，理论上 res 应该多 1，但是注意到这时候 (x,x) 是一个白色的点，而他还是被赋值两次，所以答案不会变. 如果不是从同一列赋值两次到了 (x,x) 这时候才会多 1.
res++; for(int i=1; i<=n; i++) if(a[i][x]=='#') { res--; break; }
for(int i=1; i<=n; i++) if(a[x][i]=='#' and cc[i]!=n) res++; //黑色的点如果最初没被填满就会被赋值一次
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1; i<=n; i++) scanf("%s",a[i]+1);
int flag=0;
for(int i=1; i<=n; i++) for(int j=1; j<=n; j++)
if(a[i][j]=='#') cr[i]++,cc[j]++,flag=1;
if(!flag) { puts("-1"); return 0; }
int ans=(1<<30);
for(int i=1; i<=n; i++) ans=min(ans,work(i)); //枚举 (i,i) 这个点的答案
printf("%d\n",ans);
return 0;
}
C
注意到我不会后缀数组
等我学了再补
D
题目大意
给 \(n\in [1,30]\) 求满足
- \(x\) 是 \(n\) 位数
- \(x=\) 将 \(x\) 各位数字降序排列 \(-\) 将 \(x\) 各位数字升序排列
所有 \(x\) 的平方的和
题解
暴力
首先我们会 \(O(10^{n-1}\cdot n)\) 算法：直接 dfs 枚举所有 \(x\) 判断是否符合条件（记得 __int128）
然后我们会 \(O(C_{n+9}^9\cdot n)\) 算法：dfs 枚举一个升序序列，这东西大概是 \(6\times 10^9\)，显然会寄.
但是输出出来发现符合条件的 \(x\) 很少，所以我们可以考虑打表
注意到打表还得乘个 \(n\)，所以我们加个小剪枝让他更快打完：注意到 \(x\) 一定是 \(9\) 的倍数，因为一个数字不管怎么排列，模 \(9\) 的余数是不会变的呢 (^w^)
于是我们可以在五分钟内打完表.
可惜考场上没跑完（）
打表程序：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 35;
int a[N],b[N],cnt[N];
int n;
void dfs(int c, int r, int lb)
{
if(lb>=9 and r!=0) return ;
if(c>n)
{
if(lb==0) return ;
__int128 A=0,B=0,D;
for(int i=1; i<=n; i++) A*=10,A+=a[i];
for(int i=n; i; i--) B*=10,B+=a[i];
D=B-A;
for(int i=0; i<=9; i++) b[i]=0;
for(int i=1; i<=n; i++) b[D%10]++,D/=10;
for(int i=1; i<=n; i++) b[a[i]]--;
for(int i=0; i<=9; i++) if(b[i]!=0) return ;
printf(" {");
for(int i=1; i<n; i++) printf("%d,",a[i]);
printf("%d},\n",a[n]);
cnt[n]++;
return ;
}
for(int i=lb; i<=9; i++) a[c]=i,dfs(c+1,(r+i)%9,i);
}
int main()
{
freopen("db.txt","w",stdout);
for(n=1; n<=30; n++)
{
puts("{");
dfs(1,0,0);
puts("},");
}
printf("{");
for(int i=0; i<=30; i++) printf("%d,",cnt[i]);
printf("}\n");
return 0;
}
输出程序：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 35;
int cnt[]={0,0,0,1,1,0,2,0,2,2,3,1,5,1,6,2,8,2,12,3,14,5,17,7,21,8,25,12,30,14,36};
int a[N][65][N]=
{
//表
};
int main()
{
int n,P;
scanf("%d%d",&n,&P);
int ans=0;
for(int i=0; i<cnt[n]; i++)
{
ll A=0,B=0;
for(int j=0; j<n; j++) A=A*10%P,A=(A+a[n][i][j])%P;
for(int j=n-1; j>=0; j--) B=B*10%P,B=(B+a[n][i][j])%P;
ll C=(B-A+P)%P;
ans=(ans+(ll)C*C%P)%P;
}
printf("%d\n",ans);
return 0;
}
正解
这数据范围就很适合折半搜索，设 \(x\) 升序排列完从高到低是 \(a_1,a_2,a_3,\cdots,a_n\)
那么 \(x=(a_1-a_n)\cdot 10^{n-1}+(a_{2}-a_{n-1})\cdot 10^{n-2}+\cdots\)
前后是对称的，于是只需要枚举一半的 \(x\)
时间复杂度 \(O(C_{\frac{n}{2}+9}^{9}\cdot n)\) 非常可过.
原文地址：http://www.cnblogs.com/copper-carbonate/p/16886597.html
