21杭电多校第八场

本文主要是介绍21杭电多校第八场，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

C

使用\(Prim\)算法求最小生成树，复杂度\(O(n^2)\)

#include<bits/stdc++.h>
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define MAXN 2500100
#define MOD 998244353
#define Fill(a,x) memset(a,x,sizeof(a))
#define rep(i,s,t) for(register int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(register 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,x[5050],y[5050],frm[5050];ll low[5050],e[5050][5050];
inline ll sqr(ll x){return x*x;}
inline ll dis(int i,int j){return sqr(x[i]-x[j])+sqr(y[i]-y[j]);}
const ll inf=9e18;
ll prim()
{
    rep(i,1,n) low[i]=e[1][i],frm[i]=1;
    frm[1]=-1;ll mx=0,mn;int v;
	rep(i,2,n)
    {
		v=-1;mn=inf;
		rep(j,1,n) if(~frm[j]&&low[j]<mn) v=j,mn=low[j];
		if(v==-1) continue;
		frm[v]=-1,mx=max(low[v],mx);
		rep(j,1,n) if(~frm[j]&&low[j]>e[v][j])
			low[j]=e[v][j],frm[j]=v;
    }
    return mx;
}
int main()
{
    rep(T,1,read())
    {
        scanf("%d",&n);
        rep(i,1,n) x[i]=read(),y[i]=read();
        rep(i,1,n) rep(j,i,n)
			if(i==j) e[i][j]=0;
			else e[i][j]=e[j][i]=dis(i,j);
		printf("%lld\n",prim());
    }
}

D

两个修改操作分别相当于减少二进制上最小的\(1\)以及把最高位的\(1\)左移一位

因为\(1\)的数量不会改变，因此最多减小\(31\)次后数就会变成\(0\)

可以把最高位的\(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 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
#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;
}
inline void inc(int &x,int y){x=pls(x,y);}
inline void tms(int &x,int y){x=mul(x,y);}
int n,g[MAXN],h[MAXN],fa[MAXN],sum[MAXN<<2],tag[MAXN<<2],isz[MAXN<<2],c[MAXN];
void add(int x,int w){for(;x<=n;x+=x&-x) inc(c[x],w);}
int pres(int x,int res=0){for(;x;x-=x&-x) inc(res,c[x]);return res;}
int gets(int l,int r){return mns(pres(r),pres(l-1));}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void upd(int k)
{
	sum[k]=pls(sum[k<<1],sum[k<<1|1]);
	isz[k]=isz[k<<1]&isz[k<<1|1];
}
inline void pshd(int k)
{
	tms(sum[k<<1],tag[k]);tms(sum[k<<1|1],tag[k]);
	tms(tag[k<<1],tag[k]);tms(tag[k<<1|1],tag[k]);
	tag[k]=1;
}
void build(int k,int l,int r)
{
	tag[k]=1;if(l==r) {sum[k]=g[l],isz[k]=0;return ;}int mid=l+r>>1;
	build(k<<1,l,mid);build(k<<1|1,mid+1,r);upd(k);
}
void mdf(int k,int l,int r,int a,int b)
{
	if(isz[k]) return ;if(a<=l&&r<=b) {tms(sum[k],2);tms(tag[k],2);return ;}
	int mid=l+r>>1;if(tag[k]!=1) pshd(k);
	if(a<=mid) mdf(k<<1,l,mid,a,b);
	if(b>mid) mdf(k<<1|1,mid+1,r,a,b);
	upd(k);
}
void dec(int k,int l,int r,int x)
{
	if(l==r) {isz[k]=1,sum[k]=0;return ;}
	int mid=l+r>>1;if(tag[k]!=1) pshd(k);
	x<=mid?dec(k<<1,l,mid,x):dec(k<<1|1,mid+1,r,x);
	upd(k);
}
int query(int k,int l,int r,int a,int b)
{
	if(isz[k]) return 0;if(a<=l&&r<=b) return sum[k];
	int mid=l+r>>1,res=0;if(tag[k]!=1) pshd(k);
	if(a<=mid) res=query(k<<1,l,mid,a,b);
	if(b>mid) inc(res,query(k<<1|1,mid+1,r,a,b));return res;
}
void work(int l,int r)
{
	for(int tmp;l<=r;l++)
	{
		l=find(l);if(l>r) break;
		if(h[l]>0) {tmp=h[l]&-h[l];add(l,-tmp);h[l]-=tmp;}
		else if(!h[l]) {dec(1,1,n,l);h[l]=-1,fa[l]=l+1;}
	}
}
int main()
{
	int t,a,b,x;
	rep(T,1,read())
	{
		n=read();rep(i,1,n)
		{
			scanf("%d",&g[i]);fa[i]=i;
			for(x=g[i];x!=(x&-x);x-=x&-x);
			h[i]=g[i]-x;add(i,g[i]-x);g[i]=x;
		}
		build(1,1,n);fa[n+1]=n+1;
		rep(Q,1,read())
		{
			scanf("%d%d%d",&t,&a,&b);
			if(t==1) printf("%d\n",pls(pls(gets(a,b),query(1,1,n,a,b)),MOD));
			else if(t==2) work(a,b);
			else mdf(1,1,n,a,b);
		}
		rep(i,1,n) if(h[i]>0) add(i,-h[i]);
	}
}

