熠丶

题解

未归档(32)

/ 注册

做想做的事，见想见的人

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

Fuel Economy 来自专栏

思路我们可以把终点看成距离为d，价格为0的加油站每次到达加油站我们都要把油箱加满如果每站之间距离大于油箱容量（第一站是否达到看当前容量），输出-1假设油箱中的油有区别，并且可被替换我们优先使用价格低的油，到下一个加油站时可以把当前油箱中比当前加油站的油贵的油替换成当前加油站的油用双端队列维护模拟即...

2021-05-01

2 721

The Fair Nut and Strings 来自专栏

思路把a看成0，把b看成1这样就形成了01字符串用类似字典树的样子来建树求每层s，t字典序大小之间（包括是s，t）的个数设为d答案即为每层min(d,k)的和代码 // Problem: The Fair Nut and Strings // Contest: NowCoder // URL: ...

2021-05-01

1 925

Cowpatibility 来自专栏

思路把每一种冰淇淋被牛喜欢用bitset存起来，第i头喜欢用第i-1位为1表示。然后遍历每一头牛的每一种喜欢的冰淇淋，并或起来可得该牛和其他牛能否和谐共处的关系，1表示能和谐共处，0表示不能和谐共处。不能和谐共处的数量即为n-s.count() 因为不能和谐共处的关系被重复计算了两次，所以最...

2021-04-27

2 919

环路运输来自专栏

时间复杂度：思路长度为n的环形首先把它拆成长度为2n的链我们只要求即可我们可以枚举i,就是个定值，用有限队列维护的最大值，同时要保证这一条件，不符合弹出即可代码 // Problem: 环路运输 // Contest: NowCoder // URL: https://ac.nowco...

2021-04-26

0 605

[CQOI2014]数三角形来自专栏

做法：组合数思路因为是的网格，所以一共有个点所以三角形数量为在所有点中任意选取三点中减去三点共线的情况即可不合理的情况分为三种 1.横线2.竖线3.斜线前两种情况很好求，所有横着（竖着）的点中选取三个点乘上竖着（横着）的点数即可第三种情况我们可以先找到一个直角边为i,j的直角三角形...

2021-04-14

2 906

[HAOI2012]音量调节来自专栏

做法：dp 思路：因为音量范围在0~maxx之间并且maxx<=1000，所以我们设dp[i][j]为第i次音量变化后此时音量为j的方案是否存在在符合条件的音量内进行转移和代码 // Problem: [HAOI2012]音量调节 // Contest: NowCoder // URL...

2021-04-13

1 773

A Simple Task 来自专栏

题意：给定一个长度不超过10^5的字符串和不超过m次操作。每个操作 L R K 表示给区间[L,R]的字符串排序，K=1为升序，K=0为降序。最后输出最终的字符串。做法：线段树思路：根据计数排序的原理，只要知道了有几个数比t小，就可以知道t的位置这道题只有26个字母，我们只需建26颗线...

2021-04-07

2 755

Modern Art 来自专栏

题意给你一个的矩阵，有个颜色在一个矩阵中涂色（每种颜色必须要涂），求出第一个涂色的颜色可能有多少种做法：二维差分思路首先把明面上留下的颜色给记录下来，并且存可能涂色的最小矩阵的四个顶点坐标然后模拟涂色，w[i][j]表示这个位置最小被涂色的次数，这里可以采用二维差分来优化如果这个位置被...

2021-03-30

0 731

Landscaping 来自专栏

思路对于每缺一单位的土，我们有两种选择1.买1单位土2.从别的地方转移过来一单位的土同理，每多一单位的土1.移除1单位土2.从别的地方转移出去一单位的土在这两种方案中要取最优的方案可以用两个大根堆堆顶来记录，q1表示多土的花盆 q2表示缺土的花盆根据贪心来选择最优的方案代码 // Proble...

2021-03-25

0 829

[SCOI2010]幸运数字来自专栏

做法：dfs+容斥思路先找出只含6和8的数，再把那些成倍数关系的给删了我们知道对于一个幸运号码x，在[l,r]中x的倍数的个数，就是之后根据容斥（奇加偶减）,答案为选1个幸运号码−选2个幸运号码的lcm+选3个幸运号码的lcm... 注意: 1.在求lcm的时候会爆long l...

2021-03-22

1 784