HDU 4768 Flyer【二分】||【异或】

<题目链接>

<转载于  >>> >

题目链接:

n个社团派发传单,有a,b,c三个参数,派发的规则是,派发给序号为a,a+c....a+k*c,序号要求是小于等于b 这其中,有一个学生只收到了奇数传单,要求找出这个学生的编号与得到的传单数目 。

解题分析:

用二分来划分区间,如果左区间传单之和为奇数,则那个学生在左区间,否则在右区间,由于每个社团的区间内得到传单的学生为等差数列,所以可以很容易得到枚举的区间内的传单数。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int M =+;
typedef long long ll;
ll n,a[M],b[M],c[M]; ll solve(ll mid){ //求出以mid为末尾所发传单的前缀
ll sum=;
for(int i=;i<=n;i++){
ll cal=min(mid,b[i]);
if(cal>=a[i])
sum+=(cal-a[i])/c[i]+;
}
return sum;
} int main(){
while(scanf("%lld",&n)!=EOF){
for(int i=;i<=n;i++){
scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
}
ll l=,r=1ll<<; //注意这里的ll不能省
while(l<r){
ll mid=(l+r)>>; //二分枚举右界
if(solve(mid)%)r=mid; //如果左区间为奇数,则选择左区间
else l=mid+; //若右区间为奇数,则将右界向右移动
}
if(l==1ll<<){
printf("DC Qiang is unhappy.\n");
}
else{
printf("%lld %lld\n",l,solve(l)-solve(l-));
}
}
return ;
}

下面是异或的做法,思路很清晰,但是不太明白为什么这个复杂度能过。

#include <cstdio>
#include <cstring> const int M =+;
typedef long long ll;
ll n,a[M],b[M],c[M]; int main(){
while(scanf("%lld",&n)!=EOF){
for(int i=;i<=n;i++){
scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
}
ll res=;
for(int i=;i<=n;i++){ //看不懂这个循环的复杂度,数据如果稍微极限一点,肯定会tle吧
for(ll j=a[i];j<=b[i];j+=c[i]){
res^=j; //因为只有一个学生有奇数个传单,根据异或的性质,偶数次异或结果仍然为0,奇数次异或结果仍然为j,所以如果res!=0,那么res就是该学生的下标
}
}
if(!res)printf("DC Qiang is unhappy.\n");
else{
ll ans=;
for(int i=;i<=n;i++){
if(res>=a[i]&&res<=b[i]&&(res-a[i])%c[i]==) //第i个社团给编号为res的学生贡献了一张传单
ans++;
}
printf("%lld %lld\n",res,ans);
}
}
return ;
}

2018-09-22

上一篇:《C和指针》


下一篇:png转tif