哒哒哒哒哒

分类

最小生成树(1) 最短路(1) 未归档(121) 题解(2)

/ 注册

全部文章（共125篇）

C. The Fair Nut and String 递推分段形dp

C. The Fair Nut and String 递推分段形dp 题意给出一个字符串选择一个序列\({p_1,p_2...p_k}\)使得对于任意一个\(p_i\) , \(s[p_i]==a\) 对于任意一个\(p_{i}<j<p_{i+1}\)来说 \({\exists}...

连续递推dp dp 构造前缀和转化字符串预处理(粘连) 分段形dp

2019-05-01

0 427

Codeforces Round #526 (Div. 2) D. The Fair Nut and the Best Path 树上dp

D. The Fair Nut and the Best Path 题意：给出一张图点有权值边也要权值从任意点出发到任意点结束到每个点的时候都可以获得每个点的权值，而从边走的时候都要消耗改边的边权，如果当前值小于边的边权，就走不通，问从任意点出发到任意点结束的可以获得的最大权多少（其中到一...

dp 树形dp 树

2019-05-01

0 581

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