仙人掌[ZJOI2017]

题目描述https://www.luogu.com.cn/problem/P3687 题面里咋还有张图啊,就不放这了 题解首先,如果原图不是仙人掌,显然答案为0 如果原图是一棵树,那么我们可以选择若干条边不相交的路径,如果某条路径长度大于一,就将路径的两个端点间加一条边,那么这样构造出来的图一定是一个仙人掌 所以原问题实际在问有多少种方案用若干条边不相交的路径覆盖原图 设f[x]表示考虑x的...

寻找车位[Code+#3]

题目描述access_globe 有一个巨大的停车场,这个停车场有N行,每行有M个车位。为了美观,access_globe 在建立这个停车场时,规定这个停车场必须是长条形的,即N\ge M。每个车位都是一个正方形的区域。 最近,access_globe 正在为抽不到 Missing Poster 而苦恼,因此他请你帮他维护这个停车场。你需要支持两个事件: 一辆车停到某一个车位中,或一辆车从...

快餐店[NOI2013]

题目描述小 T 打算在城市 C 开设一家外送快餐店。送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的,小 T 希望快餐店的地址选在离最远的顾客距离最近的地方。 快餐店的顾客分布在城市 C 的N个建筑中,这N个建筑通过恰好N条双向道路连接起来,不存在任何两条道路连接了相同的两个建筑。任意两个建筑之间至少存在一条由双向道路连接而成的路径。小 T 的快餐店可以开设在任一建筑中,也可...

贪吃蛇[CSP2020]

题面https://www.luogu.com.cn/problem/P7078 题解考场上开T4的时候只有40~50分钟了 努力思索了10分钟想到一个结论(中途想假了一次) 然后发现部分分还挺多:70分 70分简单说说70分做法:先假设游戏一直进行,那么就可以用set把每轮游戏是谁吃谁处理出来 显然游戏共有n-1轮,从最后一轮开始向前扫,假设当前到第i轮,是A吃掉B,记t为第i\sim ...

函数调用[CSP2020]

题目描述https://www.luogu.com.cn/problem/P7077 题解第一眼看像是数据结构题? 后来发现这题压根不用数据结构 考虑对于给出的操作建一个图:对于所有操作3,按顺序向它调用的函数连边,这样会得到一个DAG 对于乘法操作,在最后给所有数组元素乘上就好了,关键在于每个加法操作最后乘了一个多大的系数 假设整个数组只有一个元素,对它依次执行:+1, *3, +2, *...

动物园[CSP2020]

题面https://www.luogu.com.cn/problem/P7076 题解这应该是最签到的一题了吧 饲料共有$c$种,1e8存不下,先对饲料编号进行重新标号 注意这里并不需要进行离散化(排序去重),由于$q_i$互不相同,所以只需要把第$i$种饲料的编号看作$i$即可 (什么叫签到题啊) 首先对于已有的动物,先处理出$K$位中哪些位有动物是1 然后扫一遍所有要求找出哪些饲料必买 ...

儒略日[CSP2020]

题面太长不放 https://www.luogu.com.cn/problem/P7075 题解如何优雅地在开考40分钟内完成此题?首先最重要的一点:发现1600年之前的闰年规律都是每4年一次,而1600又正好是400的倍数,所以以1600作为分界线,分成1600年前后两种情况比较好处理 其次,发现0年不存在也不方便,所以把所有的负数年份+1,输出时再改回来 公元前4913年1月1日是第0天...

矩形区域[IOI2019]

题目描述https://loj.ac/problem/3177 题解假设某个合法的矩形只有一行,是$a_{1,l}\sim a_{1,r}$,那么显然有这样一个结论成立:$a_{1,l-1}$是$a_{1,r+1}$左侧第一个大于它的 或者$a_{1,r+1}$是$a_{1,l-1}$右侧第一个大于它的 那么对于一个合法矩形,每一行都应该满足这个条件 每一列应该也要满足类似的条件 所以对于一...

Mr Panda and Survey[HDU6001]

题目链接https://acm.hdu.edu.cn/showproblem.php?pid=6001 题解设$f(S)$表示有多少种选问卷的情况使得$S$中所有元素都不是好问题 设$ans[S]$表示选择的问题集合是$S$时,有多少种选择问卷的方案使得它们全部是好问题 那么由容斥原理,$ans[S]=2^n+\sum\limits_{S_2\subseteq S}(-1)^{t(S)}f(...

矩阵游戏[NOI2013]

题目描述婷婷是个喜欢矩阵的小朋友,有一天她想用电脑生成一个巨大的$n$行$m$列的矩阵(你不用担心她如何存储)。她生成的这个矩阵满足一个神奇的性质:若用$F[i][j]$来表示矩阵中第$i$行第$j$列的元素,则$F[i][j]$满足下面的递推式: $$F[1][1]=1$$ $$F[i,j]=a\times F[i][j-1]+b (j\neq 1)$$ $$F[i,1]=c\times ...