CF1684
Codeforces Round 792 (Div. 1 + Div. 2)
CF1684A
CF1684A题意
有一个用十进制表示的没有前导零的正整数 \(n\) 。Alice 和 Bob 正在用这个数玩一个游戏。Alice 先手，他们轮流进行游戏。
在她的这一轮中，Alice 应该交换这个数中的任何不同位置的两位。轮到 Bob 时，他每次都会删除这个数的末一位。当这个数只剩一位时，游戏结束。
你需要找出 Alice 用最佳方法在最后找出的最小数。
CF1684A题解
如果只有两位数就没辙了，只能是最后一位。
否则就是最小的那一位。
CF1684A代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
int n;
char ch[100];
signed main(){
int T = read();
while(T--){
scanf("%s",ch + 1);
n = strlen(ch + 1);
if(n == 2){putchar(ch[2]);}
else{
int x = 10;
for(int i = 1;i <= n;i++)x = min(x,ch[i] - '0');
putchar(x + '0');
}
puts("");
}
return 0;
}
CF1684B
CF1684B题意
给你三个数字 \(a,b,c(a<b<c)\)，让你构造三个数字 \(x,y,z\)，满足
CF1684B题解
不难发现当 \(x=a+b+c,y=b+c,z=c\) 时满足条件，证明略。
CF1684B代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
signed main(){
int T = read();
while(T--){
int a = read(), b = read(), c = read();
printf("%lld %lld %lld\n",a + b + c,b + c,c);
}
return 0;
}
CF1684C
link
当前用时：33:34.25
CF1684C题意
如果一个表格每行都单调不降，称它为好的。
给你 \(t\) 个 \(n_i\) 行 \(m_i\) 列的表格，对于每个表格，询问是否能通过调换某两列 （不一定不同） 使得这个表格是好的（这样的操作需要且仅能执行一次）。如果可以，输出两列的编号；不可以，输出 \(-1\)。
CF1684C题解
先排序，然后看哪里不同就交换哪里，然后只能操作一次，交换完了在看下是不是正确的即可。
CF1684C代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 2e5 + 10;
vector<int> vec[maxn], srt[maxn];
int n, m;
void solve(){
n = read(); m = read();
for(int i = 1;i <= n;i++){
vec[i].clear();vec[i].push_back(-114514);
for(int j = 1;j <= m;j++)vec[i].push_back(read());
srt[i] = vec[i];
sort(srt[i].begin(),srt[i].end());
}
int pos0 = -1, pos1 = -1;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
if(srt[i][j] != vec[i][j]){
if(pos0 == -1){pos0 = j;continue;}
if(pos1 == -1){pos1 = j;break;}
}
}
if(pos0 != -1 && pos1 != -1)break;
}
for(int i = 1;i <= n;i++){
swap(vec[i][pos0],vec[i][pos1]);
for(int j = 1;j <= m;j++)
if(vec[i][j] != srt[i][j]){puts("-1");return;}
}
if(pos0 == -1 && pos1 == -1)pos0 = pos1 = 1;
printf("%d %d\n",pos0, pos1);
}
signed main(){
int T = read();
while(T--)solve();
return 0;
}
CF1684D
link
当前用时：47:52.82
Remote Judge 又双叒叕炸了，好似
CF1684D题意
这里有 \(n\) 个陷阱，你需要按照给出的顺序穿过这些陷阱，每个陷阱将会对你造成 \(a_i\) 的伤害
你有至多 \(k\) 次机会跳过这些陷阱，可以避免你所跳过的陷阱给你造成的伤害，不过接下来的所有陷阱都会给你多造成 \(1\) 点伤害
跳过陷阱所造成的额外伤害会叠加，如果你当前已经跳过了 \(3\) 个陷阱，接下来的陷阱给你造成的伤害将会是 \(a_i +3\)
现在需要你求出受到的最小伤害
CF1684D题解
首先，如果只考虑跳一次陷阱，这道题就很简单了。
答案是 \(\sum_{i=1}^na_i\)\(-\max_{i=1}^n(a_i-n+i)\) 对吧。
那如果可以跳很多次呢？
答案是前 \(k\) 大的 \(a_i-n+i\) 吗？
好像不对吧，举个栗子，你在 \(7,2\) 两个位置分别跳了一次，那么在 \(2\) 位置计算的答案就应该是 \(a_2-n+2+1\)，因为在 \(7\) 位置是不受伤的。
将结论扩展到 \(k\) 个数，如果先不考虑后来躲开的伤害对前面的影响，那么答案就是 \(\sum_{i=1}^na_i\) 减去前 \(k\) 大的 \((a_i-n+i)\)。
如果考虑后来躲开的伤害呢？
从排序第一个躲闪开始看起，它后面的 \(k-1\) 个躲闪对它的贡献是 \(1-k\)，第二个同理。
然后最终答案就是 \(\sum_{i=1}^na_i\) 减去前 \(k\) 大的 \((a_i-n+i)\) 再减去 \(\frac{k\times (k-1)}{2}\)
CF1684D代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 2e5 + 10;
int n, k;int a[maxn];
priority_queue<int,vector<int>,less<int> > que;
signed main(){
int T = read();
while(T--){
n = read(); k = read();
while(!que.empty())que.pop();
int ans = 0;
for(int i = 1;i <= n;i++){
ans += (a[i] = read());
que.push(a[i] - (n - i));
}
for(int i = 1;i <= k;i++){ans -= que.top();que.pop();}
printf("%lld\n",ans - k * (k - 1) / 2);
}
return 0;
}
CF1684E
link
当前用时:2:27:18.34
另：有的时候停下来想想会有意想不到的收获。
CF1684E题意
给你一个大小为n的数组a，保证数组内元素非负，你可以执行以下操作k次：
在一次操作中将数组内任意一个数字改为任何一个非负整数。
现在定义这个数组的成本为 \(DIFF(a)−MEX(a)\)，其中 \(DIFF(a)\) 为 \(a\) 数组内元素去重后的数量，\(MEX(a)\) 为数组中未出现的元素中最小的元素。
举个例子，\(MEX( { 1 , 2 , 3 } )=0\), \(MEX( { 0 , 1 , 2 , 4 , 5 } ) = 3\)。
现在给你数组 \(a\)，求能实现的最小成本。
CF1684E题解
这很好WA，爱来自对拍
首先想一个问题，对于一个确定的数组，答案是什么？
不难发现，如果将数组排好序之后，答案就是 \(Dif[Mex(a),INF]\)。
其中 \(Dif[l,r]\) 表示将数组中值域为 \([l,r]\) 之间的数字取出得到新的数组 \(b\)，\(DIFF(b)\) 的值。
如果以值域为 \(x\) 轴，以出现次数为 \(y\) 轴，那么对于每个数组中出现的数字 \(x\)，作矩形 \((x,0)\to(x,cnt_x)\)，然后就会发现，这玩应好像堆叠积木块。
如果称一个从 \((x,0)\to(x,k)\) 的矩形叫做一个塔，答案就变成了 \([Mex(a),INF]\) 的塔的数量。
如果设当前数组的 \(Mex(a)=t\)。
不难想到，每次操作有两种选择：
- 将 \([t,INF]\) 值域范围内的某个数字变成 \(t\)，对应在平面中就是取出在 \([t,INF]\) 中的一个积木块，放到 \(t\) 位置，称之为铺路。此时 \(t\gets t+1\)。
- 将任意一个数字变成已经出现的另一个数字，对应在平面上就是将某一个积木块放在其他的积木块之上，称之为堆叠
想想这两个操作的贡献：
- 铺路：如果拿出积木块后塔少了一个（就是这个积木块自己组成了一个塔），那么造成 \(-1\) 贡献，否则贡献是 \(0\)。
- 堆叠：同铺路。
这时不难发现，与其进行堆叠，不如直接铺路，因为铺路可能会扩展更多的塔联通，而堆叠没有。
这思路不就出来了，先排序，然后先 \(for\) 一遍看看能铺到哪里（就是 \(Mex(a)\) 最大是多少），然后每次从塔最矮的开始铺路。
然后就完了~~~~吗？
亿堆细节慢慢调吧。
CF1684E代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 1e5 + 10;
int n, k;
int a[maxn];
int buc[maxn];
signed main(){
int T = read();
while(T--){
n = read();int t = k = read();
for(int i = 1;i <= n;i++)a[i] = read();
sort(a + 1,a + 1 + n);
int rp = n, i = 1;
a[n + 1] = 0x3f3f3f3f;a[0] = -1;
for(i = 0;i <= rp && k > 0;i++){
if(a[i + 1] - a[i] <= 1)continue;
if(a[i + 1] - a[i] - 1 > k)break;
while(a[i + 1] - a[i] > 1 && rp > i && k > 0){rp--;k--;a[i]++;}
// if(a[i + 1] - a[i] > 1)break;
}
while(a[i + 1] - a[i] <= 1 && i <= n)i++;i++;
// for(int i = 1;i <= n;i++){printf("a[%d]=%d ",i,a[i]);}
// printf("\nrp = %d,i = %d\n",rp,i);
int cnt = 1, l = i, mx = 0;
if(i > rp){puts("0");continue;}
memset(buc,0,sizeof(buc));
for(int i = l;i <= n;i++){
if(a[i] != a[i + 1]){buc[cnt]++;mx = max(mx,cnt);cnt = 1;}
else{cnt++;}
}
i = 1;
while(t && i <= mx){
if(buc[i] <= t / i){t -= buc[i] * i;buc[i] = 0;}
else{buc[i] -= t / i;t = 0;break;}
i++;
}
cnt = 0;
for(int i = 1;i <= mx;i++){cnt += buc[i];}
printf("%d\n",cnt);
}
return 0;
}
CF1684F
link
当前用时：已超时。
CF1684F题意
给定长度为 \(n\) 的序列 \(a\)，以及 \(m\) 个数对 \((l_i,r_i)\)。
你可以进行下列操作至多一次：
- 选择序列 \(a\) 的一个子段，并将其中的每个元素的值都改成任意整数。
你需要保证执行完操作之后，对于每个整数 \(i(1\leq i\leq m)\)，都有 \(a[l_i,r_i]\) 中所有元素互不相同。
你需要最小化操作时选择的子段的长度，并求出这个长度的最小值。
特别的如果没有必要进行操作，答案为 \(0\)。
CF1684F题解
破防，BYD 调了 \(3h\) 才调出来。
菜就多练练。
不难想到，首先将 \(m\) 个数对转化成对每个点 \(i\) 的限制。
如果设 \(lim_i\) 表示 \([lim_i,i]\) 之间不得有重复数字，那么 \(lim_i=\min_{1\le j\le m}^{i\in[l_j,r_j]}l_j\)。
不难发现，这个 \(lim_i\) 满足单调不减（后面要考）。
然后分开不同的数字，将同一个数字的下标存在一起（设存在 \(vec_{a_i}\)数组中）。
然后设 \([L_i,R_i]\) 表示如果不选择 \(i\) 在所求区间中时，\([L_i,R_i]\) 中的每一个数字都要选择。
显然
L[i] = vec[a[i]][lower_bound(vec[a[i]].begin(),vec[a[i]].end(),lim[i]) - vec[a[i]].begin()];
R[i] = vec[a[i]][upper_bound(vec[a[i]].begin(),vec[a[i]].end(),i - 1) - vec[a[i]].begin() - 1];
然后坑爹的来了（也是我调了三个小时的原因）
对于以上这两样代码算出的 \(L_i,R_i\)，需要进行边界判定：如果 \(lim_i=n+1\) 或者 \(L_i>R_i\)（尤其是这个），则 \(L_i=n+1,R_i=0\)，即一定成立。
然后问题就变成了给你 \(n\) 个点，可以选择一个区间，这个区间中的所有点都会被选中，并且每个点要不然选择自己，要不然选择所有 \([L_i,R_i]\) 中的点，问这个区间最短是多少？
先说一个问题，就是是否存在一种情况，在其他条件满足的情况下，你选择了 \(i\) 但没选择 \(j(i<j)\)，这时 \(i\) 的条件满足了，但是 \(j\) 的没满足？
显然不存在，因为前文说到 \(lim_i\) 单调不减，也就是 \(j\) 对 \(i\) 的限制不强于 \(i\) 自己的限制，故一定满足。
并且由于 \(lim_i\) 单调不减，故 \(L_i\) 也单调不减，也就是说，如果使用双指针的话，左端点右移并不会导致右端点左移也能够成立。
所以线段树维护没有选择的所有点的 \(L\) 最小值和 \(R\) 最大值+双指针即可。
当然，如果你愿意，也可以预处理 \([1,i]\) 的最小最大值和 \([i,n]\) 的最小最大值，达到 \(O(n)\) 的时间复杂度。
CF1684F代码
// LUOGU_RID: 137133385
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 3e5 + 10;
int n, a[maxn], m;
int L[maxn], R[maxn];
int lim[maxn];
vector<int> vec[maxn];
struct Segment_Tree{
struct node{
int maxx, minn;
node(int maxx = 0,int minn = 0):maxx(maxx),minn(minn){}
}d[maxn << 2];
node mergenode(node l,node r){return node(max(l.maxx,r.maxx),min(l.minn,r.minn));}
void build(int l,int r,int p){
if(l == r){d[p] = node(R[l],L[l]);return;}
int mid = l + r >> 1;
build(l,mid,p << 1);build(mid + 1,r,p << 1 | 1);
d[p] = mergenode(d[p << 1],d[p << 1 | 1]);
}
void update(int l,int r,int pos,int p,int x,int y){
if(l == r && l == pos){d[p] = node(y,x);return;}
int mid = l + r >> 1;
if(pos <= mid)update(l,mid,pos,p << 1,x,y);
else update(mid + 1,r,pos,p << 1 | 1,x,y);
d[p] = mergenode(d[p << 1],d[p << 1 | 1]);
}
node query(int l,int r,int s,int t,int p){
if(s <= l && r <= t)return d[p];
int mid = l + r >> 1;
if(t <= mid)return query(l,mid,s,t,p << 1);
if(mid < s)return query(mid + 1,r,s,t,p << 1 | 1);
return mergenode(query(l,mid,s,t,p << 1),query(mid + 1,r,s,t,p << 1 | 1));
}
void update(int pos,int x,int y){update(1,n,pos,1,x,y);}
}tree;
inline bool check(int l,int r){
Segment_Tree::node tmp = tree.query(1,n,1,n,1);
return l <= tmp.minn && tmp.maxx <= r;
}
map<int,int> mp;int tot;
signed main(){
int T = read();
while(T--){
n = read(); m = read();int u, v;mp.clear();tot = 0;
for(int i = 1;i <= n;i++){
a[i] = read(); if(!mp[a[i]])mp[a[i]] = ++tot;
a[i] = mp[a[i]]; vec[i].clear();
lim[i] = L[i] = R[i] = 0;
}
for(int i = 1;i <= m;i++){
u = read(); v = read();
vec[v].push_back(u);
}
u = n + 1;
for(int i = n;i;i--){
for(int j : vec[i]){u = min(u,j);}
lim[i] = u;vec[i].clear();
}
for(int i = 1;i <= n;i++)vec[a[i]].push_back(i);
for(int i = 1;i <= tot + 1;i++)vec[i].push_back(n + 1);
for(int i = 1;i <= n;i++){
if(lim[i] < i && i != vec[a[i]][0]){
L[i] = vec[a[i]][lower_bound(vec[a[i]].begin(),vec[a[i]].end(),lim[i]) - vec[a[i]].begin()];
R[i] = vec[a[i]][upper_bound(vec[a[i]].begin(),vec[a[i]].end(),i - 1) - vec[a[i]].begin() - 1];
}
else L[i] = n + 1;
if(L[i] == n + 1 || R[i] < L[i])R[i] = 0, L[i] = n + 1;
// printf("%d %d %d\n",i,L[i],R[i]);
}
u = 1; v = 0;tree.build(1,n,1);
int ans = n, ll = 0, rr = 0;
for(;u <= n;u++){
while(v < n && !check(u, v)){v++;tree.update(v,n + 1,0);}
if(check(u, v)){
if(ans >= max(0,v - u + 1)){
ans = max(0,v - u + 1);
ll = u; rr = v;
}
}
// if(a[1] == 827218149){
// if(u == 83119)printf("u = %d,v = %d ans = %d\n",u,v,ans);
// if(u == 53887)printf("u = %d,v = %d ans = %d\n",u,v,ans);
// }
tree.update(u,L[u],R[u]);
}
// if(ans == 62326)printf("l = %d, r = %d\n",ll,rr);
printf("%d\n",ans);
// for(int i = 3133;i <= 3140;i++)printf("a[%d]=%d\n",i,a[i]);
}
return 0;
}
CF1684G
CF1684G题意
下面是一个经过部分改动的求 \(\gcd\) 的伪代码（其中 \(t\) 是一个初始为空的序列）：
function Euclid(a, b):
if a < b:
swap(a, b)
if b == 0:
return a
r = reminder from dividing a by b (即设 r 为 a mod b)
if r > 0:
append r to the back of t (即将 r 插入到 t 的尾部)
return Euclid(b, r)
有一个由数对构成的序列 \(p\)，接下来我们对 \(p\) 中每个数对都执行一次上述函数，然后把 \(t\) 重新排列并给定到输入中。
给定 \(n,m\) 和长度为 \(n\) 的序列 \(t\)。
你需要构造一个长度不超过 \(2\times10^4\) 的数对序列 \(p\)，满足：
- 每个数对中的元素都是不超过 \(m\) 的正整数。
- 根据序列 \(p\) 可以经过上述操作得到输入中给定的 \(t\)。
有解输出任意一组解，无解输出 -1。
CF1684G题解
身为网络流睪手的我当然是被秒啦（bushi）
不难想到，如果用 \((3t,2t)\) 这样的数对，就能构造出 \(t\) 这个数字，且不会附带出其他的数字。
所以对于 \(t_i\le \frac{m}{3}\) 的数字显然可以直接构造。
称 \(a\le\frac{m}{3}\) 的数 \(a\) 为小数，否则为大数
那剩下的 \((\frac{m}{3},m]\) 怎么办呢？
不难发现，如果用诸如 \((2t+a,t+a)\) 这样的数对，就能同时构造 \(t,a\) 这两个数字，如果还能保证 \(a|t\)，那就只会构造出这两个数字。
但是同样发现，如果有一个数 \(t_i>\frac{m}{2}\)，那一定无解，因为在这个代码中，一定是大数模小数，如果想构造出 \(t_i>\frac{m}{2}\)，那就一定有 \(x=y+kt_i\)，其中 \(k\in \mathbb{Z}且k\ge1\)，\(y>k_i\)，故 \(\min x=y+t_i>m\) 无解。
然后不难发现，如果用 \((2t+a,t+a)\) 这样的数对，来构造 \(t,a\) 这两个数字，那一定是 \(t>\frac{m}{3}\)，不然自己构造自己的就好了。
因为 \(t>\frac{m}{3}\)，由 \(2t+a\le m\) 得 \(a\le\frac{m}{3}\)。
一个大数匹配一个小数，二分图匹配！
于是每个大数 \(t_i\) 尝试匹配一个小数 \(t_j\)，满足 \(t_j|t_i\) 且 \(2t_i+t_j\le m\)。
跑二分图匹配即可。
CF1684G代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 1e3 + 10;
int n, m;
int a[maxn];
int mn[maxn], mx[maxn], tot1, tot2;
int match[maxn];
bool book[maxn];
bool dfs(int u){
for(int v = 1;v <= tot1;v++){
if(mx[u] % mn[v] == 0 && !book[v] && mx[u] * 2 + mn[v] <= m){
book[v] = 1;
if(!match[v] || dfs(match[v])){
match[v] = u;
return true;
}
}
}
return false;
}
vector<pair<int,int> > vec;
signed main(){
n = read(); m = read();
for(int i = 1;i <= n;i++)a[i] = read();
sort(a + 1,a + 1 + n);
if(a[n] > m / 2){puts("-1");return 0;}
for(int i = 1;i <= n;i++){
if(a[i] <= m / 3)mn[++tot1] = a[i];
else mx[++tot2] = a[i];
}
if(tot1 < tot2){puts("-1");return 0;}
for(int i = 1;i <= tot2;i++){
for(int j = 1;j <= tot1;j++)book[j] = 0;
if(!dfs(i)){puts("-1");return 0;}
}
for(int i = 1;i <= tot1;i++){
if(!match[i])vec.push_back(make_pair(mn[i] * 3,mn[i] * 2));
else vec.push_back(make_pair(mx[match[i]] + mx[match[i]] + mn[i],mx[match[i]] + mn[i]));
}
printf("%d\n",vec.size());
for(auto i : vec)printf("%d %d\n",i.first,i.second);
return 0;
}
CF1684H
*3400不会QWQ
菜就多练练pwp