1626C - Monsters And Spells ，D - Carry Bit 组合数学

1626C - Monsters And Spells 

一开始想的是倒着去遍历，如果h[i]<=k[i]-k[i-1]就说明可以从1开始加，否则就不能断开，但是这样忽略了下面的情况，即h[i-1]也不是最大值，需要从k[i-2]的地方连续加，所以就蔫了

3
1 2 3
1 1 3

看题解发现雀氏是要从后面开始看的，并且后面的大小是可以决定前面的数的，设一个f数组表示第i位需要多大才可以满足条件，即f[i]=max(h[i],f[i]-(k[i]-k[i-1]);

然后接着分析就可以了，还是一样，如果f[i]<=k[i]-k[i-1]就可以从1开始加，否则就不能重新开始，这两种情况对应着两种等差数列求和，分别做一下就可以

CF1626C Solution - Alejandro 的小屋 - 洛谷博客

#include
//#pragma-GCC-optimize("-Ofast");
#define int long long
#define ll __int128
#define lowbit(x) ((x)&(-x))
#define endl '\n'
#define pause system("pause")
using namespace std;
const int N=1e6+5;
const int mod=1e9+7;
const int inf=1e18;
int qpow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int getinv(int a){return qpow(a,mod-2);}
int t,n,k[N],h[N],f[N];
signed main()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n;k[n+1]=f[n+1]=0;
        for(int i=1;i<=n;i++) cin>>k[i];
        for(int i=1;i<=n;i++) cin>>h[i];
        f[n]=h[n];
        for(int i=n-1;i>=1;i--)
        {
            f[i]=max(h[i],f[i+1]-(k[i+1]-k[i]));
           // cout<
        }
        int ans=(1+f[1])*f[1]/2,las=f[1];
        for(int i=2;i<=n;i++)
        {
            if(f[i]<=k[i]-k[i-1]) ans+=(1+f[i])*f[i]/2,las=f[i];
            else
            {
                ans+=(las+1+las+k[i]-k[i-1])*(k[i]-k[i-1])/2;las=las+k[i]-k[i-1];
            }
        }
        cout<
    }
    return 0;
}