problem A. Twin Permutations
题目大意：给定一个全排列数组，要求输出另一个全排列数组，使得a1 + b1 <= a2 + b2 <= a3 + b3 <= … <= an + bn
思路：直接让所有数相等即可
数据范围：1 ≤ n ≤ 100 1 ≤ ai ≤ n
#include <iostream>
using namespace std;
int main()
{
int T; cin >> T;
while (T --)
{
int n; cin >> n;
for (int i = 0; i < n; i ++)
{
int x; cin >> x;
cout << n - x + 1 << " ";
}
cout << endl;
}
return 0;
}
problem B. Array merging
题目大意：给定两个长度为n的数组，将它们合并成另一个长度为2n的数组c，每次合并的时候可以从任意数组的开头拿过来一个元素，然后将该元素从原数组中删除，问合并数组中相同数字构成的最长子串是多长
思路：找到a中每个元素的最长连续相同子串，再找到b里面每个元素的最长连续相同子串，然后枚举所有元素的最长相同子串，然后答案取最大值
数据范围：1 ≤ n ≤ 2e5， 1 ≤ ai ≤ 2n， 1 ≤ bi ≤ 2n
#include <iostream>
#include <map>
using namespace std;
const int N = 2e5 + 10;
int a[N], b[N];
int main()
{
int T; cin >> T;
while (T --)
{
int n; cin >> n;
map<int, int> m1, m2;
for (int i = 0; i < n; i ++)
{
cin >> a[i];
m1[a[i]] = 1;
}
for (int i = 0; i < n; i ++)
{
cin >> b[i];
m2[b[i]] = 1;
}
for (int i = 0; i < n; i ++)
{
int j = i;
if (a[i] == a[j])
{
while (j < n && a[i] == a[j]) j ++;
m1[a[i]] = max(m1[a[i]], j - i);
i = j - 1;
}
}
for (int i = 0; i < n; i ++)
{
int j = i;
if (b[i] == b[j])
{
while (j < n && b[i] == b[j]) j ++;
m2[b[i]] = max(m2[b[i]], j - i);
i = j - 1;
}
}
int ans = 0;
for (int i = 0; i <= 2 * n; i ++) ans = max(ans, m1[i] + m2[i]);
cout << ans << endl;
}
return 0;
}
problem C. Copil Copac Draws Trees
吐槽：这题刷新了我单题错误类型数量，WA, TLE, MLE都出现了。。。
题目大意：给定n个点，n - 1条边，一个人按照如下方式画树，1：选定节点1开始，2：扩展从一个已经画好的节点开始扩展，3：检查是否绘制了所有点，没有则返回第一步。问这个人需要重复多少次这样的操作才可以画好树
思路：比赛的时候第一时间想到并查集，但并查集会tle，可以使用类似于下面给出的数据进行hack
5
4 5
3 4
2 3
1 2
由于每次都要遍历一遍所有边，因此时间复杂度是O(n^2)
正解是dfs，每次存一下扩展点的操作步数cnt，然后用f表示走到该边的代价，如果步数cnt[i] < cnt[father]那么说明要多走一步，否则则可以在f[father]的代价内完成
在参考了大佬写的之后发现了一种更为简单的写法,对于这题来说vector有着更可观的效率
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10, M = 2 * N;
vector<PII> e[N];
// int e[M], ne[M], h[N], w[M], idx;
int res = 0;
// void add(int a, int b, int c)
// {
// e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
// }
void dfs(int u, int father, int now, int tot)
{
res = max(res, tot);
for (auto i : e[u])
{
if (i.first == father) continue;
if (i.second < now) dfs(i.first, u, i.second, tot + 1);
else dfs(i.first, u, i.second, tot);
}
// for (int i = h[u]; ~i; i = ne[i])
// {
// int ver = e[i];
// if (ver == father) continue;
// if (w[i] < now) dfs(ver, u, w[i], tot + 1);
// else dfs(ver, u, w[i], tot);
// }
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
int T; cin >> T;
while (T --)
{
res = 0;
// res = idx = 0;
// memset(h, -1, sizeof h);
int n; cin >> n;
for (int i = 1; i <= n; i ++) e[i].clear();
for (int i = 0; i < n - 1; i ++)
{
int x, y; cin >> x >> y;
// add(x, y, i), add(y, x, i);
e[x].push_back({y, i});
e[y].push_back({x, i});
}
dfs(1, 0, 0, 1);
cout << res << endl;
}
return 0;
}
先给出并查集写法
#include <iostream>
#include <map>
using namespace std;
const int N = 2e5 + 10;
int p[N];
struct Edge
{
int a, b;
}e[N];
int find(int x)
{
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
bool check(int n)
{
for (int i = 1; i <= n; i ++)
{
if (p[i] != 1) return false;
}
return true;
}
int main()
{
int T; cin >> T;
while (T --)
{
int n; cin >> n;
for (int i = 1; i <= n; i ++) p[i] = i;
for (int i = 0; i < n - 1; i ++) cin >> e[i].a >> e[i].b;
int ans = 0;
while (true)
{
if (check(n))
{
cout << ans << endl;
break;
}
bool flag = true;
for (int i = 0; i < n - 1; i ++)
{
int k1 = find(e[i].a), k2 = find(e[i].b);
if (k1 == 1 && k2 == 1) continue;
if (k1 != k2 && (k1 == 1 || k2 == 1))
{
if (k1 == 1) p[k2] = k1;
else p[k1] = k2;
}
}
// for (int i = 1; i <= n; i ++) cout << p[i] << " ";
ans ++;
}
}
return 0;
}
dfs写法
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
vector<int> e[N];
vector<int> a(N), b(N), fa(N), cnt(N), f(N);
void dfs(int u, int father)
{
fa[u] = father;
for(auto i : e[u])
{
if(i == father) continue;
dfs(i, u);
}
}
void dfs1(int u, int father)
{
for(auto i : e[u])
{
if(i == father) continue;
else if(cnt[i] < cnt[u])
{
f[i] = f[u] + 1;
dfs1(i, u);
}
else
{
f[i] = f[u];
dfs1(i, u);
}
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
int T; cin >> T;
while(T --)
{
int n;
cin >> n;
for (int i = 1; i <= n; i ++) e[i].clear();
for(int i = 0; i < n - 1; i ++)
{
int u, v; cin >> u >> v;
a[i] = u, b[i] = v;
e[u].push_back(v);
e[v].push_back(u);
}
fa.clear();
dfs(1, 0);
cnt.clear();
for(int i = 0; i < n - 1; i ++)
{
if(fa[a[i]] == b[i]) swap(a[i], b[i]);
cnt[b[i]] = i;
}
f.clear();
f[1] = 1;
dfs1(1, 0);
int res = 0;
for(int i = 1;i <= n; i ++) res = max(res, f[i]);
cout << res << endl;
}
return 0;
}
链式向前星加bfs写法
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 2e5 + 10, M = 2 * N;
int e[M], ne[M], h[N], idx;
int a[N], b[N], fa[N];
int cnt[N], f[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u, int father)
{
fa[u] = father;
for (int i = h[u]; ~i; i = ne[i])
{
int ver = e[i];
if (ver == father) continue;
dfs(ver, u);
}
}
void bfs(int u)
{
queue<int> q;
q.push(u);
while (!q.empty())
{
auto t = q.front();
q.pop();
for (int i = h[t]; ~i; i = ne[i])
{
int ver = e[i];
if (f[ver]) continue;
else if (cnt[ver] < cnt[t])
{
f[ver] = f[t] + 1;
q.push(ver);
}
else
{
f[ver] = f[t];
q.push(ver);
}
}
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
int T; cin >> T;
while (T --)
{
idx = 0;
memset(h, -1, sizeof h);
int n; cin >> n;
for (int i = 0; i < n - 1; i ++)
{
cin >> a[i] >> b[i];
add(a[i], b[i]), add(b[i], a[i]);
}
dfs(1, 0);
for (int i = 0; i < n - 1; i ++)
{
if (fa[a[i]] == b[i]) swap(a[i], b[i]);
cnt[b[i]] = i;
}
memset(f, 0, sizeof f);
f[1] = 1;
bfs(1);
cout << *max_element(f + 1, f + 1 + n) << endl;
}
return 0;
}
