热身赛总结 题解

1. 旅行计划

赛时思路

因为目标是：求出一直向东以城市 \(i\) 为终点最多能够游览多少个城市，我进行逆向思维，转换题意，将目标改成：以城市 \(i\) 为起点一直向西最多能够游览多少个城市，再看题目的数据范围：$n \le 10^5 $，因此便直接用 dfs 进行搜索，最后 TLE 了4个点 QwQ 。
改进思路

因为题目中说图中没有环，因此我们可以通过 DP 解决此题，所以我们就可以通过记忆化递归防止进行无效的 dfs 。
AC代码

点开有惊喜[code]#include#define ll long longusing namespace std;ll n,m,x,y,dp[100005];vectort[100005];ll dfs(ll x,ll val){        if(!t[x].size()) return val;        ll mx=0;        for(auto y:t[x]){                if(!dp[y]) dp[y]=dfs(y,val);                mx=max(mx,dp[y]);        }        return mx+1;}int main(){        cin>>n>>m;        for(int i=1;i>x>>y;                t[y].push_back(x);        }        for(int i=1;i>x;                        zh[++cnt]=x;                        cxa(1,1,n,x,1);                }                else if(ch=='Q'){                        cin>>x;                        if(!check(1,1,n,x)){                                coutm;        for(int i=1;i>a;                l=max(l,a);                r+=a;        }        while(l

鼓励转贴优秀软件安全工具和文档！