Codeforces Round #792 (Div. 1 + Div. 2) A - E 题解
传送门
A. Digit Minimization
一开始以为是只能换相邻的，wa 了好多发
如果是 n = 2 的话，只能是第二个
其他的情况就都是最小的那个，把最小的放到第一个，然后剩下的慢慢磨
#include
#include
#include
#include
#include
#include
#include
#include B. Z mod X = C
一个构造题
因为给了约束条件： \(1 \leq a < b < c \leq 10^8\)
我们按照条件构造一下就行了
$z = c, y = b, x = b * c + a $
构造方式还挺多，随便构造就行
#include
#include
#include
#include
#include
#include
#include
#include C. Column Swapping
这个题目的 pretest 真的太弱了吧
首先要明确的是，如果成立的话，最终排序后的数组的样子是唯一的
然后我们就找对于每一行有多少列是不匹配的，然后换就行，如果有 3 个及以上，显然不成立
找到要换的两列后，直接交换这两列，判断是否成立就行
我被 hack 是引入了原本的 index 作为判断，显然有点多余，还会错
#include
#include
#include
#include
using namespace std;
const int maxn = 2e5 + 10;
vectorgra[maxn], a[maxn], nex[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--)
{
int n, m;
cin >> n >> m;
int f = 1;
for(int i=0; i> x;
gra[i].push_back(x);
a[i].push_back(x);
}
sort(a[i].begin(), a[i].end());
for(int j=0; j= 3) f = 0;
}
if(f == 0) {cout << -1 << endl; continue;}
int l = -1, r = -1;
for(int i=0; i D. Traps
贪心
第一个要明确的是，我们一定要取完 k 个。如果有一个解是没取完 k 个的，必然有一个更优解：取走最后一个没有被取走的陷阱
假设我们只取一个，那么对于第 \(i\) 个位置的陷阱，我们跳过这个陷阱，减少的伤害值应该是 \(a_i - (n - i)\)，\(a_i\) 是本身陷阱的值，\(n - i\) 是他给后面的陷阱提供的额外值
如果我们取 \(k\) 个，那么额外值就不一定是 \(n - i\) 了，但是这并不会对我们之前的贪心造成影响。
跳到整个局面来看，我们取 k 个，对于第一个拿走的陷阱，他造成的额外值，必然会减少 \(k - 1\)，因为后面有 \(k - 1\) 个陷阱要拿走，同理对于第二个也是 \(k - 2\)
所以这个额外值的减少对于整个局面来说是个定值：
\[\sum_{i=0}^{k-1}i \]因此最终只需要按照 \(a_i - (n - i)\) 进行贪心，选择最大的 k 个即可
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int num[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--)
{
ll n, m;
cin >> n >> m;
ll sum = 0;
for(int i=1; i<=n; i++)
{
cin >> num[i];
sum += num[i];
num[i] = num[i] - (n - i);
}
sort(num + 1, num + 1 + n);
for(int i=0; i E. MEX vs DIFF
贪心
先把 MEX 的最大值计算出来，然后贪心的找比 MEX 大的数，改变他们的值去填补 MEX
贪心的地方在于：我们已知 MEX 一定能够补充到一开始计算的最大值，因此我们选择哪些数是一个问题
如果我们选择的数只出现了单个，那么 DIFF 没变
如果我们选择的数出现了若干次，那么 DIFF + 1
因此我们要贪心出现次数少的
如果是一边推 MEX，一边选取最大值的情况，不能保证贪心是最优秀的，因为没有考虑上述的情况
给一个例子：
10 2
2 3 4 5 6 8 10 10 10 10
#include
#include
#include
#include
#include
#include
#include
#include