CF#892 div2
过了abc，卡在了d
A
将数组a拆分乘数组b和c，使得满足任意c[i]不是b[j]的因子，b和c中至少存在一个数。
如果不能输出-1
法一：
巧妙构造：
因为一个大的数不可能是一个小的数的因子，所以我把最大的数(最大的数数量可能有很多个，需要全都放在c里面，因为两个相等的数之间也互为因子)放在c后，其他剩下的数放在b，即构造成功。
只有当所有的数都是最大的数(也就是a中所有数都相等)，没有数放到b，输出-1
// 赛时代码
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define x first
#define y second
#define endl "\n"
using namespace std;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int INF = 0x3f3f3f3f;
void solve()
{
int n;
cin >> n;
vector<int> a(n);
int maxv = 0;
for (int i = 0; i < n; i++)
{
cin >> a[i];
maxv = max(maxv, a[i]);
}
sort(a.begin(), a.end());
if (maxv == a[0])
{
cout << "-1" << endl;
return;
}
int pos = 0;
for (int i = 0; i < a.size(); i++)
if (a[i] == maxv)
{
pos = i;
break;
}
cout << pos << ' ' << n - pos << endl;
for (int i = 0; i < pos; i++)
cout << a[i] << ' ';
cout << endl;
for (int i = pos; i < a.size(); i++)
cout << a[i] << ' ';
cout << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
法二： from jiangly
SCC
如果 x % y == 0，连接一条 x -> y 的有向边。
一个强连通分量里面的点互相之间都满足 x % y == 0，所以一个强连通分量里面的点需要全放在b或者c里面。
如果整个图只有一个强连通分量的话，故输出-1
如果大于一个的话，因为SCC后按照下标递减的顺序就是拓扑排序
所以 bel[i] == 0 => 表示的是只有入度没有出度的那个点
除了这个强连通分量里的点都不是这些点的因子，其他点都只可能是这些点的倍数
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define x first
#define y second
#define endl "\n"
using namespace std;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int INF = 0x3f3f3f3f;
struct SCC
{
int n;
vector<vector<int>> adj;
vector<int> stk;
vector<int> dfn, low, bel;
int cur, cnt;
SCC() {}
SCC(int n)
{
init(n);
}
void init(int n)
{
this->n = n;
adj.assign(n, {});
dfn.assign(n, -1);
low.resize(n);
bel.assign(n, -1);
stk.clear();
cur = cnt = 0;
}
void addEdge(int u, int v)
{
adj[u].push_back(v);
}
void dfs(int x)
{
dfn[x] = low[x] = cur++;
stk.push_back(x);
for (auto y : adj[x])
{
if (dfn[y] == -1)
{
dfs(y);
low[x] = min(low[x], low[y]);
}
else if (bel[y] == -1)
{
low[x] = min(low[x], dfn[y]);
}
}
if (dfn[x] == low[x])
{
int y;
do
{
y = stk.back();
bel[y] = cnt;
stk.pop_back();
} while (y != x);
cnt++;
}
}
vector<int> work()
{
for (int i = 0; i < n; i++)
{
if (dfn[i] == -1)
{
dfs(i);
}
}
return bel;
}
};
void solve()
{
int n;
cin >> n;
SCC g(n);
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (a[i] % a[j] == 0)
g.addEdge(i, j);
auto bel = g.work();
if (bel == vector(n, 0))
{
cout << -1 << endl;
return;
}
vector<int> b, c;
for (int i = 0; i < n; i++)
{
if (bel[i] == 0)
b.push_back(i);
else
c.push_back(i);
}
cout << b.size() << ' ' << c.size() << endl;
for(auto i : b)
cout << a[i] << " \n"[i == b.back()];
for(auto i : c)
cout << a[i] << " \n"[i == c.back()];
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
B
最小的 + 选 n-1 组中的次小值
- 如果最小的不动，那么就是最小的加上其他所有组的次小值
- 如果最小的动，这组变成加次小值，最小的移动到的组变成加最小值
两种情况是等价的
比赛的时候我是暴力枚举把哪 n-1 行的最小值扔到 另外一行 在加上这一行(包括被扔过来的)的最小值
// 赛时代码
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define x first
#define y second
#define endl "\n"
using namespace std;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int INF = 0x3f3f3f3f;
void solve()
{
int n, m;
cin >> n;
vector<int> vm1(n + 1), vm2(n + 1);
vector<vector<int>> a(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> m;
int minv1 = INF, minv2 = INF;
a[i].resize(m + 1);
for (int j = 1; j <= m; j++)
{
cin >> a[i][j];
if (a[i][j] < minv1)
{
minv2 = minv1;
minv1 = a[i][j];
}
else if (a[i][j] < minv2)
{
minv2 = a[i][j];
}
}
vm1[i] = minv1;
vm2[i] = minv2;
}
LL ans = 0;
for (int i = 1; i <= n; i++)
{
LL res = 0;
int minv = vm1[i];
for (int j = 1; j <= n; j++)
if (i != j)
{
res = res + (LL)vm2[j];
minv = min(minv, vm1[j]);
}
res = res + (LL)minv;
ans = max(ans, res);
}
cout << ans << endl;
// for (int i = 1; i <= n; i++)
// cerr << i << ' ' << vm1[i] << ' ' << vm2[i] << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
from jiangly
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define x first
#define y second
#define endl "\n"
using namespace std;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int INF = 0x3f3f3f3f;
void solve()
{
int n;
cin >> n;
vector<int> a;
int min1 = 1E9;
int min2 = 1E9;
LL ans = 0;
for (int i = 0; i < n; i++)
{
int m;
cin >> m;
a.resize(m);
for (int j = 0; j < m; j++)
{
cin >> a[j];
}
nth_element(a.begin(), a.begin() + 1, a.end());
min1 = min(min1, a[0]);
min2 = min(min2, a[1]);
ans += a[1];
}
ans -= min2;
ans += min1;
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
Trick
nth_element(a.begin(), a.begin() + x, a.end())
作用是将第(x + 1)小的数放在a[x]上
并且满足
a[0] ~ a[x - 1] <= a[x] <= a[x] ~ a[n - 1]
所以
nth_element(a.begin(), a.begin() + 1, a.end())
将第二小的数放到了a[1]
进而a[0]只能为最小的数