• 周二. 8月 9th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

21牛客多校第四场

admin

11月 28, 2021

A

很猛的生成函数 咕

B

不妨考虑将题意转化为图,设(0)为起始点,(n+1)为终止点

假设当前在(i)点,下一次生成的数需要更大才能继续,即每次可以走到(i+1,dots n)这些点

而对于生成更小数的情况则代表了结束,对这种情况我们对(i)(n+1)连这些概率的边代表结束

(f_i)表示到从(i)走到(n+1)的步数期望,(g_i)表示从(i)走到(n+1)的步数平方的期望,最终要求的即为(g_0)

显然可以得到(f_i=sumlimits_{j=i}^{n+1} p_{iightarrow j}(f_j+1)),其中(p_{iightarrow j})表示从(i)走到(j)的概率

将右侧的(f_i)移动到等式左边即可得到(f_i)从后向前的递推式,((1-p_{iightarrow i})f_i=sumlimits_{j=i+1}^{n+1}(f_j+1))

考虑(g_i)的转移,(g_i=sumlimits_{j=i}^{n+1}p_{iightarrow j}E[(L_j+1)^2]),其中(L_j)表示到(j)还需走几步

(E[(x+1)^2])具体表示,得:

[egin{aligned}
E[(x+1)^2]&=sumlimits_{i=0}^{infty}p_i(i+1)^2\
&=sumlimits_{i=0}^{infty}p_i(i^2+2i+1)\
&=sumlimits_{i=0}^{infty}p_icdot i^2+2sumlimits_{i=0}^{infty}p_icdot i+sumlimits_{i=0}^{infty}p_i\
&=E[x^2]+2E[x]+1
end{aligned}
]

(E[(L_j+1)^2]=E[L_j^2]+2E[L_j]+1=g_j+2f_j+1)

(g_i=sumlimits_{j=i}^{n+1}p_{iightarrow j}(g_j+2f_j+1)),同样将右侧的(g_i)移动至左侧即可

