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. ...
丹麦语 DU 3.2 13-14 Fortæl om ferier og oplevelser
Datid 3 种类型 Gruppe 1：词尾 -ede Gruppe 2：词尾 -te Gruppe 3：不规则变化，fx: tager - tog kan - kunne finder - fandt spørger - spurgte sidder - sad nyder - nød drikker - drak 情态动词 modalverber 的过去式 都是不规则变化 kan - kunne skal - skulle vil - ville må - måtte Esme på kunstmuseum udstilling -en -er -erne 展览 er spændt på at infinitiv 急切期待做某事 vente -r -de -t 等待 gå -r gik -et 走 gå ind 走进 omvisning -en -er -erne 参观 fortale -r fortalte fortalt 告诉，说出 flot 漂亮的，美好的 Solen skinnede, og himlen var helt blå. 阳光普照，天空很蓝。（有点 ...
随机算法 14 Markov Chains and Random Walks
Lecture notes by Elias Koutsoupias from Oxford Markov Chains Definitions A discrete-time finite Markov chain is a sequence of random variables X=X0,X1,X2,⋯X=X_0,X_1,X_2,\cdotsX=X0,X1,X2,⋯ taking values in a finite set of states {1,2,⋯ ,n}\{1,2,\cdots,n\}{1,2,⋯,n} s.t. ∀t∈N:\forall t\in\mathbb N:∀t∈N: Pr(Xt+1=j∣Xt=i)=Qi,j,\Pr(X_{t+1}=j|X_t=i)=Q_{i,j}, Pr(Xt+1=j∣Xt=i)=Qi,j, where Q=(Qi,j)Q=(Q_{i,j})Q=(Qi,j) is an n×nn\times nn×n stochastic transition matrix. XtX_tXt represents the state ...
随机算法 13 Nearest Neighbor Search with Different Distance Metrics
Recall Recall the problem of nearest neighbor search: Randomized ccc-approximate RRR-near neighbor search. Recall that given a set PPP of nnn points in Rd\mathbb R^dRd and parameters R>0,δ>0R\gt0,\delta\gt0R>0,δ>0. Also given a distance function dist:Rd×Rd→Rdist:\mathbb R^d\times\mathbb R^d\rarr\mathbb Rdist:Rd×Rd→R. For a query point qqq, if there is an RRR-near neighbor ppp of qqq (dist(p,q)≤Rdist(p,q)\le Rdist(p,q)≤R), we must report some point p′p'p′ that is a cRcRcR-near n ...
