ACwing 题目地址 https://www.acwing.com/problem/content/122/
Solution
套路题. 不会做只是我没见过这个套路而已
突破口: 但是整条防线上也最多只有一个位置有奇数个防具
我们知道一个原理 : 偶 + 偶 = 偶, 奇 + 偶 = 奇.
又因为我们可以快速算出一个前缀和, 比如说算出 \(x\) 之前有多少个防具,(用等差数列的一些公式快速 \(O(1)\)算出, 因为有 \(n\) 个等差数列所以算一次前缀和的的时间是 \(O(n)\)). 记 \(x\) 的前缀和为 \(S(x)\)
我们又发现如果答案 (奇数) 在 \(p\) 这个位置,\(\forall x \in [0,p)\) \(S(x)\) 都是偶数, 而 \(\forall x \in [p,∞)\) \(S(x)\) 都是奇数. 这样就有了一个分界点, 可以二分了. 二分答案的位置.
时间复杂度 \(O(n \log L)\) \((n<=200000,L<=2^{31}-1)\), 可以过.
Code
Talk is cheap.Show me the code.
- #include<bits/stdc++.h>
- #define INF 0x3f3f3f3f
- using namespace std;
- inline int read() {
- int x=0,f=1; char ch=getchar();
- while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
- while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
- return x * f;
- }
- const int N = 200007;
- int n,pos,ans;
- int S[N],E[N],D[N];
- int check(int x) {
- int res = 0, sum;
- for(int i=1;i<=n;++i) {
- if(x <S[i]) sum = 0;
- else sum = ((min(E[i],x)-S[i])/D[i]) + 1;
- res += sum;
- }
- return res;
- }
- void work() {
- int l = 1, r = -INF, mid, tmp;
- n = read();
- for(int i=1;i<=n;++i) S[i] = read(), E[i] = read(), D[i] = read(), r = max(r,E[i]);
- pos = -1;
- while(l <= r) {
- mid = (l+r)>>1;
- if(check(mid) & 1) {
- pos = mid, ans = check(mid) - check(mid-1);
- r = mid - 1;
- } else l = mid + 1;
- }
- if(pos==-1) puts("There's no weakness.");
- else printf("%d %d\n",pos,ans);
- }
- int main()
- {
- int T = read();
- while(T--) work();
- return 0;
- }
- Summary
这个题目让我学会了从奇偶性推导出单调性的套路
让我学会了等差数列的一些小性质
[算进] 防线 题解
来源: http://www.bubuko.com/infodetail-3345230.html