• 欢迎光临~

2022“杭电杯”中国大学生算法设计超级联赛(2)

开发技术 开发技术 2022-07-22 次浏览

链接

这次的界面终于让我有了一点我是花了钱的感觉(

(Static Query on Tree)

树链剖分做法:把在 (A,B) 中的点到根的路径染色,把 (C) 中的点的子树染色,都被染色过的点就是答案。
容斥做法:按 (C) 中节点的从属分成多个子树,若 (a)(b) 的子树中,则无需考虑 (a)。求出 (A,B,Acap B)(C) 经过的点集大小,容斥即可。
虚树做法:直接构建 (A,B,C) 中的点的虚树,直接 (DP) 即可。
此外,前两种方法不适用于无向边,虚树做法直接换根即可。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IL inline
#define LL long long
#define max(x,y) (x>y?x:y)
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
using namespace std;
const int N=2e5+3;
struct hh{
	int to,nxt;
}e[N<<1];
int n,m,fir[N],num,fa[N][20],dep[N],cnt,dfn[N],siz[N],sta[N],tp,bo[N][3],f[N][3];
int di[N],ans;
vector<int>E[N];
IL LL in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    LL x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}

bool cmp1(int x,int y){return dfn[x]<dfn[y];}

IL void add(int x,int y){
	e[++num]=(hh){y,fir[x]},fir[x]=num;
}

IL void clear(){
	num=cnt=0,memset(fir,0,sizeof(fir));
	memset(fa,0,sizeof(fa));
}

IL void Add(int x,int y){
	E[x].push_back(y);
}

void dfs1(int u,int f){
	fa[u][0]=f,siz[u]=1,dfn[u]=++cnt,dep[u]=dep[f]+1;
	for(int i=0;fa[u][i];++i)
	  fa[u][i+1]=fa[fa[u][i]][i];
	for(int i=fir[u],v;v=e[i].to;i=e[i].nxt)
	  dfs1(v,u),siz[u]+=siz[v];
}

IL int Lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=17;~i;--i)
	  if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
	if(x==y) return x;
	for(int i=17;~i;--i)
	  if(fa[x][i]^fa[y][i]) x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}

IL void ins(int x){
	if(!tp){sta[++tp]=x;return;}
	int lca=Lca(sta[tp],x);
	if(lca==sta[tp]){sta[++tp]=x;return;}
	while(dep[lca]<dep[sta[tp-1]]) Add(sta[tp-1],sta[tp]),--tp;
	Add(lca,sta[tp]),--tp;
	if(lca!=sta[tp]) sta[++tp]=lca;
	sta[++tp]=x;
}

void dfs2(int u,int fa){
	f[u][2]=f[fa][2]|bo[u][2];
	for(int i=0;i<E[u].size();++i){
		int v=E[u][i];
		dfs2(v,u);
		f[u][0]|=f[v][0],
		f[u][1]|=f[v][1];
		if(f[u][2]&&(f[v][0]&&f[v][1])) ans+=dep[v]-dep[u]-1;
	}
	f[u][0]|=bo[u][0],f[u][1]|=bo[u][1];
	if(f[u][2]&&(f[u][0]&&f[u][1])) ++ans;
}

void dele(int u,int fa){
	f[u][0]=f[u][1]=f[u][2]=bo[u][0]=bo[u][1]=bo[u][2]=0;
	for(int i=0;i<E[u].size();++i) dele(E[u][i],u);
	E[u].clear();
}
void solve(){
	n=in(),m=in(),clear();
	for(int i=2;i<=n;++i) add(in(),i);
	dfs1(1,0);
	int nn[3];
	while(m--){
		di[0]=ans=0;
		for(int i=0;i<=2;++i) nn[i]=in();
		for(int i=0;i<=2;++i)
		  for(int j=1;j<=nn[i];++j)
		    bo[di[++di[0]]=in()][i]=1;
		sort(di+1,di+di[0]+1),di[0]=unique(di+1,di+di[0]+1)-di-1;
		sort(di+1,di+di[0]+1,cmp1);
		for(int i=1;i<=di[0];++i) ins(di[i]);
		while(tp>1) Add(sta[tp-1],sta[tp]),--tp;
		dfs2(sta[1],0),dele(sta[1],0);tp=0;
		printf("%dn",ans);
	}
}
int main()
{
    int T=in();
    while(T--) solve();
    return 0;
}

