POJ:2100-Graveyard Design(尺取)
Graveyard Design
Time Limit: 10000MS Memory Limit: 64000K
Total Submissions: 8504 Accepted: 2126
Case Time Limit: 2000MS
Description
King George has recently decided that he would like to have a new design for the royal graveyard. The graveyard must consist of several sections, each of which must be a square of graves. All sections must have different number of graves.
After a consultation with his astrologer, King George decided that the lengths of section sides must be a sequence of successive positive integer numbers. A section with side length s contains s2 graves. George has estimated the total number of graves that will be located on the graveyard and now wants to know all possible graveyard designs satisfying the condition. You were asked to find them.
Input
Input file contains n — the number of graves to be located in the graveyard (1 <= n <= 1014 ).
Output
On the first line of the output file print k — the number of possible graveyard designs. Next k lines must contain the descriptions of the graveyards. Each line must start with l — the number of sections in the corresponding graveyard, followed by l integers — the lengths of section sides (successive positive integer numbers). Output line’s in descending order of l.
Sample Input
2030
Sample Output
2
4 21 22 23 24
3 25 26 27
解题心得:
- 给你一个数,问你他可以由多少个连续数的平方和得到,输出第一行为方案数,然后每一行第一个数是由多少个连续数的平方和得到,然后是连续数。
- 直接跑尺取,满足尺取的两个特点。
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <vector>
using namespace std;
typedef long long ll;
vector < pair<ll,ll> > ve;
void solve(ll n) {
ll l = 1,r = 1,sum = 0;
while(1) {
while(sum < n && r <= 1e7) {
sum += r*r;
r++;
}
if(sum < n)
break;
if(sum == n)
ve.push_back(make_pair(l,r-1));
sum -= l*l;
l++;
if(l*l > n)
break;
}
printf("%lld\n",ve.size());
for(ll i=0;i<ve.size();i++) {
printf("%d ",ve[i].second-ve[i].first+1);
for(ll j=ve[i].first;j<=ve[i].second;j++) {
if(j == ve[i].first)
printf("%lld",j);
else
printf(" %lld",j);
}
printf("\n");
}
}
int main() {
ll n;
scanf("%lld",&n);
solve(n);
return 0;
}
最新文章
- 10款.net 图形插件
- delphi 取cpu号
- IOS培训还值得么
- Programming Entity Framework 翻译(1)-目录
- orm获取关联表里的属性值
- AppScan 测试需要输入用户名密码的网站
- npm穿墙
- 探索 OpenStack 之(17):计量模块 Ceilometer 中的数据收集机制
- pyenv ipython jupyter
- redis学习笔记——(3)
- Nginx的一些基本功能极速入门
- win32开发基础
- 为什么selenium定位不到元素
- 静态变量和Session
- 调用MediaScannerConnection 发生内存泄露的解决方法
- centos7 rabbitmq集群搭建+高可用
- [Database]各数据库连接配置:Oracle:thin 数据库连接/MySQL 连接配置
- Apater适配器模式(结构型模式)
- 20145331魏澍琛《网络对抗》Exp6 信息搜集与漏洞扫描
- git创建仓库,并提交代码(第一次创建并提交)(转)