题目 题目描述 Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a…

前言：最近做了很多动态规划题，但是每次遇到新的题目的时候还是做不出来，于是就像做一个小结，梳理下近些天做的题目，从中获取经验。 第零节：DP的基础概念 动态规划和其他某些算法具有一定的相似度，都是利用问题的可划分性以及子问题的相似性来进行归纳，降低时间复杂度。 来说说动态规划的几个基本条件： 条件 解释 无后效性 已求解的子问题不受后续阶段的影响[…

题目 题目描述 杨先生希望为他的班级拍照。学生将排成一行，每行不超过后面的行，并且行的左端对齐。例如，可以安排12名学生排列（从后到前）5,3,3和1名学生。 [crayon-67ee457cc66be084756870/] 此外，杨先生希望每排学生安排高度从左到右减少。此外，学生身高应从后向前减少。想想看，杨先生看到，对于这个12人的例子，至少有…

题目 题目描述 [latex]1944[/latex] 年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛，营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里，迷宫地形复杂，但幸好麦克得到了迷宫的地形图。迷宫的外形是一个长方形，其南北方向被划分为 [latex]N[/latex] 行，东西方向被划分为 [latex]M[/latex] 列…

题目 PDF 题解 虽然我很想说这是一道字典树模板题，但是还是有点技巧的。 对于每组输入，我们先把它存入字典树，然后再来查找（也就是所谓的离线） 为了说明方便，用表格说明一下变量吧 变量名 变量作用 [latex]st[/latex] 保存读入的字符串，用于离线 [latex]word[/latex] 保存字典树每条边被覆盖的次数，遍历时为1说明不…

题目 题目描述 无向连通图G 有n 个点，n – 1 条边。点从1 到n 依次编号，编号为 i 的点的权值为W i ，每条边的长度均为1 。图上两点( u , v ) 的距离定义为u 点到v 点的最短距离。对于图G 上的点对( u, v) ，若它们的距离为2 ，则它们之间会产生Wu ×Wv 的联合权值。 请问图G 上所有可产生联合权值的有序点对中，…

题目 题目描述 C 国有n 个大城市和m 条道路，每条道路连接这n 个城市中的某两个城市。任意两个 城市之间最多只有一条道路直接相连。这m 条道路中有一部分为单向通行的道路，一部分 为双向通行的道路，双向通行的道路在统计条数时也计为1 条。 C 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价 格不一定相同。但是，同一种商…

题目 题目描述 求有多少种长度为 n 的序列 A，满足以下条件： 1 ~ n 这 n 个数在序列中各出现了一次 若第 i 个数 A[i] 的值为 i，则称 i 是稳定的。序列恰好有 m 个数是稳定的 满足条件的序列可能很多，序列数对 10^9+7 取模。 输入格式 第一行一个数 T，表示有 T 组数据。 接下来 T 行，每行两个整数 n、m。 T=…

题目 题目描述 给出 [latex]N[/latex] ,求 [latex]1[/latex] 到 [latex]N[/latex] 个数中选出任意个数相乘能组成的最大平方数,由 于此数可能很大,你只需要输出此数除 [latex]100000007[/latex] 的余数即可。 样例输入 [crayon-67ee457cc6fb0096662793…

2018年的国际信息学奥赛的比赛已经告一段落，官网也发布了一些视频，蒟蒻看没人搬就搬过来了。 【国际信息学奥赛】IOI 2018 JAPAN Arrival Sep.1 【国际信息学奥赛】IOI 2018 JAPAN Opening Ceremony Sep.2 【国际信息学奥赛】IOI 2018 JAPAN Contest Day 1 Sep.3…