2022.02.10 模拟赛
2022.02.10 模拟赛
Tree
Step 1
设当 \(k=i\) 时，一共需要 \(ans_i\) 条链。当 \(k=i+1\) 时，\(ans_{i+1}<=ans_i\) 。情况最差就是把 \(k=i\) 时的覆盖方式再覆盖一遍。
Step 2
对于每个叶子节点，无论怎么选，它们一定会被选到链上（废话，每个点都会被选！），不过叶子们更优。这就是个贪心的小方法。再仔细一想，对于每个点，我们只需要把这些点的儿子们计算出来需要多少条链覆盖，然后从中选择一个剩余链数最长的就行。
计算剩余链数可以用dfs序，完美地把一个递归变成一个for循环，老方便了。
Step 3
这是个有根树，所以说可爱的链子最长也就是最深的层数，接下来的 \(dep\) 可以等同于链长。
设最深的层数为 \(maxndep\) 。因为是多次询问，而且 \(q\) 贼大，干脆优选打这一摊询问处理完算了。
用类似于分治的方法：
1.对 \(dep\) 分治，每一块的 \(depl\) 与 \(depr\) 都会在 \(ans_{depl}==ans_{depr}\) 时更新这个区间
2.在一块 \(depl\) 与 \(depr\) 之间（链长递增），\(ans\) 也不上升，每次查询出 \(ans_{dep_{mid}}\) 与 \(ans_{dep_{mid+1}}\) ，可以确定下一个分治区间 \(ans\) 的取值范围，为步骤1做铺垫
代码如下：
#include
#include
#include
#include
#include
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define R register
const int N=1e5+10;
int n,m,cnt,head[N],vis[N],dep[N],fa[N];
int maxndep,ind,dfsx[N],ans[N],f[N];
struct node{
int to,next;
}a[N*2];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
inline void add(int u,int v){
++cnt;
a[cnt].to=v;
a[cnt].next=head[u];
head[u]=cnt;
}
inline void dfs(int x,int fai){
fa[x]=fai;
dep[x]=dep[fai]+1;
dfsx[++ind]=x;
maxndep=max(maxndep,dep[x]);
for(R int i=head[x];i;i=a[i].next){
int v=a[i].to;
if(v==fai)continue;
dfs(v,x);
}
}
inline int query(int k){
int len=k,now=0;
memset(f,0,sizeof(f));
for(R int i=n;i>=1;i--){
if(f[dfsx[i]]==0)f[dfsx[i]]=len,++now;
f[fa[dfsx[i]]]=max(f[fa[dfsx[i]]],f[dfsx[i]]-1);
}
return now;
}
inline void final(int l1,int r1,int l2,int r2){
if(l2==r2){
for(R int i=l1;i<=r1;i++)ans[i]=l2;
return ;
}
int mid=(l1+r1)>>1;
int midl=query(mid),midr=query(mid+1);
final(l1,mid,l2,midl);final(mid+1,r1,midr,r2);
}
signed main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
n=read();
for(R int i=1;i Count
Step 1
我是废物，我不会，我思索思索。
Sort
Step 1
手动计算之后，发现一个小规律：
对于数字 \(a\) 与 \(b\) ，且 \(a
当顺序是 \(a,b\) 时，接下来 \(a\) 与 \(b\) 是两个数；
当顺序是 \(b,a\) 时，接下来 \(b,a\) 当成一个数或者 \(a=b+0.5\) 。
所以 \(a=a||b+0.5\) ，\(b=b\) 。
Step 2
题目的操作2可以转化为查询 \(num[x]\) 排序后有 \(y-1\) 个数比它小的排列有几种。
看到“比它小”，看到“\(y-1\)”，上来就是一个树状数组，哦不对，是俩：一个记录顺序为 \(a,b\) 的，称为 \(minn\) ；另一个记录顺序为 \(b,a\) ，称之为 \(maxn\) 。
因为有 \(b+0.5\) ，这种骚气的数字，所以 \(a\) 的值与 \(b\) 的值统统乘2。
对于操作2：
设 \(minnans\) 是在 \(minn\) 中查询到的比 \(num[x]\) 小的数字个数，\(maxnans\) 则是在 \(maxn\) 中查询到的比 \(num[x]\) 的数字个数，则 \(maxnans<=minnans\) （我随便写的，就是这个意思）。
Case 1 第 \(x\) 项是较小值
如果 \(minnans>=y-1\) 并且 \(maxnans
Case 2 第 \(x\) 项是较大值
前面跟 \(Case 1\) 一样，懒得复制了，只不过如果第 \(x\) 项较小值小于较大值而不是等于，本身就是较大值了， \(minnans=minnans-1\) 。
实际上这两种情况我还是有点儿小懵逼，毕竟是真的就是半猜的，尤其是 \(Case 2\) 的减一，笔算之后才发现错了，我枯了/欲哭无泪脸。
Step 3
操作1就是交换两个值，然后修改。
Step 4
记得预处理一下乘法逆元和阶乘，方便算 \(ans\) 。
代码如下：
#include
#include
#include
#include
#include
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define int long long
#define R register
const int N=7e4;
const int M=N*2;
const int mod=1e9+7;
int n,m,num[N],a[N],b[N];//a:minn b:maxn
int fac[N],inv[N],powi[N];
struct node{
int val[M];
inline void init(){
memset(val,0,sizeof(val));
}
inline int lowbit(int x){
return x&(-x);
}
inline void add(int x,int k){
if(!x)return ;
for(R int i=x;i<=n*2+1;i+=lowbit(i))val[i]+=k;
}
inline int query(int x){
int ans=0;
for(R int i=x;i;i-=lowbit(i))ans+=val[i];
return ans;
}
};
node maxn,minn;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
inline void change(int x){
minn.add(a[x],-1);minn.add(a[x+1],-1);
maxn.add(b[x],-1);maxn.add(b[x+1],-1);
//cout<<"Case 1"<=y-1&&maxnansa[x])--minnans;
if(minnans>=y-1&&maxnans