bzoj 5287 [Hnoi2018]毒瘤

bzoj 5287 [Hnoi2018]毒瘤

​​ 题目:​​​ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int mod=998244353;int n,m;namespace sol1{ const int N=1e5+10; struct node{ int y,next; }data[N<<1]; int h[N],num,dp[N][2]; inline void dfs(int x,int fa){dp[x][0]=dp[x][1]=1; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if(y==fa) continue;dfs(y,x); dp[x][0]=(ll)dp[x][0]*(dp[y][0]+dp[y][1])%mod; dp[x][1]=(ll)dp[x][1]*dp[y][0]%mod; } } inline void gao(){ for (int i=1;i<=m;++i){ int x=read(),y=read(); data[++num].y=y;data[num].next=h[x];h[x]=num; data[++num].y=x;data[num].next=h[y];h[y]=num; }dfs(1,1);dp[1][0]+=dp[1][1];dp[1][0]%=mod; printf("%d\n",dp[1][0]); }}namespace sol2{ const int N=50; struct node{ int x,y; }nd[N]; inline void gao(){ for (int i=1;i<=m;++i){ nd[i].x=read()-1;nd[i].y=read()-1; }int ans=0; for (int s=0;s<(1< pd; inline void dfs2(int x,int fa){ if (mark[x]) pd.push_back(x);visit[x]=1; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (y==fa) continue; if (mark[y]&&!visit[y]) dfs2(y,x); } } inline void gao(){ for (int i=1;i<=m;++i){ int x=read(),y=read(); data[++num].y=y;data[num].next=h[x];h[x]=num; data[++num].y=x;data[num].next=h[y];h[y]=num; }dfs1(1,1);int st=0;memset(visit,0,sizeof(visit)); for (int i=1;i<=n;++i) if (mark[i]) {st=i;break;}dfs2(st,st); for (int i=0;i

2、发现我们这个返祖边很少于是可以3^(m-n)来枚举 但是显然这样多余了 可以发现状态一共是(0,1)(1,0)(0,0) 对于一对返祖边来说只有这些状态 接着又发现(0,1)(0,0) 其实i是一种状态 于是2^(m-n)枚举再暴力dp即可

#include#include#include#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int mod=998244353;const int N=1e5+10;inline int inc(int x,int v){return x+v>=mod?x+v-mod:x+v;}struct node{ int y,next;}data[N<<1];int h[N],fr[N],to[N],num,cnt,dfn[N],dp[N][2],n,m,bin[20];bool visit[N],mark[N][2];inline void dfs_init(int x,int fa){ dfn[x]=++num; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (y==fa) continue; if (!dfn[y]) dfs_init(y,x); else if(dfn[y]

3、发现这样过不去 为什么 因为暴力dp的时候有很多重复的状态

怎么办 考虑将那些被返祖边包含的点提取出来 建虚树

提前预处理出dp转移时候的系数 然后再dp的时候只需要这虚树上的有限的点即可

设k[x][0] k[x][1]分别表示x节点 状态是0或者1 他们对于下一个虚树节点的转移系数分别是多少tr0,tr1就是真正虚树的下一个节点到我这里的转移了

遇到不是虚树上的节点 就把他的系数加进去 遇到虚树节点 就重置

#include#include#include#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if(ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=1e5+10;const int mod=998244353;struct node{ int y,next;}data[N<<1],data1[N];inline int inc(int x,int v){return x+v>=mod?x+v-mod:x+v;} struct node1{ int x,y; inline node1 operator +(const node1 &a){ return (node1){inc(a.x,x),inc(a.y,y)}; } inline node1 operator *(ll a){ return (node1){x*a%mod,y*a%mod}; }}k[N][2],tr1[N],tr0[N];int dfn[N],num,h[N],h1[N],fr[N],to[N],g[N][2],dp[N][2],cnt,n,m,bin[30],size[N];bool mk[N][2],visit[N],mark[N];inline void dfs_init(int x,int fa){ dfn[x]=++num; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (y==fa) continue; if(!dfn[y]) dfs_init(y,x),size[x]+=size[y]; else if(dfn[y]=2);size[x]=mark[x]?1:size[x];}inline void insert1(int x,int y,const node1 &a,const node1 &b){ data1[++num].y=y;data1[num].next=h1[x];h1[x]=num;tr0[num]=a;tr1[num]=b;}inline int build(int x){ g[x][0]=g[x][1]=1;visit[x]=1;int vt=0; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (visit[y]) continue; int w=build(y); if (!w) g[x][0]=(ll)g[x][0]*(g[y][0]+g[y][1])%mod,g[x][1]=(ll)g[x][1]*g[y][0]%mod; else{ if (mark[x]) insert1(x,w,k[y][0]+k[y][1],k[y][0]); else k[x][0]=k[y][0]+k[y][1],k[x][1]=k[y][0],vt=w; } } if(mark[x]) k[x][0]=(node1){1,0},k[x][1]=(node1){0,1},vt=x; else k[x][0]=k[x][0]*g[x][0],k[x][1]=k[x][1]*g[x][1]; return vt;}inline void dfs(int x){ dp[x][0]=mk[x][0]?0:g[x][0];dp[x][1]=mk[x][1]?0:g[x][1]; for (int i=h1[x];i;i=data1[i].next){ int y=data1[i].y;dfs(y); dp[x][0]=(ll)dp[x][0]*((ll)tr0[i].x*dp[y][0]%mod+(ll)tr0[i].y*dp[y][1]%mod)%mod; dp[x][1]=(ll)dp[x][1]*((ll)tr1[i].x*dp[y][0]%mod+(ll)tr1[i].y*dp[y][1]%mod)%mod; }}int main(){ freopen("bzoj5287.in","r",stdin); n=read();m=read(); for (int i=1;i<=m;++i){ int x=read(),y=read(); data[++num].y=y;data[num].next=h[x];h[x]=num; data[++num].y=x;data[num].next=h[y];h[y]=num; }num=0;dfs_init(1,1);num=0;mark[1]=1;build(1);int S=(1<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。