今天的题目都比较有思维量,嗯
A. 星际旅行
考虑一下去掉那两条有向边,就是一个典型的欧拉回路
然后问的就是能够生成的欧拉回路的个数
考虑每次删掉两条边,有三种删除方法:
$\quad\mathfrak{1:}$ 删掉两个自环
$\quad\mathfrak{2:}$ 删掉一个自环和一条边
$\quad\mathfrak{3:}$ 删掉两条有公共顶点的边
注意到如果原图有两个以上分开的连通块无解
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<cstdio> #include<cstring> #include<string> #include<queue> #define int long long #define WR WinterRain using namespace std; const int WR=300100,INF=1099588621776; struct Edge{ int pre,to; }edge[WR<<1]; int n,m; int cnt=0; int head[WR],tot,opt[WR]; bool vis[WR]; int read(){ int s=0,w=1; char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ s=(s<<1)+(s<<3)+ch-'0'; ch=getchar(); } return s*w; } void add(int u,int v){ edge[++tot].pre=head[u]; edge[tot].to=v; head[u]=tot; } void dfs(int u){ vis[u]=true; for(int i=head[u];i;i=edge[i].pre){ int v=edge[i].to; if(!vis[v]) dfs(v); } } signed main(){ n=read(),m=read(); for(int i=1;i<=m;i++){ int u=read(),v=read(); if(u==v){ cnt++; continue; } add(u,v);add(v,u); opt[u]++,opt[v]++; } if(!tot){ printf("0\n"); return 0; } int ans=(cnt*tot/2)+(cnt*(cnt-1)/2); for(int i=1;i<=n;i++){ if(opt[i]){ dfs(i); break; } } for(int i=1;i<=n;i++){ if(!vis[i]&&opt[i]){ printf("0\n"); return 0; } } for(int i=1;i<=n;i++){ ans+=opt[i]*(opt[i]-1)/2; } printf("%lld\n",ans); return 0; }View Code
B. 砍树
考虑用数论分块维护这个 $d$ 就好了
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<cstdio> #include<cstring> #include<string> #include<cmath> #define int long long #define WR WinterRain using namespace std; const int WR=300100,INF=1099588621776; int n,k,sum; int ans; int a[WR]; int read(){ int s=0,w=1; char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ s=(s<<1)+(s<<3)+ch-'0'; ch=getchar(); } return s*w; } signed main(){ n=read(),k=read(); for(int i=1;i<=n;i++) a[i]=read(),sum+=a[i]; int l,tot=sum+k,r; for(l=1;l<=tot;l=r+1){ r=tot/(tot/l); int res=0; for(int i=1;i<=n;i++) res+=ceil((double)a[i]/r); if(res*r<=tot) ans=r; } printf("%lld\n",ans); return 0; }View Code
C. 超级树
题解写得很明白了
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<cstdio> #include<cstring> #include<string> #include<cmath> #define int long long #define WR WinterRain using namespace std; const int WR=300100,INF=1099588621776; int n,mod; int dp[1010][1010]; int read(){ int s=0,w=1; char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ s=(s<<1)+(s<<3)+ch-'0'; ch=getchar(); } return s*w; } signed main(){ n=read(),mod=read(); dp[1][0]=dp[1][1]=1; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ for(int l=0;l<=j;l++){ int r=j-l,tmp=dp[i][l]*dp[i][r]%mod; dp[i+1][l+r]=(dp[i+1][l+r]+tmp+2*tmp*(l+r)%mod)%mod; dp[i+1][l+r+1]=(dp[i+1][l+r+1]+tmp)%mod; dp[i+1][l+r-1]=(dp[i+1][l+r-1]+tmp*(l*(l-1)%mod+r*(r-1)%mod)%mod+2*tmp%mod*l*r%mod)%mod; } } } printf("%lld\n",dp[n][1]); return 0; }View Code
D. 求和
场切题目我没分
挂分原因:写了个树剖
正解非常平凡,预处理出所有的 $dpt[i]^k$ 然后查询完事
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #define int long long #define WR WinterRain using namespace std; const int WR=300500,INF=1099588621776,mod=998244353; struct Edge{ int pre,to; }edge[WR<<1]; struct Query{ int u,v,k,id; bool operator<(const Query &b)const{ return k<b.k; } }ask[WR]; int n,m; int head[WR],tot; int dis[WR][51],fa[WR][30]; int dpt[WR]; int ans[WR]; bool vis[100]; int read(){ int s=0,w=1; char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ s=(s<<1)+(s<<3)+ch-'0'; ch=getchar(); } return s*w; } void add(int u,int v){ edge[++tot].pre=head[u]; edge[tot].to=v; head[u]=tot; } int quick_pow(int a,int b){ int base=a,res=1; while(b){ if(b&1) res=res*base%mod; base=base*base%mod; b>>=1; } return res; } void dfs(int u,int root){ fa[u][0]=root;dpt[u]=dpt[root]+1; for(int i=1;i<=25;i++){ fa[u][i]=fa[fa[u][i-1]][i-1]; } for(int i=1;i<=50;i++){ dis[u][i]=(dis[root][i]+quick_pow(dpt[u],i))%mod; } for(int i=head[u];i;i=edge[i].pre){ int v=edge[i].to; if(v==root) continue; dfs(v,u); } } int LCA(int x,int y){ if(dpt[x]<dpt[y]) swap(x,y); for(int i=25;i>=0;i--){ if(dpt[fa[x][i]]>=dpt[y]){ x=fa[x][i]; } } if(x==y) return x; for(int i=25;i>=0;i--){ if(fa[x][i]!=fa[y][i]){ x=fa[x][i]; y=fa[y][i]; } } return fa[x][0]; } signed main(){ n=read(); for(int i=1;i<n;i++){ int u=read(),v=read(); add(u,v);add(v,u); } dpt[0]=-1;dfs(1,0); m=read(); for(int i=1;i<=m;i++){ int x=read(),y=read(),k=read(); int lca=LCA(x,y); printf("%lld\n",(dis[x][k]+dis[y][k]-dis[fa[lca][0]][k]-dis[lca][k]+2*mod)%mod); } return 0; }View Code
标签:ch,17,int,long,WR,2022.8,include,集训,define From: https://www.cnblogs.com/WintersRain/p/16593595.html