省选测试31

首页 > 省选测试31 > 列表

省选测试31

A. coin

分析

设带某种礼物 \(x\) 件的贡献是 \(f(x)\) 那么有 \(f(x+2)?f(x+1) \leq f(x+1)?f(x)\)

那么就是说每多一件礼物,收益是递减的

所以开一个堆,维护 \((i,j,w)\) 表示第 \(i\) 种礼物选第 \(j\) 份的收益是 \(w\)

贪心的选最大的就好了

问题在于求出 \(w\)

设 \(f(k,c,n)\) 表示对于前 \(n\) 个人第 \(k\) 种礼物一共有 \(c\) 份的贡献

\(w=f(i,j,n)?f(i,j?1,n)\)

直接 \(dp\) 是 \(n^2m\) 的

但是可以发现有用的不是很多,所以把 \(dp\) 的形式改成记忆化搜索,需要的时候再搜

代码

#includecstdio
#includecstring
#includealgorithm
#includeiostream
#includemap
#includevector
#includequeue
#define rg register
inline int read(){
	rg int x=0,fh=1;
	rg char ch=getchar();
	while(ch'0' || ch'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch='0'  ch='9'){
		x=(x1)+(x3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
const int maxn=3e3+5,maxm=3e2+5;
int n,m;
double p[maxn][maxm],ans;
std::vectordouble g[maxm][maxn];
double getf(rg int k,rg int c,rg int nn){
	while(nn  !p[nn][k]) nn--;
	if(c==0 || !nn) return 0;
	if(g[k][c][nn]) return g[k][c][nn];
	return g[k][c][nn]=(getf(k,c-1,nn-1)+1)*p[nn][k]+getf(k,c,nn-1)*(1.0-p[nn][k]);
}
struct jie{
	int num,tim;
	double val;
	jie(){}
	jie(rg int aa,rg int bb,rg double cc){
		num=aa,tim=bb,val=cc;
	}
	bool operator (const jie A)const{
		return valA.val;
	}
};
std::priority_queuejie q;
int main(){
	n=read(),m=read();
	for(rg int i=1;i=n;i++){
		for(rg int j=1;j=m;j++){
			p[i][j]=read();
			p[i][j]/=1000.0;
		}
	}
	for(rg int i=1;i=m;i++){
		g[i][0].resize(n+1),g[i][1].resize(n+1);
		q.push(jie(i,1,getf(i,1,n)));
	}
	rg int aa,bb;
	rg double cc;
	for(rg int i=1;i=n;i++){
		aa=q.top().num,bb=q.top().tim,cc=q.top().val;
		q.pop();
		ans+=cc;
		g[aa][bb+1].resize(n+1);
		q.push(jie(aa,bb+1,getf(aa,bb+1,n)-getf(aa,bb,n)));
	}
	printf("%.10f\n",ans);
	return 0;
}

B. B

分析

把问题转化一下,要求的就是与给定树重合边数 \(\geq n?1?k\) 的树的个数

众所周知矩阵树求的是这个

\(\sum_{T}\prod_{e\in T}w_e\)

把原树中的边权设为 \(x\),其它的边权设为 \(1\)

代入矩阵树定理得到的是一个多项式

多项式的 \(k\) 次方项的系数就是重合边为 \(k\) 条时的答案

多项式显然是一个 \(n-1\) 次多项式

可以代入 \(n\) 项求出值,然后用高斯消元算出系数

代码

#includecstdio
#includecstring
#includealgorithm
#includeiostream
#includecmath
#includemap
#includevector
#define rg register
inline int read(){
	rg int x=0,fh=1;
	rg char ch=getchar();
	while(ch'0' || ch'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch='0'  ch='9'){
		x=(x1)+(x3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
const int maxn=55,mod=998244353;
inline int addmod(rg int now1,rg int now2){
	return now1+=now2,now1=modnow1-mod:now1;
}
inline int delmod(rg int now1,rg int now2){
	return now1-=now2,now10now1+mod:now1;
}
inline int mulmod(rg long long now1,rg int now2){
	return now1*=now2,now1=modnow1%mod:now1;
}
inline int ksm(rg int ds,rg int zs){
	rg int nans=1;
	while(zs){
		if(zs1) nans=mulmod(nans,ds);
		ds=mulmod(ds,ds);
		zs=1;
	}
	return nans;
}
int mp[maxn][maxn],e[maxn][maxn],ans[maxn],tmp[maxn][maxn],n,m;
int solve(rg int val){
	for(rg int i=1;i=n;i++){
		for(rg int j=1;j=n+1;j++){
			mp[i][j]=0;
		}
	}
	for(rg int i=1;i=n;i++){
		for(rg int j=i+1;j=n;j++){
			if(e[i][j]){
				mp[i][i]=addmod(mp[i][i],val);
				mp[j][j]=addmod(mp[j][j],val);
				mp[i][j]=delmod(mp[i][j],val);
				mp[j][i]=delmod(mp[j][i],val);
			} else {
				mp[i][i]=addmod(mp[i][i],1);
				mp[j][j]=addmod(mp[j][j],1);
				mp[i][j]=delmod(mp[i][j],1);
				mp[j][i]=delmod(mp[j][i],1);
			}
		}
	}
	rg int nans=1;
	for(rg int i=2;i=n;i++){
		for(rg int j=i+1;j=n;j++){
			if(!mp[i][i]  mp[j][i]){
				std::swap(mp[i],mp[j]);
				nans=delmod(0,nans);
				break;
			}
		}
		rg int ny=ksm(mp[i][i],mod-2);
		for(rg int j=i+1;j=n;j++){
			rg int tmp=mulmod(ny,mp[j][i]);
			for(rg int k=i;k=n+1;k++) mp[j][k]=delmod(mp[j][k],mulmod(mp[i][k],tmp));
		}
	}
	for(rg int i=2;i=n;i++) nans=mulmod(nans,mp[i][i]);
	return nans;
}
int main(){
	n=read(),m=read();
	rg int aa;
	for(rg int i=2;i=n;i++){
		aa=read()+1;
		e[i][aa]=e[aa][i]=1;
	}
	for(rg int i=1;i=n;i++){
		for(rg int j=1;j=n;j++){
			tmp[i][j]=ksm(i,j-1);
		}
		tmp[i][n+1]=solve(i);
	}
	for(rg int i=1;i=n;i++){
		for(rg int j=1;j=n+1;j++){
			mp[i][j]=tmp[i][j];
		}
	}
	for(rg int i=1;i=n;i++){
		rg int ny=ksm(mp[i][i],mod-2);
		for(rg int j=i;j=n+1;j++) mp[i][j]=mulmod(mp[i][j],ny);
		for(rg int j=i+1;j=n;j++){
			rg int tmp=mp[j][i];
			for(rg int k=i;k=n+1;k++) mp[j][k]=delmod(mp[j][k],mulmod(mp[i][k],tmp));
		}
	}
	ans[n]=mp[n][n+1];
	for(rg int i=n-1;i=1;i--){
		ans[i]=mp[i][n+1];
		for(rg int j=i+1;j=n;j++){
			ans[i]=delmod(ans[i],mulmod(ans[j],mp[i][j]));
		}
	}
	rg int sum=0;
	for(rg int i=n-m;i=n;i++) sum=addmod(sum,ans[i]);
	printf("%d\n",sum);
	return 0;
}

C. battery

分析

发现不确定的只有炮台的方向

而炮台的方向只有两种,所以可以看成一个 \(2-SAT\) 问题

因为炮台之间不能相互攻击,所以合法的情况下一个空地最多只能由两个炮台经过

代码

#includecstdio
#includecstring
#includealgorithm
#includeiostream
#includecmath
#includemap
#includevector
#define rg register
inline int read(){
	rg int x=0,fh=1;
	rg char ch=getchar();
	while(ch'0' || ch'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch='0'  ch='9'){
		x=(x1)+(x3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
const int maxn=105,maxm=1e4+5,dx[6]={1,-1,0,0},dy[6]={0,0,1,-1};
int h[maxm],tot=1;
struct asd{
    int to,nxt;
}b[maxm];
void ad(rg int aa,rg int bb){
    b[tot].to=bb;
    b[tot].nxt=h[aa];
    h[aa]=tot++;
}
int dfn[maxm],low[maxm],dfnc,sta[maxm],tp,shuyu[maxm],js;
void tar(rg int xx){
    dfn[xx]=low[xx]=++dfnc;
    sta[++tp]=xx;
    for(rg int i=h[xx];i!=-1;i=b[i].nxt){
        rg int u=b[i].to;
        if(!dfn[u]){
            tar(u);
            low[xx]=std::min(low[xx],low[u]);
        } else if(!shuyu[u]){
            low[xx]=std::min(low[xx],dfn[u]);
        }
    }
    if(low[xx]==dfn[xx]){
        js++;
        while(1){
            rg int y=sta[tp--];
            shuyu[y]=js;
            if(y==xx) break;
        }
    }
}
int t,n,m,rk1[maxn][maxn],rk2[maxn][maxn],vx1[maxm],vx2[maxm],vy1[maxm],vy2[maxm],cnt1,cnt2,jud,haha;
std::vectorint g[maxm],tmp;
char s[maxn][maxn];
void dfs(rg int nx,rg int ny,rg int d){
    if(s[nx][ny]=='#' || nxn || nx1 || nym || ny1 || !jud) return;
    else if(s[nx][ny]=='.'){
        tmp.push_back(rk2[nx][ny]);
        dfs(nx+dx[d],ny+dy[d],d);
    } else if(s[nx][ny]=='\\'){
        dfs(nx+dx[d^2],ny+dy[d^2],d^2);
    } else if(s[nx][ny]=='/'){
        dfs(nx+dx[3-d],ny+dy[3-d],3-d);
    } else {
        jud=0;
    }
}
int main(){
    t=read();
    while(t--){
        memset(h,-1,sizeof(h));
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(shuyu,0,sizeof(shuyu));
        for(rg int i=1;i=cnt2;i++) g[i].clear();
        tot=haha=1,dfnc=tp=js=cnt1=cnt2=0;
        n=read(),m=read();
        for(rg int i=1;i=n;i++) scanf("%s",s[i]+1);
        for(rg int i=1;i=n;i++){
            for(rg int j=1;j=m;j++){
                if(s[i][j]=='.'){
                    cnt2++;
                    vx2[cnt2]=i,vy2[cnt2]=j,rk2[i][j]=cnt2;
                } else if(s[i][j]=='-' || s[i][j]=='|'){
                    cnt1++;
                    vx1[cnt1]=i,vy1[cnt1]=j,rk1[i][j]=cnt1;
                }
            }
        }
        rg int tmp1=0,tmp2=0;
        for(rg int i=1;i=n;i++){
            for(rg int j=1;j=m;j++){
                if(s[i][j]=='|' || s[i][j]=='-'){
                    tmp1=tmp2=0,jud=1;
                    tmp.clear(),dfs(i+1,j,0);
                    dfs(i-1,j,1);
					if(jud) for(rg int o=0;otmp.size();o++) g[tmp[o]].push_back(rk1[i][j]);
                    tmp1=jud,jud=1;
                    tmp.clear(),dfs(i,j+1,2);
                    dfs(i,j-1,3);
					if(jud) for(rg int o=0;otmp.size();o++) g[tmp[o]].push_back(rk1[i][j]+cnt1);
                    tmp2=jud;
                    if(!tmp1  !tmp2) haha=0;
                    if(!tmp1){
                        ad(rk1[i][j],rk1[i][j]+cnt1);
                    } 
                    if(!tmp2){
                        ad(rk1[i][j]+cnt1,rk1[i][j]);
                    }
                }
            }
        }
        for(rg int i=1;i=cnt2;i++){
            if(g[i].size()==0) haha=0;
            else if(g[i].size()==1){
                if(g[i][0]cnt1) ad(g[i][0]-cnt1,g[i][0]);
                else ad(g[i][0]+cnt1,g[i][0]);
            } else {
                if(g[i][0]cnt1) ad(g[i][0]-cnt1,g[i][1]);
                else ad(g[i][0]+cnt1,g[i][1]);
                if(g[i][1]cnt1) ad(g[i][1]-cnt1,g[i][0]);
                else ad(g[i][1]+cnt1,g[i][0]);
            }
        }
        for(rg int i=1;i=cnt1+cnt1;i++){
            if(!dfn[i]) tar(i);
        }
        for(rg int i=1;i=cnt1;i++) if(shuyu[i]==shuyu[i+cnt1]) haha=0;
        if(!haha) printf("IMPOSSIBLE\n");
        else {
            printf("POSSIBLE\n");
            for(rg int i=1;i=cnt1;i++){
                if(shuyu[i]shuyu[i+cnt1]) s[vx1[i]][vy1[i]]='-';
                else s[vx1[i]][vy1[i]]='|';
            }
            for(rg int i=1;i=n;i++) s[i][m+1]='\0';
            for(rg int i=1;i=n;i++) printf("%s\n",s[i]+1);
        }
    }
    return 0;
}