shyyhs

题解

DP专题(52) 图论(4) 多校补题(2) 数据结构(27) 数论(4) 日记(14) 未归档(38)

/ 注册

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

[SCOI2010]幸运数字来自专栏

思路本来以为是数位,想不出状态,后来又想着容斥一下以为都是的倍数的数量+的数量-的数量,然后就死了.万万没想到是. 思路很简单,就是先爆搜出那些合法的数/基数,其他数一定是这些数的倍数,然后把爆搜的数去个重,有些数是里面数的倍数,然后从小到大排序一下(剪枝).然后再用容斥原理统计答案即可. 坑点 ...

dfs 容斥原理

2021-03-22

3 846

Tree Decoration 来自专栏

思路不要想复杂就好了...贪心的选取子树中最小的那个,多了就不要选,少了就更新数量...一个dfs就可以解决了.. 代码 #include <bits/stdc++.h> using namespace std; const int N=1e5+5; typedef long long...

dfs 贪心

2021-03-08

0 716

Giving Awards 来自专栏

思路: 因为给定的是个有向图,所以一定有解,构造方案就是把这个u当前它欠钱的人先安排好,然后直接输出方案就是一组解了...其实就是按dfs序统计即可啦... 代码: #include <bits/stdc++.h> using namespace std; const int N=1e5...

dfs

2021-02-21

1 583

边的染色来自专栏

前言: 思维不够,看到这种陌生的题目无从下手. 思路: 这题应该做过一次的人会觉得它其实并不难.主要思想:把边权->点权.这样做的好处是,无论你怎么分配点权,在环内的异或值一定为(前提是环内的一定合法.)做题步骤也是围绕这些性质来的.1.首先判断给定的点是否有矛盾,就是你给一个点赋值,它假如是...

dfs 图论

2021-01-28

2 688

Alliances 来自专栏

前言: 这个每日一题对我来说稍微复杂了亿点点... 思路: 首先的题目的条件就是所有点的lca到所有点的路径都被标记了.我们要求点V到这些点集的一个最小距离. 假如这个点集的LCA和V的lca不是LCA的话,那么显然的一个结论距离就是V到lca的距离. 假如不是,那么V一定位于LCA的子树中.这是我...

dfs 二分 LCA

2021-01-22

2 841

最长树链来自专栏

前言: 之前那个博客有大问题...确实是数据太水了. 思路: 首先我们处理出4e4以内的质数,然后因为任何合数都可以写成的形式,显然大于4e4的数,假如经过这么一次筛选,一定是不会出现超过4e4的合数.对于每个数,我们处理出来它们的质因子,这里呢,用的是最原始的判断方法,假如有n个数是大质数,那么就...

思维题 dfs 数论

2021-01-11

5 1000

Camels and Bridge 来自专栏

这题也是拖欠了几天的...emmm 题目大意:你有n头骆驼,他们要过桥,桥呢,有m座有两个属性l,v,l是它的长度,v表示在这个长度下,你不能超过v的载重,你呢,必须.让你安排下他们的过桥顺序.假如它们能够过桥,就要算出你安排的第一头骆驼和最后一头骆驼的间距,否则的话,输出-1. 思路是这样滴....

DFS 二分 DP

2020-10-16

8 820

Garland 来自专栏

可能就我写的比较麻烦...emmm菜的真实.我写了两个dfs,因为我不想写lca...acm带板子还是好..写完看了评论区,都比我短.思路就是dfs1找到第一个sum/3,dfs2找到第二个sum/3即可. //i<->ai ti a[i]=0的i为根节点 #include <bi...

DFS

2020-10-14

6 843

[SCOI2009]最长距离来自专栏

100%的数据,满足1<=N,M<=30,0<=T<=30---来自洛谷的数据范围.简单来说就是暴力,暴力枚举一个点,然后再算到其他点的之间最少需要移除多少障碍物.然后就结束了. #include <bits/stdc++.h> using namespace s...

DFS

2020-09-25

6 909

Numbers 来自专栏

直接dfs即可...emmm好水,好了,学树状数组线段树去了...ggg #include <bits/stdc++.h> using namespace std; const int N=100; string s; int vis[N],ans; void dfs(int u,in...

DFS

2020-09-18

2 641