Contestant~. Rank 1938. Rating -45.掉分日记.md
A. United We Stand
题意
给定一个数组 \(a\)，将其分成两个非空数组 \(b, c\)，满足任意一个 \(c\) 中的元素都不是任意一个 \(b\) 中的元素的约数。
思路
很显然，若 \(x > y\)，则 \(x\) 一定不可能是 \(y\) 的约数。
因而，找出数组中最大值，并将等于最大值的所有数都放到 \(c\) 中，剩余的放到 \(b\) 中即可。
显然，若 \(a\) 中所有元素都相同，那么无解，否则必有解。
时间复杂度：\(O(n) - O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n;
cin >> n;
vector<int> a(n);
for(int i=0;i<n;i++) cin >> a[i];
sort(rall(a));
int cnt = 0;
for(int i=0;i<n;i++){
if(a[i] == a[0]) cnt ++;
else break;
}
if(cnt == n){
cout << -1 << '\n';
return;
}
cout << n - cnt << ' ' << cnt << '\n';
for(int i=cnt;i<n;i++) cout << a[i] << ' ';
cout << '\n';
for(int i=0;i<cnt;i++) cout << a[i] << ' ';
cout << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}速签
B. Olya and Game with Arrays
题意
给定 \(n\) 个序列，定义操作如下：
遍历所有序列；
对于每一个序列，取出一个数，放入任意一个其他序列中
更具体地说，每一个序列最多取出一个元素，但可以放入任意数量的元素。
输出操作之后，所有序列最小值之和的最大值。
思路
我们既然希望最小值之和尽可能小，那么我们肯定希望把每个序列的最小值都尽可能拿走。
显然，所有序列中的最小值无法不参与计算，且所有的最小值都可以转移到同一个序列中。
我们记所有最小值都转移到了序列 \(p\) 中。
那么，最后我们的答案就是 所有序列的次小值之和 \(-\) \(p\) 的次小值 \(+\) 所有序列的最小值。
那么，很显然，最后答案就是 次小值之和 \(-\) 次小值的最大值 \(+\) 最小值
时间复杂度：\(O(nm) - O(n m \log m)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n;
cin >> n;
vector<vector<int>> a(n + 1);
int mn = inf, sum = 0, mn2 = inf;
for(int i=1;i<=n;i++){
int c;
cin >> c;
a[i] = vector<int>(c);
for(int j=0;j<c;j++) cin >> a[i][j];
sort(all(a[i]));
sum += a[i][1];
mn = min(mn, a[i][1]);
mn2 = min(mn2, a[i][0]);
}
cout << sum - mn + mn2 << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}为什么做了这么久呢？为什么呢？
C. Another Permutation Problem
题意
给定整数 \(n\)，构造一个 \(n\) 的排列 \(p\)，使 \(\displaystyle (\sum_{i = 1}^{n} p_i \cdot i) - (\max_{j = 1}^{n} p_j \cdot j)\) 最大。
思路
这道题很有趣，\(std\) 的复杂度是 \(O(n ^ 3)\)，但存在一种 \(O(n ^ 2)\) 的做法。
做法很好猜，我们直接枚举拐点，从拐点开始，从 \(n\) 开始倒着放，变成诸如 \(1, 2, 3, 6, 5, 4\) 的形式，然后代入即可。
为什么呢？我也不知道。
引用官方题解的一句话：
We know about the \(O(N^2)\) solution in C, but we did not find a good suitable proof for it (and, using the method, we could achieve faster solutions).
时间复杂度：\(O(n ^ 2)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n;
cin >> n;
int sum = 0;
for(int k=1; k <= n; k++) {
int t = 0, mx = 0;
for (int i = 1; i < k; i++) {
t += i * i;
mx = max(i * i, mx);
}
int now = n;
for (int i = k; i <= n; i++) {
t += now * i;
mx = max(mx, now * i);
now--;
}
t -= mx;
sum = max(sum, t);
}
cout << sum << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}尝试找到一个证明，但失败了
D. Andrey and Escape from Capygrad
题意
给定 \(n\) 个传送装置，对应到数轴上，装置由两条线段表征。
两条线段的端点分别为给定的 \(l, r, a, b\)，满足 \(l \leq a \leq b \leq r\)。若位于 \([l, r]\) 上，那么可以传送到 \([a, b]\)。
现在，给定 \(q\) 个询问，每次询问给定一个点的坐标 \(x_j\)，输出最远能到达的点的下标。
思路
首先，我们可以贪心地认为，如果我们要使用某一个传送装置 \(i\)，一定会传送到 \(b_i\)，而非其他点。
证明是很显然的，因为如果我们希望从 \(p\) 传送到 \(b_i\) 的右边，那么我们也一定可以从 \(b_i\) 传送。
那么，我们也可以得到另一个结论：\(r_i\) 毫无用处。
因此，我们考虑使用扫描线，离线处理答案并输出。
我们记 \(ans_i\) 为 \(i\) 点可以到达的最大坐标，\(p_j\) 为第 \(j\) 个查询的答案，那么显然 \(p_j = \max(x_j, \max_{i = 1}^n {ans_i \vert l_i \le x_j \le r_i})\)。
具体地说，我们考虑从后往前枚举 \(b_i, x_j, l_i\)，并维护一个数据结构来更新 \(ans_i, p_j\)：
对于 \(b_i\)，我们将 \(ans_i\) 更新为数据结构中的最大值，并将最大值放入数据结构中；
对于 \(x_j\)，我们将 \(p_j\) 更新为数据结构中的最大值；
对于 \(l_i\)，我们将 \(ans_i\) 从数据结构中删去
如上，为了快速得到最大值，我们使用 \(\mathtt{multiset}\)，对于删除重复元素的其中一个元素，我们考虑使用 \(\mathtt{extract}\) 方法。
时间复杂度：\(O((n + q) \log (n + q))\)
对应AC代码
#define chatgpt "bits/stdc++.h"
#include chatgpt
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n;
cin >> n;
vector<tpi> ask;
vector<int> a(n);
for(int i=0;i<n;i++){
int l, r, A, b;
cin >> l >> r >> A >> b;
a[i] = b;
ask.pb(b, 3, i);
ask.pb(l, 1, i);
}
int q;
cin >> q;
//离线
vector<int> ans(q);
for(int i=0;i<q;i++){
cin >> ans[i];
ask.pb(ans[i], 2, i);
}
sort(rall(ask));
multiset<int> st;
for(auto [x, op, ind] : ask){
if(op == 3){
if(!st.empty()) a[ind] = max(a[ind], *st.rbegin());
st.emplace(a[ind]);
}else if(op == 2){
if(!st.empty()) ans[ind] = max(ans[ind], *st.rbegin());
}else st.extract(a[ind]); //extract保证只删除最早的一个
}
for(auto e : ans) cout << e << ' ';
cout << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}没想到这个贪心，直接想合并区间去了（