【Codeforces Round #639 (Div. 2) B】Card Constructions
Codeforces div round Card
2023-09-14 09:03:41 时间
题目链接
翻译
给你 \(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 #326 (Div. 2) B. Pasha and Phone C. Duff and Weight Lifting
- 【Codeforces Round #695 (Div. 2) B】Hills And Valleys
- 【Codeforces Round #695 (Div. 2) A】Wizard of Orz
- 1800*1【Codeforces Round #665 (Div. 2) D】Maximum Distributed Tree
- 【Codeforces Round #223 (Div. 1) C】Sereja and Brackets
- 【Codeforces Round #668 (Div. 2) C】Balanced Bitstring
- 【ICM Technex 2018 and Codeforces Round #463 (Div. 1 + Div. 2, combined) B】Recursive Queries
- 【ICM Technex 2018 and Codeforces Round #463 (Div. 1 + Div. 2, combined) A】 Palindromic Supersequence
- 【Codeforces Round #239 (Div. 1) A】Triangle
- 【Codeforces Round #460 (Div. 2) A】 Supermarket
- 【Codeforces Round #445 (Div. 2) C】 Petya and Catacombs
- 【Codeforces Round #442 (Div. 2) D】Olya and Energy Drinks
- 【Codeforces Round #435 (Div. 2) B】Mahmoud and Ehab and the bipartiteness
- 【Codeforces Round #435 (Div. 2) C】Mahmoud and Ehab and the xor
- 【Codeforces Round #424 (Div. 2) B】Keyboard Layouts
- 【Codeforces Round #423 (Div. 2) B】Black Square
- 【Codeforces Round #420 (Div. 2) B】Okabe and Banana Trees
- C. Arthur and Table(Codeforces Round #311 (Div. 2) 贪心)
- Codeforces Beta Round #25 (Div. 2)--A. IQ test
- Codeforces Round #311 (Div. 2) E - Ann and Half-Palindrome(字典树+dp)
- Codeforces Round #256 (Div. 2/C)/Codeforces448C_Painting Fence(分治)
- Codeforces Round #107 (Div. 2)---A. Soft Drinking
- Tinkoff Internship Warmup Round 2018 and Codeforces Round #475 (Div. 2)
- Codeforces Round #470 (rated, Div. 2, based on VK Cup 2018 Round 1)
- Codeforces Round #443 (Div. 2)
- Codeforces Round #412 Div. 2 补题 D. Dynamic Problem Scoring
- Codeforces Round #412 Div. 2 第一场翻水水