【Codeforces Round #639 (Div. 2) B】Card Constructions

题目链接

点我呀

翻译

给你 \(n\) 张卡, 问你最多能叠成多少个金字塔卡组。

题解

找找规律会发现。

高度为 \(h\) 的三角形, 一共有 \(0+1+2+...+h-1\) 个横着放的卡。

然后一共有 \(2 \times (1+2+3+...+h)\) 个竖着放的卡。

所以高度为 \(h\) 的三角形一共有 $ \frac{ (0 + h-1) \times h}{2} + 2 \times \frac{ (1+h)\times h}{2}$ 张卡片

能在 \(\mathcal{O}(\sqrt{n})\) 的时间复杂度下算出来 \(1\) ~ \(maxh\) 高度的三角形需要多少张卡片, 其中 \(maxh\) 是

\(10^9\) 规模的 \(n\) 能够堆成的最高高度的三角形。

预处理出来之后, 每个询问从大到小把所有高度的三角形试一下能不能用 \(n\) 张卡片堆出来, 能堆出来就

减去就行 (别真一个一个减啊, 直接用除法和取模表示扣掉卡片)

代码

#include<bits/stdc++.h>
#define ll long long
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%I64d",&x)
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
using namespace std;

const int N = 26e3;
const int MOD = 998244353;

int n,m;
int a[N+10];

int main(){
    #ifdef LOCAL_DEFINE
        freopen("D:\\rush.txt","r",stdin);
    #endif
    ios::sync_with_stdio(0),cin.tie(0);
    //an = 2*n + 3*n*(n-1)/2
    rep1(i, 1, N){
        a[i] = 2 * i + 3 * i * (i - 1) / 2;
    }
    int T;
    for (cin >> T;T > 0;T--){
        cin >> n;
        int cnt = 0;
        rep2(i, N, 1){
            cnt += n / a[i];
            n = n % a[i];
        }
        cout << cnt << endl;
    }
    return 0;
}

【Codeforces Round #639 (Div. 2) B】Card Constructions

原文：https://www.cnblogs.com/AWCXV/p/13173311.html