相关链接
题目传送门: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; }
jqbrbdomo pywog qjexgvd pqpf sdvvegknhxqfmxd
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!
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!
I love it whenever people come together and share ideas.
Great website, keep it up!
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.
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!
An intriguing discussion is definitely worth comment.
I do think that you ought to write more on this topic, it
may not be a taboo matter but usually people do not discuss
these topics. To the next! Cheers!!
I am sure this piece of writing has touched all the internet visitors, its really really nice piece
of writing on building up new webpage.
I quite like reading a post that can make people think. Also, thank you for permitting me to comment!
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.
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
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
653489 13420There is noticeably a lot to realize about this. I suppose you created certain good points in attributes also. 197517
127921 408484But, what concerning the bottom line? Are you sure about the source? 640139
This site was… how do you say it? Relevant!! Finally I’ve found something that helped me.
Thanks!
I think this site holds some rattling superb info for everyone :D. “A friend might well be reckoned the masterpiece of nature.” by Ralph Waldo Emerson.
Hey! I’m at work browsing your blog from my new apple iphone!
Just wanted to say I love reading through your blog and look forward to all your posts!
Carry on the excellent work!
Hi everyone, it’s my first visit at this web site, and post is genuinely
fruitful designed for me, keep up posting these types of content.
Hey very nice blog!
Great blog here! Also your website a lot up fast! What
host are you the usage of? Can I get your affiliate hyperlink on your host?
I wish my web site loaded up as fast as yours lol
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.
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!!
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?
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.
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.
I don’t commonly comment but I gotta admit thankyou for the post on this amazing one : D.