青岛网站定制多少钱,专业定制网红柴火灶,网站代码查询,提供温州手机网站制作哪家好$ CH~0805~ $ 防线 (二分值域#xff0c;前缀和#xff0c;特殊性质) $ solution: $ 注意博主所给题面的输出和原题有些不同 这道题当时想了很久很久#xff0c;就是想不到怎么写。果然还是太 $ vegetable $ 了。首先我们可以肯定的是#xff0c;我们不能暴力枚举#xff… $ CH~0805~ $ 防线 (二分值域前缀和特殊性质) $ solution: $ 注意博主所给题面的输出和原题有些不同 这道题当时想了很久很久就是想不到怎么写。果然还是太 $ vegetable $ 了。首先我们可以肯定的是我们不能暴力枚举复杂度太高数据范围太大所以我们需要从题目中寻找性质 题目说了要寻找一个数目为奇数的点本来以为自己在二进制是与否这方面已经很有经验但是这道题反手打脸。奇偶数是一个以二进制很有关的东西奇数奇数偶数类似 1 异或 1 0 奇数偶数奇数类似 1 异或 0 1 所以这道题我们可以用前缀和来判断。题目给了一条很不起眼的条件最多只有一个奇数位置 这个条件让我可以二分值域搞个前缀和如果前面有奇数存在那么前缀和一定是奇数反之为偶数。所以我们二分值域算前缀和即可找到那个位置 $ code: $ #includeiostream
#includecstdio
#includeiomanip
#includealgorithm
#includecstring
#includecstdlib
#includectime
#includecmath
#includevector
#includequeue
#includemap
#includeset#define ll long long
#define db double
#define rg register intusing namespace std;ll ans;
int t,n;
int a[200005];
int b[200005];
int v[200005];inline int qr(){register char ch; register bool sign0; rg res0;while(!isdigit(chgetchar()))if(ch-)sign1;while(isdigit(ch))resres*10(ch^48),chgetchar();if(sign)return -res; else return res;
}inline ll ask(ll x){ll res0;for(rg i1;in;i){if(a[i]x)continue;if(b[i]x) res1(ll)(b[i]-a[i])/v[i];else res1(ll)(x-a[i])/v[i];}return res;
}int main(){//freopen(.in,r,stdin);//freopen(.out,w,stdout);tqr();while(t--){ nqr();rg l2147483647,r0; ans0;for(rg i1;in;i){a[i]qr(),b[i]qr(),v[i]qr();lmin(l,a[i]); rmax(r,b[i]);ans(b[i]-a[i])/v[i]1;}if(ans%20){puts(Poor QIN Teng:();continue;} ll mid;while(lr){mid((ll)lr)1;if(!(ask(mid)%2))lmid1;else rmid-1;}printf(%d %lld\n,l,ask(l)-ask(l-1));}return 0;
} 转载于:https://www.cnblogs.com/812-xiao-wen/p/11250602.html
