子谦。

未归档

入门教程(10)

/ 注册

全部文章 / 未归档（共52篇）

P2331 [SCOI2005]最大子矩阵

我是题面题面这么简洁，清晰，易懂，真是不可多得的良心题面（比我上一篇博客那道题良心多了）我们会发现m只有2 如果m是一个较大的数的话可能会麻烦一点，只有2的话就很好做了我们先来考虑m为1的情况，很简单，\(f[i][j][0/1]\)表示是否选第i个，已经选了j个连续矩形，最大为多少，...

2019-01-15

0 379

P3709 大爷的字符串题

我是题面神奇的阅读题，没有良好的语文功底可能就真的要拿10分了很明显这道题的意思是求区间众数出现的次数的相反数怎么维护呢？又没有强制在线，上莫队啊 \(cnt[i]\)记录\(i\)出现的次数，\(sum[i]\)记录出现i次的数有几个，\(maxa\)记录答案好了，这道题我们做完...

2019-01-10

0 491

UVA10859 Placing Lampposts

我是题面这道题使我知道了一种很神奇的方法，一定要认真看哦如果没有被两盏灯同时照亮的边数应尽量大这个限制的话，这就是一道很经典的树形DP题——没有上司的舞会很可惜，这个限制就在那里，它使得我辛苦写出来的贪心是错的，我只能做到尽量小 /托腮由于总的边数是确定的，我们可以通过维护被一盏灯照...

2019-01-10

0 353

P2286 [HNOI2004]宠物收养场

我是题面题意简单明了，两种数，如果加入一个数的时候有另一种数还存在，那就取出另一种数中与这个数差值的绝对值最小的将其删除（多个则取较小），并对答案产生它们差值的绝对值的贡献，如果没有另一种数存在，那就先将这个数存下平衡树裸题，直接两个平衡树维护就ok了，一个也能维护，稍麻烦一点线段树好像...

2019-01-10

0 506

P1484 种树

我是题面会T+M的方法一：读完题很容易想到直接DP \(f[i][j][k]\)表示到第\(i\)棵树为止共种了\(j\)棵树（\(k\)为1表示包括第\(i\)棵树，否则不包括）最大权值和为多少显然，先不说会T，我们甚至开不下这么大的数组优化掉一维，\(f[i][j]\)表示选\...

2019-01-09

0 413

CF530D sum in the tree

我是题面、原题地址很简单的一道贪心题首先，先想想怎么判断是否合法题目中说，a是自然数，那么子节点的s明显是不能比父节点大的，如果比父节点大，不合法！所有深度为偶数的点的s被删除了，也只有深度为偶数的点被删除了，所以如果深度为奇数的点被删除了，或者有深度为偶数的点没有被删除，不合法！ ...

2019-01-08

0 430

洛谷 P5078 Tweetuzki 爱军训

题目连接很明显，1e6的范围，要么nlgn要么O(n) nlgn的话可能会想到借助一些数据结构，我并没有想到这种做法对于这种题，O(n)的做法要么是线性递推，要么就应该是贪心了考虑这道题我们怎么贪心如果可以走无数个来回的话，那很明显我们可以从小到大依次取出，一定是最大的可惜只能...

2018-12-14

0 391

洛谷 P1560 蜗牛的旅行

明显这是一道搜索题，其他题解写的有点复杂，我有更简便的写法既然题目说走到不能再走，那我们就干脆一点，一条路走到黑，不到南墙不回头，一下把要走的路都走完，不但效率高，也好写，关键是大大节省了系统栈一口气走很多点的关键在于如何记录一个点是否遍历过呢？退出后又如何删除标记呢？或许正是这两个问题...

2018-11-07

0 326

洛谷 [USACO09OPEN]工作调度

题面读完题，我们会发现有一个很重要的信息，每件物品代价相同，但价值不同。那么我们很容易想到，在满足限制的情况下，我们肯定会选择价值尽可能大的物品。我们可否用背包来实现呢，答案是否定的，或者说我不会QwQ 那么，我们来看看贪心由于物品的代价相同，那么当物品之间冲突时，我们留下价值大者，必...

2018-10-30

0 415

洛谷 P3177 树上染色

题面题目要求将k个点染成黑色，求黑点两两距离及白点两两距离，使他们之和最大。我们可以将距离转化为路径，然后再将路径路径拆分成边，就可以记录每条边被经过的次数，直接计算即可。很简单对吧？那么问题来了，距离转化为路径好理解，路径拆为边也好说，可是每条边被经过的次数怎么计算呢？我们可以这样...

2018-10-15

0 415