(C++ to Python)

只输出 (()-,) 与数字即可。

#include<bits/stdc++.h>
#define IL inline
#define LL long long
#define max(x,y) (x>y?x:y)
using namespace std;
const int N=1e5+3;

IL LL in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    LL x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
IL int chk(char c){return (c>='0'&&c<='9')||(c=='-')||(c=='(')||(c==')')||(c==',');}
void solve(){
    string s,t;
    cin>>s;
    for(int i=0;i<s.size();++i)
      if(chk(s[i])) t+=s[i];
    cout<<t<<endl;
}
int main()
{
    int T=in();
    while(T--) solve();
    return 0;
}

(Copy)

真的真的要仔细看数据范围啊。。。如果 (l,r > n) 就不太好做了。
很明显要倒序操作,由于 (l,r leq n),我们只需维护前 (n) 个位置即可。
于是本来的加区间变成删区间,在 (r) 后的序列会向前挪 (r-l+1) 个位置。
于是,亲爱的 (bitset) 又来了呢~
此外还需注意下运算符的优先级。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=2e5+3;
struct que{
    int op,l,r;
}q[N];
int n,m,a[N];
bitset<N>bit1,bit2;
IL int in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    int x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
void solve(){
    n=in(),m=in(),bit1=bit2=0;
    for(int i=1;i<=n;++i) a[i]=in();
    for(int i=1;i<=m;++i){
        q[i].op=in(),q[i].l=in();
        if(q[i].op==1) q[i].r=in();
    }
    for(int i=1;i<=n;++i) bit2[i]=1;
    while(m){
        if(q[m].op==1){
            bit1=(((bit1&(bit2<<q[m].r))>>(q[m].r-q[m].l+1)))^(bit1&(bit2>>(n-q[m].r)));
        }
        else bit1[q[m].l]=bit1[q[m].l]^1;
        m--;
    }
    int ans=0;
    for(int i=1;i<=n;++i)
      if(bit1[i]) ans^=a[i];
    printf("%dn",ans);
}
int main()
{
    int T=in();
    while(T--) solve();
    return 0;
}

(Slayers Come)

对于每个技能,我们可以求出它可打倒的怪物区间,线段树上二分或二分 (+) (ST) 表都可做到 (O(nlogn))
于是问题变为给若干区间,求选择一些区间使数轴 (1) ~ (n) 的点全覆盖的方案数。
定义 (f_i)(1) ~ (i) 的点全覆盖的方案数 ( (i+1) 不会被覆盖,((i+2)) ~ (n) 的点不一定被覆盖 ) 。
将区间按右端点从小到大排序,右端点相同的再按左端点从大到小排序,这样可以包含区间被覆盖的情况。
对于区间 ((l,r)) ,对 (f_r) 的贡献为 (displaystyle sum_{i=l-1}^{r}f_i),注意这里算了 (f_r) 的值,以此涵盖区间被覆盖的情况。
而对于 ((0,l-2)) ,该区间取不取对其的转移无影响,故而直接乘 (2)
用线段树维护。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IL inline
#define LL long long
#define max(x,y) (x>y?x:y)
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
using namespace std;
const int N=2e5+3,p=998244353;
int n,m;
struct hh{
    int a,b;
}mo[N];
struct kk{
    int x,l,r;
}sk[N];
struct zz{
    int l,r;
    bool operator<(const zz &a) const{
    return r^a.r?r<a.r:l>a.l;}
}a[N];
IL LL in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    LL x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}

