【BZOJ 4828】[HNOI2017] 大佬

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4828

解题报告

先$DP$出最多可以有多少天不做题
然后我们发现两次$D$人其实是独立的
于是我们再$DP$出攻击达到$x$的最小天数

最后回答每个询问的时候
用个双指针扫一扫

Code

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

const int N = 109;
const int M = 930000;

int n,m,mc,tot,MX,ispri[N],w[N],a[N],f[N][N];
pair<int,int> itm[M];

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;
}

void DFS(int t, LL sum) {
	if (t > MX) return;
	else {
		DFS(t + 1, sum);
		if (ispri[t]) {
			for (;sum*=t,sum<=1e8;) {
				itm[++tot].first = sum;
				DFS(t + 1, sum);
			}
		}
	}
}

inline int cal(int x) {
	int ret = x + 1;
	for (int i=min(MX,x-1),cnt,tmp;i;i--) {
		if (x % i) continue;
		cnt = i + 1; tmp = x;
		for (int j=i;j>1&&tmp>1;j--) {
			while (tmp % j == 0) {
				tmp /= j;
				++cnt;
			}
		}
		if (tmp == 1) {
			ret = min(ret, cnt);
		} else {
			break;
		}
	}
	return ret;
}

int main() {
	n = read(); m = read(); mc = read();
	for (int i=1;i<=n;i++) {
		a[i] = read();
	}
	for (int j=1;j<=n;j++) {
		w[j] = read();
	}
	//DP最多空出来的天数 
	memset(f, -1, sizeof(f));
	f[1][mc] = 0;
	for (int i=1;i<=n;i++) {
		for (int j=a[i];j<=mc;j++) {
			if (f[i][j] == -1) continue;
			int t1 = min(j - a[i] + w[i], mc), t2 = j - a[i];
			if (t1 >= 0) {
				f[i + 1][t1] = max(f[i + 1][t1], f[i][j]);
			}
			if (t2 >= 0) {
				f[i + 1][t2] = max(f[i + 1][t2], f[i][j] + 1);
			}
		}
	}
	MX = -1; 
	for (int j=2;j<=n+1;j++) {
		for (int i=0;i<=mc;i++) {
			MX = max(MX, f[j][i]);
		}
	} 
	//搞出每一个物品的最小花费 
	for (int j=2;j<=100;j++) {
		ispri[j] = 1;
		for (int i=2;i*i<=j;i++) {
			if (j % i == 0) {
				ispri[j] = 0;
			}
		}
	}
	DFS(1, 1); 
	for (int i=1;i<=tot;i++) {
		itm[i].second = cal(itm[i].first);
	}
	itm[++tot] = make_pair(0, 0);
	sort(itm+1, itm+1+tot);
	//对于每个询问用一个双端队列
	for (int tt=1;tt<=m;tt++) {
		int C = read(), ans = 0;
		for (int i=tot,pfx=1,cur=-1e9;i;i--) {
			while (pfx <= tot && itm[pfx].first <= C - itm[i].first) {
				cur = max(cur, itm[pfx].first - itm[pfx].second);
				pfx++;
			}
			if (cur + itm[i].first - itm[i].second >= C - MX) {
				ans = 1; 
				break;
			}
		}
		printf("%d\n",ans);
	} 
	return 0;
}

