题目描述刚入学,班上一共有 n 名同学,互相都不认识。每天,班上会多出一对新朋友(xi,yi),xi≠yi(xi,yi),xi≠yi,在这对新朋友确定后,大家会一起商量翘课的事情。一个人翘课,仅当他的至少 K 个朋友也翘课。问每天最多会有多少人翘课。 题解(暴力部分):感觉还挺具有思考性的,蒟蒻考场 ...
洛谷P1385 【密令】
数论题与DP结合应该是很常见了,尤其是背包问题,经常可以换汤不换药的考很多种题目。。本题一个最显著的特征就是:对于一个序列,不论你进行多少此操作,其字典序总和不变(因为操作会加一减一,抵消了),进一步推进的话,就会发现一个序列无论长成啥样都无所谓,因为答案只和他的字典序总和有关(因为你一定可以通过一 ...
洛谷P2686 【老虎的题目】
这题确实可以通过一些微妙的做法,巧妙的将复杂度降低,但是并不具有 通用性。 做法依然是DP,设$f[i][j]$表示从第i个题目,到第j个题目可达到的最大值。 一个不难想出的式子是: 当$low<=l[j]-l[i-1]<=high$时,$f[i][j]=max(f[x][y] |x&l ...
[AHOI2017初中组]rexp
马上又是一年一度的AHOI了呢……目前两个题解都是正解的递归算法,但是考场上像我这种蒟蒻,只能想到暴力模拟对不对啊(只有你一个人吧) 所以本蒟蒻就给大家模拟一下考场上如何 暴力骗分!因为暴力骗分的程序也能拿90(第八个点超时了),所以只要第一题稳住,第二题玄学找规律骗分,拿一等奖真的不是梦! 暴力 ...
[SDOI2010]古代猪文
一个数论没学到1个月的蒟蒻在经过题解的帮助下能A了这道综合性很强的题,感到十分荣幸_(:з」∠)此题有哪些数论的应用其他题解已经十分完备了,这里我就给大家讲讲做这道题的一些思路以及一些板子在洛谷很少见的一些写法。 题意 推出真正式子的描述就两段 ...根据相关文献记载,那个朝代流传的猪文文字恰 ...
[NOI2001]食物链
开三个并查集感觉太作弊了于是学了下带权并查集,写篇题解巩固一下_(:з」∠)_。 上网大概搜了下,对带权并查集的诠释是这样的: 在对并查集进行路径压缩和合并操作时,这些权值具有一定属性,即可将他们与父节点的关系,变化为与所在树的根结点关系。也就是说,权值代表着当前节点与父节点的某种关系(即使路径压缩 ...
USACO刷题集锦(Part.4)
仿佛活在题解的阴影里。。。 平均蓝题对于刚拿tg1=的我仍有些吃力,虽然题解一点就通但这没有刷题的任何效果。。 以后还是要克制一下自己的思考时间,不能那道题就翻题解,点TAG,你们这个功能害人不浅啊! $Section 5.1$[USACO5.1]圈奶牛Fencing the Cows题面: 求凸包 ...
USACO刷题集锦(Part.3)
感觉好像比第三章题少了点,但是个个都好麻烦啊。。 不打啥$eg$了,这些题全得自己理一下思路。。 $Section 4.1$麦香牛块Beef McNuggets:题面: “看,”奶牛们说,“如果你只用一次能装3块、6块或者10块的三种包装盒包装麦香牛块,你就不可能满足一次只想买1、2、4、5、7、8 ...
USACO刷题集锦(Part.2)
完了,第三章就难死了,后面估计每张都是一个新的PART。。 $Section 3.1$ 难题:P2723,2724还有等等,估计每道题都要稍微摸一下了。。。 $eg_1:P2723$ 丑数 Humble Numbers题意:对于一给定的素数集合 S = {p1, p2, …, pK},考虑一个正整 ...