哒哒哒哒哒

未归档

最小生成树(1) 最短路(1) 题解(2)

/ 注册

全部文章 / 未归档（共121篇）

Codeforces Round #525 (Div. 2) C. Ehab and a 2-operation task 数学 mod运算的性质

C. Ehab and a 2-operation task 数学 mod运算的性质题意: 有两种对前缀的运算 1.对前缀每一个\(a +x\) 2.对前缀每一个\(a\mod(x)\) 其中x任选思路：这里只有加法所以膜运算可以看作是减法而膜运算当成减法使用需要合理运用其性质 \(a[...

数学构造膜运算性质

2019-05-01

0 499

Codeforces Round #525 (Div. 2) E. Ehab and a component choosing problem 数学

题意：给出树求最大的sigma(a)/k k是选取的联通快个数联通快不相交思路：这题和1个序列求最大的连续a 的平均值这里先要满足最大平均值而首先要满足最大也就是一个数的时候可以找出最大值满足第二个条件最长也就是看最大值有多少个连续即可而本题也就是先找出最大值然...

数学贪心思维树

2019-04-29

0 537

Codeforces Round #553 (Div. 2) C. Problem for Nazar 数学

题意：从奇数列 1 3 5 7 9 .... 偶数列2 4 6 8 10...分别轮流取 1 2 4 ....2^n 个数构成新数列求新数列的区间和（就一次询问）思路：首先单次区间和就是一个简单的类似前缀和就可以搞定那么如何求新数列的和呢　　我们明确一个观点：原数列的区间和结果显而...

数学复杂度计算奇偶分割

2019-04-29

0 526

Codeforces Round #524 (Div. 2) C. Masha and two friends 几何：判断矩形是否相交以及相交矩形坐标

题意：给出一个初始的黑白相间的棋盘有两个人第一个人先用白色染一块矩形区域第二个人再用黑色染一块矩形区域问最后黑白格子各有多少个思路：这题的关键在于求相交的矩形区间给出一个矩形的左下和右上角则相交的条件为 max(X1,X3)<=min(X2,X4)&&...

数学几何容斥

2019-04-29

0 557

Codeforces Round #553 (Div. 2) D. Stas and the Queue at the Buffet 贪心+公式转化

题意给出n个pair （a,b）把它放在线性序列上 1--n 上使得 sum(a*(j-1)+b*(n-j)) 最小思路：对式子进行合并同类项有： j*(a-b)+ (-a+b*n) 可以发现只和第一项有关所以把a-b小的和大的j 结合即可比赛的时候被B搞得...

贪心数学公式转化

2019-04-29

0 421

Codeforces Round #553 (Div. 2)B. Dima and a Bad XOR 思维构造+异或警告

题意：给出一个矩阵n(<=500)*m(<=500)每一行任选一个数异或在一起求一个异或在一起不为0 的每行的取值列号思路：异或的性质交换律 x1^x2^x3==x3^x2^x1 可以任意换位置并且 x1^x2==x3^x4 等于 x1^x2^x3==x4 可以...

思维构造异或

2019-04-29

0 456

Codeforces Round #523 (Div. 2) D. TV Shows 模拟（多重集先把所有区间加入多重集合）+贪心+二分

题意：给出n个电视节目的起始和结束时间并且租一台电视需要x +y*(b-a) 【a,b】为时段问完整看完电视节目的最小花费是多少思路：贪心的思想情况1 如果新租一台电视的花费<=在空闲电视上面看节目那么肯定新租电视　　　　　　　　情况2 否则就直接在空闲电视上看就好 ...

模拟贪心多重集二分

2019-04-29

0 565

Educational Codeforces Round 63 (Rated for Div. 2) B. Game with Telephone Numbers 博弈思维+模拟+贪心思维

题意：博弈题面给出一个数字序列（>=11）有两个人任意删除数字直到数字只剩下11位如果删除后的数字串开头是8那么就是第一个赢否则就是第二个人赢第一个人先手数字序列一定是奇数长度思路: 首先计算一共走多少步第二个人想赢只有以下两种方法想法1：如果第二个人能...

博弈思维贪心模拟

2019-04-29

0 531

Educational Codeforces Round 63 (Rated for Div. 2) C. Alarm Clocks Everywhere gcd

题意：给出一个递增的时间序列a 给出另外一个序列b （都是整数）以b中任选一个数字作为间隔自己从1开始任选一个时间当成开始时间输出选择的数字标号以及开始时间思路直接求间隔的公共gcd 然后看给的序列b 中有没有数 b[i]|gcd 即可如果没有则输出-1 ...

2019-04-29

0 525

Educational Codeforces Round 63 (Rated for Div. 2) D. Beautiful Array 分类讨论连续递推dp

题意：给出一个数列和一个x 可以对数列一个连续的部分每个数乘以x 问该序列可以达到的最大连续序列和是多少思路：不是所有区间题目都是线段树！！！！！！这题其实是一个很简单的dp 使用的是分类讨论的思想我们设置dp数组 dp[1][i] 表示一直没有用x 乘过的数组必须...

dp 分类讨论思想连续递推dp

2019-04-29

0 390