Tsinsen A1504. Book(王迪) 数论,贪心
2024-08-25 19:13:02
A1504. Book(王迪)
试题来源
2013中国国家集训队第二次作业
问题描述
Wayne喜欢看书,更喜欢买书。
某天Wayne在当当网上买书,买了很多很多书。Wayne有一个奇怪的癖好,就是第一本书的价格必须恰为X,而之后买的每一本书,若是比上一本更昂贵,则价格最多多A元;若是比上一本更便宜,则价格最多少B元。
Wayne心血来潮,一口气买了N本书,但他记不得每本书的价格了,只记得总价格是M。Wayne于是很想知道一种可能的书价分布。为了简化问题,我们假定书价的定义域是整数,且每本书与上一本书的价格差,要么恰为+A,要么恰为-B。
只要给出任意一个合法的书价序列就算正确。
某天Wayne在当当网上买书,买了很多很多书。Wayne有一个奇怪的癖好,就是第一本书的价格必须恰为X,而之后买的每一本书,若是比上一本更昂贵,则价格最多多A元;若是比上一本更便宜,则价格最多少B元。
Wayne心血来潮,一口气买了N本书,但他记不得每本书的价格了,只记得总价格是M。Wayne于是很想知道一种可能的书价分布。为了简化问题,我们假定书价的定义域是整数,且每本书与上一本书的价格差,要么恰为+A,要么恰为-B。
只要给出任意一个合法的书价序列就算正确。
输入格式
第一行一个正整数N。
第二行四个整数依次是X,A,B,M。
第二行四个整数依次是X,A,B,M。
输出格式
输出一行N个整数,用空格隔开。数据保证有解。
样例输入
4
10 1 2 37
10 1 2 37
样例输出
10 11 9 7
数据规模和约定
对于5%的数据,满足N = 1。
对于另外25%的数据,满足A = B = 1, N <= 100。
对于另外10%的数据,满足A, B <= 5, N <= 100。
对于另外20%的数据,满足N <= 1000。
对于100%的数据,满足1 <= A, B <= 10^6,|X| <= 10^6,N <= 10^5,M可用带符号64位整型存储。
对于另外25%的数据,满足A = B = 1, N <= 100。
对于另外10%的数据,满足A, B <= 5, N <= 100。
对于另外20%的数据,满足N <= 1000。
对于100%的数据,满足1 <= A, B <= 10^6,|X| <= 10^6,N <= 10^5,M可用带符号64位整型存储。
题解:
数论+贪心
以下是王迪的解题报告:
#include<bits/stdc++.h>
using namespace std;
#define LL long long
//LL prey[100010];
bool vis[];
LL read()
{
LL s=,fh=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
return s*fh;
}
int main()
{
LL n,x,a,b,m,k,i,j,lp;
n=read();
x=read();a=read();b=read();m=read();
k=n*x+((n-)*n)/*a;//假设全部增加a的总钱数.
k-=m;//用 全部增加a的总钱数 减去 实际花费的钱数 得到有多少钱从 +a 转化为 -b ,也就是减去(a+b).
k/=(a+b);//计算出有多少书进行了从 +a 转化为 -b.
//因为改变每一个差量,所影响的数的个数为(0,1,2...n-1)中的一个.所以,我们只需要求出k可以由 0~(n-1) 中的哪一些组成.
memset(vis,false,sizeof(vis));
for(i=n-;i>=;i--)//倒着去找,一定保证k可以组成.(有点类似倍增LCA的倒着找的原理)
{
if(k>=i)
{
k-=i;
vis[i]=true;//标记为true的代表要转换为-b.
if(k==)break;
}
}
/*双重循环(60分)
for(i=1;i<=n;i++){prey[i]=x;x+=a;}
for(i=1;i<=n-1;i++)
{
if(vis[i]==true)
{
for(j=n;j>=n-i+1;j--)prey[j]-=(a+b);
}
}
for(i=1;i<=n;i++)printf("%lld ",prey[i]);*/
printf("%lld",x);
for(i=n-;i>=;i--)
{
if(vis[i]==true)//若要转化为-b,就要在原先的x的基础上加上-b(即减去b).
{
x-=b;
}
else
{
x+=a;
}
printf(" %lld",x);
}
fclose(stdin);
fclose(stdout);
return ;
}
最新文章
- Mosquitto搭建Android推送服务(二)Mosquitto简介及搭建
- Win7 64位 VS2015环境使用qt-msvc2015-5.6.0
- C# 结构转化
- jQuery实现无缝滚动条
- 深入剖析 redis 事件驱动
- grep 查找当前文件夹下所有文件内内容 并显示文件名
- nutch2.3中nutch-site.xml设置说明
- Oracle EBS-SQL (SYS-21):sys_用户名与人员对应关系查询.sql
- Java 之 web.xml(Java之负基础实战)
- VB6之阴影图层
- Leetcode题解(六)
- Node.js的内存问题
- java中date日期格式的各种转换
- 洛谷P2480 [SDOI2010]古代猪文(费马小定理,卢卡斯定理,中国剩余定理,线性筛)
- [算法总结] 6 道题搞定 BAT 面试——堆栈和队列
- 浅谈webuploader上传文件
- Sprint4
- bzoj 4034(DFS序+线段树)
- Win7下SQLPlus登录时报错";SP2-1503:无法初始化Oracle调用界面";
- RocketMQ Java 客户端实现