阿里巴巴网站导航怎么做,旅游网站建设规划,wordpress用户登录显示请求失败,高明网站建设1.P4017 最大食物链计数
确实比较板子#xff0c;但是考验思维#xff0c;我愿称之为思维拓扑排序
作为拓扑的第一题#xff0c;确实没想到要进行思维处理
这里考虑用一种dp的思维方式#xff08;#xff1f;
多引入两个变量#xff0c;一个记录出度但是考验思维我愿称之为思维拓扑排序
作为拓扑的第一题确实没想到要进行思维处理
这里考虑用一种dp的思维方式
多引入两个变量一个记录出度一个记录每一个点的种类数量这样就可以一直满足不同方向过来所产生的种类数量
出度的缘由是这里需要绝对的两端我开始以为是大于二的食物链都行那样的话就每一次操作都1就好
贴代码不要忘记取模不然只有两个点捏
// Problem:
// P4017 最大食物链计数
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4017
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#includeiostream
#includequeue
#includevector
using namespace std;
const int N5010;
vectorint e[N];
int ans;
int din[N];//入度
int oin[N];//出度
int n,m;
int f[N];//每个点的数量void toposort(){queueint q;for(int i1;in;i){if(din[i]0) q.push(i),f[i]1;} while(q.size()){auto kq.front();q.pop();for(auto t:e[k]){if(--din[t]0) q.push(t);f[t](f[k]f[t])%80112002;}}for(int i1;in;i){if(oin[i]0) ans(f[i]ans)%80112002;}
}int main(){cinnm;while(m--){int a,b;cinab;e[a].push_back(b);din[b];oin[a];} toposort();coutans%80112002endl;return 0;
}
2.P2712 摄像头
这道题比较板子在操作的时候如果pop就ans--即可有几个坑点
输出yes 摄像头的范围 摄像头所能照到的位置不一定会存在摄像头怎么会有题卡这种鬼地方
// Problem:
// P2712 摄像头
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2712
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#includeiostream
#includequeue
#includevector
using namespace std;
const int N505;
vectorint e[N];
int ans0;
int din[N];
bool check[N];
vectorint kkk(N);void toposort(){queueint q;for(int i1;ians;i){if(din[kkk[i]]0) q.push(kkk[i]);}while(q.size()){auto tq.front();q.pop();//couttendl;//coutansendl;//coutendl;if(check[t]) ans--;for(auto x:e[t]){if(--din[x]0) q.push(x);}}
}int main(){int n;cinn;ansn;int cnt0;while(n--){int a,b;cinab;if(!check[a]) kkk[cnt]a,check[a]true;while(b--){int k;cink;e[a].push_back(k);din[k];}}toposort();if(ans0) coutYESendl;else coutansendl;return 0;
}
3.P1137 旅行计划
这道题比上一道题要简单不少与第一题思路相同但这一题的想法就是维护一个max就好了我其实没有太看懂提但是这么操作不管有几个起始点都可以获得最大的值看来自各个方向哪个大就选哪个方向
// Problem:
// P1137 旅行计划
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1137
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#includeiostream
#includequeue
#includevector
using namespace std;
const int N1e510;
vectorint e[N];
int din[N];
int f[N];
int n,m;void toposort(){queueint q;for(int i1;in;i){if(din[i]0) q.push(i);f[i]1;}while(q.size()){auto tq.front();q.pop();for(auto x:e[t]){if(--din[x]0) q.push(x);f[x]max(f[t]1,f[x]);}}
}
int main(){cinnm;while(m--){int a,b;cinab;e[a].push_back(b);din[b];}toposort();for(int i1;in;i) coutf[i]endl;return 0;
}
4.P1960 郁闷的记者
这道题难过的令人无语调试了一整天才发现是读错题了。这题面真的阴间.......
我的想法是开两个堆分别维护最大字典序和最小字典序如果答案不同说明有不同情况极端情况
贴代码
// Problem:
// P1960 郁闷的记者
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1960
// Memory Limit: 500 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#includeiostream
#includevector
#includequeue
using namespace std;
const int N1e410;
int cnt1[N];//记录名次
int cnt2[N];
int n,m;
vectorint e[N];
int din1[N];
int din2[N];void toposort(){priority_queueint a;priority_queueint,vectorint,greaterint b;for(int i1;in;i){//coutdin1[i]endl;if(din1[i]0){a.push(i);b.push(i);//coutiendl;}}int now0;while(a.size()){auto ta.top();a.pop();cnt1[t]now;//couttendl;//couttendl;for(auto x:e[t]){if(--din1[x]0) a.push(x);}}now0;while(b.size()){auto tb.top();b.pop();cnt2[t]now;couttendl;for(auto x:e[t]){if(--din2[x]0) b.push(x);}}
}int main(){cinnm;while(m--){int a,b;cinab;e[a].push_back(b);din1[b];din2[b];}toposort();//for(int i1;in;i) coutcnt2[i]endl;for(int i1;in;i){if(cnt1[i]!cnt2[i]){cout1endl;return 0;}}cout0endl;return 0;
}
5.P6145 [USACO20FEB] Timeline G
一遍就AC想的时间也是最短的。
但是这道题确实比较难想要是没跟我说这是拓扑排序我不一定能想到。这道题比较隐晦我的思路是一个类似dp的操作每一次都更新最大也就是每一次都要更新到最大。
这里使用拓扑排序的原因我总结为每一个的结局时间都是不确定的要先确定前面的才能确定后面的这个过程就是一个拓扑序。
在这个拓扑序遍历的时候对每一次进行更新对某个点有影响的所有点已经没有入度了继续更新语言无力请看代码。我没看懂题解区说的递推是啥
// Problem:
// P6145 [USACO20FEB] Timeline G
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6145
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#includeiostream
#includevector
#includequeue
using namespace std;
int n,m,s;
const int N1e510;
int f[N];
vectorpairint,int e[N];
int din[N];void toposort(){queueint q;for(int i1;in;i){if(din[i]0) q.push(i);}while(q.size()){auto tq.front();q.pop();for(auto x:e[t]){int ax.first,bx.second;f[a]max(f[a],f[t]b);//每次都更新一下if(--din[a]0) q.push(a);}}
}int main(){cinnms;for(int i1;in;i) cinf[i];while(s--){int a,b,c;cinabc;e[a].push_back({b,c});din[b];}toposort();for(int i1;in;i) coutf[i]endl;return 0;
}
6.P1807 最长路
这道题有点坑有不少遭点一开始我以为可以直接copy上一题代码还是太想去睡觉了结果发现必须是从1到n的路径。
这里有几个坑点
1.从1到n 且题目已经告诉你路径一定是从小节点到大节点的枉我想了这么久的环
2.这里的权值可以是负数所以应该把2-n的所有编程-1e9
3.由于指定了起始位置还会存留一下入度为0的值对后面的数字造成不良影响对此我们可以把这些先一步捞出来处理一下就好见代码
好像是dp的方法吧话说感觉越来越板了拓扑都是这样的题目每道题都要结合一点dp思想来着
上代码
#includeiostream
#includevector
#includequeue
using namespace std;
int n,m,s;
const int N2000;
const int M5e410;//数据不要开错了
int f[N];
vectorpairint,int e[M];
int din[N];
bool check;void toposort(){queueint q;for(int i2;in;i){if(din[i]0) q.push(i);f[i]-1e9;}while(q.size()){//多一个处理减少这些不会入队的值对入队的影响auto tq.front();q.pop();for(auto x:e[t]){int ax.first;if(--din[a]0) q.push(a);}}q.push(1);while(q.size()){auto tq.front();q.pop();if(tn) checktrue;for(auto x:e[t]){int ax.first,bx.second;f[a]max(f[a],f[t]b);if(--din[a]0) q.push(a);}}
}int main(){cinnm;while(m--){int a,b,c;cinabc;e[a].push_back({b,c});din[b];}toposort();if(check) coutf[n]endl;else cout-1endl;return 0;
} 7.P1113 杂务
这道题小细节比较多我调试了一个钟但是思路与前面又很大的相似之处其实好像又是dp思想难度不大直接贴代码
// Problem:
// P1113 杂务
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1113
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#includeiostream
#includevector
#includequeue
using namespace std;
int n;
const int N1e410;
int din[N];
int f[N];
int now[N];
vectorint e[N];
int ans0;void toposort(){queueint q;for(int i1;in;i){if(din[i]0) q.push(i);}while(q.size()){auto tq.front();q.pop();ansmax(ans,now[t]);for(auto x:e[t]){now[x]max(now[x],now[t]f[x]);//coutnow[x]endl;//cout1endl;if(--din[x]0) q.push(x);}}
}int main(){cinn;for(int i1;in;i){cini;int k;cinf[i];now[i]f[i];while(cink){if(k0) break;else{e[k].push_back(i);din[i];//couti din[i]endl;}}}//for(int i1;in;i) coutdin[i]endl;toposort();coutansendl;return 0;
}
