题目链接: Problem - 1419B - Codeforces
题目
题意
给x个格子,你可以用这x个格子去拼成楼梯
好的楼梯的要求如下:
1. 第n列有n个格子
2. 这个楼梯的所有格子可以被划分为几个正方形,正方形的个数必须=n,一个正方形可以由至少一个格子组成
输出可以用x个格子去拼成几个不一样的好的楼梯
解析
看看例子,会发现只有当n=1,3,7......时,才可以是好的楼梯
解释:前面排好的不动,后面加一个大正方形,上面放的和前面排好的一样
里面阴影部分就是前面的复制到新正方体上面了
找到了n,用等差数列求格子数(n+1)*n/2
最后输出结果为能造出几个不同的楼梯
把x一遍遍减去就行
AC代码
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; int main() { int t; cin >> t; while(t --) { ll x; ll a = 1, cnt = 0; cin >> x; while(1) { ll tmp = (a+1)/2*a; x -= tmp; if(x < 0) break; cnt ++; a = a * 2 + 1; } cout << cnt << endl; } return 0; }
卡住的英语点
1.
翻译:
一个有n个台阶的楼梯叫做nice,如果楼梯可能被n个不相交的正方形所覆盖。所有的正方形都应该完全由楼梯单元组成。
(前面说这是个nice楼梯,后面是条件)disjoint打散的,不相交的
2.
大意:
找到不同的好的楼梯的最大个数,用不超过x个格子