BZOJ 4723 Flappy Bird

发表于 | 更新于

Link

据说是比较水的题目？然而我似乎被NOIP题框住了。。

Solution

维护小鸟能到达的范围。因为是每次只能上下11，所以根据横坐标的差值可以得到纵坐标的变化区间。 一开始是[0,0][0,0]，然后依次扩大，并与可以通过障碍物的区间取交。 注意：可以通过障碍物的区间并不是每个点都可以到达，只有纵坐标值奇偶性和横坐标相同的时候才可以。但是区间之内的点不会造成影响，只有区间端点才会造成影响(区间长度≥3\ge 3的时候，一定存在合法的点)。所以每次要判断一下得到的区间是否合法。 当区间为空集的时候立即退出，因为后面的操作还会再把区间扩大，可能就又合法了。

Tips

做到题目的弱化或者强化版不要被之前的思路限制住，要找到原来的做法套在当前题目上多了什么，少了什么。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//Code by Lucida
#include<bits/stdtr1c++.h>
//#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
typedef long long int64;
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
namespace IO {
	template <class T> inline void get(T &x) {
		static bool f;static char ch;
		for(f=0,ch=0;ch<'0' || '9'<ch;ch=getchar()) f|=ch=='-';
		for(x=0;'0'<=ch && ch<='9';ch=getchar()) (x*=10)+=ch-'0';
		x=f?-x:x;
	}
}
using IO::get;
using std::max;
using std::min;
const int MAXN=5e5+11;
struct Block {
	int x,a,b;
}block[MAXN];
struct Interval
{
	int l,r;
	Interval(int l,int r):l(l),r(r){}
	bool isEmpty() {
		return l>r;
	}
	friend Interval operator & (const Interval &a,const Interval &b) {
		return Interval(max(a.l,b.l),min(a.r,b.r));
	}
	Interval &operator &= (const Interval &a) {
		return *this=*this & a;
	}
};
int main() {
	int n,goal;get(n),get(goal);
	for(int i=1;i<=n;++i) {
		get(block[i].x);
		get(block[i].a);
		get(block[i].b);
	}
	Interval va(0,0);//(0,0)
	for(int i=1;i<=n;++i) {
		int d=block[i].x-block[i-1].x;
		va.l-=d,va.r+=d;
		va&=Interval(block[i].a+1,block[i].b-1);
		if((va.l-block[i].x)&1) va.l++;
		if((va.r-block[i].x)&1) va.r--;
		if(va.isEmpty()) break;//2333???
	}
	if(va.isEmpty())
		puts("NIE");
	else
		put((block[n].x+va.l)>>1),putchar('\n');
	return 0;
}