Codeforces Round 963 (Div. 2) 部分题目总结
本次比赛 链接。说实话出的比较糟糕，题目难度的梯度非常不均匀。 A, B, C 题没什么好说的，跳过。 D. Med-imize 题目大意 给定一个包含 n 个 int 的数组 a，给定 k。在 a 中，每次选择长度刚好为 k 的任意的连续子数组进行删除，删除至 a 长度小于等于 k 为止。求删除操作结束后数组 a 最大可能的中位数值。 解题思路 二分搜索答案 + 动态规划。 当输入数组长度小于等于 k 时，答案就是当前数组的中位数。 ❓如何在不排序的情况下求出一个数组的中位数呢？二分查找。 对每一个给定的值 x，建立另一个和 a 一样大的标签数组 b。 当 x<=a[i] 时，标记 b[i]=1；反之 b[i]=-1。 这样通过判断 b 数组和的正负性，我们就能判断 x 是否比中位数小了。 当 n>k 时，同理进行二分搜索答案。为了检查当前值是否小于最优可能解，我们只需使用动态规划求出 b 数组最大的和，检查其正负性。 ❓如何用动归求 b 数组最大的和呢？ 注意到每次删除完成后数组的长度为 m=((n-1)%k)+1。 注意到删除完成后的数组 a' 中的每 ...
算法和计算复杂度 6 Randomized Computation
What if Turing machine models have access to a source of randomness? This would allow to compute more in same time/space, at the price of possibly not giving correct answer with small probability. Current consensus: Randomization only gives Polynomial saving in time Constant factor saving in space Because of hardness-based pseudo-random generator. Exponential time: E=DTIME(2O(n))=UL−SIZE(2O(n))E=DTIME(2^{O(n)})=U_L-SIZE(2^{O(n)})E=DTIME(2O(n))=UL−SIZE(2O(n)). (By corollary 2) Recall that SIZE ...
新坑预告——《安徒生童话》丹麦语原文精读
在童年的梦境中，我们曾徜徉于安徒生笔下的神奇世界。他的故事不仅构建了我们幼年的幻想，也深深触动了我们的内心。如今，当我重拾这些经典童话，并用丹麦语的原汁原味去品读，那份久违的感动再次涌上心头。透过丹麦语的细腻表达，我希望与你们分享那些在翻译中可能被忽略的细节与韵味，揭开每一个故事背后的语言魅力与文化底蕴。 开启新坑的目的 这个全新项目不仅是我对丹麦语学习热情的延续，也是对童年回忆的深情追溯。通过精读安徒生的经典童话，我希望在积累更多丹麦语单词和地道表达的同时，重温那些陪伴我们成长的故事。这不仅是语言学习的旅程，更是一次文化与情感的深度体验。 童年记忆中的经典 从《丑小鸭》的蜕变，到《卖火柴的小女孩》的动人心魄，这些故事早已成为我们共同的记忆。以下是我小学初中时在语文课堂上涉及到的童话故事： 人教版小学语文 二年级下册——《丑小鸭》Den grimme ælling 六年级下册——《卖火柴的小女孩》Den lille Pige med Svovlstikkerne 人教版初中语文 七年级上册——《皇帝的新装》Kejserens nye klæder 精读形式与内容 ...
Codeforces Round 957 (Div. 3) 解题思路
本次比赛 链接 现在的水平只能碰碰 Div 3 A. Only Pluses 三个数越相近，乘积就越大。因此五次递增每次分别作用于当前三个数中最小的那个。 B. Angry Monk 除了当前最长的那一个片段之外，其他片段都必须要掰成一节节之后再拼上。这样总步数最小。 C. Gorilla and Permutation 定义的两个函数 f(i)f(i)f(i) 表示数组前缀长度 iii 中所有大于 kkk 的数字之和，g(i)g(i)g(i) 表示数组前缀长度 iii 中所有小于 mmm 的数字之和。要想最大化 ∑i(f(i)−g(i))\sum_i(f(i)-g(i))∑i(f(i)−g(i)), 就必须要让 f(i)f(i)f(i) 尽量大，g(i)g(i)g(i) 尽量小。 所以构造的排列就是先是比 kkk 大的数字降序排列，中间的无所谓，之后是比 mmm 小的数字的升序排列。 D. Test of Love 题目大意 给出一个长度为 nnn 的序列，其中包含水 W、鳄鱼 C 和浮木 L。如果在岸上或在浮木上，可以向前最多跳 m 格，可以跳到水里、浮木或岸上；如果当 ...
算法和计算复杂度 5 The Polynomoial-Time Hierarchy
Idea: arithmetic hierarchy from recursion theory. Halting problem HALTHALTHALT is a recursive enumerable language that is undecidable. The polynomial-time hierarchy considers polynomial time and SATSATSAT instead of HALTHALTHALT. Oracle Turing Machines An oracle Turing machine M?M^?M? is equipped with an additional tape, the query tape, and has three new special states qask,qyes,qnoq_{ask},q_{yes},q_{no}qask,qyes,qno. The query tape is a write-only tape. The operation of M?M^?M? is defined r ...
算法和计算复杂度 4 Reductions and Completeness
Reductions NP-completeness: by polynomial-time many-one reductions (aka Karp reductions) Studying completeness of P and NL: by log-space many-one reduction. Also too powerful for completeness inside L. 📖Definition 14 (Log-space reductions). Let L1⊆Σ1∗L_1\subseteq\Sigma_1^*L1⊆Σ1∗ and L2⊆Σ2∗L_2\subseteq\Sigma_2^*L2⊆Σ2∗ be languages. A log-space many-one reduction from L1L_1L1 to L2L_2L2 is a function f:Σ1∗→Σ2∗f:\Sigma_1^*\rarr\Sigma_2^*f:Σ1∗→Σ2∗ s.t. There exists a log-space Turing mach ...
德语学习 B2 Kapitel 6 Fit für ...
Inhalt Fit für den Onlineeinkauf Fit am Telefon Fit für die Kollegen Fit für die Prüfung 6-1 Fit für … (1) fit für Akkusativ 适合某事，胜任某事 Kurios 奇特的，奇怪的 6-2 Fit für … (2) der Quark 凝乳 das Eisen-/ 铁 Edelmetal 贵金属 die Analogie-n 类比，类推 die Denksportaufgabe-n 脑筋急转弯 6-3 Fit für den Onlineeinkauf (1) Was kaufen Sie in Geschäften? Was kaufen Sie im Internet? In Geschäften: Lebensmittel, Arzneimittel, Brillen Im Internet: Elektronische Geräte, Kleidung, Onlinekurs, Spielwaren, Tickets, Reise der Ko ...
算法和计算复杂度 3 Boolean Circuits
Non-uniform model of computation: Boolean circuit model. In contrast to uniform model like Turing machine. Boolean circuit: Fixed number of inputs. To study computation of arbitrary inputs, we need a family of Boolean circuits. Some Definitions 📖Definition of Boolean circuit. A Boolean circuit CCC with nnn inputs and mmm outputs consists of: A directed acyclic graph D=(V,A)D=(V,A)D=(V,A) where the in-degree of every node is at most 222. A labeling ℓ\ellℓ of all nodes g∈Vg\in Vg∈V with \ell(g) ...
算法和计算复杂度 2 Nondeterminism and Determinism
The sequence of transitions is called computation history. Non-deterministic Turing machine will crush also when there is no possible next step according to the transition relation. Non-deterministic Time and Space Complexity Worst-case definition of time and space to solve a issue by non-deterministic Turing machine. Let MMM be a non-deterministic Turing machine. For given input x∈Σ∗x\in\Sigma^*x∈Σ∗, timeM(x)time_M(x)timeM(x) is the maximum number of computation steps that MMM performs on in ...
算法和计算复杂度 1 Turing Machines, Time and Space
Theory of Algorithms and Computational Complexity Lecturer: Kristoffer Arnsfelt Hansen ☠️☠️☠️The most difficult (no “one of”) course in my master’s study.☠️☠️☠️ Brief Intro to TACC Study of efficient computation 1960s Hartmanis, Stearns - Time Hierarchy Theorem. Turing machine, register based machine can simulate each other. Turing Machines Turing machines - simple, and has some nice properties: Clean definition of complexity (time and space) Straightforward to non-determinism and randomness. ...
