left_right_2022

分类

题解(45)

/ 注册

全部文章（共13篇）

Codeforces 1527B1.Palindrome Game (easy version)

题意：ALICE先手，每次能对一个字符串做两种操作:选择任意i(1≤i≤n)，其中s[i]= '0'，将s[i]改为'1'。支付1美元。把整个字符串反过来，付0元。此操作只允许在字符串当前不是回文且上次操作没有反转的情况下进行。也就是说，如果Alice翻转了串，那么Bob在下一个动作中就不能翻转，反...

贪心博弈论

2021-05-29

0 561

Codeforces 1520E.Arranging The Sheep

题目描述：有一块长度为n的一维地，每格地可能为空('.')也可能有一只羊('*')每次可以令一只羊左移或右移一格，当且仅当目的地是空。问最少几步能让这些羊相邻。我的做法：记所有羊的坐标为ai,维护两个值f(x)=Σ|x-ai|，sum1[x]为x及之前的羊数，sum2[x]为x及之后的羊数，定义g...

曼哈顿距离贪心数学前缀和

2021-05-29

0 631

Codeforces 1520C.Not Adjacent Matrix

题意描述：给定n，用1-n^2构造一个n×n矩阵，要求上下左右相邻的数的差值大于1，无解输出-1，有解就给出任意一组解。图省事特判n=1,n=2() n>=3时，按照对角线方向依次填数，先填对角线再轮流在上下侧填数，得到的矩阵符合要求，输出即可。大胆猜测小心使用不用证明编辑：网上有一种想...

贪心数学

2021-05-29

0 891

Codeforces 1525B.Permutation Sort

题意描述：给你由1-n组成的数组a[],每次操作可以任意交换任意次长度小于n的一段区间内的数，问几次操作能把a[]好排序。贪心地发现操作次数主要和1与n的位置有关。总结如下0：如果已经排好序1：如果仅1或n不在原位置3：如果1在[n]且n在a[1]2：其他所有情况 ```#include<b...

贪心

2021-05-29

0 526

Codeforces 1445B.Elimination

题目描述：有大于100个人参加比赛，第一轮第100名获得a分且前100名在第二轮获得至少b分；第二轮第100名获得c分且前100名在第一轮获得至少d分，问两轮得分加起来，第100名最少为多少分。至少100人获得不少于a+b分，至少有100人获得不少于c+d分，问第100名最少分数。贪心：一定在a+...

贪心

2021-05-29

0 642

Codeforces 1445A.Array Rearrangment

题目描述：给你两个长度为n的数组a、b,让你重组b使得任意i都有ai+bi<=x问能不能求得这样一个b，能Yes不能No 贪心：给最大的ai以最小的bi,次大对次小，以此类推。按上述贪心构建好之后，发现交换b中的任意两个数，都会让其中至少一个ai+bi变大，所以这个贪心是最优的。按贪心构造完之...

贪心

2021-05-29

0 543

Codeforces 1529C.Parsa's Humongous Tree

题意描述：有一个编号为1-n的树，每个节点v都有一个区间[lv,rv],这个节点可以取这个范围内的值(记为av)，两个直接相连的节点(u,v)产生的贡献为|au-av|，求整棵树的贡献和的最大值。设f(x)=|x-a1|+|x-a2|+……+|x-ak|为节点x对答案产生的贡献，其中a1~ak为x...

树上dp 贪心

2021-05-25

0 569

Codeforces 1529B.Sifid and Strange Subsequences

题意描述：给一个长度为n的数组a[]，现从中挑k个数构成一个新数组b[]，要求b[]满足：任意1<=i<j<=k,都有|b[i]-b[j]|>=MAX,MAX为b[]中最大的数，求k的最大值。经过观察，我们能发现一些性质：1.b[]数组最多含有1个正数；2.为了能放入这个正...

贪心

2021-05-25

0 552

Codeforces 1529A.Eshag Loves Big Arrays

题意描述：给定n个数，每次操作可以任意取x个数，求平均数，然后把所挑的比这个平均数小的数在原数组中删去，一直做此操作直到无法删去任何数，求最多能删掉的数。令每次操作取最小数和另一个不是最小的数，删掉不是最小数的数。所以剩下的数一定都是原数组中最小的数，统计一下个数b，答案就是n-b。 #inclu...

贪心

2021-05-25

0 676

Codeforces 1525B.Permutation Sort

题意描述：给长度为n的由1-n组成的数组a，每次操作可以选取长度严格小于n的区域，将其排序，问将整个a数组排序需要的最少的操作次数。操作步骤取决于两点：1、原数组是否有序2、1和n的位置。 1容易理解，2具体思考如下：数字1在1的位置的时候，无需额外花费步数处理；1不在1的位置也不在n的位置时，需...

贪心数学

2021-05-24

0 610