题意:
给一个如图所示的三角形,输入n,击倒方块n,获得分数n*n,同时方块n上面的两个方块也会落下,同时获得这两个方块的分数,一直向上走,知道方块1,如图所示为n=9的时候掉落的方块,求获得的分数。
思路:
先初始化每一层的第一个数,方便找到n所在的层数,这里用二分找。然后维护每一层的区间l,r。不难发现区间向上走的规律:
l = l - fl, r = r - fl + 1, fl为当前层,当然,要考虑边界情况,l = max(s[fl - 1], l - fl), r = min(s[fl] - 1, r - fl + 1). 至于求区间分数和,可以用前缀和的方法求,具体看代码。
代码:
/*************************************************************************
> File Name: g.cpp
> Author: Beans
> Mail: 3112748286@qq.com
> Created Time: 2023/5/24 13:03:43
************************************************************************/
#include <iostream>
#include <algorithm>
#define int long long
#define endl '\n'
using namespace std;
const int maxn = 1e6 + 7;
int n, s[maxn], sum[maxn];
int cnt;
void init(){
s[1] = 1;
cnt = 1;
for(cnt = 2; s[cnt - 1] <= maxn; cnt ++ )
s[cnt] = s[cnt - 1] + (cnt - 1);
cnt -- ;
for(int i = 1; i <= maxn - 1; i ++ )
sum[i] = sum[i - 1] + i * i;
}
void solve(){
cin >> n;
int fl = lower_bound(s + 1, s + cnt + 1, n + 1) - s;
fl -- ;
int l = n;
int r = n;
int ans = 1;
while(fl >= 2){
ans += sum[r] - sum[l - 1];
l = max(s[fl - 1], l - fl);
r = min(s[fl] - 1, r - fl + 1);
fl -- ;
}
cout << ans << endl;
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
init();
while(t -- )
solve();
}