因为保证只有一个数为奇数,所以所有区间内满足的数的总数一定是奇数
且包含这个数的所有区间内 能满足条件的数的个数和也一定是奇数
那么二分这个数...在所有的区间内查找满足的条件...代码不到20行
/********************* Template ************************/ #include <set> #include <map> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <bitset> #include <cstdio> #include <string> #include <vector> #include <cassert> #include <cstdlib> #include <cstring> #include <sstream> #include <fstream> #include <numeric> #include <iomanip> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define EPS 1e-8 #define DINF 1e15 #define MAXN 20100 #define LINF 1LL << 60 #define MOD 95041567//1000000007 #define INF 0x7fffffff #define PI 3.14159265358979323846 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define BUG cout<<" BUG! "<<endl; #define LINE cout<<" ------------------ "<<endl; #define FIN freopen("in.txt","r",stdin); #define FOUT freopen("out.txt","w",stdout); #define mem(a,b) memset(a,b,sizeof(a)) #define FOR(i,a,b) for(int i = a ; i < b ; i++) #define read(a) scanf("%d",&a) #define read2(a,b) scanf("%d%d",&a,&b) #define read3(a,b,c) scanf("%d%d%d",&a,&b,&c) #define write(a) printf("%d ",a) #define write2(a,b) printf("%d %d ",a,b) #define write3(a,b,c) printf("%d %d %d ",a,b,c) #pragma comment (linker,"/STACK:102400000,102400000") template<class T> inline T L(T a) {return (a << 1);} template<class T> inline T R(T a) {return (a << 1 | 1);} template<class T> inline T lowbit(T a) {return (a & -a);} template<class T> inline T Mid(T a,T b) {return ((a + b) >> 1);} template<class T> inline T gcd(T a,T b) {return b ? gcd(b,a%b) : a;} template<class T> inline T lcm(T a,T b) {return a / gcd(a,b) * b;} template<class T> inline T Min(T a,T b) {return a < b ? a : b;} template<class T> inline T Max(T a,T b) {return a > b ? a : b;} template<class T> inline T Min(T a,T b,T c) {return min(min(a,b),c);} template<class T> inline T Max(T a,T b,T c) {return max(max(a,b),c);} template<class T> inline T Min(T a,T b,T c,T d) {return min(min(a,b),min(c,d));} template<class T> inline T Max(T a,T b,T c,T d) {return max(max(a,b),max(c,d));} template<class T> inline T exGCD(T a, T b, T &x, T &y){ if(!b) return x = 1,y = 0,a; T res = exGCD(b,a%b,x,y),tmp = x; x = y,y = tmp - (a / b) * y; return res; } //typedef long long LL; typedef unsigned long long ULL; typedef __int64 LL; typedef unsigned __int64 ULL; /********************* By F *********************/ LL a[MAXN],b[MAXN],c[MAXN]; int n; bool solve(LL m){ LL ret = 0; for(int i = 0 ; i < n ; i++){ if(m >= b[i]) ret += (b[i] - a[i]) / c[i] + 1; else if(m >= a[i]) ret += (m - a[i]) / c[i] + 1; } if(ret&1) return true; return false; } int main(){ while(~scanf("%d",&n)){ for(int i = 0 ; i < n ; i++) scanf("%I64d%I64d%I64d",&a[i],&b[i],&c[i]); LL l = 0 , r = 1LL<<32; while(l < r){ LL m = (l+r)/2; if(solve(m)) r = m; else l = m + 1; } LL cnt = 0 ; for(int i = 0 ; i < n ; i++) if(l <= b[i] && l >= a[i] && (l-a[i])%c[i] == 0) cnt++; if(cnt) printf("%I64d %I64d ",l,cnt); else printf("DC Qiang is unhappy. "); } return 0; }