wweiyiのblog

【解题报告】洛谷P1168 中位数 题目链接 https://www.luogu.com.cn/problem/P1168 思路 这道题目是个数据结构 由于数据结构很长时间没有码了，所以就开了一个这个 发现不怎么有思路 本来想开一个数组，然后比较位置，然后加入数组的，发现炸掉 然后主流的思路有以下两种，我也基本搞懂了 STL大法 stl大法好！ 用一个vector,然后直接查询就好了 然后vector我似乎不太会用，所以我就查了一下下百度 void push_back(const T& x):向量尾部增加一个元素X iterator insert(iterator it,const T& x):向量中迭代器指向元素前增加一个元素x iterator insert(iterator it,int n,const T& x):向量中迭代器指向元素前增加n个相同的元素x iterator insert(iterator it,const_iterator first,const_iterator last):向量中迭代器指向元素前插入另一个相同...

【解题报告】洛谷P3627 抢掠计划 题目链接 https://www.luogu.com.cn/problem/P3627 思路 简要题意： 一个有向有环图，每个点有一个权值，请问，从某一个点出发，到某些特殊的点作为终点，经过点的时候可以得到它的权值，并且该点权值变为0，每个点可以走任意多次，请问可以得到的最大权值是多少 首先，这道题目中说了是有向有环图，我们再结合酒吧的定义，和路径可以走任何多遍，知道了，我们可以把一个强连通分量里面的点全部缩成一个，权值为所有里面的点的和，如果里面有酒吧的话，就把这个缩的点变成酒吧，以此类推 这里我们用强连通分量缩点需要使用到tarjan算法，然后跑一个最长路就可以了 但是这里还有一点需要注意的就是，如何把点权转化为边权（纯属因为边权更加好算 然后我们就可以快乐地玩耍了 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737...

【解题报告】洛谷P1219 八皇后 题目链接 https://www.luogu.com.cn/problem/P1219 思路 这个的话，直接搜索吧 唯一需要注意的就是如何表示行或者列，或者对角线已经被选择了 其中对角线就直接加起来就好了 另一条对角线就直接用一个新的数组，然后也转化成相加相等的形式就可以了 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>using namespace std;const int maxn=30;int n;int cnt;bool hang[maxn],lie[maxn],dj[maxn],dj2[maxn];int rec[maxn];void dfs(int x){ if(x...

【解题报告】洛谷P1433 吃奶酪 题目链接 https://www.luogu.com.cn/problem/P1433 思路 这道题目出现在搜索的题单里，我就当搜索做了吧 然后就直接做了 发现超时一个点 怎么办 玄学优化，当递归次数超过某个值的时候直接返回当前最优解 似乎是参数的选择是凭借运气吧 大概似乎貌似好像 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>#include <cmath>#include <ctime>using namespace std;const int...

【解题报告】洛谷P1074 靶形数独 题目链接 https://www.luogu.com.cn/problem/P1074 思路 大模拟+贪心 这道题目我们要填数独，如果要直接填的话，”复杂度肯定爆炸“ 所以我们要贪心地去找应该填的列 比如，我们平常在自己手玩数独的时候，会去找填的比较多的行或者列去填，这样就好填一些，相对于这道题目而言，就是0比较少的行或者列去填 然后我们按照行0少的去填 所以先建立一个结构体，去统计一下每行有0的数量，然后按照从小到大的顺序排序 我们就先填0少的，然后以此去填，我们可以预处理一下填某一个位置的顺序，这里可以用一个一维数组就存下来，这就比较牛逼了 然后我们对于每个进行搜索，在搜索开始之前，我们还可以预处理在每个位置所在的行列和九宫格内已经存在的数字，然后这样就方便确认是否填了这个数字了，我们在枚举的时候直接枚举可以填的数字就可以了 这道题目的难点，在于dfs顺序的确定，我们需要进行预处理，这里的预处理方法也是比较好的，虽然也可以用结构体来干，但是这种似乎更加省空间？ 这是一个小tip，但是我觉得用结构体的正确率更高一点，至少不至于就和行和列的计...

【解题报告】洛谷P1312 Mayan游戏 题目链接 https://www.luogu.com.cn/problem/P1312 思路 直接大模拟 考虑每次向左向右移动，然后对于每次移动做出相应的操作，更改地图 在地图更改之前保存一个副本 然后对于每一个方块，我们进行一次搜索，每个方块向左向右移动 然后我们移动完了之后模拟重力，然后将方块全都落下来 然后消除应该消除的方块 同理继续搜索 每次搜索完了之后，应该回溯到之前的状态，方便之后的搜索 然后就是大模拟了，我干了一个半小时什么都没赶出来草 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181...

【解题报告】洛谷P2668 斗地主 题目链接 https://www.luogu.com.cn/problem/P2668 思路 大模拟+搜索 按照从顺子开始的顺序贪心，从三顺子先出，到双顺子，然后到顺子 然后出四带二，三带二，三带一，然后最后就是可以一次出完的那种了 这个题目呢贪心的思路想到不难，但是模拟出来及其考察代码能力 所以我就炸了 我代码能力超蒻的好不好 那是不是今年再出一个大模拟我就炸了 还有一个点就在于回溯 我们每次搜进去之后记得出来的时候回溯，以便搜索其他的状态，这样就比较方便了 强烈建议多练大模拟 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411...

【解题报告】洛谷P1017 进制转换 题目链接 https://www.luogu.com.cn/problem/solution/P1017 思路 我们知道进制的转换是可以从十进制转换到其他进制的 所以我们考虑是怎么转换的 假设数字为 nnn ,我们要把它转化成 kkk 进制的话，我们就要对其进行一波操作，每次对它进行魔（模）法，剩下来的数字就是他的对应的进制位置上的数字，举个例子，比如192转化为八进制 192 mod 8=0192/8=2424 mod 8=024/8=33 mod 8=3 192 \space mod \space 8=0 \\ 192 /8=24 \\ 24 \space mod \space 8 =0 \\ 24/8=3 \\ 3 \space mod \space 8=3 192 mod 8=0192/8=2424 mod 8=024/8=33 mod 8=3 然后从下往上倒序输出就是 300(8)300_{(8)}300(8)​ 还原回去 3×82=192 3 \times 8^2=192 3×82=192 成立，所以说明我们的方法是对的 然后我...

【解题报告】洛谷P1072 Hankson 的趣味题 题目链接 https://www.luogu.com.cn/problem/P1072 思路 这道题目我们首先直接模拟，可以得到50pts的高分 123456789101112131415161718192021222324252627282930313233#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>#include <cmath>using namespace std;int T; int gcd(int a,int b){ return b? gcd(b,a%b):a; }int lcm(int a,int b){ return 1ll*a*b/gcd(a,b);}int main(){ cin>>T; while(T--) { int a0...

【解题报告】洛谷P6189 跑步 题目链接 https://www.luogu.com.cn/problem/P6189 思路 发现相当于给一个数字 nnn ，问你有多少种方法能使得一个不递减序列的和为 nnn 这实际上是一个分拆数的模板题目 根据OIES，这个分拆数的伪代码是 123456789>def A000041(n): if n == 0: return 1 S = 0; J = n-1; k = 2 while 0 <= J: T = A000041(J) S = S+T if is_odd(k//2) else S-T J -= k if is_odd(k) else k//2 k += 1 return S 然后我们就把它翻译成C++就好了 1234567891011121314151617181920212223242526272829303132#include <iostream>#include <cstdio>#include <algorith...