首页 > 其他分享 >Codeforces Round #751 (Div. 2) D

Codeforces Round #751 (Div. 2) D

时间:2022-11-05 13:11:07浏览次数:54  
标签:pre 10 751 int Codeforces while push Div dp

D. Frog Traveler

考虑dp
dp[i]表示i高度的时候最少多少步能达到
然后再bfs就可以了 但是这样是n2的 虽然看起来只有n个点
我们考虑优化
我们主要复杂度是当前点 还会去搜索其他已经入队的点
这样怎么办呢 我们可以维护一个set 要是已经入队的点 我们就不用去搜索了
我们直接二分出一个没搜索过的 并且合法的 然后给她erase掉就表示他搜过了

int x = *s.lower_bound(u - a[u]);
            if (u < x)break;
            s.erase(x);

然后就是更新

int v=x+b[x];
            if(dp[v]>dp[u]+1){
                dp[v]=dp[u]+1;
                pre[v]={u,x};
                q.push(v);
            }

最后是输出路径 我们记录一个pre数组就是了 但是这里记录的不是出发点 而是到达点 所以我们要多记录一个

int x=0;
        vector<int>ans;
        while(x!=n){
            ans.push_back(pre[x].second);
            x=pre[x].first;
        }
        cout<<ans.size()<<endl;
        reverse(all(ans));
        for(auto i:ans)cout<<i<<' ';cout<<endl;

完整代码

void solve() {
    int n;cin>>n;
    vector<int>a(n+10),b(n+10),dp(n+10);
    vector<pair<int,int>>pre(n+10);
    set<int>s;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=0;i<=n+1;i++)dp[i]=INF,s.insert(i);
    queue<int>q;
    q.push(n);
    dp[n]=0;
    while(q.size()){
        auto u=q.front();q.pop();
        while(1) {
            int x = *s.lower_bound(u - a[u]);
            if (u < x)break;
            s.erase(x);
            int v=x+b[x];
            if(dp[v]>dp[u]+1){
                dp[v]=dp[u]+1;
                pre[v]={u,x};
                q.push(v);
            }
        }
    }
    if(dp[0]==INF)cout<<-1<<endl;
    else {
        int x=0;
        vector<int>ans;
        while(x!=n){
            ans.push_back(pre[x].second);
            x=pre[x].first;
        }
        cout<<ans.size()<<endl;
        reverse(all(ans));
        for(auto i:ans)cout<<i<<' ';cout<<endl;
    }
}

标签:pre,10,751,int,Codeforces,while,push,Div,dp
From: https://www.cnblogs.com/ycllz/p/16860011.html

相关文章

  • 用DIV+CSS技术设计的音乐主题网站(web前端网页制作课作业)
    ......
  • Codeforces Round #832 (Div. 2) A-D
    比赛链接A题解知识点:贪心。我们考虑把正数和负数分开放,显然把负数和正数放在一起的结果不会更优。时间复杂度\(O(n)\)空间复杂度\(O(1)\)代码#include<bits/std......
  • Codeforces Round #832 (Div. 2)
    A.TwoGroups数组和的绝对值即为答案。B.BANBAN大概就是尽可能把前面的B搞到后面,尽可能把后面的N搞到前面。答案为\(\lceil\frac{n}{2}\rceil\),操作为每次......
  • Codeforces Round #764 (Div. 3) G
    G.MinOrTree看到或运算我们思考如何按位来做我们可以贪心的从高位到低位的要是该位可以都用0的来构成一颗生成树我们显然是很高兴的但是怎么check?我们每次遍历一......
  • CodeForces - 914C Travelling Salesman and Special Numbers
    题意:给出一个二进制数a,每次操作将当前数变成其二进制下1的个数,若干次操作后可以将其变为1.给定k,求不大于a的数中,经过k次操作能变成1的数的数量。解:观察一下这个操作,可以求......
  • Codeforces Round #776 (Div. 3) E
    E.ReschedulingtheExam显然我们能想到的每次操作都是先将最小的取出来操作要是我们有两个数都是最小的我们只有相邻的时候才能操作要是大于两个那我们就不管怎么操......
  • Codeforces Round #778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round) F M
    A-E都还是比较简单的。首先,容易想到的,异或上\(2^k\),相当于以\(2^{k+1}\)的长度分块,然后每一块对半切,然后交换左右部分。我的想法是由于这个交换的性质,也许我们可以尝......
  • Codeforces Round #766 (Div. 2)
    CodeforcesRound#766(Div.2)\(\color{Green}{★}\)表示赛时做出。\(\color{Yellow}{★}\)表示赛后已补。\(\color{Red}{★}\)表示\(\text{To\be\solved}\)......
  • Codeforces Round #820 (Div. 3) F
    F.KireiandtheLinearFunction首先我们知道的是给定长度w都是%9意义下的所以我们枚举四个位置的数就是9^4预处理出来答案这里我们要去w长度的串%9但是w的位数过......
  • Codeforces Global Round 20 D F1 F2/more
    https://codeforc.es/contest/1672F1https://www.luogu.com.cn/blog/AlexWei/solution-cf1672f1将置换分解为若干轮换(环),悲伤值越大\(\Rightarrow\)环越少(设环为\(k......