夜间模式暗黑模式
字体
阴影
滤镜
圆角
主题色
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$ 。 思路 …
10128. 「一本通 4.3 练习 2」花神游历各国
题意 每一次旅行中,花神会选择一条旅游路线,它在那一串国家中是连续的一段,这次旅行带来的开心值是这些国家的喜欢度的总和,当然花神对这些国家的喜欢程序并不是恒定的,有时会突然对某些国家产生反感,使他对这些国家的喜欢度 $\delta$ 变为 $\sqrt \delta$(可能是花神虐爆了那些国家的 OI,从而感到乏味)。 现在给出花神每次的旅行路线,…
10202. 「一本通 6.2 练习 5」樱花
题意 求不定方程: $$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$$ 的正整数解 $(x,y)$ 的数目。 思路 $$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$$ $$\frac{y}{xy}+\frac{x}{xy}=\frac{1}{n!}$$ $$\frac{x+y}{xy}=\…
10147. 「一本通 5.1 例 1」石子合并
题意 将 $n$ 堆石子绕圆形操场排放,现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆,并将新的一堆的石子数记做该次合并的得分。 请编写一个程序,读入堆数 $n$ 及每堆的石子数,并进行如下计算: 选择一种合并石子的方案,使得做 $n-1$ 次合并得分总和最大。选择一种合并石子的方案,使得做 $n-1$ 次合并得分总和最小。 思…
10153. 「一本通 5.2 例 1」二叉苹果树
题意 有一棵二叉苹果树,如果数字有分叉,一定是分两叉,即没有只有一个儿子的节点。这棵树共 $N$ 个节点,标号 $1$ 至 $N$,树根编号一定为 $1$。 我们用一根树枝两端连接的节点编号描述一根树枝的位置。一棵有四根树枝的苹果树,因为树枝太多了,需要剪枝。但是一些树枝上长有苹果,给定需要保留的树枝数量,求最多能留住多少苹果。 思路 设$f[i]…
10149. 「一本通 5.1 例 3」凸多边形的划分
题意 给定一个具有 $N$ 个顶点的凸多边形,将顶点从 $1$ 至 $N$ 标号,每个顶点的权值都是一个正整数。将这个凸多边形划分成 $N-2$ 个互不相交的三角形,试求这些三角形顶点的权值乘积和至少为多少。 思路 首先随便搞一个多边形: 然后给它顺时针每个顶点表上序号: 然后枚举$i,j$,要求:$i+1<j$,然后给$i,j$连一条线,分…
10106. 「一本通 3.7 例 2」单词游戏
题意 有 $N$ 个盘子,每个盘子上写着一个仅由小写字母组成的英文单词。你需要给这些盘子安排一个合适的顺序,使得相邻两个盘子中,前一个盘子上单词的末字母等于后一个盘子上单词的首字母。请你编写一个程序,判断是否能达到这一要求。如果能,请给出一个合适的顺序。多组数据。第一行给出数据组数 $T$,每组数据第一行给出盘子数量 $N$,接下去 $N$ 行给出…
10178. 「一本通 5.5 例 4」旅行问题
题意 John 打算驾驶一辆汽车周游一个环形公路。公路上总共有 $n$ 车站,每站都有若干升汽油(有的站可能油量为零),每升油可以让汽车行驶一千米。John 必须从某个车站出发,一直按顺时针(或逆时针)方向走遍所有的车站,并回到起点。在一开始的时候,汽车内油量为零,John 每到一个车站就把该站所有的油都带上(起点站亦是如此),…