今天的题目都比较有思维量，嗯
A. 星际旅行
考虑一下去掉那两条有向边，就是一个典型的欧拉回路
然后问的就是能够生成的欧拉回路的个数
考虑每次删掉两条边，有三种删除方法：
$\quad\mathfrak{1:}$ 删掉两个自环
$\quad\mathfrak{2:}$ 删掉一个自环和一条边
$\quad\mathfrak{3:}$ 删掉两条有公共顶点的边
注意到如果原图有两个以上分开的连通块无解
#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$ 就好了
#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. 超级树
题解写得很明白了
#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$ 然后查询完事
#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