Codeforces Round #267 (Div. 2)
5618 ワード
Codeforces Round #267 (Div. 2)
A:問題にサインして、直接for一回
B:异数か异なる数をとって、それからbitcountで判断すればいい
C:dp,dp[i]はiの最大値を表し、現在位置を取るか取らないかを移行すればよい.接頭辞と前処理を先に行う
D:まずmapを利用して、文字列hashを落として、それから図を建てて、現場はする時直接記憶化の検索で、しかしこのように環の情況を処理することができなくて、断固としてfstして、それから姿勢を変えて、先に強い連通を求めて縮める点を行って、縮める点は1つのdagで、それから記憶化の検索
E:欲張り+単調性メンテナンス、単調スタックメンテナンスを利用して、同じ数字に出会うたびに、真ん中の段でスタックをポップアップし、一致する数字を記録し、次にこの数字に出会ったとき、優先的に1つを構成し、その後の位置から探し続けることができます.
コード:
A:
B:
C:
D:
E:
A:問題にサインして、直接for一回
B:异数か异なる数をとって、それからbitcountで判断すればいい
C:dp,dp[i]はiの最大値を表し、現在位置を取るか取らないかを移行すればよい.接頭辞と前処理を先に行う
D:まずmapを利用して、文字列hashを落として、それから図を建てて、現場はする時直接記憶化の検索で、しかしこのように環の情況を処理することができなくて、断固としてfstして、それから姿勢を変えて、先に強い連通を求めて縮める点を行って、縮める点は1つのdagで、それから記憶化の検索
E:欲張り+単調性メンテナンス、単調スタックメンテナンスを利用して、同じ数字に出会うたびに、真ん中の段でスタックをポップアップし、一致する数字を記録し、次にこの数字に出会ったとき、優先的に1つを構成し、その後の位置から探し続けることができます.
コード:
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
", ans);
return 0;
}
B:
#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
", ans);
return 0;
}
C:
#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
", dp[n][k]);
return 0;
}
D:
#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;
}
E:
#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
const int N = 500005;
int n, b[N];
void solve() {
vector<int> ans;
int u = 0;
for (; u < n; u++) {
map<int, int> pre, sum;
stack<int> s;
for (int &i = u; i < n; i++) {
if (pre[b[i]]) {
for (int j = 0; j < 2; j++) {
ans.push_back(pre[b[i]]);
ans.push_back(b[i]);
}
break;
}
while (!s.empty() && (sum[b[i]] > 1 || sum[b[i]] == 1 && b[i] != s.top())) {
pre[s.top()] = b[i];
sum[s.top()]--;
s.pop();
}
s.push(b[i]);
sum[b[i]]++;
}
}
printf("%d
", ans.size());
for (int i = 0; i < ans.size(); i++)
printf("%d%c", ans[i], ans.size() - 1 == i? '
' : ' ');
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &b[i]);
solve();
return 0;
}