E

考虑每一位的贡献，题目相当于在\(n-1\)个空位里插\(\le k-1\)个板，枚举这一位之后的板插在哪里或不插，答案为：

\[\begin{aligned} ans&=\sum\limits_{x=0}^k\sum\limits_{i=1}^na_i\lgroup \sum\limits_{j=0}^{n-i-1}10^j\binom{n-2-j}{x-1}+10^{n-i}\binom{i-1}{x}\rgroup\\ &=\sum\limits_{i=1}^na_i\lgroup\sum\limits_{j=0}^{n-i-1}10^j\sum\limits_{x=0}^{k-1}\binom{n-2-j}{x}+10^{n-i}\sum\limits_{x=0}^k\binom{i-1}{x}\rgroup \end{aligned} \]

注意到两个组合数求和都是对每一行求一段连续固定长度的和，则可以算出第一行后直接递推

处理出\(sum_i=\sum\limits_{j=0}^{k-1}\binom{i}{j}\)后，前半部分即为\(\sum\limits_{j=0}^{n-i-1}10^jsum_{n-2-j}\)，也很容易递推

#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 k,n,m,fac[MAXN],ifac[MAXN],ans,pw10[MAXN];
int f[MAXN],g[MAXN],s[MAXN];char ch[MAXN];
int q_pow(int bas,int t,int res=1)
{
    for(;t;t>>=1,bas=mul(bas,bas)) if(t&1) res=mul(res,bas);return res;
}
#define inv(x) q_pow(x,MOD-2)
inline int C(int n,int m)
{
	if(m<0||n<m) return 0;
	return mul(fac[n],mul(ifac[m],ifac[n-m]));
}
void mem(int n=1e6)
{
	fac[0]=ifac[0]=pw10[0]=1;
	rep(i,1,n) fac[i]=mul(fac[i-1],i),pw10[i]=mul(pw10[i-1],10);
	ifac[n]=inv(fac[n]);
	dwn(i,n-1,1) ifac[i]=mul(ifac[i+1],i+1);
}
ll Force(ll ans=0,ll res=0)
{
	rep(x,0,k) rep(i,1,n)
	{
		res=0;
		rep(j,0,n-i-1) res=pls(res,mul(C(n-2-j,x-1),pw10[j]));
		res=pls(res,mul(pw10[n-i],C(i-1,x)));
		res=mul(res,g[i]),ans=pls(ans,res);
	}
	return ans;
}
int main()
{
	int res,tmp;mem();
	rep(T,1,read())
	{
		k=read()-1;scanf("%s",ch+1);n=strlen(ch+1);
		rep(i,1,n) g[i]=ch[i]-'0';ans=0;tmp=1;
		//cout<<Force()<<endl;
		rep(i,1,n)
			res=mul(tmp,mul(g[i],pw10[n-i])),ans=pls(ans,res),
			tmp=mul(tmp,2),tmp=mns(tmp,C(i-1,k));
		if(!k) {printf("%d\n",ans);continue;}
		f[0]=tmp=1;rep(i,1,n)
			tmp=mul(tmp,2),tmp=mns(tmp,C(i-1,k-1)),f[i]=tmp;
		rep(i,0,n-2) s[i]=mul(pw10[i],f[n-2-i]);
		rep(i,1,n-2) s[i]=pls(s[i],s[i-1]);
		rep(i,1,n) ans=pls(ans,mul(g[i],s[n-i-1]));
		printf("%d\n",ans);
	}
}

F

对于每个数，每次操作相当于除一些质因数

令\(f[i]\)表示\(i\)这个数质数分解后的质数幂次之和，则原题相当于对一些石子数量为\(f[a_i]\)的石子做\(nim\)博弈