(发现自己解释的很麻烦 直接理解也可以做

#include<bits/stdc++.h>
#define inf 2139062143
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define MAXN 100100
#define MOD 998244353
#define Fill(a,x) memset(a,x,sizeof(a))
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define pls(a,b) (a+b)%MOD
#define mns(a,b) (a-(b)+MOD)%MOD
#define mul(a,b) (1LL*(a)*(b))%MOD
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll n,f[110],g[110],p[110];
ll qp(ll x,ll t)
{
	ll res=1;for(;t;t>>=1,x=mul(x,x)) if(t&1) res=mul(res,x);return res;
}
#define inv(x) qp(x,MOD-2)
int main()
{
	n=read();int s=0,pp;rep(i,1,n) p[i]=read(),s+=p[i];
	s=inv(s);rep(i,1,n) p[i]=mul(p[i],s);
	f[n+1]=g[n+1]=0;
	dwn(i,n,0)
	{
		s=pp=0;rep(j,1,i-1) pp=pls(p[j],pp);p[n+1]=pp;
		rep(j,i+1,n+1) s=pls(s,mul(p[j],f[j]+1));
		f[i]=mul(pls(s,p[i]),inv(mns(1,p[i])));
	}
	dwn(i,n,0)
	{
		s=pp=0;rep(j,1,i-1) pp=pls(p[j],pp);p[n+1]=pp;
		rep(j,i,n+1) s=pls(s,mul(p[j],pls(g[j]+1,mul(2,f[j]))));
		g[i]=mul(s,inv(mns(1,p[i])));
	}
	printf("%lld
",g[0]);
}

C

不妨令(c<ale b),考虑这样一种构造

(s1=underbrace{adots a}_{a个} underbrace{bdots b}_{b-a个} underbrace{cdots c}_{c-a个} underbrace{ddots d}_{剩余补位})

(s2=underbrace{adots a}_{a个} underbrace{bdots b}_{剩余补位})

(s3=underbrace{adots a}_{a个} underbrace{cdots c}_{剩余补位})

这种构造已经用了最少的字符,当(a+(b-a)+(c-a)> n)时无解,其余情况有解

#include<bits/stdc++.h>
#define inf 2139062143
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define MAXN 100100
#define MOD 998244353
#define Fill(a,x) memset(a,x,sizeof(a))
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define pls(a,b) (a+b)%MOD
#define mns(a,b) (a-b+MOD)%MOD
#define mul(a,b) (1LL*(a)*(b))%MOD
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int a,b,c,n;char s[5][1010];
int main()
{
	a=read(),b=read(),c=read(),n=read();
	int mn=min(min(a,b),c);if(mn+a-mn+b-mn+c-mn>n) return puts("NO"),0;
	rep(i,1,mn) s[1][i]=s[2][i]=s[3][i]='a';
	a-=mn,b-=mn,c-=mn;
	if(!a)
	{
		rep(i,mn+1,n) s[1][i]='b',s[2][i]='c';
		rep(i,mn+1,mn+b) s[3][i]='c';
		rep(i,mn+b+1,mn+b+c) s[3][i]='b';
		rep(i,mn+b+c+1,n) s[3][i]='x';
	}
	if(!b)
	{
		rep(i,mn+1,n) s[2][i]='b',s[3][i]='c';
		rep(i,mn+1,mn+a) s[1][i]='b';
		rep(i,mn+a+1,mn+a+c) s[1][i]='c';
		rep(i,mn+a+c+1,n) s[1][i]='x';
	}
	if(!c)
	{
		rep(i,mn+1,n) s[1][i]='b',s[3][i]='c';
		rep(i,mn+1,mn+b) s[2][i]='c';
		rep(i,mn+b+1,mn+b+a) s[2][i]='b';
		rep(i,mn+b+a+1,n) s[2][i]='x';
	}
	printf("%s
%s
%s
",s[1]+1,s[2]+1,s[3]+1);
}

D

求原题的方案数等价于求将树分成(k+1)个联通块再求生成树的数量

对于(s_1,s_2,dots,s_{k+1})(k+1)个联通块,考虑(prufer)序列有(n^{k-1})种,而每次连边的时候还要从联通块里选一个连边,答案即为(n^{k-1}cdot s_1cdot s_2cdots s_{k+1})

后面的连乘式并不好计算,转化成对于整个树删了(k)条边且每个联通块内选一个点的方案数

(dp[i][j][0/1])表示节点(i)的子树内选了(j)个联通块,(i)所在联通块是否选择过点

(dp)方程显然,(dp[x][i],dp[v][j])可以转移到(dp[x][i+j],dp[x][i+j-1])(O(nk) dp)即可

#include<bits/stdc++.h>
#define inf 2139062143
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define MAXN 50100
#define MOD 998244353
#define Fill(a,x) memset(a,x,sizeof(a))
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define pls(a,b) (a+b)%MOD
#define mns(a,b) (a-b+MOD)%MOD
#define mul(a,b) (1LL*(a)*(b))%MOD
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,k,dp[MAXN][120][2],nxt[MAXN<<1],to[MAXN<<1],fst[MAXN],cnt,sz[MAXN];
void inc(int &x,int y) {x=pls(x,y);}
void add(int u,int v){nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v;}
int qp(int x,int t,int res=1)
{
	for(;t;t>>=1,x=mul(x,x)) if(t&1) res=mul(res,x);
	return res;
}
int tmp[120][2],ans;
void dfs(int x,int pa)
{
	sz[x]=1;dp[x][1][1]=dp[x][1][0]=1;int v;
	ren if(to[i]^pa)
	{
		v=to[i];dfs(v,x);Fill(tmp,0);
		dwn(i,min(sz[x],k+1),1) dwn(j,min(sz[v],k+2-i),1)
			inc(tmp[i+j-1][0],mul(dp[x][i][0],dp[v][j][0])),
			inc(tmp[i+j-1][1],mul(dp[x][i][1],dp[v][j][0])),
			inc(tmp[i+j-1][1],mul(dp[x][i][0],dp[v][j][1])),
			inc(tmp[i+j][0],mul(dp[x][i][0],dp[v][j][1])),
			inc(tmp[i+j][1],mul(dp[x][i][1],dp[v][j][1]));
		sz[x]+=sz[to[i]];
		rep(j,1,min(sz[x],k+1)) dp[x][j][0]=tmp[j][0],dp[x][j][1]=tmp[j][1];
	}
}
int main()
{
	n=read(),k=read();int a,b;
	rep(i,2,n) a=read(),b=read(),add(a,b),add(b,a);
	dfs(1,0);ans=qp(n,k-1,dp[1][k+1][1]);
	printf("%d
",ans);
}

E

对于这棵树,如果有一个点的值被确定则所有点的值都被确定

考虑通过(2,cdots,n)这些点来找到(1)的取值范围

预处理出所有点到(1)的异或距离(dis_i),则对于(i)点的限制,(1)点的合法选择是(jotimes dis_i, l_ile jle r_i)

对于([1,r_i])区间内的所有数,每次异或一个值相当于交换一次子树,而这些数构成的(trie)树从左至右是满的

因此对于每一位都有一段连续的区间的数满足条件,用动态开点线段树维护

最后查询线段树上有多少个点被加了(n-1)次,即满足所有点的限制,维护线段树上最大值与最大值个数即可

#include<bits/stdc++.h>
#define inf 2139062143
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define MAXN 100100
#define MOD 998244353
#define Fill(a,x) memset(a,x,sizeof(a))
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define pls(a,b) (a+b)%MOD
#define mns(a,b) (a-b+MOD)%MOD
#define mul(a,b) (1LL*(a)*(b))%MOD
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,l[MAXN],r[MAXN],nxt[MAXN<<1],to[MAXN<<1],val[MAXN<<1],fst[MAXN],Cnt;
int dis[MAXN];
void add(int u,int v,int w) {nxt[++Cnt]=fst[u],fst[u]=Cnt,to[Cnt]=v,val[Cnt]=w;}
const int lim=(1<<30)-1;
int rt,tot,ls[MAXN<<6],rs[MAXN<<6],cnt[MAXN<<6],mx[MAXN<<6],tag[MAXN<<6],ans;
inline void pshd(int k,int l,int r,int mid)
{
	if(!ls[k]) ls[k]=++tot,mx[tot]=0,cnt[tot]=mid-l+1;
	if(!rs[k]) rs[k]=++tot,mx[tot]=0,cnt[tot]=r-mid;
	tag[ls[k]]+=tag[k],tag[rs[k]]+=tag[k];
	mx[ls[k]]+=tag[k],mx[rs[k]]+=tag[k],tag[k]=0;
}
inline void upd(int k)
{
	mx[k]=cnt[k]=0;
	if(ls[k]) mx[k]=max(mx[k],mx[ls[k]]);
	if(rs[k]) mx[k]=max(mx[k],mx[rs[k]]);
	if(ls[k]) cnt[k]+=cnt[ls[k]]*(mx[ls[k]]==mx[k]);
	if(rs[k]) cnt[k]+=cnt[rs[k]]*(mx[rs[k]]==mx[k]);
}
void mdf(int &k,int l,int r,int a,int b,int w)
{
	if(!k) k=++tot,mx[k]=0,cnt[k]=r-l+1;
	if(a<=l&&r<=b) {tag[k]+=w,mx[k]+=w;return ;}
	int mid=l+r>>1;if(tag[k]) pshd(k,l,r,mid);
	if(a<=mid) mdf(ls[k],l,mid,a,b,w);
	if(b>mid) mdf(rs[k],mid+1,r,a,b,w);
	upd(k);
}
int query(int k,int l,int r,int a,int b,int w)
{
	if(!k) return 0;
	if(a<=l&&r<=b) return (mx[k]==w)*cnt[k];
	int mid=l+r>>1,res=0;if(tag[k]) pshd(k,l,r,mid);
	if(a<=mid) res=query(ls[k],l,mid,a,b,w);
	if(b>mid) res+=query(rs[k],mid+1,r,a,b,w);
	return res;
}
int tmp[50];
void calc(int t,int v)
{
	if(t<0) return ;
	int w=0;dwn(i,29,0) if((t>>i)&1)
	{
		if(!tmp[i]) {mdf(rt,0,lim,w,w+(1<<i)-1,v);w+=(1<<i);}
		else mdf(rt,0,lim,w+(1<<i),w+(1<<i+1)-1,v);
	}
	else if(tmp[i]) w+=(1<<i);
	mdf(rt,0,lim,w,w,v);
}
void work(int x)
{
	dwn(i,29,0) if((dis[x]>>i)&1) tmp[i]=1;else tmp[i]=0;
	calc(r[x],1);calc(l[x]-1,-1);
}
void dfs(int x,int pa)
{
	if(x!=1) work(x);
	ren if(to[i]^pa) {dis[to[i]]=dis[x]^val[i];dfs(to[i],x);}
}
int main()
{
	n=read();rep(i,1,n) l[i]=read(),r[i]=read();int a,b,c;
	rep(i,2,n) a=read(),b=read(),c=read(),add(a,b,c),add(b,a,c);
	dfs(1,0);ans=query(rt,0,lim,l[1],r[1],n-1);
	printf("%d
",ans);
}

F

由于删除联通块的时候联通块不能有环,显然可以考虑两人先顺次删掉所有非树边

对于剩下的若干个森林,继续删边使联通块个数(+1),删除联通块使联通块个数(-1),二者对奇偶性影响相同

因此求出联通块个数和非树边个数加和求奇偶性即可

#include<bits/stdc++.h>
#define inf 2139062143
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define MAXN 3001001
#define MOD 1000000007
#define Fill(a,x) memset(a,x,sizeof(a))
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define pls(a,b) (a+b)%MOD
#define mns(a,b) (a-b+MOD)%MOD
#define mul(a,b) (1LL*(a)*(b))%MOD
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,fa[MAXN],m,totn,tote;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int main()
{
	n=totn=read(),m=read();rep(i,1,n) fa[i]=i;int a,b;
	rep(i,1,m) 
	{
		a=read(),b=read();
		if(find(a)!=find(b)) totn--,fa[find(a)]=find(b);
		else tote++;
	}
	printf((1&(tote+totn))?"Alice":"Bob");
}

G

先不考虑(k),我们有结论:

[sum_{a_ige 0,sum_{i=1}^na_i = D} prod_{i=1}^n frac{1}{a_i!} = frac{n^D}{D!}
]

可以用二项式定理证明

对于题目来说,可以做如下转化:

[egin{aligned}
Ans&=D!sum_{a_ige 0,sum_{i=1}^na_i = D} prod_{i=1}^n frac{1}{(a_i+k)!}\
&=D!sum_{a_ige k,sum_{i=1}^na_i = D+nk} prod_{i=1}^n frac{1}{a_i!}
end{aligned}
]

不考虑范围限制,有:

[Ans=D!sum_{a_ige 0,sum_{i=1}^na_i = D+nk} prod_{i=1}^n frac{1}{a_i!} = frac{n^{D+nk}}{(D+nk)!}D!
]

需要容斥,考虑有至少(t)个数(<k)时的贡献:

[D! cdot inom{n}{t}(-1)^tsum_{0<a_i<k} prodlimits_{i=1}^tfrac{1}{a_i}cdot sum_{a_ige 0,sum_{i=1}^na_i= D+nk} prod_{i=t+1}^n frac{1}{a_i!} \
=D! cdot inom{n}{t}(-1)^tsum_{0<a_i<k} prodlimits_{i=1}^tfrac{1}{a_i}cdot lgroup frac{(n-t)^{D+nk-a_1-dots-a_t}}{(D+nk-a_1-dots-a_t)!}group
]

(f[i][j])表示有(i)个数每个(<k)总和为(j)时的贡献即(sum_{0<a_i<k,sum_{i=1}^t a_i=j} prodlimits_{i=1}^tfrac{1}{a_i})

可以(O(n^2k^2))简单(dp)转移得到

为方便计算,可以继续化简一下贡献:

[D! cdot inom{n}{t}(-1)^tcdot f[i][j]cdot frac{(n-t)^{D+nk-j}}{(D+nk-j)!}\
=frac{D!}{(D+nk)!}inom{n}{t}(-1)^tcdot f[i][j]cdot (n-t)^{D+nk-j}prod_{i=D+nk-j+1}^{D+nk}i
]

这样在枚举((i,j))时可以记录后面的连乘积,最后再计算前面的(frac{D!}{(D+nk)!})(prodlimits_{i=D+1}^{D+nk}frac{1}{i})

#include<bits/stdc++.h>
#define inf 2139062143
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define MAXN 100100
#define MOD 998244353
#define Fill(a,x) memset(a,x,sizeof(a))
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define pls(a,b) (a+b)%MOD
#define mns(a,b) (a-b+MOD)%MOD
#define mul(a,b) (1LL*(a)*(b))%MOD
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,k,f[3000][3000],fac[3000],ifac[3000],ans;
const int lim=2550;
int qp(int x,int t)
{
	int res=1;for(;t;t>>=1,x=mul(x,x)) if(t&1) res=mul(res,x);
	return res;
}
#define inv(x) qp(x,MOD-2)
inline int C(int n,int m)
{
	if(n<0||m<0||n<m) return 0;
	return mul(fac[n],mul(ifac[m],ifac[n-m]));
}
int main()
{
	n=read(),k=read(),m=read();int c,tmp;
	fac[0]=1;rep(i,1,lim) fac[i]=mul(fac[i-1],i);
	ifac[lim]=inv(fac[lim]);dwn(i,lim-1,0) ifac[i]=mul(ifac[i+1],i+1);
	f[0][0]=1;rep(i,1,n) rep(j,0,i*(k-1)) rep(o,0,min(k-1,j))
		f[i][j]=pls(f[i][j],mul(f[i-1][j-o],ifac[o]));
	rep(i,0,n) rep(j,0,i*(k-1))
	{
		c=C(n,i);if(i&1) c=MOD-c;if(!j) tmp=1;
		ans=pls(ans,mul(mul(c,tmp),mul(f[i][j],qp(n-i,m+n*k-j))));
		tmp=mul(tmp,m+n*k-j);
	}
	rep(i,m+1,m+n*k) ans=mul(ans,inv(i));printf("%d
",ans);
}

H

题目中(xotimes y=frac{ab}{gcd(a,b)^2}=frac{a}{gcd(a,b)}cdot frac{b}{gcd(a,b)}),即可设(x=icdot k,y=jcdot k,(i,j)=1)

(b_{xotimes y}=b_{ij}=sum_{k=1}^{lfloor frac{n}{max(i,j)}floor } a_{ik}cdot (jk)^c=sum_{k=1}^{lfloor frac{n}{max(i,j)}floor } a_{ik}cdot k^ccdot j^c)

考虑枚举(i),则可设(sum_m=sumlimits_{k=1}^m a_{ij}cdot j^c)

由于枚举((i,j))是调和级数即(nlogn)级别的,对于每个((i,j))可以通过(sum)(O(1))计算,即(b_{ij}+=j^ccdot sum[{lfloor frac{n}{max(i,j)}floor}])

#include<bits/stdc++.h>
#define inf 2139062143
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define MAXN 1001001
#define MOD 998244353
#define Fill(a,x) memset(a,x,sizeof(a))
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define pls(a,b) (a+b)%MOD
#define mns(a,b) (a-b+MOD)%MOD
#define mul(a,b) (1LL*(a)*(b))%MOD
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,c,g[MAXN],h[MAXN],ans,b[MAXN],s[MAXN];
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int qp(int x,int t)
{
	int res=1;for(;t;t>>=1,x=mul(x,x)) if(t&1) res=mul(res,x);
	return res;
}
int main()
{
	n=read(),c=read();int tmp;
	rep(i,1,n) g[i]=read(),h[i]=qp(i,c);
	rep(i,1,n) 
	{
		rep(j,1,n/i) s[j]=pls(s[j-1],mul(g[i*j],h[j]));
		rep(j,1,n/i)
		{
			if(gcd(i,j)!=1) continue;
			tmp=mul(h[j],s[n/max(i,j)]);
			b[i*j]=pls(b[i*j],tmp);
		}
	}
	rep(i,1,n) ans^=b[i];printf("%d
",ans);
}

I

修改会改变答案当且仅当(a[i]+1)在之前出现过且没被修改过,则可以将(a[i]++)使逆序对(-1)

对这些情况可以连边(a[i]ightarrow a[i]+1),最终会得到一些链

每一条长度为(L)的链会使答案减小(lfloor frac{L}{2}floor)

#include<bits/stdc++.h>
#define inf 2139062143
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define MAXN 200100
#define MOD 998244353
#define Fill(a,x) memset(a,x,sizeof(a))
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define pls(a,b) (a+b)%MOD
#define mns(a,b) (a-b+MOD)%MOD
#define mul(a,b) (1LL*(a)*(b))%MOD
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,to[MAXN],vis[MAXN],c[MAXN],g[MAXN];ll ans;
void mdf(int x){for(;x<=n;x+=x&-x) c[x]++;}
int query(int x,int res=0){for(;x;x-=x&-x) res+=c[x];return res;}
int main()
{
	n=read();rep(i,1,n) {g[i]=read();ans+=query(g[i]);mdf(g[i]);}
	ans=1LL*n*(n-1)/2-ans;int cnt=0,x;
	rep(i,1,n) {if(vis[g[i]+1]) to[g[i]]=g[i]+1;vis[g[i]]=1;}
	Fill(vis,0);
	rep(i,1,n) if(!vis[i])
	{
		cnt=0;x=i;
		while(x) vis[x]=1,cnt++,x=to[x];
		ans-=cnt/2;
	}
	printf("%lld
",ans);
}

J

要求(max{frac{sumlimits_{i=a}^bsumlimits_{j=c}^dW_{i,j}}{(b-a+1)(d-c+1)} },b-a+1ge x,d-c+1ge y)

(frac{sumlimits_{i=a}^bsumlimits_{j=c}^dW_{i,j}}{(b-a+1)(d-c+1)}=sumlimits_{i=a}^bsumlimits_{j=c}^dfrac{A_i+B_j}{(b-a+1)(d-c+1)}=frac{sumlimits_{i=a}^bA_i}{b-a+1}+frac{sumlimits_{i=b}^dB_i}{d-c+1})

即将问题转化为两个独立的问题,分别求长度不小于某个长度的最大连续子序列平均值

可以二分答案然后用前缀和(O(n))判断

#include<bits/stdc++.h>
#define inf 2139062143
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define MAXN 100100
#define MOD 998244353
#define Fill(a,x) memset(a,x,sizeof(a))
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define pls(a,b) (a+b)%MOD
#define mns(a,b) (a-b+MOD)%MOD
#define mul(a,b) (1LL*(a)*(b))%MOD
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const db eps=1e-8;
int n,m,lx,ly,g[MAXN];
db ans,sum[MAXN];
int cheq(db x,int n,int len)
{
	rep(i,1,n) sum[i]=g[i]-x;
	rep(i,2,n) sum[i]+=sum[i-1];
	db res=-inf,mn=inf;rep(i,len,n)
	{
		mn=min(mn,sum[i-len]);
		res=max(res,sum[i]-mn);
	}
	return res>=eps;
}
db work(int n,int len)
{
	db l=inf,r=0,mid;rep(i,1,n) l=min(l,1.0*g[i]),r=max(r,1.0*g[i]);
	while(r-l>eps)
	{
		mid=(l+r)/2;
		if(cheq(mid,n,len)) l=mid;
		else r=mid;
	}
	return l;
}
int main()
{
	n=read(),m=read(),lx=read(),ly=read();
	rep(i,1,n) g[i]=read();ans=work(n,lx);
	rep(i,1,m) g[i]=read();ans+=work(m,ly);
	printf("%.7lf
",ans);
}

发表评论

您的电子邮箱地址不会被公开。