【Codeforces 212B】Polycarpus is Looking for Good Substrings

Qizy 其他, 杂项, 解题报告

相关链接

题目传送门：http://codeforces.com/contest/212/problem/B
中文题面：http://www.tsinsen.com/A1470

解题报告

这题你需要观察到一个非常重要的结论：

以字符串某个特定位置为开头的字符串，至多只有26个会产生贡献

于是我们就可以暴力枚举这$O(26n)$的字符串
然后去更新答案
时间复杂度：$O(26n \log q)$

Code

这份代码我写挫了
时间复杂度是：$O(676n \log q)$的

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

const int N = 1000009;
const int SGZ = 26;
const int M = 10009;

int n, m, nxt[N][SGZ], crt[N][SGZ], q[M], ans[M];
vector<int> val;
char s[N], qy[SGZ]; 

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

inline int index(int x) {
	for (int l = 0, r = val.size() - 1, mid; l <= r; ) {
		mid = l + r >> 1;
		if (val[mid] == x) {
			return mid; 
		} else if (val[mid] < x) {
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	} 
	return -1;
}

int main() {
	scanf("%s", s);
	n = strlen(s);
	m = read();
	for (int i = 1; i <= m; i++) {
		scanf("%s", qy);
		int len = strlen(qy);
		for (int j = 0; j < len; j++) {
			q[i] |= 1 << qy[j] - 'a';
		}
		val.push_back(q[i]);
	}
	sort(val.begin(), val.end());
	val.resize(unique(val.begin(), val.end()) - val.begin());
	int last_position[SGZ];
	fill(last_position, last_position + SGZ, n);
	for (int i = n - 1; ~i; i--) {
		last_position[s[i] - 'a'] = i;
		for (int j = 0; j < SGZ; j++) {
			nxt[i][j] = last_position[j];
		}
	}
	memset(crt, -1, sizeof(crt));
	for (int i = 0; i < n; i++) {
		for (int j = 0, p = i, sta = 0; j < 26 && p < n; j++) {
			int np = n, c = -1;
			for (int k = 0; k < 26; k++) {
				if ((sta >> k & 1) == 0) {
					if (np > nxt[p][k]) {
						c = k;
						np = nxt[p][k];
					}
				}
			}
			if (~c) {
				sta |= 1 << c;
				p = np;
				crt[i][j] = sta;
				if (!i || crt[i - 1][j] != sta) {
					int idx = index(sta);
					if (~idx) { 
						ans[idx]++;
					}
				}
			}
		}
	}
	for (int i = 1; i <= m; i++) {
		printf("%d\n", ans[index(q[i])]);
	}
	return 0;
}

283 thoughts to “【Codeforces 212B】Polycarpus is Looking for Good Substrings”

  50. Hey there, You’ve done a fantastic job.
    I will definitely digg it and personally recommend to my friends.
    I’m confident they will be benefited from this website.

    Reply

  80. I’m not sure why but this weblog is loading incredibly slow for me.

    Is anyone else having this issue or is it a issue on my end?
    I’ll check back later on and see if the problem still exists.

    Reply

  94. Hey just wanted to give you a brief heads up and let you know a few
    of the pictures aren’t loading correctly. I’m not sure why but I think its a linking issue.
    I’ve tried it in two different browsers and both
    show the same outcome.

    Reply

  101. I just like the helpful information you supply for your articles.
    I will bookmark your blog and take a look at again here regularly.
    I am reasonably sure I will learn many new stuff right here!
    Good luck for the following!

    Reply

  127. I like the helpful information you provide in your articles.
    I will bookmark your weblog and check again here frequently.
    I am quite sure I will learn lots of new stuff right here!
    Best of luck for the next!

    Reply

  128. Do you have a spam problem on this website; I also am a blogger, and I was
    wondering your situation; we have created some nice practices and
    we are looking to exchange methods with others, why not shoot me an e-mail if interested.

    Reply

  135. Undeniably consider that that you said. Your favourite reason seemed to
    be on the net the easiest factor to take into account of.
    I say to you, I certainly get irked while folks think about
    worries that they just do not recognize about.

    You controlled to hit the nail upon the highest and
    outlined out the whole thing with no need side-effects , people can take a signal.

    Will probably be back to get more. Thank you

    Reply

  138. I think the admin of this website is really working hard in favor of his web site, because here every information is quality based stuff.

    Reply

  180. I believe everybody went like Ones New website, reason being things like this site without doubt has a article on quality. I loved read A New content. go on To remain a useful article, I will avail Once more by One additional time. Bless you.

    Reply

  209. What’s Happening i’m new to this, I stumbled upon this I have found It positively useful
    and it has aided me out loads. I’m hoping to contribute & aid other customers like its aided me.

    Good job.

    Reply

  210. You could certainly see your enthusiasm in the paintings you write. The arena hopes for even more passionate writers such as you who are not afraid to mention how they believe. All the time follow your heart. “Every man serves a useful purpose A miser, for example, makes a wonderful ancestor.” by Laurence J. Peter.

    Reply

  213. Greetings from Ohio! I’m bored to death at work soI decided to check out your site on my iphone during lunch break.I love the information you provide here and can’t wait to take alook when I get home. I’m shocked at how quick your blog loaded on my mobile ..I’m not even using WIFI, just 3G .. Anyways, great blog!

    Reply

  215. Thank you, I’ve just been looking for information approximately this topic for agesand yours is the greatest I’ve came upon so far. But, what about the bottomline? Are you sure in regards to the supply?

    Reply

  217. Write more, thats all I have to say. Literally, it seems as though you relied on the video to make your point. You obviously know what youre talking about, why throw away your intelligence on just posting videos to your blog when you could be giving us something informative to read?

    Reply

  228. [url=https://azithromycinzpak.com/]azithromycin 500mg price[/url] [url=https://allopurinol365.com/]buy allopurinol 300 mg[/url] [url=https://allopurinolzyl.com/]allopurinol 209[/url] [url=https://levitravard.com/]levitra 20 mg india price[/url]

    Reply

  233. Its such as you learn my thoughts! You appear to know so muchapproximately this, such as you wrote the e-book in it orsomething. I feel that you just could do with a few to pressurethe message home a little bit, however other than that, that isgreat blog. A fantastic read. I’ll certainly be back.

    Reply

  235. Balıkesir evden eve nakliyat hızlı bir şekilde yükseliş yakalamış ve detaylı hizmetleri ile birlikte insanlar için planlama ortaya koymuş firmaların, buradaki sonuçlarına bakmak gerekmektedir. Müşteri memnuniyetinin önemini her türlü standart sektörde görmek gerekiyor. Müşterisi için çalışan firmaların özellikle gelişim noktasında daha iyi bir yere gelmesi planın bir parçası olarak dikkat çekmektedir. Gerek ticari piyasaya gerekse de bireysel insan ihtiyacına cevap veren Balıkesir evden eve nakliyat ile birlikte, burada ayrıntılardaki gizli hedefi bulmak çok daha kolay olmuştur. Kendine ve müşterilerine en iyi şekilde davranan firma anlayışı, gerekli sektör hassasiyeti ile birlikte iyi bir çözüm yaratmak durumundadır. Uygun teklifler için özellikle internet üzerinden yapacağınız detaylı araştırmalar, makul fiyat garantisi için sizi en iyi sonuçlara götürecektir.

    Reply

  241. Nice post. I was checking constantly this weblog and I’m impressed! Extremely helpful info particularly the closing section 🙂 I maintain such information much. I was seeking this certain information for a long time. Thank you and best of luck. |

    Reply

  243. Nice post. I was checking continuously this blog and I’m impressed! Extremely helpful information specially the last part 🙂 I care for such info much. I was seeking this particular information for a very long time. Thank you and best of luck.|

    Reply

  251. Greetings! Quick question that’s totally off topic. Do you know how to make your site mobile friendly? My site looks weird when viewing from my apple iphone. I’m trying to find a theme or plugin that might be able to correct this issue. If you have any suggestions, please share. Thank you!|

    Reply

  259. That is very interesting, You are an overly professional blogger. I’ve joined your rss feed and sit up for searching for more of your fantastic post. Also, I have shared your website in my social networks|

    Reply

  260. Wonderful site. Lots of useful information here. I am sending it to some friends ans additionally sharing in delicious. And naturally, thanks for your effort!|

    Reply

  265. always i used to read smaller articles or reviews which also clear their motive, and that is also happening with this post which I am reading at this time.|

    Reply

  266. Howdy! I know this is kinda off topic however I’d figured I’dask. Would you be interested in trading links or maybe guest writinga blog post or vice-versa? My website covers a lot of the same subjects as yours and I feel we could greatlybenefit from each other. If you’re interested feel freeto shoot me an email. I look forward to hearingfrom you! Fantastic blog by the way!

    Reply

  276. you are in point of fact a good webmaster. The site loading pace is amazing. It sort of feels that you’re doing any distinctive trick. In addition, The contents are masterwork. you have performed a fantastic job in this subject!|

    Reply

  277. After going over a few of the articles on your site, I seriously like your technique of writing a blog. I book marked it to my bookmark website list and will be checking back soon. Take a look at my web site as well and tell me your opinion.|

    Reply

Leave a Reply

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