IL int mod(int x){return x>=p?x-p:x;}
#define ls k<<1
#define rs k<<1|1
struct tree{
    int Min[N<<2];
    IL void pushup(int k){
        Min[k]=min(Min[ls],Min[rs]);
    }
    int ask1(int k,int l,int r,int ll,int rr,int v){
        if(l>=ll&&r<=rr){
            if(Min[k]>=v||l==r) return l;
            int mid=l+r>>1;
            if(Min[k<<1|1]<v) return ask1(k<<1|1,mid+1,r,ll,rr,v);
            else return ask1(k<<1,l,mid,ll,rr,v);
        }
        int mid=l+r>>1;
        if(ll>mid) return ask1(k<<1|1,mid+1,r,ll,rr,v);
        if(rr<=mid) return ask1(k<<1,l,mid,ll,rr,v);
        int pos=ask1(k<<1|1,mid+1,r,ll,rr,v);
        if(mo[pos].a-mo[pos-1].b<v) return pos;
        return ask1(k<<1,l,mid,ll,rr,v);
    }
    int ask2(int k,int l,int r,int ll,int rr,int v){
        if(l>=ll&&r<=rr){
            if(Min[k]>=v||l==r) return r;
            int mid=l+r>>1;
            if(Min[k<<1]<v) return ask2(k<<1,l,mid,ll,rr,v);
            else return ask2(k<<1|1,mid+1,r,ll,rr,v);
        }
        int mid=l+r>>1;
        if(ll>mid) return ask2(k<<1|1,mid+1,r,ll,rr,v);
        if(rr<=mid) return ask2(k<<1,l,mid,ll,rr,v);
        int pos=ask2(k<<1,l,mid,ll,rr,v);
        if(mo[pos].a-mo[pos+1].b<v) return pos;
        return ask2(k<<1|1,mid+1,r,ll,rr,v);
    }
}T1,T2;
struct Tree{
    int sum[N<<2],mul[N<<2];
    void build(int k,int l,int r){
        sum[k]=0,mul[k]=1;
        if(l==r) return;
        int mid=l+r>>1;
        build(ls,l,mid),build(rs,mid+1,r);
    }
    IL void Mul(int k,int x){sum[k]=1ll*sum[k]*x%p;mul[k]=1ll*mul[k]*x%p;}
    IL void pushdown(int k){
        if(mul[k]^1) Mul(ls,mul[k]),Mul(rs,mul[k]),mul[k]=1;
    }
    void insert(int k,int l,int r,int p,int x){
        if(l==r){sum[k]=mod(sum[k]+x);return;}
        int mid=l+r>>1;
        pushdown(k);
        if(p<=mid) insert(ls,l,mid,p,x);
        else insert(rs,mid+1,r,p,x);
        sum[k]=mod(sum[ls]+sum[rs]);
    }
    int ask(int k,int l,int r,int ll,int rr){
        if(l>=ll&&r<=rr) return sum[k];
        int mid=l+r>>1;
        pushdown(k);
        if(rr<=mid) return ask(ls,l,mid,ll,rr);
        if(ll>mid) return ask(rs,mid+1,r,ll,rr);
        return mod(ask(ls,l,mid,ll,rr)+ask(rs,mid+1,r,ll,rr));
        sum[k]=mod(sum[ls]+sum[rs]);
    }
    void modify(int k,int l,int r,int ll,int rr,int v){
        if(l>=ll&&r<=rr) return Mul(k,v);
        int mid=l+r>>1;
        pushdown(k);
        if(ll<=mid) modify(ls,l,mid,ll,rr,v);
        if(rr>mid) modify(rs,mid+1,r,ll,rr,v);
        sum[k]=mod(sum[ls]+sum[rs]);
    }
}T;
void build(int k,int l,int r){
    if(l==r){T1.Min[k]=mo[l].a-mo[l-1].b,T2.Min[k]=mo[l].a-mo[l+1].b;return;}
    int mid=l+r>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    T1.pushup(k),T2.pushup(k);
}
void solve(){
    n=in(),m=in();
    for(int i=1;i<=n;++i) mo[i]=(hh){in(),in()};mo[n+1].b=0;
    for(int i=1;i<=m;++i) sk[i]=(kk){in(),in(),in()};
    build(1,1,n);
    for(int i=1;i<=m;++i){
        int l=T1.ask1(1,1,n,1,sk[i].x,sk[i].l),r=T2.ask2(1,1,n,sk[i].x,n,sk[i].r);
        a[i]=(zz){l,r};
    }
    sort(a+1,a+m+1),T.build(1,0,n),T.insert(1,0,n,0,1);
    for(int i=1;i<=m;++i){
        int v=T.ask(1,0,n,a[i].l-1,a[i].r);
        T.insert(1,0,n,a[i].r,v);
        if(a[i].l-2>=0) T.modify(1,0,n,0,a[i].l-2,2);
    }
    printf("%dn",T.ask(1,0,n,n,n));
}
int main()
{
    int T=in();
    while(T--) solve();
    return 0;
}

