A
直接取 $n$ ,然后就是 $\frac{n-1}{2}+1$ 。
B
注意到只要超出一行的数目 $c$,就可以连接在一起,此方案就为 $c$ ,等差数列求和,如果只有一行,那么方案数一定为 $1$
C
不难发现第二种客人无论怎么拿,最多只能拿 $\min\{n,m\}$ 个,因为他们总是取低的那个,于是低的高度减 $1$ ,不存在什么能取两次 $a$ 高度的, 然后借此判断即可
D
就是一构造数列,对角线随便造。
E
枚举 $x$ ,不难发现,$x$ 的范围总在 $(\max\{a_i\}-n+1,\max\{a_i\}-1)$ 范围中,因为方案数既不能为 $0$ 也不能为 $n!$ ( $p$ 可整除)。
然后就可以枚举 $x$ ,得到 $\prod\limits_{i=x}^{x+n-1}b_{i}-(i-x)=\prod\limits_{i=x}^{x+n-1}x-(b_{i}-i)$
仅需要满足所有的 $x-b_i+i\equiv 0(\text{mod } p)$ ,即 $x\equiv b_i-i(\text{mod p})$
其中,$b_i$ 表示 小于等于 $i$ 糖果的敌人数。
$\Theta(n^2)$ 做法就是直接暴力算所有的 $b_i-i$ 。
$\Theta(n)$ 做法就是发现 $x+1$ ,只会增加一个 $b_{x+n}-(x+n)$ ,减去一个 $b_{x-1}-(x-1)$ ,用个数组记录数出现的次数即可,实现过程需要整体移位,即 $-\max\{a_i\}+n$
const int N=1e5+10;
int a[N],b[N<<1],ans[N],c[N],len;
int n,p;
int mod(int x){return (x%p+p)%p;}
int main()
{
int mx=0;scanf("%d%d",&n,&p);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),mx=max(a[i],mx);
for(int i=1;i<=n;i++)b[max(0,a[i]-mx+n)]++;
for(int i=1;i<=(n<<1);i++)b[i]+=b[i-1];int tmp=mx-n;
for(int i=1;i<=n;i++)c[mod(i-b[i])]++;
for(int i=1;i<n;i++){if(!c[mod(i)])ans[++len]=i+tmp;c[mod(i-b[i])]--;c[mod(i+n-b[i+n])]++;}
printf("%d\n",len);for(int i=1;i<=len;i++)printf("%d ",ans[i]);
return 0;
}
F
即可码农,也可不码农。
这里介绍一种不码农的做法。
不妨分别存储翻转,和没翻转的序列信息,然后在区间合并时,分别合并信息。
在合并信息时,注意左区间的后缀与右区间的前缀的合并方式,可以分为四种情况,也即
左区间前缀分别为 $<<<<<<<$ 以及不是 $<<<<<<<$ 的情况,后缀、右区间同理。
之后就是考虑细节的问题了。
const int N=5e5+5;
template<class o>void qr(o &x)
{
x=0;char c=gc;int f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}x*=f;
}
template<class o>void qw(o x){if(x<0)putchar('-'),x=-x;if(x/10)qw(x/10);putchar(x%10+48);}
struct SGT
{
int l[2],m[2],r[2],S;bool rv;
/*
l[0]>0 means sufix <<<<<<<....< l[0]<0 means >><<<...< or >>>>>...>>(this state means l[0]=r[0]=S or other ....)
r[0]>0 means the same as l[0]>0,r[0]<0 means the same as l[0]<0
the others are the same.
*/
I void set(bool v)
{
m[0]=m[1]=1;S=1;rv=0;
if(v)r[0]=1,l[0]=-1,r[1]=-1,l[1]=1;
else r[1]=1,l[1]=-1,r[0]=-1,l[0]=1;
}
I void rev(){swap(l[0],l[1]);swap(m[0],m[1]);swap(r[0],r[1]);rv^=1;}
friend SGT operator +(const SGT &l,const SGT &r)
{
SGT n;n.S=l.S+r.S;int L=l.S,R=r.S;n.rv=0;
for(int i=0;i<2;i++)
{
n.l[i]=l.l[i];n.r[i]=r.r[i];
if(l.l[i]>0)n.l[i]+=(l.l[i]==L&&r.l[i]>0?r.l[i]:0);
else if(l.l[i]==-L)if(l.r[i]==L||r.l[i]>0)n.l[i]-=abs(r.l[i]);
if(r.r[i]>0)n.r[i]+=(r.r[i]==R&&l.r[i]>0?l.r[i]:0);
else if(r.r[i]==-R)if(r.l[i]==R||l.r[i]>0)n.r[i]-=abs(l.r[i]);
n.m[i]=max(l.m[i],r.m[i]);
if(l.r[i]>0||r.l[i]>0)n.m[i]=max(n.m[i],abs(l.r[i])+abs(r.l[i]));
}
return n;
}
}t[N<<2],cur;char s[N];int cl=0;
void pushdown(int p){if(t[p].rv){t[p<<1].rev();t[p<<1|1].rev();t[p].rv=0;}}
void build(int p,int l,int r)
{
t[p].S=r-l+1;if(l==r){t[p].set(s[l]=='>');return ;}
int mid=l+r>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);
t[p]=t[p<<1]+t[p<<1|1];
}
void upd(int p,int l,int r,int ql,int qr)
{
if(ql<=l&&qr>=r){t[p].rev();if(cl)cur=cur+t[p];else cur=t[p];++cl;return ;}
int mid=l+r>>1;pushdown(p);if(ql<=mid)upd(p<<1,l,mid,ql,qr);if(qr>mid)upd(p<<1|1,mid+1,r,ql,qr);
t[p]=t[p<<1]+t[p<<1|1];
}
int main()
{
int n,m;qr(n),qr(m);
scanf("%s",s+1);
build(1,1,n);
for(int i=1;i<=m;i++)
{
int l,r;qr(l),qr(r);
upd(1,1,n,l,r);cl=0;
qw(cur.m[0]);puts("");
}
return 0;
}
0 条评论