left_right_2022

分类

题解(45)

/ 注册

全部文章（共20篇）

Codeforces 597A.Divisibility

题意描述：给定区间[a,b]，问有多少个整数可以被k整除。一个小思路是分别计算a到0、b到0有多少个整数被k整除，然后再分类讨论求解。尤其注意0和端点的判断。 #include<bits/stdc++.h> using namespace std; int main() { l...

数学

2021-06-06

0 654

Codeforces 1527A.And Then There Were K

题目描述：给定n,求最大的k使得 n & (n−1) & (n−2) & (n−3) & ... (k) = 0 大胆猜测当且仅当n的最高位被0与掉了的时候这个式子会等于0，所以k满足2^m-1<n<=2^(m+1)-1，找到这个k=2^m-1输出即可...

数学二进制枚举

2021-05-29

0 954

Codeforces 1520E.Arranging The Sheep

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

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

2021-05-29

0 631

Codeforces 1520D.Same Differences

题意描述：给定长度n的数组a[],问有多少对(i,j)满足1<=i<j<=n使得aj-ai=j-i. 对式子整理得到aj-j=ai-i. 这……根本不带掩饰的？这太经典了给b[]=a[i]-i，问有多少对相同的数？这都见过吧？用map维护1到i-1中，b[i]出现了mp[b[...

数学前缀和

2021-05-29

0 948

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 1520B.Ordinary Numbers

题目描述：给定n，求1-n中有几个数字满足各位数上的数相同。统计位数len和最高位h，构造位数和n相同的数hh，hh各位数上都是h，比较n和hh，n小了就--h;ans=h+9*(len-1). #include<bits/stdc++.h> #define ll long long ...

数学

2021-05-29

0 768

Codeforces 1519C.Berland Regional

题目描述：有n个人，给出所属学校和实力值，k个人才能组成一队，每个学校都按照实力值和尽可能大的方法派出队伍，问k从1~n，分别求所有学校所有队伍的实力值和。把人按照学校分开，实力值从小到大排序做前缀和，对某个学校有m个人，派出的实力值和sum[m]-sum[m%k]。累加进ans[k]即可。复杂度...

数学前缀和

2021-05-29

0 654

Codeforces 1525A.Potion-making

题意描述：每次能向锅里添加1份魔法精华或者1份水，问最少几次操作能让锅里精华比例为k% 朴素的想，往里放入k份精华和100-k份水。然后发现可以约分，约分完了加起来，最终答案为100/gcd(k,100-k). ```#include<bits stdc++.h>#define ll l...

简单数论数学

2021-05-29

0 698

Codeforces 1499A.Domino on Windowsill

题目描述：你有个2n的方格区域，第一行有k1个白块，第二行有k2个白块，其余全部为黑块。现在有w个2×1的白的多米诺骨牌和b个黑的骨牌，问能不能将它们全部放在各自对应的颜色块上且彼此不重叠？设第一行有x1个白，第二行有x2个白，一定能找到一种方法，放下至多(x1+x2)/2块白的骨牌，黑同理。黑白...

数学

2021-05-29

0 592

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