哒哒哒哒哒

分类

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

/ 注册

全部文章（共15篇）

Codeforces Round #522 (Div. 2, based on Technocup 2019 Elimination Round 3) D. Barcelonian Distance 几何代数（简单）

题意:给出一条直线 ax +by+c=0 给出两个整点 (x1,y1) (x2,y2) 只有在x,y坐标至少有一个整点的时以及给出的直线才有路径（也就是格子坐标图的线上）问两个整点所需要经过的最短距离思路：整点和整点之间的最短路径要么经过直线要么不经过直线如果不经...

数学坐标轴

2019-04-29

0 522

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) 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 #524 (Div. 2) C. Masha and two friends 几何：判断矩形是否相交以及相交矩形坐标

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

数学几何容斥

2019-04-29

0 557

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 #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

D. Minimum Diameter Tree 思维+猜结论

D. Minimum Diameter Tree 思维+猜结论题意给出一颗树和一个值v 把该值任意分配到任意边上使得\(\sum\limits_{i,j}p_{ij}=v\) 使得这颗树任意两个点的简单路的最大值最小思路根据样例我们可以很好得蒙出只要平均分在度数位1的点所连的...

思维构造数学树猜结论结论

2019-05-01

0 542

C. Polygon for the Angle 几何数学

C. Polygon for the Angle 几何数学题意给出一个度数，问可以实现的最小的n的n边形是多少思路由n边形的外角和是180度直接就可以算出最小的角是多少如果给出的度数是其最小角的倍数并且在这个n边形最大度数之内，那么就可以得到了直接从小到大枚举n边形即可 #i...

数学几何

2019-05-01

0 554

D. Game with modulo 交互题（取余（膜）性质）附带a mod b<a/2证明

D. Game with modulo 交互题（取余（膜）性质）题意猜一个点\(a\)可以向机器提问点对\((x,y)\) 如果\(x\mod(a)>=y\mod(a)\)回答\(x\) 反之回答\(y\) 询问不能超过60下，请你猜出a 思路 \(a\mod(b)<a/2...

数学思维膜运算性质交互

2019-05-01

0 483

E. Pavel and Triangles dp+问题转化

E. Pavel and Triangles dp+问题转化题意给出n种线段，每种线段给出一定数量，其中每个线段都是 \(2^k\) 问最多能组成多少个三角形思路因为每个是\(2^k\)所以能组成三角形的线段要么是ABB要么是AAA 问题就转化成了凑ABB和BBB的组成怎么凑最多怎...

dp 数学转化问题

2019-05-01

0 559