Codeforces Contest 1213
工作之余随便找几道简单的算法题练练手，权当锻炼思维。
A - Chips Moving
题意陷阱，题目写的很长很玄乎，其实是最简单的逻辑。分奇偶，选最少的一边
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
#define MAXN 150000
int main() {
int n, m, a = 0, b = 0;
scanf("%d", &n);
for(int i=0; i<n; ++i) {
scanf("%d", &m);
m&1 ? ++a : ++b;
}
printf("%d\n", a>b ? b : a);
return 0;
}
B - Bad Prices
单调栈
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
#define MAXN 150000
int buf[MAXN + 5];
int main() {
int T;
scanf("%d",&T);
while(T--) {
int n, ans = 0, top = 0;
scanf("%d", &n);
int tmp;
for(int i = 0; i < n; ++i) {
scanf("%d", &tmp);
while(top > 0 && buf[top-1] > tmp) {
--top;
++ans;
}
buf[top++] = tmp;
}
printf("%d\n", ans);
}
return 0;
}
C - Book Reading
根据底数的奇偶分情况讨论，规律没找透，被坑了一把...
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
#define MAXN 1000
int main() {
int T;
scanf("%d",&T);
while(T--) {
ll n, m, ans = 0;
scanf("%I64d%I64d", &n, &m);
if(n < m) {
ans = 0;
} else {
ll base = m % 10;
ll len = m & 1 ? 10 : 5;
ll sum = 0;
ll arr[10] = {0};
for(int i = 0; i < len; ++i) {
arr[i] = (base * i) % 10;
sum += arr[i];
}
ll div = n / m;
ans = (div / len) * sum;
ll last = div % len;
for(int i = 1; i <= last; ++i) {
ans += arr[i];
}
}
printf("%I64d\n", ans);
}
return 0;
}
D - Equalizing by Division
预处理，每个数字维护能得到的数字的队列，排序后顺序地找
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
#define INF (2 * 1000 * 1000 * 1000)
#define MAXN (200 * 1000 + 2)
int buf[MAXN];
vector<int> vec[MAXN];
int main() {
int n, k;
scanf("%d%d", &n, &k);
for (int i = 0; i < n; ++i) {
scanf("%d", &buf[i]);
}
sort(buf, buf + n);
for (int i = 0; i < n; ++i) {
int tmp = buf[i], cnt = 0;
while (tmp > 0) {
vec[tmp].push_back(cnt);
tmp = tmp >> 1;
++cnt;
}
vec[tmp].push_back(cnt); // tmp == 0
}
for (int i = 0; i < MAXN; ++i) {
if(!vec[i].empty()) {
sort(vec[i].begin(), vec[i].end());
}
}
int ans = INF;
for (int i = 0; i < MAXN; ++i) {
if(vec[i].size() >= k) {
int cast = 0;
for(int j = 0; j < k; ++j) {
cast += vec[i][j];
}
ans = min(ans, cast);
}
}
printf("%d\n", ans);
return 0;
}
E - Two Small Strings
贪心，以两种方式扩展基本串
- abc => aabbcc
- abc => abcabc
在模板串不冲突的情况下，扩展出来的串是不会有冲突的
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
#define INF (2 * 1000 * 1000 * 1000)
#define MAXN (100 * 1000)
char buf[MAXN];
vector<string> vec_template = {
"abc", "acb",
"bac", "bca",
"cab", "cba"
};
int main() {
int n;
string inp[2];
cin >> n >> inp[0] >> inp[1];
string ans;
if (inp[0][0] == inp[0][1] || inp[1][0] == inp[1][1]) {
for (int i = 0; i < vec_template.size(); ++i) {
string th = vec_template[i] + vec_template[i];
if (th.find(inp[0]) == string::npos &&
th.find(inp[1]) == string::npos) {
for (int j = 0; j < n; ++j) {
ans.append(vec_template[i]);
}
break;
}
}
} else {
for (int i = 0; i < vec_template.size(); ++i) {
string & th = vec_template[i];
if (th.find(inp[0]) == string::npos &&
th.find(inp[1]) == string::npos) {
for (int j = 0; j < th.size(); ++j) {
ans.append(n, th[j]);
}
break;
}
}
}
if (ans.empty()) {
cout << "NO" << endl;
} else {
cout << "YES" << endl;
cout << ans << endl;
}
return 0;
}
F - Unstable String Sort
给n个节点和k条有向路径，得到一个可能带环、带孤点的图，为图中每个点标一个小写字母：
- 在a1->a2的情况下，a1标的字母<=a2
也就是说对于一个环，或者说一个带环的连通块，其中所有节点的字母是相同的 - 字母数不少于k个
所以每个连通块必须是最小环
整体思路是找连通块，然后连通块缩成一个点，最后得到一个拓补排序，依次标字母
void wait();
G - Path Queries
题意是给出一棵树，然后对于每个query，去除树中所有边权值大于w的边，求剩下的图（森林）中的连通量（任意两点能连通即一个连通量）
离线处理，按权值对边排序后从小到大加边，用并查集表示森林，每次求到连通量并记录下来
#include <cstdio>
#include <algorithm>
#include <iostream>
#define MAXN 200000
struct Edge {
int from, to, val;
}edge[MAXN + 5];
bool comp(const Edge & left, const Edge & right) {
return left.val < right.val;
}
long long count;
int cnt[MAXN + 5];
int father[MAXN + 5];
int find(int now) {
father[now] = father[now]==now ? now : find(father[now]);
return father[now];
}
void join(int a, int b) {
int aa = find(a);
int bb = find(b);
count += 1LL * cnt[aa] * cnt[bb];
if (aa != bb) {
father[bb] = aa;
cnt[aa] += cnt[bb];
cnt[bb] = 0;
}
}
int query[MAXN + 5];
long long ans[MAXN + 5];
int main() {
int n, m, a, b, val, max_val = 0;
scanf("%d%d", &n, &m);
for (int i=0; i<n-1; ++i) {
scanf("%d%d%d", &a, &b, &val);
edge[i].from = a;
edge[i].to = b;
edge[i].val = val;
if (val > max_val) {
max_val = val;
}
}
for (int i=0; i<m; ++i) {
scanf("%d", &val);
query[i] = val>max_val ? max_val : val;
}
for (int i=1; i<=n; ++i) {
father[i] = i;
cnt[i] = 1;
}
std::sort(edge, edge+n-1, comp);
int idx = 0;
for (int now=1; now<=max_val; ++now) {
while (idx<n-1 && edge[idx].val<=now) {
join(edge[idx].from, edge[idx].to);
++idx;
}
ans[now] = count;
}
for (int i=0; i<m-1; ++i) {
printf("%lld ", ans[query[i]]);
}
printf("%lld\n", ans[query[m-1]]);
return 0;
}
