Codeforces Round #267 (Div. 2)

A：签到题，直接for一遍

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

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

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

代码：

A：

#include <cstdio>

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 <cstdio>
#include <cstring>

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 <cstdio>
#include <cstring>
#include <algorithm>

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 <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>
#include <string>
#include <iostream>
#include <map>
using namespace std;

typedef long long ll;

const int N = 1000005;

vector<int> g[N], scc[N];
int pre[N], lowlink[N], sccno[N], dfs_clock, scc_cnt;
stack<int> S;

typedef pair<ll, ll> pii;
int n, m, hn;
map<string, int> hash;
string str[N];
pii s[N];
pii p[N];
pii dp[N];
int vis[N];

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

Codeforces Round #267 (Div. 2)