224 thoughts to “【BZOJ 4828】[HNOI2017] 大佬”

  1. When I initially commented I clicked the “Notify me when new comments are added” checkbox and now each time a
    comment is added I get four emails with the same comment.
    Is there any way you can remove me from that service? Bless you!

  2. Wow that was strange. I just wrote an very long comment but after I clicked submit my comment didn’t appear.
    Grrrr… well I’m not writing all that over again.
    Regardless, just wanted to say fantastic blog!

  3. Sweet blog! I found it while browsing on Yahoo News.

    Do you have any suggestions on how to get listed in Yahoo News?
    I’ve been trying for a while but I never
    seem to get there! Thank you

  4. My brother suggested I would possibly like this web site.
    He was entirely right. This put up actually made my day.
    You cann’t imagine simply how a lot time I had spent for this info!
    Thanks!

  5. Its like you read my thoughts! You appear to understand a
    lot approximately this, like you wrote the e book in it or something.
    I think that you simply could do with a few %
    to drive the message home a little bit, however instead of that,
    that is wonderful blog. A fantastic read. I’ll definitely be back.

  6. My developer is trying to persuade me to move to .net from PHP.

    I have always disliked the idea because of the expenses.
    But he’s tryiong none the less. I’ve been using WordPress on numerous
    websites for about a year and am anxious about switching to another platform.
    I have heard good things about blogengine.net. Is there a way I can transfer all my wordpress posts into it?
    Any kind of help would be really appreciated!

  7. Hi would you mind letting me know which hosting company
    you’re utilizing? I’ve loaded your blog in 3
    different internet browsers and I must say this blog loads a
    lot quicker then most. Can you recommend a good hosting provider at a honest
    price? Many thanks, I appreciate it!

  8. Please let me know if you’re looking for a writer for your site.
    You have some really good articles and I feel I would be a good asset.
    If you ever want to take some of the load off, I’d really like to write some
    articles for your blog in exchange for a link back to mine.
    Please send me an email if interested. Many thanks!

  9. I am really inspired along with your writing skills and also with the structure for your blog. Is this a paid theme or did you customize it your self? Anyway stay up the excellent quality writing, it is rare to look a nice weblog like this one nowadays..

  10. Hello, I do think your website may be having browser
    compatibility problems. When I look at your blog in Safari, it looks fine but when opening in Internet Explorer, it’s got some overlapping issues.
    I just wanted to give you a quick heads up! Apart
    from that, great blog!

  11. It’s a pity you don’t have a donate button! I’d most certainly donate to this excellent blog!
    I guess for now i’ll settle for bookmarking and adding your RSS feed to my Google
    account. I look forward to brand new updates and
    will talk about this website with my Facebook group.

    Chat soon!

  12. I’m truly enjoying the design and layout of your site. It’s a very easy on the eyes which makes it much more pleasant for me to come here and visit more often. Did you hire out a designer to create your theme? Fantastic work!|

  13. I absolutely love your blog and find the majority of your post’s to be exactly what I’m looking for. can you offer guest writers to write content for yourself? I wouldn’t mind publishing a post or elaborating on a number of the subjects you write concerning here. Again, awesome weblog!|

  14. Hi, I do believe this is an excellent website.

    I stumbledupon it 😉 I’m going to revisit yet again since i have
    saved as a favorite it. Money and freedom is the best way to change, may you
    be rich and continue to help others.

  15. Hi! Do you know if they make any plugins to help with SEO? I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very good results. If you know of any please share. Kudos!|

  16. Undeniably believe that which you said. Your favorite reason seemed to be on the internet the easiest thing to be aware of. I say to you, I certainly get irked while people think about worries that they plainly don’t know about. You managed to hit the nail upon the top and also defined out the whole thing without having side effect , people can take a signal. Will likely be back to get more. Thanks|

  17. Hi I am so excited I found your website, I really found you by accident, while I was researching on Bing for something else, Anyhow I am here now and would just like to say thanks a lot for a tremendous post and a
    all round exciting blog (I also love the theme/design), I don’t
    have time to look over it all at the minute but I have book-marked it and also included your RSS feeds, so when I have time I will be back
    to read a lot more, Please do keep up the great job.

  18. Hello just wanted to give you a quick heads up. The words in your
    content seem to be running off the screen in Chrome. I’m not sure if this is a formatting issue
    or something to do with web browser compatibility but
    I figured I’d post to let you know. The design look great though!
    Hope you get the problem resolved soon. Kudos

  19. I have been surfing online more than three hours today, yet I never found any interesting article like yours.
    It is pretty worth enough for me. In my view, if all webmasters and bloggers made good content as you did, the net will be a lot
    more useful than ever before.

  20. Hi! Do you know if they make any plugins to assist with Search
    Engine Optimization? I’m trying to get my blog to rank for some targeted keywords but I’m not
    seeing very good results. If you know of any please share.

    Thanks!

  21. Hello I am so excited I found your blog page, I really found you by accident, while I was browsing on Google
    for something else, Nonetheless I am here now and
    would just like to say cheers for a marvelous post and a
    all round interesting blog (I also love the
    theme/design), I don’t have time to read it
    all at the moment but I have book-marked 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
    superb jo.

  22. Thank you a bunch for sharing this with all of us you really recognise what
    you’re talking approximately! Bookmarked. Please additionally talk over with
    my website =). We could have a link exchange contract among
    us

  23. Do you mind if I quote a few of your posts as long as I provide credit and sources back to
    your webpage? My blog is in the exact same niche as yours and my visitors would certainly benefit from
    a lot of the information you present here.
    Please let me know if this okay with you.

    Regards!

  24. This is the right site for anyone who hopes to understand this topic.

    You realize a whole lot its almost tough to argue with you (not that I actually would want
    to…HaHa). You definitely put a new spin on a topic that’s been discussed for ages.
    Wonderful stuff, just wonderful!

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

  26. Heya! I just wanted to ask if you ever have any issues with
    hackers? My last blog (wordpress) was hacked and I ended up losing a
    few months of hard work due to no back up. Do you have any solutions to prevent hackers?

  27. Its like you read my mind! You appear to know a lot about this, like you wrote the book in it or something.

    I think that you could do with some pics to drive the message home a little bit, but other than that, this is great blog.
    An excellent read. I will definitely be back.

  28. Please let me know if you’re looking for a writer for your blog.
    You have some really great posts and I think I would be a good asset.
    If you ever want to take some of the load off, I’d absolutely
    love to write some content for your blog in exchange for a link back to mine.
    Please blast me an email if interested. Cheers!

  29. Pretty section of content. I just stumbled upon your weblog and in accession capital to assert
    that I get actually enjoyed account your blog posts.
    Any way I’ll be subscribing to your feeds and even I achievement you access consistently rapidly.

  30. Thank you for the good writeup. It in fact was a amusement account it.

    Look advanced to far added agreeable from you!
    By the way, how can we communicate?

  31. whoah this blog is great i love studying your posts. Stay up
    the good work! You know, many individuals are looking around for this information, you could help them greatly.

  32. Excellent read, I just passed this onto a colleague who was doing a little research on that. And he just bought me lunch because I found it for him smile So let me rephrase that: Thank you for lunch! “Never let inexperience get in the way of ambition.” by Terry Josephson.

  33. Hi! I could have sworn I’ve been to this web site before but after browsing through some of the articles I realized it’s new to me.
    Regardless, I’m definitely pleased I found it and I’ll be bookmarking it and checking back often!

  34. My brother recommended I might like this blog.
    He used to be entirely right. This post truly made my day.
    You cann’t believe simply how much time I had spent for this information! Thanks!

  35. An interesting discussion is worth comment. I think that you should write more on this topic, it might not be a taboo subject but generally people are not enough to speak on such topics. To the next. Cheers

  36. What’s up to every body, it’s my first go to see of this webpage; this blog includes amazing
    and truly fine stuff in favor of visitors.

  37. I am now not sure the place you are getting your info, however good topic.
    I must spend a while finding out much more or figuring out more.
    Thanks for wonderful info I was in search of this info
    for my mission.

  38. Everyone loves what you guys are up too. This kind of clever work and exposure!

    Keep up the terrific works guys I’ve included you guys to blogroll.

  39. My brother suggested I might like this blog.
    He was totally right. This post actually made my day. You can not imagine just how much time I had
    spent for this information! Thanks!

  40. Today, I went to the beachfront with my kids.
    I found a sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put the shell to her ear and screamed.
    There was a hermit crab inside and it pinched her ear. She never wants to
    go back! LoL I know this is completely off topic but
    I had to tell someone!

  41. I’m extremely impressed with your writing
    skills as well as with the layout on your weblog.
    Is this a paid theme or did you customize it yourself?
    Either way keep up the nice quality writing, it is rare to see a great blog like this one today.

发表评论

电子邮件地址不会被公开。 必填项已用*标注