CF1329B Dreamoon Likes Sequences

题目描述

一个数列是符合条件的，当且仅当该数列非空且单增且前缀异或和单增。
给定\(d,m\)（\(d,m\leq 10^9\)），问所有每个数都是不超过\(d\)的正整数的数列中，符合条件的数列个数模\(m\)是多少。

题解

假设某个合法数列长度为\(n\)，数列为\(a_1,a_2,...,a_n\)，前缀和为\(b_1,b_2,...,b_n\)。
要想使\(\{b_n\}\)单增，就得有\(\forall i,b_i<b_{i+1}\)。
\(b_i<b_{i+1}\)有两种情况：1.\(b_{i+1}\)的最高的二进制位比\(b_i\)高；2.二者最高的二进制位相同，且二者都减去最高位后\(b_{i+1}\)更大。
考虑第2种情况，发现如果二者最高二进制位相同，由\(a_{i+1}=b_i\space xor\space b_{i+1}\)可得\(a_{i+1}\)的最高位比\(b_i\)低，而\(a_1,...,a_i\)中至少有一个的最高位和\(b_i\)相同，这与\(\{a_n\}\)单增的条件不符。
所以不会出现第二种情况。也就是说，\(\{b_n\}\)中每个数的最高二进制位都比前一个数高。
可以得出\(\{a_n\}\)中每个数的最高二进制位都比前一个数高。
把\(1,2,...,d\)中的数按最高二进制位分类。每一类中可以随便选一个或者不选。

代码

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#define LL long long
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define dwn(i,x,y) for(int i=(x);i>=(y);--i)
#define view(u,k) for(int k=fir[u];~k;k=nxt[k])
using namespace std;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)&&ch!='-')ch=getchar();
	if(ch=='-')f=-1,ch=getchar();
	while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	return x*f;
}
void write(int x)
{
	char ch[20];int f=0;
	if(!x){putchar('0'),putchar('\n');return;}
	if(x<0)putchar('-'),x=-x;
	while(x)ch[++f]=x%10+'0',x/=10;
	while(f)putchar(ch[f--]);
	putchar('\n');
}
int t,d,m,ans;
int mo(int x){if(x>=m)return x-m;if(x<0)return x+m;return x;}
int main()
{
	t=read();
	while(t--)
	{
		d=read(),m=read();ans=1;
		LL now=1,nxt=1;
		while(1)
		{
			if(nxt>=d){ans=(LL)ans*(d-now+2)%m;break;}
			ans=(LL)ans*(nxt-now+2)%m,now=nxt+1;nxt=(now<<1)-1;
		}
		ans=mo(ans-1);
		write(ans);
	}
	return (~(0-0)+1);
}

CF1329C Drazil Likes Heap

题目描述

有一个高度为\(h\)的有点权的满二叉树，满足大根堆的性质。
删掉一个不是叶子的点，这个点的权值较大的儿子会移动到这个点的位置，然后在这个儿子原来的位置重复该过程。
要删掉一些点，使它变成高度为\(g\)的满二叉树，且剩下的点的点权和尽可能小。问最小点权和、删掉哪些点。
所有点的点权不同，\(g\leq h\leq 20\)。

题解

首先发现剩下的部分的点权与删点顺序无关，因为每个点的点权在删完后都会变成原子树的最大值。
考虑一种贪心的构造方法：从下往上构造，让每个点的新点权是原子树中 大于该点左右儿子的新点权 的 尽可能小的点权。
该点选尽可能小的点权，不会使该点祖先的下界更大。
可以在每个点处维护按大小排好序的子树点权数组，一个点的数组可以由左右儿子的数组用类似归并排序的方法合并。时间复杂度\(\Theta(2^h\times h)\)。
如果用每到一个点都遍历一遍这个点的所有儿子来找它的点权的话，时间复杂度也是\(\Theta(2^h\times h)\)的，但递归常数略大。