线性筛预处理\(f_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 10010010
#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 ntp[MAXN],f[MAXN],p[MAXN/7],tot,n,ans;
void mem(int n=1e7)
{
	rep(i,2,n)
	{
		if(!ntp[i]) p[++tot]=i,f[i]=1;
		rep(j,1,tot) if(i*p[j]>n) break;
			else {ntp[i*p[j]]=1,f[i*p[j]]=f[i]+1;if(i%p[j]==0) break;}
	}
}
int main()
{
	mem();rep(T,1,read())
	{
		n=read();rep(i,1,n) ans^=f[read()];
		puts(ans?"Alice":"Bob");ans=0;
	}
}

H

对于一个正方形和圆来说，正方形能够被圆完全包含的中心位置也形成一个圆

题目转化为两个圆面积求交

特判一下圆\(B\)无法包含正方形以及两个圆包含相离的情况

#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 pi=acos(-1);
db r1,r2,d,len;
struct Point{db x,y;}a,b;
inline db sqr(db x){return x*x;}
inline db dis(Point a,Point b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
db solve()
{
	db d=dis(a,b);
	if(d>=r1+r2) return 0.0;
	if(d<=r1-r2) return pi*r2*r2;
	if(d<=r2-r1) return pi*r1*r1;
	db p=(r1+r2+d)/2.0;
    db a1=acos((r1*r1+d*d-r2*r2)/(2.0*r1*d));
    db a2=acos((r2*r2+d*d-r1*r1)/(2.0*r2*d));
    return a1*r1*r1+a2*r2*r2-2.0*sqrt(p*(p-r1)*(p-r2)*(p-d));
}
int main()
{
	rep(T,1,read())
	{
		cin>>r1>>a.x>>a.y>>r2>>b.x>>b.y>>len;
		if(len*len>=r2*r2*2) {puts("0.000000");continue;}
		r1=sqrt(sqr(r1)-sqr(len/2))-len/2;
		r2=sqrt(sqr(r2)-sqr(len/2))-len/2;
		printf("%.6lf\n",solve()/(pi*r1*r1));
	}
}

I

因为模式串的长度不超过\(30\)，可以用字符串哈希暴力算出母串所有长度不超过\(30\)的子串的答案

每次\(check\)所有模式串即可

#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 400100
#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 Clear(x) {x.clear();vector<pii> (x).swap(x);}
#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 int mod=998244353,bas=137;
int n,m,len,p[MAXN],res[MAXN],ans[MAXN];
char ch[MAXN],cc[40];
int w1[MAXN],w2[MAXN],val[MAXN];
vector<pii> vec[40];map<int,int> mp;
int hsh[MAXN],pw[MAXN];
inline int calc(int l,int r)
{
	return (hsh[r]-(1LL*hsh[l-1]*pw[r-l+1])%mod+mod)%mod;
}
void work(int x)
{
	int tmp,tot=0;
	rep(i,1,m-x+1)
	{
		tmp=calc(i,i+x-1),w1[i]=tmp;
		if(!mp[w1[i]]) mp[w1[i]]=++tot,w2[i]=tot;
		else w2[i]=mp[w1[i]];
	}
	rep(i,1,tot) p[i]=-m,res[i]=0;
	rep(i,1,m-x+1) if(p[w2[i]]<=i-x) res[w2[i]]++,p[w2[i]]=i;
	for(auto t:vec[x])
	{
		tmp=t.se;
		if(!mp.count(tmp)) ans[t.fi]=0;
		else ans[t.fi]=res[mp[tmp]];
	}
	Clear(vec[x]);mp.clear();
}
int main()
{
	int h1;rep(T,1,read())
	{
		scanf("%s",ch+1);m=strlen(ch+1);pw[0]=1;
		rep(i,1,m)
        	pw[i]=(1LL*pw[i-1]*bas)%mod,hsh[i]=((1LL*hsh[i-1]*bas)%mod+ch[i]-'a'+1)%mod;
		n=read();rep(i,1,n)
		{
			scanf("%s",cc+1);len=strlen(cc+1);h1=0;
			rep(i,1,len)
				h1=((1LL*h1*bas)%mod+cc[i]-'a'+1)%mod;
			vec[len].pb({i,h1});
		}
		rep(i,1,30) if(vec[i].size()) work(i);
		rep(i,1,n) printf("%d\n",ans[i]);
	}
}

这篇关于21杭电多校第八场的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！