n个最多2W个社团发传单,因为传单不够,所有只能按照学生学号间隔着发…… 比如发给A_i,A-i+k,A_i+2*k ,只要不大于B_I就好;
而且已知收到传单的同学当中只有一个人收到奇数张;
这个题初看没有思路,但是仔细一想就挺简单了,在某个学号范围内比如说1-x范围内,根据社团发传单的数量,我们很容易知道他是按照等差数列来发送的,所以可能很容易算出这段区间内有多少张发出去,统计完所有的社团然后只要是奇数,那么那个唯一的收获奇数张的同学就在里面,然后利用二分的思想把这一段区间精确到1……
http://acm.hdu.edu.cn/showproblem.php?pid=4768
下面的代码是借用山科的
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> using namespace std; const int maxn=20010; long long A[maxn],B[maxn],C[maxn]; long long cal(long long mid,int n){ long long sum=0; for (int i=0;i<n;i++){ long long up=min(mid,B[i]); if (up>=A[i]) sum+=(up-A[i])/C[i]+1; } // cout<<mid<<" "<<sum<<endl; return sum; } int main() { int n; while (scanf("%d",&n)==1) { for (int i=0;i<n;i++){ cin>>A[i]>>B[i]>>C[i]; } long long L=0,R=1LL<<31; while (L<R){ long long mid=(L+R)/2; if (cal(mid,n)%2) R=mid; else L=mid+1; } if (L==1LL<<31) cout<<"DC Qiang is unhappy."<<endl; else { while (cal(L,n)%2==0) L--; cout<<L<<' '<<cal(L,n)-cal(L-1,n)<<endl; } } return 0; }