Codeforces Round #656 (Div. 3)
Codeforces Round #656 (Div. 3)
待补
- G
1. 题目分析
- A: 思维
- B: 思维
- C: 思维
- D: 思维+dfs
- E: 拓扑排序性质
- F: 模拟
2. 题解
A. Three Pairwise Maximums
题意: 给定t个测试样例,每个测试样例给定x，y，z，需要找到a，b，c三个数，使得max(a, b)=x, max(a, c)=y, max(b, c)=z，输出a，b，c(顺序无所谓)，如果找不到输出NO。t~2e4, a、b、c~1e9
题解： max(a, b) = x, max(a, c) = y, 则max(a, b, c) = max(x, y)，同理max(a, b, c) = max(x, y) = max(y, z) = max(x, z)，则①x=y=z，②x < y = z。因此，只需要把x, y, z排序，最小的为x，中间的为y，最大的为z，判断y是否为z，不相等为NO，相等的话，输出x, x, y
代码:
#include <bits/stdc++.h>
using namespace std;
int main() {
int a[3];
int T ;
cin >> T;
while (T--) {
for (int i = 0; i < 3; ++i) scanf("%d", &a[i]);
sort(a, a + 3);
if (a[1] != a[2]) {
cout << "NO\n";
continue;
}
cout << "YES\n";
cout << a[0] << " " << a[0] << " " << a[1] << endl;
}
return 0;
}
B. Restore the Permutation by Merger
题意： t个测试样例，每个测试样例输入长度为2n的数组，该数组是由两个不改变相对位置的全排列数组merge而成的，每次要求输出原来的全排列数列。t ~ 400，n ~ 50
题解： 观察可以知道，同样的数字只需要取前一个出现的那个即可，因此，只需要扫一遍，如果这个数字没出现过，那么打印；如果没出现过，那么跳过
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
unordered_map<int, int> mp;
for (int i = 1, x; i <= n * 2; ++i) {
cin >> x;
if (mp.count(x)) continue;
cout << x << " " ;
mp[x] = 1;
}
cout << endl;
}
return 0;
}
C. Make It Good
题意: 定义一个good数列：每次从该数列的头或者尾拿出一个数字，拿出来的数字是单调不减的。现在给定t个测试样例，每个测试样例给定一个长度为n的数列，问需要将长度为n的数列的删除前k个数字，使之变为good数列，这个k最小取多少？\(\sum_{} n~2e5\)
题解: 对于任意两个数字x, y，如果这两个数字都是从前面拿出，那么需要x <= y；对于任意两个数字x和y，如果这两个数字都是从后面被拿出，那么需要x >= y，因此只需要倒着往前扫，找到类似小山坡的形状，即先增加后下降，一旦再次上升，即为到达边界。
代码:
#include <bits/stdc++.h>
using namespace std;
int const N = 2e5 + 10;
int a[N];
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
for (int i = 1; i <= n ; ++i) {
scanf("%d", &a[i]);
}
if (n == 1) {
cout << 0 << endl;
continue;
}
int i = n - 1;
while (a[i] >= a[i + 1] && i >= 1) i--;
while (a[i] <= a[i + 1] && i >= 1) i--;
cout << i << endl;
}
return 0;
}
D. a-Good String
题意： 定义一个'a'-good字符串为:
- 字符串长度为1，且只有一个字符'a'
- 字符串长度大于1，前半部分全为'a'，后半部分为'b'-good字符串
- 字符串长度大于1，后半部分全为'a,',前半部分为'b'-good字符串
现在有t个测试样例，每个测试样例给定一个长度为n的字符串，每次操作可以把任意位置的一个字符替换为任意一个小写字母，问最少需要多少次这样的操作后，才能使得当前字符串为'a'-good字符串?保证所有的字符串总长度为2e5
题解： 仔细分析可知，'a'-good字符串是递归定义的，肯定为一半为a，另一半的前一半为b。另一半的后一半的前一半为c，。。。，即出现16-8-4-2-1这样的情况，因此每次只需要把当前字符串分为两半，分别统计两半内当前字符哪个出现的多，少的那个则为b字符串处理，不断dfs即可，由于这个规模不大，因此不会超时
代码：
#include <bits/stdc++.h>
using namespace std;
int T, n;
int const N = 2e5 + 10;
char str[N];
int dfs(int st, int ed, char a) {
if (st == ed) {
if (str[st] != a) return 1;
else return 0;
}
int cnt1 = 0, cnt2 = 0;
for (int i = st; i <= (st + ed) / 2; ++i) if (str[i] != a) cnt1++;
for (int i = (st + ed) / 2 + 1; i <= ed; ++i) if (str[i] != a) cnt2++;
return min(cnt1 + dfs((st + ed) / 2 + 1, ed, a + 1), cnt2 + dfs(st, (st + ed) / 2, a + 1));
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
cin >> T;
while (T--) {
cin >> n;
scanf("%s", str);
cout << dfs(0, n - 1, 'a') << endl;
}
return 0;
}
E. Directing Edges
题意： 给定t个测试样例，每个测试样例给定n和m，n为图的点数，m为图的边数，给定m条边，每条边为op, a, b。如果op为1,表示有一条有向边a -> b;如果op为0，表示a和b之间有一条无向边。现在要求把无向边变成有向边(把a--b变成a->b或b->a)，使得最后这m条边没有环。【累加】n、m~2e5
题解： 题意可以转换为现在有一张有向图，要求向这张有向图内加入有向边，使得这张有向图没有环，求加边的方法。因此，可以先做一次拓扑排序，求出拓扑序，如果没有拓扑序，说明已经存在环；否则，只需要加入拓扑序小的指向拓扑序大的边即可。(因为想要形成环，必须有回路，则必须a->b，同时b->a,一旦出现拓扑序，说明存在a->b,不存在b->a,因此只要不加入b->a,则不可能出现环)
代码如下：
#include<bits/stdc++.h>
using namespace std;
int const N = 2e5 + 10;
int t, n, m;
set<int> point;
int e[N * 2], ne[N * 2], idx, h[N];
int d[N], sorted[N];
vector<pair<int, int> > undirect, direct;
vector<int> ans;
struct Edge{
int op, u, v;
};
vector<Edge> E;
void top_sort() {
queue<int> q;
for (int i = 1; i <= n; ++i) {
if (!d[i]) {
// cout << i << endl;
q.push(i);
}
}
while (q.size()) {
auto t = q.front();
q.pop();
ans.push_back(t);
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
d[j]--;
if (!d[j]) {
q.push(j);
}
}
}
for (int i = 0; i < ans.size(); ++i) {
sorted[ans[i]] = i + 1;
}
return ;
}
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
cin >> t;
while (t--) {
memset(h, -1, sizeof h);
memset(d, 0, sizeof d);
idx = 0;
E.clear();
memset(sorted, 0, sizeof sorted);
ans.clear();
cin >> n >> m;
for (int i = 0, op, a, b; i < m; ++i) {
scanf("%d%d%d", &op, &a, &b);
E.push_back({op, a, b});
if (op == 1) {
add(a, b);
d[b]++;
}
}
top_sort();
// cout << ans.size() << endl;
if (ans.size() != n) {
cout << "NO\n";
continue;
}
cout << "YES\n";
for (int i = 0; i < E.size(); ++i) {
if (E[i].op == 1) {
cout << E[i].u << " " << E[i].v << endl;
}
else {
if (sorted[E[i].u] < sorted[E[i].v]) cout << E[i].u << " " << E[i].v << endl;
else cout << E[i].v << " " << E[i].u << endl;
}
}
}
return 0;
}
F. Removing Leaves
题意： t个测试样例，每个测试样例给定一棵有n个节点的无根树，每次选择一个有k个叶子的节点，删除这k个叶子，问最多能够做多少次这样的操作？第一行输入t，而后每个样例先输入n和k，再输入n-1条边。t ~ 2e4, \(\sum_{}n<=2e5\)
题解： 由于每次只能删除某个点的k个叶子，因此使用一个队列把能够删除的点给维护起来即可，每次删除k个叶子节点后，看是否能产生新的叶子，产生新的拥有k个叶子以上的节点，有的话放入队列。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
vector<int> g[N];
int leave[N];
int all[N];
int t,n,k;
int main () {
scanf("%d",&t);
while (t--) {
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++) g[i].clear(),leave[i]=0,all[i]=0;
for (int i=1;i<n;i++) {
int x,y;
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
if (k==1) {
printf("%d\n",n-1);
continue;
}
int ans=0;
for (int i=1;i<=n;i++) {
all[i]=g[i].size();
if (all[i]==1) leave[g[i][0]]++;
}
int inq[n+1]={0};
queue<int> q;
for (int i=1;i<=n;i++) {
if (leave[i]>=k) {
q.push(i);
inq[i]=1;
}
}
while (!q.empty()) {
int u=q.front();
q.pop();
ans++;
leave[u]-=k;
all[u]-=k;
inq[u]=0;
if (leave[u]>=k) {
q.push(u);
inq[u]=1;
}
if (all[u]==1) {
all[u]=0;
for (auto v:g[u]) {
if (all[v]) {
leave[v]++;
if (leave[v]>=k&&!inq[v]) {
q.push(v);
inq[v]=1;
}
}
}
}
}
printf("%d\n",ans);
}
}
