题目描述 给定一个长度为 $n$ 的数字串 $a$，和一个长度为 $m$ 的数字串 $b$，保证 $b$ 中出现的元素在 $a$ 中都出现过，且 $b$ 中任一元素只出现过一次。现求一个 $a$ 的长度尽可能短，且尽可能靠左的子串，使 $b$ 成为其子序列。 数据范围 多测 $1≤T≤1000$ $1≤m≤n≤10^6$ $1≤∑n≤5×10^6$…

题目大意 在一条数轴上有 $n$ 人 $k$ 把钥匙，每个人能拿且仅能拿一把钥匙，办公室坐标为 $p$ ，所有人同时开始去拿钥匙，然后去办公室。求所有人消耗的最大时长。 每人的坐标在 $a_i$ ，每个钥匙的坐标在 $b_i$ 。 题解 我们先将每个人的坐标和钥匙先排序，然后可以证明： $$\forall a_i\leq a_j\ …

[题目链接] 题目描述 Bessie喜欢在手机上下游戏玩（……），然而她蹄子太大，很难在小小的手机屏幕上面操作。 她被她最近玩的一款游戏迷住了，游戏一开始有$n$个正整数，$(2\leq n\leq262144)$，范围在$1-40$。在一步中，贝西可以选相邻的两个相同的数，然后合并成一个比原来的大一的数（例如两个$7$合并成一个$8$)，目标是使…

最长上升子序列(LIS) 1. $\mathcal{O}(n^2)$ 做法 设 $dp_{i}$ 表示以i 结尾的答案。所以先枚举一个 $i$ ，再从$1$ 开始枚举 $j$ ，每次看到小于 $a_{j}$ 的数，取一个最大的更新 $dp_{i}$ 。 2. $\mathcal{O}(nlog_n)$ 做法 状态设计： $dp_i$ 表示长度为 $…

一. 01背包 01背包问题关键在于某个物品取还是不取，状态可以从上一个占用空间转移而来。 for(int i = 1; i <= n; i++) { for(int j = m; j >= c[i]; j--) { dp[j] = max(dp[j], dp[j - c[i]] + w[i]); } } 二. 完全背包 完全背包问题就…

2. 摘 Galo(OvO) 1s/512M [XOJ]仅评测链接 2.1 题目描述： 0v0 在野外看到了一棵 Galo 树，看到食物的 0v0 瞪大了眼睛，变成了 OvO 。 这棵 Galo 树可以看做是一棵以 $1$ 号点为根的$n$个点的有根树，除了根节点 以外，每个节点i都有一个 Galo ，美味度为$w[i]$。 OvO…

[题目链接] 金明的预算方案 题目大意 有 $n$ 块钱，$m$ 个物品，有些物品是主件，有些物品是附件，主件和附件的关系是：一个主件最多两个附件，选附件必须选主件。每个物品有一个权值 $w$ ，有一个花费 $v$ 物品的贡献为 $w * v$，求最大贡献。 输入格式 第一行有两个整数，分别表示总钱数 $n$ 和希望购买的物品个数 …

题目链接 [T3]表达式 [T4]方格取数 为什么写这个题解呢，因为当年打的时候对题目不是很理解，今天突然看到自己“尝试过的题目”，忍不住去写一下，结果又花了好多时间……我还不够强啊！ T3 题目描述 给出一个后缀表达式，包含 $x_{1 - n}$ , $\And$ 符号 , $|$ 符号与 $!$ 符号。求出当删去每个 $x_i$ 时，表达式的…

[题目链接]最大食物链计数 题目背景 你知道食物链吗？Delia 生物考试的时候，数食物链条数的题目全都错了，因为她总是重复数了几条或漏掉了几条。于是她来就来求助你，然而你也不会啊！写一个程序来帮帮她吧。 题目描述 给你一个食物网，你要求出这个食物网中最大食物链的数量。 （这里的“最大食物链”，指的是生物学意义上的食物链，即最左端是…

题目链接 - [NOIP2010 提高组] 乌龟棋 题目大意 你有一个数字串为地图，从$pos = 1$开始走，有4种走法，分别走1、2、3、4步，每种走法都有次数限制（最大不超过40），保证走完地图，求走完地图的最大分数。 分析 1.dp 很容易想到dp，数据范围不大，直接开多维： $$dp[x1][x2][x3][x4]$$ 在这个数组中，$x…