简单之至的题解

\(Luogu\)

比楼上的简单，代码只有二十行

首先看题的时候发现这个无法做到直接求

因为数据范围好像有点超乎想象

但是对于这种递推的题来说一般就是从小的往大的推

那么我们递推的过程就是每一次挽回

我们发现我们挽回一次之后问题就变成了一个子问题

但是这个子问题的挽回顺序变了，我们只需要在递推的时候反过来就好了

这个题又非常的善良给了我们当前这一行的最大值

明显的暗示递推好吧~~~

我们直接枚举当前的枫叶数量

计算挽回一次之后还剩下多少

用剩下的枫叶数目对应的答案，先翻转一下，在计算这个答案的位置之前拿走了多少叶子

直接加上就是答案

最后直接输出就好了

code

#include<bits/stdc++.h>

using namespace std;

#define fxt(i,x,y) for(int i=(x);i<=(y);i++)

#define pyt(i,x,y) for(int i=(x);i>=(y);i--)

const int N=1e6+5;

int t,q,m,n,ans[N];

signed main(){

    scanf("%d",&t);

    fxt(k,1,t){

        scanf("%d%d",&q,&m);

        ans[1]=1;

        fxt(i,2,m){

            int las=i-(i-1)/(k+1)-1;

            int pos=las-ans[las]+1;

            ans[i]=pos+(pos-1)/k+1;

        }

        while(q--){

            scanf("%d",&n);

            printf("%d ",ans[n]);

        }

        printf("\n");

    }

}

巴特西

[Stoi 2031]枫

简单之至的题解

最新文章

热门文章