网站开发的自适应,房地产信息查询平台,网站上的ar是什么软件做的,制作网站培训学校目录
题目#xff1a;最大食物链
解法一#xff1a; 解法二#xff1a; 记忆化
题目#xff1a;游走
思路#xff1a; 题目#xff1a;最大食物链 解法一#xff1a; 我们标记f[i]是被f[x]捕食的点对应的类食物链数 不难得出#xff1a; f[x]∑(f[i]) 首先从生…目录
题目最大食物链
解法一 解法二 记忆化
题目游走
思路 题目最大食物链 解法一 我们标记f[i]是被f[x]捕食的点对应的类食物链数 不难得出 f[x]∑(f[i]) 首先从生产者开始每去掉一个被捕食的点那么相邻捕食者就要加上去掉点的类食物链数但是我们还需要找到出度为0的消费者。 所以这道题我们要同时记录入度还有出度其实单纯的topo排序就用不上出度记录出度是为了找食物链结尾的个数 #includebits/stdc.h
using namespace std;
const int MOD80112002,M500005,N5005;
vector intv[N];
queueint q;
int n,m,ans,f[N],in[N],out[N];//我们需要标记每个点的入度和出度f为以该点结尾的类食物链数
int main(){cinnm;int x,y;for(int i1;im;i){cinxy;v[x].push_back(y);//y吃xx指向yout[x];in[y];}for(int i1;in;i){//找到所有没有入度的点为起点if(in[i]0){q.push(i);f[i]1;}}while(q.size()){//进行拓扑排序int curq.front();q.pop();for(int i0,szv[cur].size();isz;i){int tv[cur][i];f[t](f[t]f[cur])%MOD;in[t]--;//去掉cur点的话就要把f[cur]加到捕食它的点上if(in[t]0) q.push(t);} }for(int i1;in;i){if(out[i]0)ans(ansf[i])%MOD;//出度为0的点的f是我们要的真正食物链数}coutans;return 0;
}解法二 记忆化 #include bits/stdc.h //记忆化搜索
using namespace std;
const int N1e55;
int n,m,ans,tot,in[N],out[N],f[N];
vectorintve[N];
int dfs(int x){//就是从每个生产者开始看看能到多少个最终消费者然后记忆化最终计算所有生产者就是答案if(f[x])return f[x];if(!out[x])return 1;for(int i0,szve[x].size();isz;i){int vve[x][i];f[x]dfs(v);}return f[x];
}
int main(){cinnm;int u,v,w;while(m--){cinuv;ve[u].push_back(v);out[u];in[v];}for(int i1;in;i){if(in[i]0out[i])ansdfs(i);}coutans;
} 题目游走 思路 给一个DAG(有向无环图)求所走路径长度的期望呗也就是所有路径长度总和/所有路径个数因为每条路径概率都一样嘛 明明是DAG图topo一下完事了 我们设置g[i]表示以i为终点的路径数f[i]表示i为终点的长度和 topo从点j到一个点i则g[i]g[j],f[i]f[j]g[i]因为啊从j到i的每个路径长度都只增加1就行一共增加了g[i] 最后就是求(L/S)MOD也就是L*(S^(MOD-2))MOD即可逆元小知识 #include bits/stdc.h
using namespace std;
typedef long long ll;
const int MAXN1e55;
const ll MOD998244353;
int n,m;
ll L,S,f[MAXN],g[MAXN];//g[i]表示以i为终点的路径数f[i]表示i为终点的长度和
vectorint edge[MAXN];
int in[MAXN],vis[MAXN];
void topo(void)//模板
{queueint q;for(int i1;in;i)if(!in[i]) q.push(i);while(!q.empty()){const int uq.front();q.pop();if(vis[u]) continue; vis[u]true;//没有环所以这句话可以不要for(auto v:edge[u]){in[v]--;if(!in[v]) q.push(v);f[v](f[v]f[u]g[u])%MOD;g[v](g[v]g[u])%MOD;}}
}ll qpow(ll base,ll k)//快速幂求逆元
{ll res1;while(k){if(k1) resres*base%MOD;basebase*base%MOD;k1;}return res;
}int main()
{cinnm;for(int i1;im;i){int u,v;cinuv;edge[u].push_back(v);in[v];}for(int i1;in;i) g[i]1;//初始化:每个点的路径数初始化为1topo();for(int i1;in;i) L(Lf[i])%MOD;//获取最终的总长度for(int i1;in;i) S(Sg[i])%MOD;//获取最终的路径个数cout(L*qpow(S,MOD-2))%MODendl;//求L/S的结果即L*S的逆元即L*S^(MOD-2)return 0;
}提一嘴 为什么要引入逆元呢 因为(ab)%MOD(a%MODb%MOD)%MOD (a-b)%MOD(a%MOD-b%MOD)%MOD (a*b)%MOD(a%MOD*b%MOD)%MOD 但是除法不满足我们要求(a/b)%p1等价于(a*x)%p1这个x就是b的乘法逆元可以理解成x为1/b也就是(b*x)%p1 再引入费马小定理假如a和p互质那么a^(p-1)1(%p)故a*a^(p-2)1(%p)故a的逆元xa^(p-2)%p 因此(x/y)%p等价于x*y^(p-2)%p注意每乘一次就要去一次模