(Bowcraft)

直接被整破防。。。(long double) 不能过, (double) 能过。。。
(f_i) 为升到 (i) 级的期望值。
对于值为 (alpha,beta) 的技能书,当前级别为 (i) ,若选则 (f_{i+1}=f_i+1+(1-alpha)(1-beta)(f_{i+1}-f_i)+(1-alpha)beta f{i+1}),若不选则 (f_{i+1}=f_{i+1}+1),选与不选取决于二者的大小关系。
比较得若后者大于等于前者,则 (f_{i+1} geq frac{alpha + beta +alpha beta}{alpha} f_i) ,故最优解必然是取 (frac{alpha + beta +alpha beta}{alpha}) 最小的前几个,将其排序后枚举。
转移方程 (f_{i+1}=frac{AB+f_i sum{frac{alpha + beta +alpha beta}{alpha}} }{sum alpha})

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IL inline
#define LL long long
#define LF double
using namespace std;
const int N=1003,M=103;
const LF inf=1e9;
int n,m,A,B;
LF f[N];
struct kk{
    int i,j;LF val;
    bool operator<(const kk &a) const{
    return val<a.val;}
}p[M*M];
IL int in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    int x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
IL void solve(){
    n=in(),A=in(),B=in(),m=A*B;
    for(int i=1;i<=B;++i) p[i]=(kk){0,i-1,inf};
    for(int i=1;i<A;++i)  
      for(int j=0;j<B;++j)                   
        p[i*B+j+1]=(kk){i,j,(1.0*j*(A-i))/(i*B)};
    sort(p+1,p+m+1);
    for(int i=0;i<n;++i){
        LF pl=0,pr=0,Min=inf;
        for(int j=1;j<=m;++j){
            pl+=1.0*p[j].i/A,pr+=1.0*(1.0*p[j].i*B+1.0*p[j].j*A-1.0*p[j].i*p[j].j)/m;
            Min=min(Min,(m+pr*f[i])/pl);
        }
        f[i+1]=Min;
    }
    printf("%.3lfn",f[n]);
}
int main()
{
    int T=in();
    while(T--) solve();
    return 0;
}

(Snatch Groceries)

对区间排序后讨论即可。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=2e5+3;
const LL inf=1e18;
struct hh{
    int l,r;
    bool operator<(const hh &a) const{
    return l<a.l;}
}a[N];
int n;
IL int in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    int x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
void solve(){
    n=in();
    for(int i=1;i<=n;++i) a[i]=(hh){in(),in()};
    sort(a+1,a+n+1);
    int ans=0;
    for(int i=2;i<=n;++i)
      if(a[i].l>a[i-1].r) ++ans;
      else break;
    if(ans==n-1) ans=n;
    printf("%dn",ans);
}
int main()
{
    int T=in();
    while(T--) solve();
    return 0;
}

(ShuanQ)

显然 (PQ-1=kM) ,枚举 (PQ-1) 的约数并判断是否是质数即可。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=2e5+3;
const LL inf=1e18;
int n,m,e;
IL int in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    int x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
IL int chk(LL x){
    if(x==1) return 0;
    LL lim=sqrt(x);
    for(LL i=2;i<=lim;++i)
      if(x%i==0) return 0;
    return 1;
}
void solve(){
    LL x,y,z,e,Max;
    x=in(),y=in(),e=in(),z=x*y-1;
    Max=max({x,y,e});
    for(LL i=1;i*Max<z;++i)
      if(z%i==0){
          LL m=z/i;
          if(chk(m)) return (void)(printf("%lldn",e*y%m));
      }
    printf("shuanQn");
}
int main()
{
    int T=in();
    while(T--) solve();
    return 0;
}

