彬子的Blog

P1439 【模板】最长公共子序列（洛谷题面） 题目 题目描述： 给出 1,2,…,n1,2,\ldots,n1,2,…,n 的两个排列 P1P_1P1​ 和 P2P_2P2​ ，求它们的最长公共子序列。 输入格式： 第一行是一个数 nnn。 接下来两行，每行为 nnn 个数，为自然数 1,2,…,n1,2,\ldots,n1,2,…,n 的一个排列。 输出格式： 一个数，即最长公共子序列的长度。 数据范围与说明： 对于 50%50\%50% 的数据， n≤103n \le 10^3n≤103； 对于 100%100\%100% 的数据， n≤105n \le 10^5n≤105。 输入输出样例 #1 输入： 1235 3 2 1 4 51 2 3 4 5 输出： 13 题意 给定 1…n1 \ldots n1…n 的两个排列 P1P_1P1​、P2P_2P2​，求它们的最长公共子序列（LCS）长度。 思路 经典做法是 O(n2)O(n^2)O(n2) 动态规划，但对于 n≤105n \le 10^5n≤105 的数据会超时。利用“两个序列都是排列”的性质，可以将...

P1434 [SHOI2002] 滑雪（洛谷题面） 题目 题目描述： Michael 喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子： 123451 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9 一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度会减小。在上面的例子中，一条可行的滑坡为 24−17−16−124-17-16-124−17−16−1（从 242424 开始，在 111 结束）。当然 252525－242424－232323－…\ldots…－333－222－111 更长。事实上，这是最长的一条。 输入格式： 输入的第一行为表示区域的二维数组的行数 RRR 和列数 CCC。下面是 RRR 行，每行有 CCC...

P1923 【深基9.例4】求第 k 小的数（洛谷题面） 题目 题目描述： 输入 nnn（1≤n<50000001 \le n < 50000001≤n<5000000 且 nnn 为奇数）个数字 aia_iai​（1≤ai<1091 \le a_i < {10}^91≤ai​<109），输出这些数字的第 kkk 小的数。最小的数是第 000 小。 请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。 输入格式： 第一行有两个整数，分别表示 nnn 和 kkk。 第二行有 nnn 个整数，第 iii 个数表示 aia_iai​。 输出格式： 一个整数，表示第 kkk 小的数。 数据范围与说明： 输入输出样例 #1 输入： 125 14 3 2 1 5 输出： 12 代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include <bits/stdc++.h>using...

P2196 题目 题目描述： 在一个地图上有 N (N≤20)N\ (N \le 20)N (N≤20) 个地窖，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后每次可以移动到一个编号比当前节点大且联通的节点去挖地雷，当无满足条件的节点时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。 输入格式： 有若干行。 第 111 行只有一个数字，表示地窖的个数 NNN。 第 222 行有 NNN 个数，分别表示每个地窖中的地雷个数。 第 333 行至第 N+1N+1N+1 行表示地窖之间的连接情况： 第 333 行有 n−1n-1n−1 个数（000 或 111），表示第一个地窖至第 222 个、第 333 个 …\dots… 第 nnn 个地窖有否路径连接。如第 333 行为 1 1 0 0 0⋯01\space 1\space 0\space 0\space 0\cdots 01 1 0 0 0⋯0，则表示第 111 个地窖至第 222 个地窖有路径，至第 333 个地窖有路径，至第 444...

P1216 [IOI 1994 / USACO1.5] 数字三角形（洛谷题面） 题目 题目描述： 观察下面的数字金字塔。 写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 在上面的样例中，从 7→3→8→7→57 \to 3 \to 8 \to 7 \to 57→3→8→7→5 的路径产生了最大权值。 输入格式： 第一个行一个正整数 rrr，表示行的数目。 后面每行为这个数字金字塔特定行包含的整数。 输出格式： 单独的一行，包含那个可能得到的最大的和。 数据范围与说明： 【数据范围】 对于 100%100\%100% 的数据，1≤r≤10001\le r\le 10001≤r≤1000，所有输入在 [0,100][0,100][0,100] 范围内。 题目翻译来自 NOCOW。 IOI1994 Day1T1 / USACO Training Section 1.5。 输入输出样例 #1 输入： 123456573 88 1 02 7 4 44 5 2 6 5 输出： 130 ...

