瑜画

题解

/ 注册

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

Collecting Bugs 题解

根据上课听的雨巨的思路，移项运算一下然后写代码 #include <iostream> #include <algorithm> #include <string.h> using namespace std; const int N = 1010; doubl...

dp

2020-08-17

0 628

带富翁题解

倒着dp，计算分母（能往几个地方转移分母就是几）用dp[i]表示i点到终点需要步数的数学期望能走到至多六个位置，直接转移就好了，要记得加上自己这个位置得分 #include <bits/stdc++.h> using namespace std; int a[105]; double d...

dp

2020-08-17

1 546

Mondriaan's Dream 题解

用二维数组dp，第一维表示状态，第二维表示当前行。最后输出的是最后一行全部都横着放的状态。用1表示竖着放，0表示横着放，注释详细。。。 #include <bits/stdc++.h> using namespace std; #define ll long long ll dp[1&l...

dp

2020-08-17

1 698

Most Powerful 题解

这题比较简单，不过有需要注意的点：1.选取的被碰气体得是对应二进制表示为0的2.选取的一个碰他的气体也得是对应二进制为0的（还没消失的气体）具体看代码，有详细注释： //1表示哪个气体被碰掉消失了 0表示气体还没被碰掉 #include <bits/stdc++.h> using nam...

dp

2020-08-17

0 0

简单环题解

前面部分跟“郊区春游”差不多，属于TSP问题，不懂的可以看一下我郊区春游的那篇题解。也是枚举起点、终点（终点这里得比起点大，避免重复统计），进行状态转移，不同的是这里的dp数组记录的是方案数量，然后每次转移以后要判终点和起点是否可以相连，相连就进行统计。最后答案要除以2，原因是大于等于3的回路可能会...

dp

2020-08-17

5 972

郊区春游

题意：一开始就在旅游的几个点选一个作为起点，然后这个点就算游过了，游完别的景点在最后一个景点停下即可。用dp[i][j]，i表示状态（哪些点游过，哪些点没有），j表示最后停留在哪个点。具体看代码详细注释： #include <bits/stdc++.h> using namespace ...

dp

2020-08-17

3 850

炮兵阵地题解

先看同一行哪一些方案可以放置，以减小时间复杂度（老套路）查看的方法是看左边第一、二，右边第一、二不能跟自己这个位置同时有1 然后统计这个方法包含的炮兵数，统计方法是线性dp，通过lowbit（树状数组的东西），转移计数。（每个方案的炮兵数量是这个方案的二进制串去除最低位的1的炮兵数量+1）最后一行...

dp

2020-08-16

3 698

D题题解

比赛时候弄错了一行代码，一直没AC，吐血。。。直接贪心，从后往前翻，只要出现连续两个1就进行翻转，这样就能确保收益大于直接修改的，具体细节看代码（不过好像dp的方法比较无脑，贪心的细节容易错，好吧，还是太菜了）记录修改的位置，通过二分查找判断每个点在翻转完毕以后是1还是0，如果是1就需要修改。 #...

贪心

2020-08-16

0 554

Happy Running 题解

题面意思，问围着一个x的跑道跑顺时针跑，打卡完毕的时候跑k米及以上的概率。思路：因为这个人跑步只能先打第一张卡，在打第二张卡，所以有可能第二张卡在第一张卡前面，那么这个人就得跑第二圈才能打第二张卡，否则是直接就可以在第一圈打掉第一张卡和第二张卡。而且，无论如何都是可以在两圈以内完成打卡的根据这个...

2020-08-14

1 633

黑白树题解

树上贪心即可解决此题： dfs的时候每往下走一步让对应结点的k值-1，因为要覆盖到同一个点，孩子比父亲会远一个距离，当无法覆盖的时候（k值被减到0了），新开辟一个结点（需要染色），然后k值又重新开始减。 #include <bits/stdc++.h> usi...

贪心

2020-08-10

0 703