(DOS Card)

合理设置节点储存的数据在线段树上直接嗯合并即可(这题没有修改操作真的很奇怪)。
变量名十分直观,合并十分浅显易懂(((

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=2e5+3;
const LL inf=1e18;
int n,m;
LL val[N];
IL int in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    int x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
struct node{
    LL i,j,ii,jj,ij,ji,iij,iji,ijj,jij,iijj,ijij;
    node operator+(const node &a) const{
        node c;
        c.i=max(i,a.i),
        c.j=max(j,a.j),
        c.ii=max({i+a.i,ii,a.ii}),
        c.jj=max({j+a.j,jj,a.jj}),
        c.ij=max({i+a.j,ij,a.ij}),
        c.ji=max({j+a.i,ji,a.ji}),
        c.iij=max({i+a.ij,ii+a.j,iij,a.iij}),
        c.iji=max({i+a.ji,ij+a.i,iji,a.iji}),
        c.ijj=max({i+a.jj,ij+a.j,ijj,a.ijj}),
        c.jij=max({j+a.ij,ji+a.j,jij,a.jij}),
        c.iijj=max({i+a.ijj,ii+a.jj,iij+a.j,iijj,a.iijj}),
        c.ijij=max({i+a.jij,ij+a.ij,iji+a.j,ijij,a.ijij});
        return c;
    }
    IL LL get(){return max(iijj,ijij);}
};
struct tree{
    #define ls k<<1
    #define rs k<<1|1
    node a[N<<2];
    void build(int k,int l,int r){
        if(l==r){a[k]={val[l]*val[l],-val[l]*val[l],-inf,-inf,-inf,-inf,-inf,-inf,-inf,-inf,-inf,-inf};return;}
        int mid=l+r>>1;
        build(ls,l,mid),build(rs,mid+1,r);
        a[k]=a[ls]+a[rs];
    }
    node query(int k,int l,int r,int ll,int rr){
        if(l>=ll&&r<=rr) return a[k];
        int mid=l+r>>1;
        if(rr<=mid) return query(ls,l,mid,ll,rr);
        if(ll>mid) return query(rs,mid+1,r,ll,rr);
        return query(ls,l,mid,ll,rr)+query(rs,mid+1,r,ll,rr);
    }
}T;
void solve(){
    n=in(),m=in();
    for(int i=1;i<=n;++i) val[i]=in();
    T.build(1,1,n);
    while(m--){
        int l=in(),r=in();
        printf("%lldn",T.query(1,1,n,l,r).get());
    }
}
int main()
{
    int T=in();
    while(T--) solve();
    return 0;
}

(Luxury cruise ship)

注意到加 (7) 的次数不会超过 $31 times 365 $ 次,
(31) 的次数不会超过 (7 times 365) 次。
与可以对 (N)(3 times 7 times 31 times 365) ,减去的天数直接用 (365) 去除,剩下的用背包即可。

#include<bits/stdc++.h>
#define IL inline
#define LL long long
#define max(x,y) (x>y?x:y)
using namespace std;
const int N=1e5+3,M=237615;
int f[M+1];
IL LL in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    LL x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
IL void init(){
    memset(f,63,sizeof(f));
    f[0]=0;
    for(int i=1;i<=M;++i){
        if(i>=7) f[i]=min(f[i],f[i-7]+1);
        if(i>=31) f[i]=min(f[i],f[i-31]+1);
        if(i>=365) f[i]=min(f[i],f[i-365]+1);
    }
}
void solve(){
    LL x=in(),y=x/M;
    x%=M;
    if(f[x]>1e9){printf("-1n");}
    else printf("%lldn",f[x]+y*31*7*3);
}
int main()
{
    init();
    int T=in();
    while(T--) solve();
    return 0;
}
程序员灯塔
转载请注明原文链接:2022“杭电杯”中国大学生算法设计超级联赛(2)
喜欢 (0)