pphkaa

题解

/ 注册

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

点权和题解

题解：由题意可知，每次操作后的点权和由三部分组成：被选中操作的点的贡献，被选择操作点的子节点的贡献，被选择操作点父亲节点的贡献故我们可以开三个数组分别维护这些贡献，每次操作完后进行跟新，再将这三种贡献加起来便可以最终计算得到hash值定义: self[x]:x被选中操作的次数 son[x]:x子节点...

2020-07-16

0 798

枚举

思路：首先用枚举第一行的按开关情况，一共有32种情况（00000-11111），分别计算出这些情况按开关后亮灭情况再通过改变第二行的将第一行的灯全亮，以此类推通过改变第三行使第二行全亮，改变第四行使第三行全亮，改变第五行使第四行全亮。最后更新最小按灯数。由于只有25个灯，int的有效范围是32位，...

枚举

2020-07-12

0 690

完全背包

思路：先将货币面值从小到大排序，再依次判断小货币能否组成大货币，如果可以则可以删除该种大货币。 #include<bits/stdc++.h> using namespace std; int a[100086]; int vis[250086]; int main() { in...

背包

2020-04-27

0 658

简单易懂的推导过程

(a[i] - a[x]) * (a[i] - a[x]) = a[i] * a[i] - 2 * a[i]* a[x] + a[x] * a[x]所以里面一共就有(n - 1)个a[i]的平方，中间这部分减法就是2 * (sum - a[i]) * a[i], sum即是所有数字的和。然后举个简单...

2020-04-21

2 719

数位dp

来记录下解题思路：坑点：long long型数据取模会TL这题主要是用了数位dp的模板，主要的难点在于，枚举出这个数字所有数位的和的可能情况。 #include<bits/stdc++.h> using namespace std; int T; long long ans; int d...

数位dp

2020-04-18

0 705

枚举优化

这道题感觉是枚举加一些优化在里面。还是以例子为例吧。dp[i]=1表示某种组合加起来除以3600的余数为i，一开始的时候dp[]数组全为0；当某个组合是3600的倍数的时候，dp[0]=1,这便是说明可以组合形成3600的倍数，便可以输出YES，否则输出NO。假如：2000 1000 3000一开始...

枚举优化

2020-04-14

3 1169

背包问题（思路+分析）

这题思路就是：讲最场的歌曲在最后一分钟播放，剩下n-1首歌曲在t-1时间内求最大值以例子演示一下：注意这里最大时长已经被预订最后一分钟播放 1 2 3 4 5 6 0 0 0 0 0 0 先加入时长为2的歌曲变为 0 2 2 2 2 2 加...

背包

2020-04-14

6 724

思路详细解析（小白专用）

首先我们来看看观察每个区间的值就以题目中的示例为例子解释一下对应区间段1-5由于可加的物品的重量必须大于等于W（4）故在1-5中只有4，5两个可加贡献为 25+25=20；2是因为有两个数符号条件在2-4中，只有4一个可加贡献为1*5=5； 3-3中，没有可以加的贡献0故这样当w取4时...

二分前缀和

2020-04-11

3 694

枚举+二分求解一元三次方程

这道题如果要解出来的话，除了要想到二分，更要想到枚举区间段为1的各部分，然后再注意注意细节就差不多了。 #include<bits/stdc++.h> using namespace std; double a,b,c,d; int ans=0; inline double f(doub...

二分枚举

2020-04-11

6 851

思路分析

这道题应该大家跟我在做的时候都想到了要使这两者数量最接近，所以要使较小的那个不断扩大两倍直到他们两数量最接近（不能超过），然后想到这一点后我就陷入了泥潭，一直在思考怎么确定再次倍增的条件呢，然后就。。。。卡这卡死了，后面补题的时候看了大佬的代码发现，其实根本不用想的这么复杂，当我们使他们两最接近的时...

2020-04-11

1 674