初赛 背包p9140 thupc

《南开大学数分I月考III在初赛开始四十分钟时结束》 早晨试图速成泰勒展开失败了 考试前 zsy 把 yzf 接到学校了，应该是国赛后第一次见 yzf 考完试发现 yzf 已经买好 KFC 了/bx，但因此迷路了。。。正好三人都少打 1h 分头签到，我开到《转化》了，真不喜欢这题但只能硬着头皮写，W ......

结论：若树上背包的上限为 \(k(k\le n)\)，时间复杂度为 \(O(nk)\)。 参考实现： dfs(u) { sz[u] = 1; init(f[u]); for (v : son[u]) { dfs(v); for (i = 0; i <= k and i <= sz[u]) for ( ......

结论：若树上背包的上限为 \(k(k\le n)\)，时间复杂度为 \(O(nk)\)。 参考实现： dfs(u) { sz[u] = 1; init(f[u]); for (v : son[u]) { dfs(v); for (i = 0; i <= k and i <= sz[u]) for ( ......

学习 算法学习——dd大佬：背包九讲（洛谷） 算法学习——dd大佬：背包九讲（博客园） 题单传送门 P236 采药 #include <bits/stdc++.h> using namespace std; int t, m; int f[1005]; int main() { cin >> t > ......

这是一篇转载的博客，相信大家肯定能看出来吧 P01: 01背包问题 题目 有\(N\)件物品和一个容量为\(V\)的背包。第\(i\)件物品的费用是\(c[i]\)，价值是\(w[i]\)。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 基本思路 这是最基础的背包问题， ......

洛谷 P9970 [THUPC 2024 初赛] 套娃 根据 CF1870E 的 结论，\(\text{mex}\) 真正“有效”的区间只有 \(\mathcal{O}(n)\) 个。 ......

题面 定义一个集合的 \(\operatorname{mex}\) 是最小的不在 \(S\) 中的非负整数。给定一个序列 \(a_1,\dots,a_n\)，对于每个 \(1\leq k\leq n\)，我们按照如下方式定义 \(b_k\)： 对于 \(a\) 的所有长为 \(k\) 的子区间，求出 ......

7-4 0-1背包 给定n(n<=100)种物品和一个背包。物品i的重量是wi(wi<=100)，价值为vi(vi<=100)，背包的容量为C(C<=1000)。 应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有两个选择：装入或不装入。不能将物品 ......

背包 DP http://oi.nks.edu.cn/zh/Contest/Details/2519 背包和其他 DP 的不同在于，背包将物体的“代价”加入了状态，以此更好地转移 背包中最典型的的模型是 \(01\) 背包和完全背包，更难的需要用玄学做法和数据结构进行优化 单调队列优化多重背包 将背 ......

Unity3D 背包系统是游戏中常见的一个功能，玩家可以在游戏中收集或购买各种道具，然后将其放入背包中进行管理。然而，当背包中的道具数量增加时，往往会导致游戏的性能下降，因为需要渲染大量的道具图标和信息。因此，如何优化背包系统的渲染成为了游戏开发中的一个重要问题。 对啦！这里有个游戏开发交流小组里面 ......

题目大意 你需要对每一个长度的区间，求出以他为长度的区间的 \(mex\) 构成集合的 \(mex\) \(n\le10^5\) 大致思路 有一个神奇的结论：对于点 \((l,r)\) 为 \(mex_{l,r}\) 的矩形，其中按颜色分割得到的矩形数是 \(O(n)\) 级别的 证明&实现：我们考 ......

难度极低。显然，句子开头是You are right, but即为人工智能。 #include <iostream> #include <string> #include <cstdio> namespace io{ template <typename T> inline void read(T& ......

B. 一棵树 首先有个暴力 dp，设 \(f_{i,j}\) 表示在 \(i\) 子树内选了 \(j\) 个的最小值，转移是平凡的。 然后发现这玩意是凸的，于是可以直接上 slope trick。 但是涉及到合并两个序列，直接平衡树启发式合并是 \(O(n\log ^2n)\) 的。但是你会发现，我 ......

注意到，\(x_i\) 取 \(k\) 的概率是 \(p(1-p)^{k-1}\)，是和为 \(1\) 的等比数列，下面考察数列前缀和的性质。 不难想到，概率每次乘以 \(1-p\) 像是概率的分步乘法，每一步正是加一的操作。于是可以得到如下转化：初始时 \(S=0\)，每一时刻 \(S\) 先增加 ......

注意到，\(x_i\) 取 \(k\) 的概率是 \(p(1-p)^{k-1}\)，是和为 \(1\) 的等比数列，下面考察数列前缀和的性质。 不难想到，概率每次乘以 \(1-p\) 像是概率的分步乘法，每一步正是加一的操作。于是可以得到如下转化：初始时 \(S=0\)，每一时刻 \(S\) 先增加 ......

我们队赛时被 J 题创死了 awa 离做出来差一个剪枝，而且赛后试了试不加剪枝甚至能过…… 6 题离场。 一些题解 J 套娃 先对 \([0,n]\) 中每个数 \(k\) 分别考虑。 假设总共出现了 \(c\) 次 \(k\)，第 \(i\) 次出现的位置是 \(pos_{i}\)，（令 \(po ......

一.题目需求 使用一个体积大小为13的背包，选择一件或多件商品带走，使得所选商品总价值最大。 商品列表如下： 二.算法思想 1，这是一个经典的0-1背包问题 它要求我们在一组物品中选择一些，每个物品只能选择一次或者不选择，目标是使得所选物品的总价值最大。这个问题在实际生活中有很多应用，比如旅行行李打 ......

【THUPC 2024 初赛】 转化 我都能做出来，那就是大水题了。 思路 首先我们要确定最大可以变色的球的数量 \(tot\)。 有如下两个贪心步骤： 所有颜色使用分裂操作，并更新 \(a_i\)。 ​ 此时的有 \(tot=\sum_{i=1}^n \min(a_i,b_i)\)（需要更新 \( ......

推荐文章：《动态规划之0-1背包问题（详解+分析+原码）》 写的很不错。但是动态数组的定义写得不如我下面： 这道题关键在于理解动态规划公式的定义： 可以定义一个二维数组dp[N][C+1]，N是物品的种类，C是背包的承重（或者体积） dp[i][j]是这个数组的一个元素，其值就表示从前i件物品进行选 ......

Misc ez_zip 题目 4096个压缩包套娃 我的解答： 写个脚本直接解压即可： import zipfile name = '附件路径\\题目附件.zip' for i in range(4097): f = zipfile.ZipFile(name , 'r') f.extractall( ......

鸣谢 cinccout。赛时两次看出了我的错误/bx。 闲话：在我看过的所有人的做题过程中，大家都不约而同的把 棋子数量相同时答案相同 当作了第一发（。但是很可惜，这个结论是错误的。 样例已经给出了当棋子数量为 \(2\) 的答案，在此我们略去讨论。 对于棋子数量为 \(1\) 答案也很明显是后手必 ......

赛时队友把这题丢给我说他们去写 B，然后我成功成为了战犯。 首先考虑一个朴素的暴力，建出一个类似线段树的结构。然后每次合并两个儿子节点，操作次数为 $n\log n$，大约需要 1e7 次操作，不能通过。 这时候有一个思路，如果一个区间里的东西比较满，就会让它很慢。但是如果区间比较满，那么重复位置的 ......

2023.12.11 今天报名了 \(\text{THUPC}\)，想玩一下，也没想打出什么结果。 和同学组了个队。 2023.12.17 \(11\) 点到学校机房。 我过 \(M\)。 lzy 到机房了。 我过 \(C\)。 zwz 会 \(E\)，zwz 写 \(E\)，挂挂挂，调调调。 lz ......

前言 THUPC 2023，Dinshey 交拧螺丝一题，罚时 20 发以上。 Dinshey：我保证不拧螺丝。 我：我保证拧螺丝。 回顾 F 从 12 点调到 15 点。TLE 爆了。 反思 时间流逝之快，我真的就过不去了吗？ ......

队伍组成： \(\text J\color{red}{\text{ijidawang}}\)，负责切题； \(\text K \color{red}{\text{8He}}\)，负责切题； \(\color{#008000}{\text{x383494}}\)，负责拖后腿。 Day -1 之前组的一 ......

大约是进复赛了，那就写个游记吧。 队伍名：福州一树开车大队。 队伍组成：CTT Day3 49.64 分选手，noip 260 分的候选队，NOI2022 E 类铁牌获得者。 2023.12.17（初赛） 原定策略是我做模 3 余 0 的题，lzq 做模 3 余 1 的题，lhr 做模 3 余 2 ......

「比赛游记」THUPC2024 初赛游记 路上小心 ずっと探してた　捧げた心臓の在処 （我一直在寻找着 曾献出的心脏如今何在） 本当の想いを教えて　夢物語でいいから （告诉我你真实的想法吧 纵使如梦话般缥缈） 最後になにがしたい？どこに行きたい？ （在这最后一刻你还想要做什么？你还想去向何方？） わ ......

算法竞赛打 THUPC，就像，只能度过一个相对失败的人生。 本来周末理综考得稀烂就急，这下打完 THUPC 就更急了。 不知道啥时候我们队就凑齐了，然后不知道啥时候就直接要比赛了。 本来分的是 ljc 先开 ABCD，我开 EFGH，lty 开 IJKLM。 结果开场一个“M 是签到，但是我不会”给 ......

洛谷传送门 LOJ 传送门 QOJ 传送门 复读官方题解。 考虑除了原图的 \(2^k\) 个点，再建一些辅助点，\((u, i, j)\) 表示前 \(i\) 位中修改了 \(j\) 位得到 \(u\)。那么除了原图的 \(m\) 条边，我们还有下面这些边： \(u \xrightarrow{0} ......

SDUT 校赛题目 Description 给定正整数 \(n\)，计算 \(n\) 个元素的集合 \(\{1,2,\cdots,n\}\)，所有非空子集和的乘积取模 \(998 \, 244 \, 353\) 后的结果。 Input 一个正整数 \(n\) \((1\le n\le200)\)，代 ......