P3654 题目 题目描述： 可是……这个篮球场，好像很久没有使用过的样子啊…… 里面堆满了学校的各种杂物呢…… 我们 Aqours 的成员要怎么在里面列队站下呢？ 我们浦之星女子学院的篮球场是一个 RRR 行 CCC 列的矩阵，其中堆满了各种学校的杂物 (用 # 表示)，空地 (用 . 表示) 好像并不多的样子呢…… 我们 Aqours 现在已经一共有 KKK 个队员了，要歌唱舞蹈起来的话，我们得排成一条 1×K1\times K1×K 的直线，一个接一个地站在篮球场的空地上呢 (横竖均可)。 我们想知道一共有多少种可行的站位方式呢。 Aqours 的真正的粉丝的你，能帮我们算算吗？ 输入格式： 第一行三个整数 R,C,KR, C, KR,C,K。 接下来的 RRR 行 CCC 列，表示浦之星女子学院篮球场。 输出格式： 总共的站位方式数量。 数据范围与说明： RRR CCC KKK 备注 1∼21\sim21∼2 ≤10\leq 10≤10 ≤10\leq 10≤10 ≤min⁡(R,C)\leq...

P10415（洛谷题面） 题目 题目描述： 给定一个 W×HW\times HW×H 的长方形，两边长度均为整数。小蓝想把它切割为很多个边长为整数的小正方形。假设切割没有任何损耗，正方形的边长至少为 222，不允许出现余料，要求所有正方形的大小相等，请问最多能切割出多少个? 输入格式： 输入一行，包含两个整数 W,HW, HW,H，用一个空格分隔。 输出格式： 输出一行包含一个整数表示答案。如果不存在满足要求的方案，输出 000。 数据范围与说明： 【样例解释 1】 切割成 5×10=505\times 10=505×10=50 个边长为 222 的正方形。 【评测用例规模与约定】 对于 30%30\%30% 的评测用例，1≤W,H≤10001\le W,H\le 10001≤W,H≤1000； 对于 60%60\%60% 的评测用例，1≤W,H≤1061\le W,H\le 10^61≤W,H≤106； 对于所有评测用例，1≤W,H≤1091\le W,H\le 10^91≤W,H≤109。 输入输出样例 #1 输入： 110 20 输出： 150 输入输出样例...

P1048 [NOIP 2005 普及组] 采药（洛谷题面） 题目 题目描述： 辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？ 输入格式： 第一行有 222 个整数 TTT（1≤T≤10001 \le T \le 10001≤T≤1000）和 MMM（1≤M≤1001 \le M \le 1001≤M≤100），用一个空格隔开，TTT 代表总共能够用来采药的时间，MMM 代表山洞里的草药的数目。 接下来的 MMM 行每行包括两个在 111 到 100100100 之间（包括 111 和...

P2347（洛谷题面） 题目 题目描述： 设有 1g1\mathrm{g}1g、2g2\mathrm{g}2g、3g3\mathrm{g}3g、5g5\mathrm{g}5g、10g10\mathrm{g}10g、20g20\mathrm{g}20g 的砝码各若干枚（其总重 ），可以表示成多少种重量？ 输入格式： 输入方式：a1,a2,a3,a4,a5,a6a_1 , a_2 ,a_3 , a_4 , a_5 ,a_6a1​,a2​,a3​,a4​,a5​,a6​ （表示 1g1\mathrm{g}1g 砝码有 a1a_1a1​ 个，2g2\mathrm{g}2g 砝码有 a2a_2a2​ 个，…\dots…，20g20\mathrm{g}20g 砝码有 a6a_6a6​ 个） 输出格式： 输出方式：Total=N （NNN 表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况） 数据范围与说明： 【题目来源】 NOIP 1996 提高组第四题 输入输出样例 #1 输入： 11 1 0 0 0 0 输出： 1Total=3 ...

P8195 题目 题目描述： 传智专修学院给了小智一个仅包含小写字母的字符串 sss，他想知道，里面出现了多少次子串 chuanzhi 呢。 我们称一个字符串 ttt 是 sss 的子串，当且仅当将 sss 的开头若干个（可以为 0 个）连续字符和结尾若干个（可以为 0 个）连续字符删去后，剩下的字符串和 ttt 相同。例如，我们称 ab 是 abc 的子串，但 ac 不是 abc 的子串。 输入格式： 输入只有一行一个字符串，表示字符串 sss。 输出格式： 输出一行一个整数表示答案。 数据范围与说明： 数据规模与约定 对于全部的测试点，保证 1≤∣s∣≤4×1051 \leq |s| \leq 4 \times 10^51≤∣s∣≤4×105，∣s∣|s|∣s∣ 表示 sss 的长度，且 sss 中只有小写字母。 输入输出样例 #1 输入： 1welcometochuanzhicupchuanzhi 输出： 12 代码 123456789101112131415161718192021#include<bits/stdc++.h>using...