<题目链接>
<转载于 >>> >
题目链接：
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