etoj专题

【ETOJ P1025】最长公共子序列 题解(动态规划+最长公共子序列)

题目描述 给你一个序列 X X X 和另一个序列 Z Z Z,当 Z Z Z 中的所有元素都在 X X X 中存在,并且在 X X X 中的下标顺序是严格递增的,那么就把 Z Z Z 叫做 X X X 的子序列。 例如: Z = < a , b , f , c > Z = <a,b,f,c> Z=<a,b,f,c> 是序列 X = < a , b , c , f , b , c

【ETOJ P1023】同鱼系 题解(数学+取余)

题目描述 给定一个大小为 n n n 的数组 a a a 和一个整数 k k k。 你可以执行以下操作任意次(0次也行): 选择一个下标 i i i 满足 1 ≤ i ≤ n − k 1 \leq i \leq n-k 1≤i≤n−k,然后交换 a i a_i ai​ 和 a i + k a_{i+k} ai+k​。 问是否可以使得数组变为非降序。 输入格式 第一行两个整

【ETOJ P1057】小e的菜篮子 题解(优先队列)

题目描述 你有一个菜篮子。 接下来会有 Q Q Q 次操作,每次操作如下: “1 x”,将一个重量为 x x x 的菜放入到菜篮子中。“2”,将菜篮子中重量最大的菜丢掉(如果菜篮子为空,则跳过)。 问 Q Q Q 次操作后,菜篮子中剩下的菜的总重量。 输入格式 第一行一个整数 Q Q Q,表示操作次数。( 1 ≤ Q ≤ 1 0 5 1 \leq Q \leq 10^5 1≤Q

【ETOJ P1012】排序去重问题 题解(集合)

题目描述 给定一个大小为 n n n 的数组 a a a,请将 a a a 中元素去重后从小到大排序输出。 输入格式 第一行一个整数 T T T 表示测试样例个数。 ( 1 ≤ T ≤ 100 ) (1≤T≤100) (1≤T≤100) 对于每一个测试样例: 第一行一个整数 n n n 表示数组大小。 ( 1 ≤ n ≤ 1 0 3 ) (1≤n≤10^3) (1≤n≤10

【ETOJ P1024】无穷背包 题解(动态规划+完全背包)

题目描述 小 e e e 的背包容量为 m m m,现在商店里有 n n n 种商品。由于在梦境中,他可以零元购,商店里的每种商品都有无穷件,每件商品有一个价值 w i w_i wi​ 和体积 v i v_i vi​。 问小 e e e 最多可以带走多少价值的商品? 输入 第一行两个整数表示 m , n m, n m,n。( 1 ≤ m ≤ 1 0 5 , 1 ≤ n ≤ 5

【ETOJ P1046】斐波那契数列 题解(数学+动态规划)

题目描述 给定一个整数 T T T,表示样例数。 对于每个样例,给定一个整数 n n n,求斐波那契数列的第 n n n 项。 斐波那契数列定义为 f ( 1 ) = f ( 2 ) = 1 f(1) = f(2) = 1 f(1)=f(2)=1, f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n) = f(n−1) + f(n−2) f(n)=f(n−

【ETOJ P1014】straax‘aks Array 题解(多重循环+暴力枚举+位运算)

题目描述 给定一个长度为 n n n 的数组 a a a 和一个整数 m m m,问数组中有多少个三元组 ( i , j , k ) (i,j,k) (i,j,k),满足: i < j < k i < j < k i<j<k ( a i + a j + a k ) × ( a i ⊕ a j ⊕ a k ) ≥ m (a_i + a_j + a_k) \times (a_i \opl