当前位置：Gxlcms > html代码 > CodeforcesRound#267(Div.2)_html/css_WEB-ITnose

CodeforcesRound#267(Div.2)_html/css_WEB-ITnose

时间：2021-07-01 10:21:17 帮助过：9人阅读

Codeforces Round #267 (Div. 2)

A：签到题，直接for一遍

B：取异或就是不同的数，然后bitcount一下判断即可

C：dp，dp[i]表示到i的最大值，然后对取与不取当前位置进行转移即可，要先把前缀和预处理出来

D：先利用map，把字符串hash掉，然后建图，现场在做的时候是直接记忆化搜索，不过这样处理不了环的情况，果断fst了，后来换了下姿势，先求强连通进行缩点，缩点完就是一个dag了，然后记忆化搜索即可

代码：

A：

#include int main() {	int n, p, q;	int ans = 0;	scanf("%d", &n);	while (n--) {		scanf("%d%d", &p, &q);		if (q - p >= 2) ans++;	}	printf("%d\n", ans);	return 0;}

#include #include int n, m, k;int bitcount(int x) {	int ans = 0;	while (x) {		ans += (x&1);		x >>= 1;	}	return ans;}const int N = 1005;int x[N];int main() {	scanf("%d%d%d", &n, &m, &k);	for (int i = 0; i <= m; i++)		scanf("%d", &x[i]);	int ans = 0;	for (int i = 0; i < m; i++) {		if (bitcount(x[i]^x[m]) <= k) ans++;	}	printf("%d\n", ans);	return 0;}

#include #include #include using namespace std;const int N = 5005;const long long INF = 0x3f3f3f3f3f3f3f;long long dp[N][N];int n, m, k;long long num[N], pre[N];int main() {	scanf("%d%d%d", &n, &m, &k);	for (int i = 1; i <= n; i++) {		scanf("%lld", &num[i]);		pre[i] = pre[i - 1] + num[i];	}	for (int i = 0; i <= n; i++)		for (int j = 0; j <= k; j++)			dp[i][j] = -INF;	dp[0][0] = 0;	for (int i = 1; i <= n; i++) {		for (int j = 0; j <= k; j++) {			if (j && i >= m)				dp[i][j] = max(dp[i][j], dp[i - m][j - 1] + pre[i] - pre[i - m]);			dp[i][j] = max(dp[i][j], dp[i - 1][j]);		}	}	printf("%lld\n", dp[n][k]);	return 0;}

#include #include #include #include #include #include #include #include using namespace std;typedef long long ll;const int N = 1000005;vector g[N], scc[N];int pre[N], lowlink[N], sccno[N], dfs_clock, scc_cnt;stack S;typedef pair pii;int n, m, hn;map hash;string str[N];pii s[N];pii p[N];pii dp[N];int vis[N];vector g2[N];void dfs_scc(int u) {	pre[u] = lowlink[u] = ++dfs_clock;	S.push(u);	for (int i = 0; i < g[u].size(); i++) {		int v = g[u][i];		if (!pre[v]) {			dfs_scc(v);			lowlink[u] = min(lowlink[u], lowlink[v]);		} else if (!sccno[v])			lowlink[u] = min(lowlink[u], pre[v]);	}	if (lowlink[u] == pre[u]) {		scc_cnt++;		pii tmp = s[S.top()];		while (1) {			int x = S.top(); S.pop();			tmp = min(tmp, s[x]);			sccno[x] = scc_cnt;			if (x == u) break;		}		p[scc_cnt] = tmp;	}}void find_scc(int n) {	dfs_clock = scc_cnt = 0;	memset(sccno, 0, sizeof(sccno));	memset(pre, 0, sizeof(pre));	for (int i = 0; i < n; i++)		if (!pre[i]) dfs_scc(i);	for (int i = 0; i < n; i++) {		for (int j = 0; j < g[i].size(); j++) {			int u = sccno[i], v = sccno[g[i][j]];			if (u == v) continue;			g2[u].push_back(v);		}	}}int get(string& str) {	for (int i = 0; i < str.length(); i++)		if (str[i] >= 'A' && str[i] <= 'Z')			str[i] = str[i] - 'A' + 'a';	if (!hash.count(str)) {		hash[str] = hn;		int cnt = 0;		for (int i = 0; i < str.length(); i++)			if (str[i] == 'r') cnt++;		s[hn].first = cnt;		s[hn].second = str.length();		hn++;	}	return hash[str];}pii dfs(int u) {	if (vis[u]) return dp[u];	vis[u] = 1;	dp[u] = p[u];	for (int i = 0; i < g2[u].size(); i++) {		int v = g2[u][i];		dp[u] = min(dp[u], dfs(v));	}	return dp[u];}int main() {	scanf("%d", &n);	for (int i = 0; i < n; i++) {		cin >> str[i];		get(str[i]);	}	scanf("%d", &m);	string u, v;	while (m--) {		cin >> u >> v;		int uu = get(u);		int vv = get(v);		g[uu].push_back(vv);	}	find_scc(hn);	ll ans1 = 0, ans2 = 0;	for (int i = 0; i < n; i++) {		int u = sccno[get(str[i])];		dfs(u);		ans1 += dp[u].first;		ans2 += dp[u].second;	}	cout << ans1 << " " << ans2 << endl;	return 0;}

CodeforcesRound#267(Div.2)_html/css_WEB-ITnose

人气教程排行