noip模拟8[星际旅行·砍树·超级树·求和]
也不能算考得好，虽然这次A了一道题，但主要是那道题太简单了，没啥成就感，而且有好多人都A掉了
除了那一道，其他的加起来一共拿了25pts，这我能咋办，无奈的去改题
整场考试的状态并不是很好啊，不知道是刚放假回来的原因还是昨天晚上没睡好，
考试的时候一直很困，那种睁不开眼的困，然后导致我这次考试前三个题，屁大点的思路都没有
所以还是要保养好精神的，毕竟还有这么多事
所以我下次考试要保持一个好的状态，然后拿最多的分；；；
这次的考题思路极其怪癖，不对，是清奇！！！而且是想不到的清奇
正解：：：：
T1 星际旅行
题意：一条路径，经过两条边一次，其他的经过两次，求方案数啊
这题迷的不行，这个让求方案数，应该很多吧，然后他还不取模，我就懵圈了，这算啥方案数？？？
做取模的题做多了，以为方案数都特别大，其实也有小一些的，longlong足以解决这个题
整个就是一大模拟，对我来说，可是我一开始没有看出来咋模拟，
后来听了硕队的讲解，才明白，这是让你去边找欧拉路呐～～～
具体做法就是将所有的路径拆分成两条不同方向的路径，我们就有了2*m条路径，然后我们在这些路径中去掉两条
去掉之后，可以使这个图上的边（拆分后的边），能够一笔画完，（找之前别忘了判断图上的边是否全部联通）
我们考虑欧拉图存在的条件，有两个或者没有连奇数条边的节点，所以根据这个定义，我们可以拆掉的边只有三种情况
1、任意两个自环（拆自环的话，每个点的边数减少二，不会影响结果）
2、两个连在同一点上的边（只能这样拆，因为这样那个共同的点拆之后还是偶数，如果任意拆两条边，那么会有四个边数为奇数的点）
3、任意一个自环和任意一条边（自环不影响，边造成两个奇点）
所以我们在实现的时候，只需要统计有多少自环，有多少边，每个点的度数，用计数原理乘一乘就好了
注意判断是否联通的时候，可以有点没有遍历到，但是边必须都要遍历到
#include<bits/stdc++.h> using namespace std; #define re register int #define ll long long const int N=100005; int n,m; int to[N*2],nxt[N*2],head[N],rp; int zi,oi,du[N]; ll ans; void add_edg(int x,int y){ to[++rp]=y; nxt[rp]=head[x]; head[x]=rp; } bool vis[N],edg[N]; int vi; void dfs(int x,int f){ //cout<<x<<" "; if(vis[x])return ; vis[x]=1; for(re i=head[x];i;i=nxt[i]){ int y=to[i]; //cout<<x<<" "<<y<<" "<<vi<<" "; //if(y==x)vi++; //cout<<vi<<endl; if(y==f)continue; vi++; //cout<<x<<" "<<y<<" "<<vi<<endl; if(vis[y]==0)dfs(y,x); } } signed main(){ scanf("%d%d",&n,&m); for(re i=1;i<=m;i++){ int x,y; scanf("%d%d",&x,&y); edg[x]=edg[y]=1; if(x==y){ add_edg(x,y); zi++; } else{ add_edg(x,y); add_edg(y,x); oi++; du[x]++; du[y]++; } } for(re i=1;i<=n;i++){ dfs(i,0); if(vi!=0)break; vis[i]=0; //cout<<endl; } for(re i=1;i<=n;i++){ if(!vis[i]&&edg[i]){ //cout<<i<<endl; printf("0");return 0; } } ans+=1ll*zi*oi; ans+=1ll*zi*(zi-1)/2; //cout<<ans<<endl; for(re i=1;i<=n;i++){ if(du[i]>1)ans+=1ll*du[i]*(du[i]-1)/2; } printf("%lld",ans); }
T1
T2 砍树
这个题好像比最后一个题还水：：：：
题意：每隔d天砍一次树，把比期望值高的那部分砍掉，问你在最多砍k长度的情况下，最大的d是多少
所以这个题是个数论题，我竟然没看出来，我瞬间感觉我莫比乌斯专题白学了，竟然连这个题都不会推！！！
气人，所以这个题就是一个简单的推式子，代码写出来25行不到。。。。
我们要求的就是
$ \sum \limits_{i=1}^{n} \left ( \left \lceil \frac{a_i}{d} \right \rceil \times d -a_i\right )\le k $
$ \sum \limits_{i=1}^{n} \left ( \left \lceil \frac{a_i}{d} \right \rceil \times d \right )-\sum\limits_{i=1}^{n}a_i\le k $
$ \sum \limits_{i=1}^{n} \left ( \left \lceil \frac{a_i}{d} \right \rceil \times d \right )\le\sum\limits_{i=1}^{n}a_i+k $
设C = $ \sum\limits_{i=1}^{n}a_i+k $
$ \sum \limits_{i=1}^{n} \left \lceil \frac{a_i}{d} \right \rceil \le \frac{C}{d} $
$ \sum \limits_{i=1}^{n} \left \lceil \frac{a_i}{d} \right \rceil \le \left \lfloor \frac{C}{d}\right \rfloor $
所以我们就发现后面的式子就是一个关于数论分块的东西
我们就可以用分块去求每个块的左右边界了，不会自己找博客
右侧的每一个块内，一定是右边界最优，而左边，显然随着d的增加他是递减的，所以我们只需要每次判断右边界的取值然后更新答案即可
#include<bits/stdc++.h> using namespace std; #define re register int #define ll long long const int N=105; int n; ll a[N],k,ans; signed main(){ scanf("%d%lld",&n,&k); for(re i=1;i<=n;i++)scanf("%lld",&a[i]),k+=a[i]; for(ll l=1,r;l<=k;l=r+1){ r=k/(k/l); ll tmp=0; for(re i=1;i<=n;i++){ tmp+=a[i]/r; if(a[i]%r!=0)tmp++; } if(tmp*r<=k)ans=r; } printf("%lld",ans); }
T2
T3 超级树
他把所有的点到他祖先的边都连起来了，这边数多的要爆炸啊
题意：按照上面说的先构建一颗超级树，然后寻找树上的路径条数，要求要遍历每一个点不超过一次，就是说可以不走这个点，单点也算一条路径
这种题，边数如此之多，我们只能往dp的方向去想，不然你去遍历整个图啊，而且你还遍历不完，这咋办，虽然考场上我看到这个题就想困，但是我知道他是个dp
但是这个dp方程也太不正常了，我看题解理解了半个多小时，那我要是自己想得想多久啊，真不知道啥境界才能想出正解啊
设dp[i][j]表示目前i层，并且这个i层的超级树中存在j条不相交的路径的方案数
这个dp含义很难理解，第一维是没问题的，我们看看第二维
简单说就是在这个超级树里，有j条路径，并且这j条路径所覆盖的点没有重复的，就是我们沿着这j条路径走过一遍，每个点只会走一次或者不走
就是j条路径上没有重复的点。。。懂了吧，这dp多么毒瘤，光看定义就知道有多麻烦了；；；；
为什么要这样定义呢，因为我们的转移方程，是有多条路径的方案数想1条转移的，这样才能求出最后的答案
一共有五个转移方程，在转移之前我们一共有三层循环，第一层一定是层数i，第二层是左子树的j，设为l；第三层是右子树的j，设为r；
设num=dp[i][l]*dp[i][r] 就是乘法原理，两颗子树分别有这些情况合并之后自然就是乘起来了。。
1、我们对这颗树没有任何操作：dp[i+1][l+r]+=num 定义的重要性，根节点此时已经空出来了
2、我们将目前的根节点与左子树或右子树中的任意一条路径相连：dp[i+1][l+r]+=2*num*(l+r) 我们一共有l+r条路径可以连
（因为这个根已经和他子树的每一个节点相连了，每条路径都可以连上而且两端是两种情况，所以×2）
3、我们把根节点自己算作一个单独的路径，就有了：dp[i+1][l+r+1]+=num
4、我们用根节点分别连接两颗子树中的路径：dp[i+1][l+r-1]+=2*num*l*r
就是两颗子树中分别有一个路径，然后通过根的链接他变成了一条，左子树l种，右子树r种
5、我们用根节点去连接某一棵子树内的两条边：dp[i+1][l+r-1]+=num*(l*(l-1)+r*(r-1)) 就是左子树内两个路径变一条，或者右子树内两条变一条
这样我们就搞完了转移方程，然后你发现，这第二维有2^n这么多种情况诶，那你不超时谁超时，
但是这每一次转移都只会将每一个的第二维+1或者-1所以我们只需要n个状态
最后求的是一条路径的方案数，所以答案就是dp[n][1]啦，定义要好好理解
这样我们就可以愉愉快快的写代码啦
#include<bits/stdc++.h> using namespace std; #define re register int #define ll long long const int N=305; ll n,mod; ll dp[N][N]; signed main(){ scanf("%lld%lld",&n,&mod); dp[1][0]=dp[1][1]=1%mod; for(re i=1;i<n;i++){ for(re l=0;l<=n;l++){ for(re r=0;r<=n-l;r++){ ll num=dp[i][l]*dp[i][r]%mod; dp[i+1][l+r]+=num; dp[i+1][l+r+1]+=num; dp[i+1][l+r]+=2*num*(l+r); dp[i+1][l+r-1]+=2*num*l*r; dp[i+1][l+r-1]+=num*(l*(l-1)+r*(r-1)); dp[i+1][l+r]%=mod; dp[i+1][l+r+1]%=mod; dp[i+1][l+r-1]%=mod; } } } printf("%lld",dp[n][1]); }
T3
T4 求和
题意：给你一个树，让你求某两个点之间的路径上的所有边权的k次方之和
直接预处理前缀和，树链剖分求lca，然后减一下，这题真水！！！！
#include<bits/stdc++.h> using namespace std; #define re register int const int N=310005; const int mod=998244353; int n,m; int to[N*2],nxt[N*2],head[N],rp; int sum[N][55]; void add_edg(int x,int y){ to[++rp]=y; nxt[rp]=head[x]; head[x]=rp; } int ksm(int x,int y){ int ret=1; while(y){ if(y&1)ret=1ll*ret*x%mod; x=1ll*x*x%mod; y>>=1; } return ret; } int dep[N],siz[N],son[N],top[N],fa[N]; void dfs1(int x,int f){ //cout<<x<<" "<<f<<endl; for(re i=1;i<=50;i++)sum[x][i]=(1ll*sum[f][i]+ksm(dep[x],i))%mod; //if(x==130934)cout<<"sb"<<endl; siz[x]=1;son[x]=0; for(re i=head[x];i;i=nxt[i]){ int y=to[i]; //if(x==130934)cout<<i<<endl; if(y==f)return ; //if(x==130934)cout<<y<<endl; fa[y]=x; dep[y]=dep[x]+1; dfs1(y,x); siz[x]+=siz[y]; if(!son[x]||siz[y]>siz[son[x]])son[x]=y; } } void dfs2(int x,int f){ top[x]=f; if(son[x])dfs2(son[x],f); for(re i=head[x];i;i=nxt[i]){ int y=to[i]; if(y==son[x]||y==fa[x])continue; dfs2(y,y); } } int LCA(int x,int y){ while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); x=fa[top[x]]; } return dep[x]<dep[y]?x:y; } signed main(){ //int o=time(NULL); scanf("%d",&n); for(re i=1;i<n;i++){ int x,y; scanf("%d%d",&x,&y); add_edg(x,y); add_edg(y,x); } //cout<<rp<<" "<<to[rp]<<endl; dfs1(1,0); //cout<<"sb"<<endl; dfs2(1,1); //cout<<"sb"<<endl; scanf("%d",&m); for(re i=1;i<=m;i++){ int l,r,k; scanf("%d%d%d",&l,&r,&k); int lca=LCA(l,r); int ans=(1ll*sum[l][k]+sum[r][k]+2ll*mod-sum[lca][k]-sum[fa[lca]][k])%mod; //if(l>300000||r>300000||k>50)cout<<"sb"<<endl; printf("%d\n",ans); } //cout<<time(NULL)-o<<endl; }
T4
完结