这题还有完全不同的极其直观的另一种贪心做法：删当前根处的值，直到离根最近的叶子到根的距离是\(g\)，然后递归处理左右子树。
因为最大值都在堆顶，而且当一个点和它所有祖先都不能被删时，它的左右子树之间不会影响。时间复杂度也是\(\Theta(2^h\times h)\)

代码

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#define LL long long
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define dwn(i,x,y) for(int i=(x);i>=(y);--i)
#define view(u,k) for(int k=fir[u];~k;k=nxt[k])
using namespace std;
#define maxn ((1<<20)+7)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define ls (u<<1)
#define rs (u<<1|1)
int read()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)&&ch!='-')ch=getchar();
	if(ch=='-')f=-1,ch=getchar();
	while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	return x*f;
}
void write(LL x)
{
	char ch[20];int f=0;
	if(!x){putchar('0'),putchar('\n');return;}
	if(x<0)putchar('-'),x=-x;
	while(x)ch[++f]=x%10+'0',x/=10;
	while(f)putchar(ch[f--]);
	putchar('\n');
}
int t,n,h,g,a[maxn],yes[maxn],len,dfn[maxn],siz[maxn],val[maxn];
LL ans;
pii ar[maxn],tmp[maxn];
void merge(int u)
{
	int nl=dfn[ls],nr=dfn[rs],c=0;
	rep(i,1,siz[u])
	{
		int va=(nl>=dfn[ls]+siz[ls]?1e9:ar[nl].fi),
		vb=(nr>=dfn[rs]+siz[rs]?1e9:ar[nr].fi),
		vc=c?1e9:a[u];
		if(va<min(vb,vc)){tmp[i].fi=va,tmp[i].se=ar[nl].se,nl++;}
		else if(vb<min(va,vc)){tmp[i].fi=vb,tmp[i].se=ar[nr].se,nr++;}
		else tmp[i].fi=a[u],tmp[i].se=u,c++;
	}
	rep(i,1,siz[u])ar[dfn[u]+i-1]=tmp[i];
}
int getv(int u,int li)
{
	int L=dfn[u],R=dfn[u]+siz[u]-1;pii res;res.fi=1e9;
	while(L<=R)
	{
		int mid=(L+R>>1);
		if(ar[mid].fi>li)
		{
			if(res.fi>ar[mid].fi)res=ar[mid];
			R=mid-1;	
		}
		else L=mid+1;
	}
	yes[res.se]=1;
	return res.fi;
}
void work(int u,int d)
{
	if(d==g)
	{
		sort(ar+dfn[u],ar+dfn[u]+siz[u]);
		val[u]=ar[dfn[u]].fi,yes[ar[dfn[u]].se]=1,ans+=val[u];
		return;
	}
	work(ls,d+1),work(rs,d+1),merge(u);
	val[u]=getv(u,max(val[ls],val[rs])),ans+=val[u];
	return;
}
void build(int u,int d)
{
	dfn[u]=++len,ar[len].fi=a[u],ar[len].se=u,siz[u]=1;
	if(d==h){return;}
	build(ls,d+1),build(rs,d+1),siz[u]+=siz[ls]+siz[rs];
	return;
}
int main()
{
	t=read();
	while(t--)
	{
		h=read(),g=read(),n=(1<<h)-1;ans=len=0;
		rep(i,1,n)a[i]=read(),yes[i]=0;
		build(1,1);
		work(1,1);
		write(ans);
		dwn(i,n,1)if(!yes[i])printf("%d ",i);
		puts("");
	}
	return (~(0-0)+1);
}

一些感想

打穿越火线不要开黑：跟穿越火线强的人组队无法提高水平，跟不那么强的人组队无法提高分数。
但是跟英语水平强的人开黑既能提高水平（指睡着前有更多时间想题而不是翻译）又能提高分数（指有更多时间想题就更容易上分）。：）