#2700 聚会 Description Alice 正在组织一次有 $M$ 位同学参加的同学聚会。Alice 有 $N$ 种不同的茶，每种茶有各自的单价和类别（红茶或绿茶）。每隔一单位时间，聚会上都有一个同学离开。Alice 希望安排一种泡茶的方案，每单位时间都给所有剩下的同学们泡同一种之前没有泡过的茶，花费就是此茶的单价乘以剩余的同学数。同时，…

BZOJ #1999 [Noip2007]Core 树网的核 Description 设 $T=(V, E, W)$ 是一个无圈且连通的无向图（也称为无根树），每条边带有正整数的权，我们称 $T$ 为树网（treenetwork），其中 $V, E$ 分别表示结点与边的集合，$W$ 表示各边长度的集合，并设 $T$  有 $n$ 个结点。 路径：树…

这篇文章受密码保护，输入密码才能阅读

前言 校内模拟考试的其中一题，细节很多，测的时候 WA 了几个点，后来才改对 题面 题目链接 (luogu.org/problem/AT2702) 有一个 $10^8 \times 10^8$ 的网格图，相邻格点间上下左右的距离都是 $100m$ ，格点上面有 $n$ 个圆，每个圆半径为 $10m$ ，同一行或同一列最多只有一个圆。 现在要从 $(…

前言 分数不算高，100 + 37 + 0，但为什么就排到靠前了？？ T1 - Snakes 原题地址 一句话题面：$n$ 个数分成 $k+1$ 组，要求每组最大值和每个值的差之和的总和最少。 挺水的一个 DP，转移有修改捕网大小和不修改两种，不修改用 ST 表求最大值记录一下最后一段的代价，修改直接转移。 $f[i][j]$ 表示当前第 $i$ …

前言 Rank 5，$130$ 分，第二题因为懒就没怎么打，第三题用玄学拿(pian)到了 $20$ 分。 P1 题面 最近几年，一场新的金融危机爆发了，这场危机使得很多人陷入的经济问题的困境。一些 X 公司的员工试图通过要求加薪度过这一难关。 X 公司有着严格的等级制度，除了公司所有者小 H 以外，其他人都有一个直属上司。没有下属的员工称为工人，…

注意这套题目有版权，所以请不要转载题面。 前言 一些话 炸了，细节有很多没处理好。 题目有些不明显，丢了很多不该丢的分。 P1 质因数 题面 有一个正整数数列 $a_1,a_2,...,a_n$ 。定义函数 $f(x)$ 为 $x$ 的不同的质因数数量。 求 $f(a_1),f(a_2)...f(a_n)$ 。 $n<=10^6$ 思路 欧拉…

前言 Rank 7，Rating +48。 第二道题 $STL$ 莫名玄学炸 T 掉 40 分。 P1 电阻 题面 题目描述 询问要得出一个电阻值为 $\frac ab$ 的电阻。 元件由 $3$ 种方式组成： 一个电阻 一个元件与一个电阻串联 一个元件与一个电阻并联 输入格式 一行两个数， $a$ 和 $b$ 表示询问元件的阻值为 $\frac …

题面 题目传送 给你一个长度为 $n$ 的整数序列 ${a_1,a_2,\dots,a_n}$ ，要求从中找出一段连续的长度不超过 $m$ 的子序列，使得这个序列的和最大。 思路 单调队列优化 DP 模板题。 设 $t[i]$ 为 $s[1]+s[2]+\dots+s[i]$，则有状态转移方程 $f[i]=t[i]-min(t[i-1],t[i-2…

题面 题目传送门 在 $N*N$ 的棋盘上放 $K$ 个国王，国王可攻击相邻的 $8$ 个格子，求使它们无法互相攻击的方案总数。 思路 状压 DP 的模板，以前 DP 技能一直没怎么点，现在数据结构什么的都差不多了，开始补 DP。 预处理 对于每一行来说，我们可以用二进制来表示当前这一行的放置状态。然后再压成十进制。 然后预处理出对于一行来说的所有…