注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

Codeforces Round #184 (Div. 2) B&&C  

2013-05-20 21:08:07|  分类: Codeforces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
Pro B:
题目描述:
给出p和q,n个数的序列a,问Codeforces Round 184 (Div. 2)  BC - fudq - fudq的博客的结果和p/q的结果是不是一样,是输出YES,否则输出NO。
(1<=q<=p<=10^18, 1<=ai<=10^18)
题解:
比赛时没仔细想,直接模拟求出了a序列的最后结果,然后和p/q进行比较。虽然过了Pretests,但还是挂了。仔细看了下代码,发现中间有个地方超__int64范围了,此法不可行。
仔细想了下,发现题目只要求判断这俩结果是否相等,没必要求出具体的值。
只考虑a序列前两个数时,a1+1/a2和p/q比较,如果要相等,则p/q的值至少为a1,且不能大于a1+1。
通过化简式子a1+1/a2=p/q,得到a2=q/(p-a1*q),也就是比较这个式子是不是成立,如果成立的话,则符合。
依次类推,我们按a序列从头到尾扫一遍,看p/q的值是不是介于ai和ai+1之间,判断完后,让p/q减去ai并化简式子循环操作。

/*
* test.cpp
*
* Created on: 2013-05-19
* Author: fudq
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
#define N 100010
#define LL __int64
LL f[N];

LL gcd(LL a,LL b)
{
return !b?a:gcd(b,a%b);
}

bool fun(LL p,LL q,LL n)
{
LL i,t,tmp;
for(i=0;i<n;i++)
{
if(q==0)
return false;
tmp=p/q;
if(f[i] != tmp && f[i]+1 != tmp)
return false;
t=q;
q=p-f[i]*q;
p=t;
}
if(q!=0)
return false;
return true;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
// freopen("testout.txt","w",stdout);
#endif
LL n,p,q,i,t;
while(scanf("%I64d%I64d",&p,&q)!=EOF)
{
scanf("%I64d",&n);
for(i=0;i<n;i++)
scanf("%I64d",&f[i]);
t=gcd(p,q);
p/=t;
q/=t;
if(fun(p,q,n))
printf("YES\n");
else
printf("NO\n");
}
return 0;
}


Pro C:
题意:
n个数的非递减序列a,计算s=2^a1+2^a2……2^an,问s最小需要加上多少个2^b(b为任意的数)才能凑成2^v-1。
题解:
比赛的时候,杯具的理解错题意了,以为加上的2^b中的b必须从0开始,必须加2^0, 2^1, 2^2...2^b。结果愣是做了快一个小时都没想出来。第二天早上仔细读了下题才发现题意理解错了。。。
题目不是很难,抓住几条性质便可解:
1. 2^v-1=2^0+2^1+2^2+2^3+...+2^(v-1);
2. 两个相同的2^ai相加等于2^(ai+1);
所以,只要把序列里相同的两个ai合成一个ai+1即可,最后从0到最大的ai看下,缺了几部分,就是最后的结果。
为了方便操作,用了优先队列处理。

/*
* test.cpp
*
* Created on: 2013-05-20
* Author: fudq
*/

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
#define N 100010
#define LL __int64

int main()
{
#ifndef ONLINE_JUDGE
freopen
("testin.txt","r",stdin);
//freopen("testout.txt","w",stdout);
#endif
LL n
,i,a,tmp,ans;
while(scanf("%I64d",&n)!=EOF)
{
priority_queue
<LL ,vector<LL>, greater<LL> > Q;
for(i=0;i<n;i++)
{
scanf
("%I64d",&a);
Q
.push(a);
}
ans
=0;tmp=-1;
while(!Q.empty())
{
LL ta
,tb;
ta
=Q.top();
Q
.pop();
if(Q.empty())
{
ans
+=ta-tmp-1;
continue;
}
tb
=Q.top();
Q
.pop();

if(ta == tb)
Q
.push(ta+1);
else
{
ans
+=ta-tmp-1;
Q
.push(tb);
tmp
=ta;
}
}
printf
("%I64d\n",ans);
}
return 0;
}


  评论这张
 
阅读(84)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018