\(\rm Codeforces ~ Round ~ 758 ~ (Div.1 + Div.2)\)
A. Find Array
给定 \(n\)，试找出 \(n\) 个数 \(a_1,a_2, \cdots,a_n\)，满足：
- \(\forall 1 \leq i \leq n,1 \leq a_i \leq 10^9\)。
- \(a_1 < a_2 < \cdots < a_n\)
- \(\forall 2\leq i \leq n,a_{i-1}\nmid a_i\)
\(T\) 组数据。
对于 \(100\%\) 的数据，满足 \(1 \leq T \leq 100,1 \leq n \leq 1000\)。
sol
显然 \(2,3, \cdots,n+1\) 是满足条件的一组解。
如果想不到的话，也可以输出前 \(n\) 个质数，这也是满足条件的一组解。
时间复杂度为 \(\mathcal{O}(Tn)\)。
#include <bits/stdc++.h>
using namespace std;
int T, n;
signed main()
{
cin >> T;
while(T--)
{
cin >> n;
for(int i = 2; i <= n + 1; ++i) cout << i << " ";
cout << "\n";
}
}
B. Build the Permutation
给定 \(n,a,b\)，试找出 \(n\) 个数 \(p_1,p_2, \cdots,p_n\)，满足有且仅有 \(a\) 个顶和 \(b\) 个谷。
定义：
- 若 \(p_{i-1} < p_i > p_{i+1}\)，则称之为一个顶（其中 \(2\leq i \leq n-1\)）。
- 若 \(p_{i-1} > p_i < p_{i+1}\)，则称之为一个谷（其中 \(2\leq i \leq n-1\)）。
\(T\) 组数据。
对于 \(100\%\) 的数据，满足 \(1 \leq T \leq 10^4,2 \leq n \leq 10^5,0 \leq a \leq b \leq n\)。
sol
显然如果 \(a+b+2>n\)，那么肯定无解。
然后，我们可以得出一个结论：\(|a-b| \leq 1\)。
简单来说，若出现一个顶，那么必然带有一个谷，反之也是。
最后可能会多出来一个顶或谷。
分类讨论即可。
#include <bits/stdc++.h>
using namespace std;
int T, n, a, b;
signed main()
{
cin >> T;
while(T--)
{
cin >> n >> a >> b;
if(a + b + 2 > n || abs(a - b) > 1)
{
puts("-1");
continue;
}
if(a == b)
{
int lb = 1, ub = (a + 1) * 2;
for(int i = 0; i <= a; ++i) printf("%d %d ", lb++, ub--);
for(int i = (a + 1) * 2 + 1; i <= n; ++i) printf("%d ", i);
}
else
{
int rev = 0;
if(b == a + 1) rev = 1, ++a;
int lb = n - a - a + 1, ub = n;
for(int i = 0; i < a; ++i) printf("%d %d ", (rev == 0 ? lb++ : n - (lb++) + 1), (rev == 0 ? ub-- : n - (ub--) + 1));
for(int i = n - a - a; i > 0; --i) printf("%d ", (rev == 0 ? i : n - i + 1));
}
puts("");
}
}
C. Game Master
有 \(n\) 名玩家在玩游戏。
每名玩家有两个属性值：\(a_i\) 代表在地图 A 比赛的力量，\(b_i\) 表示在地图 B 比赛的力量。
同一张地图里所有玩家的力量都不相同。
你可以安排 \(n−1\) 场比赛，每次可以选择任意比赛场地和任意两个未淘汰的玩家进行比赛。
比赛时，力量大的玩家获胜，失败则被淘汰。
现在要求求出：对于每个玩家，是否有可能通过某种安排使其获胜？
\(T\) 组数据。
对于 \(100\%\) 的数据，满足 \(1 \leq T \leq 100,1 \leq n \leq 10^5,1 \leq a_i,b_i \leq 10^9\)。
sol
我们对于地图 A 和 B 中的所有玩家分别按照力量值排序，之后把力量大的向力量小的连边。
每个地图只连一个链，不需要连成完全图。
这两个地图在同一个图里连边。
之后发现这样连出的图里，一个环里的所有的玩家都可以赢。
找下环即可。
时间复杂度 \(\mathcal O(T n \log n)\)
#include <bits/stdc++.h>
using namespace std;
const int _ = 100005;
#define pii pair<int, int>
int T, n;
vector<pii> a, b;
vector<int> d[_];
bool vis[_];
void dfs(int u)
{
vis[u] = 1;
for(int v : d[u])
{
if(!vis[v]) dfs(v);
}
}
void init()
{
a.clear();
b.clear();
for(int i = 0; i < _; i++)
{
d[i].clear();
vis[i] = 0;
}
}
signed main()
{
cin >> T;
while(T--)
{
init();
cin >> n;
for(int i = 0, x; i < n; i++)
{
cin >> x;
a.push_back({x, i});
}
for(int i = 0, x; i < n; i++)
{
cin >> x;
b.push_back({x, i});
}
sort(a.begin(), a.end());
reverse(a.begin(), a.end());
sort(b.begin(), b.end());
reverse(b.begin(), b.end());
for(int i = 1; i < a.size(); i++)
{
d[a[i].second].push_back(a[i - 1].second);
d[b[i].second].push_back(b[i - 1].second);
}
dfs(a[0].second);
dfs(b[0].second);
for(int i = 0; i < n; i++)
cout << vis[i];
cout << "\n";
}
return 0;
}