【BZOJ 4881】[Lydsy2017年5月月赛] 线段游戏

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4881
神犇题解:http://krydom.com/bzoj4881/

解题报告

不难发现,这就是一个二分图染色问题
那么我们首先需要判无解
分析题目我们可以发现,如果存在长度为$x+2$的奇环,那么一定存在长度为$x$的奇环
于是我们只需要判有没有长度为$3$的奇环,然后我们发现这就是三个递减的数,于是随便搞一搞就好
至于输出方案数,就是$2$的连通块个数次方

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int MOD = 998244353;

int n, p[N], mx[N], mn[N];
stack<int> stk; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		p[i] = read();
	}
	mx[1] = p[1];
	for (int i = 2; i <= n; i++) {
		mx[i] = max(mx[i - 1], p[i]);
	}
	mn[n] = p[n];
	for (int i = n - 1; i; i--) {
		mn[i] = min(mn[i + 1], p[i]);
	}
	for (int i = 2; i < n; i++) {
		if (mx[i - 1] > p[i] && p[i] > mn[i + 1]) {
			puts("0");
			exit(0);
		}
	}
	for (int i = 1; i <= n; i++) {
		if (stk.empty() || stk.top() < p[i]) {
			stk.push(p[i]);
		} else {
			int tt = stk.top();
			for (; !stk.empty() && stk.top() > p[i]; stk.pop());
			stk.push(tt);
		}
	}
	int ans = 1;
	for (int i = 1; i <= (int)stk.size(); i++) {
		ans = (ans << 1) % MOD;
	}
	cout<<ans<<endl;
	return 0;
}

26 thoughts to “【BZOJ 4881】[Lydsy2017年5月月赛] 线段游戏”

  1. It is perfect time to make some plans for the future and it is time to be happy.
    I’ve read this post and if I could I want to suggest
    you few interesting things or tips. Perhaps you could write next articles
    referring to this article. I want to read more things about it!

  2. I do not even know how I ended up here, but I thought this post was great.
    I don’t know who you are but certainly you are going to a famous
    blogger if you aren’t already 😉 Cheers!

  3. Hmm it looks like your website ate my first comment (it was extremely long) so I guess I’ll just sum it up
    what I submitted and say, I’m thoroughly enjoying your blog.

    I as well am an aspiring blog blogger but I’m still new to the whole thing.
    Do you have any tips for inexperienced blog writers?
    I’d definitely appreciate it.

  4. Howdy superb website! Does running a blog such as this
    require a great deal of work? I’ve virtually no knowledge of computer programming however I
    was hoping to start my own blog soon. Anyhow,
    if you have any recommendations or techniques for new blog owners
    please share. I understand this is off topic but I just had
    to ask. Thanks a lot!

  5. Hello I am so thrilled I found your weblog, I really found you by mistake,
    while I was looking on Digg for something else, Nonetheless I am here now and would just like to say thanks a lot for
    a tremendous post and a all round entertaining blog (I also love the theme/design), I don’t have time to browse it all at the minute
    but I have saved it and also added your RSS feeds, so when I
    have time I will be back to read a lot more, Please do keep
    up the excellent b.

  6. 790889 930096Of course like your site but you require to check the spelling on several of your posts. Several of them are rife with spelling issues and I discover it really bothersome to tell the truth nevertheless Ill surely come back once more. 264724

  7. 6748 135817Once I originally commented I clicked the -Notify me when new feedback are added- checkbox and now every time a remark is added I get four emails with exactly the same comment. Is there any means you possibly can remove me from that service? Thanks! 85591

  8. I’m not sure where you’re getting your info, but great
    topic. I needs to spend some time learning much
    more or understanding more. Thanks for excellent info I was looking for this
    information for my mission.

  9. An interesting discussion is worth comment. There’s no doubt that that you ought to write more on this
    issue, it may not be a taboo matter but usually people do not speak about such
    subjects. To the next! Kind regards!!

  10. Hey there! Do you know if they make any plugins to protect against hackers?
    I’m kinda paranoid about losing everything I’ve worked hard on. Any tips?

  11. Nice post. I learn something totally new and challenging on websites I stumbleupon everyday.
    It’s always helpful to read through content from other authors and use
    a little something from their web sites.

  12. I am extremely impressed with your writing skills and also with the layout on your weblog.
    Is this a paid theme or did you modify it yourself?
    Either way keep up the nice quality writing, it is
    rare to see a nice blog like this one today.

Leave a Reply

Your email address will not be published. Required fields are marked *