wanqi2010-CSDN博客

原创 [NOIP2019]P5662 纪念品

这道题是道巧妙的思路题，要想到每天即使拿手里也可以当作全卖了再当天全买了。这样就相当于转换成了T-1天个完全背包问题，背包容量为金钱数，背包最大价值为所有物品下一天与今天物品价值差的和。 #include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <set> #include <cm

2020-08-05 21:03:21 276

原创【NOIP2018]】P5021 赛道修建

看到题意描述第一反应就是先二分那个修建的 mm 条赛道中长度最小的赛道的长度 kk ，然后 O(n)O(n) 或 O(n\log n)O(nlogn) 判断。那么怎么判断呢？对于每个结点，把所有传上来的值 valval 放进一个 multisetmultiset ，其实这些值对答案有贡献就两种情况： val\geq kval≥k val_a+val_b\geq kval a +val b ≥k 那么第一种情况可以不用放进 multisetmultiset，直接答案 +1+1 就好了。第二种情

2020-08-03 22:14:36 170

原创 P2038 无线网络发射器选址

这道题我用来练习二维树状数组把一维变成二维思路也很简单，代码不麻烦关键是计算区间和时要注意正方形边界是否包含，是否-1 #include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <cmath> inline int lowbit(int

2020-07-31 23:13:49 133

原创【NOIP2014】P2296 寻找道路

一道比较基础的图遍历的题。思路很巧妙，要考虑到反向建图，反向BFS,找出能达到终点的点1，再正向遍历，找到这些点1中出边点均能到终点的所有点2，然后再从起点遍历，只所有2类点中找最短路径一开始总是TLE，后来发现是初始化建图时候没有考虑到重复操作，同一个点被处理了多次，时间耗时大大降低，见代码中关键优化一段 #include <cstdio> #include <iostream> #include <cstring> #include <algorithm&g

2020-07-31 22:29:59 151

原创【洛谷】【NOIP2014】P1351 联合权值

本题练习用邻接表储存图，之后对每个点的邻接点统计最大值，次大值，总和联合权值即为每组中最大值×次大值的最大一个。每个组的总和为累加和的平方-每个点的值平方，每次操作均取模，防止爆long long #include <cstdio> #include <iostream> #include <cstring> using namespace std; int n; struct node { int v; int next; } a[400005]; int hea

2020-07-26 21:49:15 85

原创【洛谷】P5318 【深基18.例3】查找文献

DFS和BFS的入门学习题目使用set储存每个点可达的边，自动对每个点可达的点进行排序，减少后续遍历sort的耗时。使用递归来进行DFS，使用队列queue来进行BFS #include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <set> #include <queue> #include <cmath>

2020-07-22 21:14:21 296

原创 2020-05-22

设计模式一句话总结，个人理解：模板方法：将公用方法放在基类或接口类，甚至是执行过程，并声明为虚函数。子类只用重载其中部分步骤，降低变更需求时的修改量策略模式：if else 这样的分支较多且处理过程类似时可以用多态方式，基类指针调用，降低增加需求时代码修改量观察者模式：多个对象订阅一个对象的修改，通常用一个接口类实现。在主对象变化时通知所有订阅对象修改自身。主对象不用知道有谁订阅 ...

2020-05-22 18:06:35 301

wanqi2010的博客