夜间模式
字体
阴影
滤镜
主题色
洛谷P1331 海战 题解
题目传送门 思路 肯定食用dfs啦。。。 但关键是两条船接触了怎么判断呢?? 上图: 可以发现一下规律 当两条船接触时,必有一条直线连续穿过两条船 当一条船不与另一条船接触时,没有一条直线连续穿过两条船 所以只需要在每一次碰见一条船的一部分(一条船内每个点都要拓展一遍)时,将其沿右上、左下分别拓展一遍,边拓展边用sum前缀和check一遍就好啦。。…
10082. 「一本通 3.3 例 1」Word Rings
题意 每组数据读入一个n和n个字符串。定义前2个与末尾2个字母相同可以连接。问使这个环串的平均长度最大。求这个最大值。不存在输出No solution。 思路 平均值公式: $$Average=(E_1+E_2+…..+E_n)/n$$ $$Average*n=(E_1+E_2+…+E_n)$$ $$(E_1-Average)+(E_2-Avera…
10086. 「一本通 3.3 练习 3」Easy SSSP
题意 给你一个图,问从源点到每个节点的最短路径分别是多少。 如果存在负权回路,只输出一行 -1;如果不存在负权回路,再求出一个点 S 到每个点的最短路的长度。如果 S 与这个点不连通,则输出 NoPath。 思路 当然食用spfa啦。 先跑一下非源点的。万一数据卡你其他有环呢? 然后再跑一次源点。得出Ans [crayon-5e3191330c50…
10087. 「一本通 3.4 例 1」Intervals
题意 从$0\sim 5\times 10^4$中选出尽量少的整数,使每个区间$ [a_i,b_i]$内都有至少 $c_i$个数被选出。 思路 当然食用spfa啦。 设s[k]表示0~k中至少选多少个整数。根据题意可得: $$s[b_i]-s[a_i-1]\geq c_i$$ $$s[k]-s[k-1]\geq0$$ $$s[k]-s[k-1]\l…
10088. 「一本通 3.4 例 2」出纳员问题
题意 R(0)、R(1)、R(2)…R(23)表示第x个时刻需要R(x)个出纳员,有n个出纳员申请工作,第i个出纳员从t_i时刻开始工作8小时,问至少需要多少出纳员? 思路 设$x[i]$表示第$i$时刻实际上需要雇佣$x[i]$人,$r[i]$为第$i$时刻至少需要$r[i]$个人。 $$x[i-7]+x[i-6]+x[i-5]+x[i-4]+x…
10089. 「一本通 3.4 练习 1」糖果
题意 满足条件: 如果 X=1.表示第 A 个小朋友分到的糖果必须和第 B 个小朋友分到的精果一样多。 如果 X=2,表示第 A 个小朋友分到的糖果必须少于第 B 个小朋友分到的糖果。 如果 X=3,表示第 A 个小朋友分到的糖果必须不少于第 B 个小朋友分到的糖果。 如果 X=4,表示第 A 个小朋友分到的糖果必须多于第 B 个小朋友分到的糖果。…
10090. 「一本通 3.4 练习 2」布局 Layout
题意 有些奶牛是好基友,它们希望彼此之间的距离小于等于某个数。有些奶牛是情敌,它们希望彼此之间的距离大于等于某个数。 思路 如果两只奶牛是好基友,那么: $$A-B\leq D$$ 如果两只奶牛是情敌,那么: $$A-B\ge D$$ 即: $$D\leq A-B$$ 也就是: $$B-A\leq -D$$ 直接上代码: [crayon-5e319…
10117. 「一本通 4.1 练习 2」简单题
题意 有一个 $n$ 个元素的数组,每个元素初始均为 $0$。有 $m$ 条指令,要么让其中一段连续序列数字反转——$0$ 变 $1$,$1$ 变 $0$(操作 $1$),要么询问某个元素的值(操作 $2$)。 思路 当然是树状数组啦。。。 这里介绍C++的一大利器——位运算。 &在C++里叫做与运算。应该差不多吧。。大概就是这样的:(按一…
10121. 「一本通 4.2 例 3」与众不同
题意 定义完美序列:一段连续的序列满足序列中的数互不相同。 想知道区间 $[L,R]$ 之间最长的完美序列长度。 思路 设$las[x]$表示盈利$x$最近出现位置。 设$st[i]$表示以第$i$个数结尾的最长完美序列的起始位置。 $$st[i]=max(st[i-1],las[a[i]]+1)$$ 设$f[i]$表示以第$i$个数结尾的最长完美…
2597. 「NOIP2011」选择客栈
题意 有$n$个客栈,每个客栈都配有咖啡馆。有两名旅客想住在同色调的客栈中,又想在两客栈之间的咖啡馆中小聚,咖啡馆的价钱不能高于$p$。 对于 $100\%$ 的数据,有 $2\leq n\leq2\times 10^6$,$0<k\leq10^4$ ,$0\leq p\leq100$,$0\leq$ 最低消费 $\leq100$ 。 思路 …