CF1237D Balanced Playlist
题意
有一个长度为(n)((nleq 10^5))的循环播放歌单，每首歌有一个优秀值(a_i)((a_ileq 10^9))。
听歌时选一首歌开始，如果某一首歌(x)的优秀值的两倍小于当前听过的歌中优秀值最大的，那么会在听完(x)之前停止听歌。
对于每首歌(i)，求(c_i)表示如果从它开始听，最多听完几首歌，如果有重复的算多首。如果从一个位置开始能无限听下去，那么(c_i=-1)。
题解
首先发现当一个位置能无限听下去时，因为从其他位置开始时一定能听到这个位置，所以所有(c_i)都是-1。
以上情况可以通过判断(min{a_i} imes 2geq max{a_i})来判断。
先把环拆成2(???)倍链。
设(b_i=i+c_i)，表示从第(i)首歌开始听，最多听完哪首歌。
对于每个(i)找出([1,i])中最大的(j)使(2 imes a_i<a_j)（可以在单调队列上二分），有(b_1,b_2,...,b_jleq i)。
这些限制可以先在(j)处打标记，最后倒着扫一遍。
需要注意的是，拆环应该拆成3倍链而不是2倍链，因为从可能会在差一首歌听完整个歌单两遍时停止。
代码
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define rep(i,x,y) for(register int i=(x);i<=(y);++i)
#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)
#define view(u,k) for(int k=fir[u];~k;k=nxt[k])
#define LL long long
#define maxn 300005
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)
{
if(x==0){putchar('0'),putchar(' ');return;}
int f=0;char ch[20];
if(x<0)putchar('-'),x=-x;
while(x)ch[++f]=x%10+'0',x/=10;
while(f)putchar(ch[f--]);
putchar(' ');
return;
}
int a[maxn],q[maxn],n,c[maxn],mk[maxn],mx,mn,hd=1,tl;
void push(int i){while(hd<=tl&&a[q[tl]]<=a[i])tl--;q[++tl]=i;}
int getpos(int i)
{
int v=a[i],l=hd,r=tl,ans=-1;
while(l<=r)
{
int mid=l+r>>1;
if(a[q[mid]]>a[i]*2)ans=max(ans,q[mid]),l=mid+1;
else r=mid-1;
}
return ans;
}
int main()
{
n=read();int li=n+n+n;
rep(i,1,n)a[i]=a[i+n]=a[i+n+n]=read();
mx=mn=a[1];
rep(i,1,n)mx=max(a[i],mx),mn=min(mn,a[i]);
if(mn*2>=mx){rep(i,1,n)printf("-1 ");return 0;}
memset(mk,0x7f,sizeof(mk));
int now=mk[0];
rep(i,1,li)
{
push(i);
int p=getpos(i);
if(p==-1)continue;
mk[p]=min(mk[p],i);
}
dwn(i,li,1)now=min(mk[i],now),c[i]=now-i;
rep(i,1,n)write(min(c[i],min(c[i+n],c[i+n+n])));
return 0;
}
CF1237E Binary Search Trees
题意
问有多少棵点数为(n)((nleq 10^6))，点权为({1,2,...,n})中的数的二叉搜索树满足：
1.除了最下面一层外，所有层都是满的；
2.对于每个点，如果它有左儿子，那么左儿子的点权和它的奇偶性不同；如果它有右儿子，那么右儿子的点权和它的奇偶性相同。
题解
考虑构造(n)个点满足要求的二叉搜索树。设满足条件一的(n)个点的树有(L)层。
发现满足第二个要求的充要条件是对于每个点，它的左儿子的右子树大小为偶数，它的右儿子的左子树的大小为奇数。
对于一个符合第二个条件的二叉搜索树，它的左右子树也是符合第二个条件的；用两个符合条件的树分别接在根节点的左右儿子处，这两个符合条件的子树内部还是符合条件的。
这样就可以考虑用两棵(x-1)层的树拼成(x)层的树。在考虑这个问题时，只有“(x-1)层的树的左右子树大小”是在拼成(x)层的树时要考虑的。
记(f(d,x,y))表示(d)层的树，左右子树大小分别为(x、y)，的满足条件1、2的二叉搜索树有多少个。
d=1时，(f(d,0,0)=1)；
d=2时，(f(d,1,0)=1)；
d=3时，(f(d,1,2)=f(d,2,2)=1)；
发现当(d=k)时只有(f(d,x_1,y_1),f(d,x_2,y_2))为1，且(x_1)为奇数，(x_2,y_1,y_2)为偶数时，它们会转移到(f(d+1,x_1+y_1+1,x_1+y_1+1),f(d+1,x_2+y_2+1,x_1+y_1+1))，而(x_1+y_1+1,x_2+y_2+1)分别为偶数、奇数。
也就是说，转移后(f)值不为0的位置的(x、y)的奇偶性不变，而且(f)值还是1。
那么就可以维护(g(k)=(x_1,y_1,x_2,y_2)(k>2))表示当(d=k)时，有且仅有(f(d,x_1,y_1)=f(d,x_2,y_2)=1)。
最后设(g(L)=(x_1,y_1,x_2,y_2))，那么判断是否有(n=x_1+y_1+1)或(n=x_2+y_2+1)就行了。
代码
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define rep(i,x,y) for(register int i=(x);i<=(y);++i)
#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)
#define view(u,k) for(int k=fir[u];~k;k=nxt[k])
#define LL long long
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)
{
if(x==0){putchar('0'),putchar(' ');return;}
int f=0;char ch[20];
if(x<0)putchar('-'),x=-x;
while(x)ch[++f]=x%10+'0',x/=10;
while(f)putchar(ch[f--]);
putchar(' ');
return;
}
int n,xa,xb,ya,yb;
int main()
{
n=read();
if(n<=2){puts("1");return 0;}
int len=1,now=1,sum=1;for(;sum<n;len++,now<<=1,sum+=now);
xa=1,ya=2,xb=2,yb=2,len-=3;
rep(i,1,len){int x1=xa+ya+1,x2=xb+yb+1;xa=x2,ya=xb=yb=x1;}
if(n==xa+ya+1||n==xb+yb+1){puts("1");}
else puts("0");
return 0;
}
一些感想
网易 云 音乐
怪物 云 猎人
C F 云 选手