熠丶

题解

未归档(32)

/ 注册

做想做的事，见想见的人

全部文章 / 题解（共156篇）

Numbers 来自专栏

题意：求在区间内满足，且对于任意都不满足的数的个数。做法：分块+数学思路： 1.求区间满足个数可以转化为的个数减去 2.由题意易得k一定是个质数，否则一定不存在满足不满足的数因为k会被整除，所以一定 3.同时i要同时满足是k的倍数且k是最小公因数 4.所以综上所述可...

2021-01-07

1 892

Topforces Strikes Back 来自专栏

做法 1.因为使得答案最大，一定是优先选大数，所以先排序因为数之间没有倍数关系，一定不能选重复的数字，所以可以去重 2.分类讨论：1）如果能选一个数，一定是最大的那个数2）如果能选两个数，一定是最大的那个数+与它不成倍数关系中最大的数证明：因为如果不选最大的那个数一定会比第一种情况小3）如果能...

2020-12-25

1 759

Special Matrices 来自专栏

做法：dp+滚动数组优化思路： 1.先求出已知前m项后每列还需要的几个1 2.然后枚举m+1~n行根据上一层状态来转移如果上层不存在某种状态直接continue 1)补两列1个1 --->(转移后) 两列0个1 2)补一列1个1+一列2个1 ---> 一列0个1+一列1个...

2020-12-24

3 664

Hacker, pack your bags! 来自专栏

做法：根据区间长度存线段，然后把每种长度的线段根据左端点进行排序枚举第二个区间的长度的所有线段，用minu存当前最优的第一个线段按照上述模拟即可代码 #include <bits/stdc++.h> using namespace std; #define pb push_b...

2020-12-23

0 688

Necklace 来自专栏

思路： 1.如果存在两个奇数，不可能找到回文字符串2.如果能找到回文串，最多能找到他们的最大公因数3.然后分不存在奇数和存在一个奇数分类讨论即可代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #...

2020-12-17

1 681

Superhero Battle 来自专栏

做法：前缀和思路： 1.如果前n天（第一轮）不能打死怪物，并且第一轮结束怪物没有掉血可以保证一定打不死怪物 2.剩下的情况可以进行模拟即可代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #...

2020-12-16

0 695

[SCOI2016]萌萌哒来自专栏

做法：st表+并查集前置芝士： st表：https://oi-wiki.org/ds/sparse-table/ 思路：令f[i][j]表示区间[i,i+ 2^j-1]这一段对于一个限制可以拆成log 份，然后进行集合合并答案就是是9*10^(集合个数-1) 代码 // Problem...

2020-12-02

3 761

Smile House 来自专栏

做法：floyd+倍增题意：求最小正环的大小思路：利用floyd+倍增的方法跑最长路路径数量从大到小的方法来判断是否成立（类似二分的思想） 1）若存在正环，则，则答案不需要增加 2）若不存在正环，则，则答案需要增加，并且更新f数组代码 // Problem: Smile H...

2020-12-02

3 711

[SCOI2015]国旗计划来自专栏

做法：倍增+贪心题意：必选一个区间后，找出剩余区间能覆盖整个环的最少区间数思路： 1.先把环转化成链 2.再把这些区间按左端点排序 3.利用倍增来查询代码 // Problem: [SCOI2015]国旗计划 // Contest: NowCoder // URL: https://ac...

2020-12-02

1 919

A and B and Lecture Rooms 来自专栏

做法：lca 题意：已知两点，求到这两点距离相同的点的个数思路：如果存在到这两点距离相同的点，那么这两点的距离一定是偶数如果这两点的深度相同，那么他们向上走到他们最近的公共祖先的子节点，然后n减去以这两个点为根节点的子树大小否则求减去这两个点的中点一下的部分代码 // Prob...

2020-12-01

1 843