首页 > 其他分享 >Codeforces Round 922 (Div. 2)

Codeforces Round 922 (Div. 2)

时间:2024-02-01 17:14:36浏览次数:28  
标签:正序 Codeforces 922 Div 从小到大 逆序

基本情况

A题当时做完提交一直编译错误后面发现是语言选择错误,浪费了五六分钟,然后去做B没想到去看C看了样例感觉可以做,结果干了好久都没出来,倒回去看B还是没做出来,感觉全程很紧张不知道为什么,脚一直在抖。

A. Brick Wall

没啥好说的,就是全部放竖直的,实在不能放了再放横的而且把横的宽度拉到最大就ok了

B. Minimize Inversions

当时卡在了不知道怎么同时处理A和B因为动了A的索引B也会改变。有一瞬间想到了把A数组按从小到大排,但觉得可能这个时候不是最小值;
其实把一个从小到大排就是最小值,一开始被样例骗了以为不能其实就按从小到大排最小的反转数是一摸一样的。那这个是为什么呢?
1.一开始就按从小到大排那么A的就全部是正序对,那么我们假设正变为逆-1,逆变为正+1,这样如果我们交换后只有更差或保持原样绝对不可能更好。
2.那么又会问,我上面说的是针对i和j相邻的,如果不相邻这样子影响的可不是只有1个会不会更好呢,其实是不会的因为假设这个i和j相差为x那么我们动A就会添加x个逆序对,那对于B来说呢,最好的情况就是添加x个正序对,这样一来最好的情况就是保持原样。
反思一下当时为什么想到了把A全部变为从小到大排而觉得不可以呢,第一点:看样例后觉得不可以其实应该继续思考就把我的答案代过去看逆序对数是否一样。第二点:想到了从小到大排发现了问题后就觉得是错误但是可能这个问题是不存在的需要证明出来这个问题

标签:正序,Codeforces,922,Div,从小到大,逆序
From: https://www.cnblogs.com/sixsix666/p/18001640

相关文章

  • Codeforces Round 921 (Div. 1)
    Preface被折纸狠狠地腐乳了,但好在手速够快光速写完前两题成功把Ohara_Rinne这个号也打上橙了之后就不开其它小号打了,也差不多该尝试去向上挑战了,不然一直呆在舒适圈内也没啥提升的说A.DidWeGetEverythingCovered?直接把序列自动机建出来,不妨设状态\((x,y)\)表示构造了长......
  • Codeforces Round 922 (Div. 2)
    CodeforcesRound922(Div.2)比赛链接A.BrickWall思路简单的模拟,要想实现最高的稳定性,就横着放就可以了,因为长度必须大于等于2,所以最后即使不能被2整除,也可以算在里面Code#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongvoidsolve(){ intn,......
  • Codeforces Round 922 (Div.2)
    题目链接点这里CF1918ABrickWallvoidsolve(){lln,m;cin>>n>>m;cout<<n*(m/2)<<endl;}CF1918BMinimizeInversions注意到,当其中一个排列有序时,总的逆序对数量最少()今天找个时间补上证明对于任意一对\(i,j\)位置,其可能的逆序对总......
  • Codeforces Round 922 (Div. 2) A-C
    这次还好,虽然还是不够满意,因为D题没写出来。。A一个明显的贪心,都竖着放就好了#include<bits/stdc++.h>#definelllonglongusingnamespacestd;inlineintread(){ charc=getchar();inta=0,b=1; for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1; for(;c......
  • Codeforces Round 922 (A-C)
    第一次打Div2,对我来说还是很难,写篇博客记录一下~A题题意:T组输入,每组输入一个n,m,代表nm大小的地板,以1k大小的地砖完全覆盖地板(k>=2,且同一地板中k可以不同)。将水平放置的地砖与垂直放置的地砖相减的值定义为稳定性,求最大的稳定性是多少。思路:尽可能的使得水平放置的地砖多,垂......
  • CodeForces 1239E Turtle
    洛谷传送门CF传送门放放/ll/ll/ll。这题是个性质题。首先第一排一定是升序,第二排一定是降序。考虑第一排若存在\(i<j\)使得\(a_{1,i}>a_{1,j}\),那么交换这两个数不会变劣。第二排类似。然后发现在\(1\)走下去或在\(n\)走下去最优。考虑先求出从\(1\)走下去的......
  • 2024 蓝桥杯模拟赛 2 (div1+div2)
    A.根据题目模拟#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e5+10;voidsolve(){inta,p;cin>>a>>p;if(p<16)a=max(0ll,a-10);elseif(p>20){inttmp=p-20;a=max(0ll,a-tmp)......
  • Codeforces Round 921 (Div. 2)
    目录写在前面ABCDE写在最后写在前面比赛地址:https://codeforces.com/contest/1925。在床上躺了两天终于复活了妈的。A发现字符串\(s\)合法当且仅当\(s\)可以被分为至少\(n\)段,其中每段都包含\(k\)种字符至少1次。正确性可以归纳证明,这里懒得写了感性理解下。于是......
  • CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
    CodeTONRound7(Div.1+Div.2,Rated,Prizes!)比赛链接A.JaggedSwaps思路:考虑到题目要求,给定的排列第一位必须是1才会构造出可行性序列,如果不是就是没有办法Code#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongvoidsolve(){ intn; cin......
  • Codeforces Round 921 (Div. 2)
    A-WeGotEverythingCovered!难度:⭐题目大意给定n和k两个整数,要求用前k个小写字母组成一个字符串;该字符串的子串应包含所有由前k个字母组成的长度为n的字符串全排列;要求输出最短的满足条件的字符串;解题思路这题题目挺唬人,但其实是个水题;所谓最短,其实......