rurutoria7 ' 筆記

@learning

各種東西的學習筆記

Public team

Community (0)
No community contribution yet

Joined on Apr 24, 2021

  • 頂點屬性 在 GPU 中有一塊 ARRAY_BUFFER,用來存頂點資料。一個頂點的資料,也就是 Vertex Shader 的輸入,由許多頂點屬性(Vertex Attribute)組成。因此需要配置 0~n 的頂點,要怎麼從 ARRAY_BUFFER 中取得一個 Vertex Attribute。 void glVertexAttribPointer(index, size, type, normalized, stride, pointer);GLuint *index*:屬性的 location GLint *size*:該屬性有幾個 Component(1, 2, 3, 4) GLenum *type*:該屬性的 component 是甚麼類型 (GL_FLOAT, GL_BYTE, GL_DOUBLE, GL_INT…) GLboolean *normalized*:在讀取 fixed-point 值(非浮點數資料,例如 GL_UNSIGNED_BYTE)時要不要把值 normalized 到 [0,1] 或 [-1,1] 之間(根據是否為 signed value) GLsizei *stride*:從 ARRAY_BUFFER 讀取資料時,每一個 Attribute 的間隔為多少。若 0 則為緊密排列 const void * *pointer*:在 ARRAY_BUFFER 中的起頭 Byte Offset。void* 型別來自歷史遺留問題
     Like 1 Bookmark
  • 前情提要 因為出 OI 題用了 TPS,以往都用 Linux 執行,用 M1 Macbook 跑時遇到不少麻煩。 費盡千辛萬苦解決用 pandoc + latex engin 輸出題敘的問題後,剛要接觸下個生成測資的指令,果不其然又噴錯了: 這次是關於 C++ 的,我已經懶得、也沒能力解決了,只好尋求 VM 的協助。 UTM macOS 上常用的 VM 平台有:VMware, VirtualBox, Parallels。其中只有 Parallels 支援 M1,但連玩手遊都沒課過金的我自然是不會選擇它。
     Like 5 Bookmark
  • 道德與宗教 0:總結:道德最終導向宗教。0.1:道德自己自足,不需要宗教。道德是奠基在存粹意志自由上Q: 存粹意志自由(實踐理性自律)是什麼?是自我立法嗎?設置目的並實踐的能力嗎? 道德自身奠基在純粹意志自由(實踐理性自律)上,不需要依賴理性之外的其他根據。道德是自給自足的,自身不需要宗教。 0.2:道德法則會責成我們要求上帝存在。 在理想情況下,純粹實踐理性在自我立法時不需要目的表象,從而不用要求上帝存在 但人類的實踐理性必然關聯到目的,並且因為人的有限理性必然將德福一致的最高善作為終極目的,我們不得不要求有上帝存在,作為最高善實現的可能性 Q: 如果不相信上帝存在會怎樣?會影響到道德實踐嗎?可能會影響到道德實踐。所以道德法則會責成我們相信上帝存在。
     Like 1 Bookmark
  • 網路流問題 給定一張圖,每條邊有容量,給定源點、匯點,求從源點到匯點的最大流量。 上述為一個最大流問題。在一個網路流問題中,我們定義: 源點為 $s$,匯點為 $t$ $F(u,v)$ 為 $u$ 到 $v$ 的流量 $C(u,v)$ 為 $u$ 到 $v$ 的容量 而一個可行流,即是對於所有邊 $u,v$ 找到一個流量 $F(u,v)$ 滿足:
     Like 1 Bookmark
  • 零、前言 考慮以下問題: 有 $n$ 座城市,以及 $m$ 條道路。每條道路連接兩個城市 $(u,v)$。請問從城市 $1$ 走到城市 $n$,最少必須經過幾個城市? 這道題目是一道標準的圖論問題,本章節將探討如何解決類似的題目。 一、圖的介紹及基本概念 一個圖(Graph)包含一些節點(Vetex)和一些邊(Edge)。我們可以一個由節點集合 $V$ 和邊集合 $E$ 構成的圖 $G$,表示為 $G=(V,E)$。圖用來描述一些節點之間的連接關係。例如節點可能可以代表一些城市、車站。而每一條邊表示了兩個節點的連接關係,就像道路和鐵軌。
     Like 1 Bookmark
  • DFS Tree DFS Tree 是將一張圖 DFS 之後構成的一顆樹。 有向圖的 DFS Tree 我們考慮 DFS 一張有向圖,在 DFS 途中,若通過 $u \to v$ 從 $u$ 走到鄰居 $v$,可能有以下情況: Tree Edge:若 $v$ 尚未被造訪過,則會繼續從 $v$ DFS 下去,且 $u \to v$ 為 Tree Edge。而這些邊也就是是在 DFS 過程中實際有走的邊。 當 DFS 結束,Tree Edge 會把所有點連成一顆樹。而剩下的邊便是在 DFS 過程中,某些節點會連向已造訪的節點,所以沒有 DFS 下去的那些邊。分成三種:
     Like 2 Bookmark
  • 字符串的比較很慢,因此我們把一個字符串映射到整數。那麼我們可以很方便的比較字串是否相等。 Hash 的核心思想是把輸入映射到一個值域比較小的範圍,方便我們做比較。因為哈希函數是一個多對少的函數映射,因此: 如果兩輸入的哈希值不同,那他們一定不同 如果兩輸入的哈希值相同,那他們可能相同(也可能不同,我們稱為碰撞。我們希望碰撞的概率很小) 我們通常這樣定義 Hash 函數,用於字符串哈希: $$
     Like 1 Bookmark
  • 前綴和無法支援修改,修改一次就要 $O(n)$ 的時間,因為一個位置被他後面所有的前綴和包含。 BIT 概念是把前綴和序列中,每一個位置所代表的區間縮小,那麼在修改時就不需要修改那麼多前綴和了。不過相對的,在查詢一個前綴時,也不能一次取得。 我們定義 BIT 序列: $$ B[i] = a[i-lowbit(i)+1] + \dots + a[i] $$
     Like  Bookmark
  • 315 D 每個回合會刪除至少一行或一列,因此刪除最多 $O(H+W)$ 次。每次的刪除,可以用 $O(HW)$ 的時間找到可以刪除的行列,但複雜度會爆炸。 考慮到元素種類只有 $\rho = 26$ 種,我們可以對每一行、每一列維護一個每個元素對應數量的表,如 $rowCnt[i][c]$ 代表第 $i$ 行有幾種 $c$ 元素。對於一個行、列,只要用 $O( \rho )$ 即可檢查是否可以刪除該行列。那麼每個回合的複雜度將為 $O(\rho(H+W)))$。 要注意的是,在統計完可刪除行列前,如果就移除字符,會對後續統計產生影響。 #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std;
     Like  Bookmark
  • TOJ 628. prob B - 國中會考分發 給定每個人的成績以及他們的志願序,求分發結果。 直接按照題目的描述模擬即可。按照給定的順序為每個學生找學校。為一個學生找學校時,按志願高到低遍歷志願序中的學校,一但找到還塞的進人的學校,就分配至該所學校。 TOJ 629. prob C - GAMAGAMA 對兩條有 ${+a, *a}$ 的路徑進行以下操作 輸出以 $k$ 開始的最大值 將 ${+a, *a}$ 接在路徑 $i$ 的後方
     Like  Bookmark
  • ABC 314 E Roulettes 計算期望值的題目經常使用動態規劃來解決。此題我們定義狀態 $dp[i]$ :目前有 $i$ 點,要達到 $m$ 點的最小花費期望值。 轉移時枚舉要轉哪一個轉盤,接著從該轉盤上的不同值計算出期望值。 $$ dp[i]=max_{j=1\dots n} , C[j] + \frac 1 P_j \sum dp[i + S[j][k]] $$ 注意到如果某個轉盤上的點數為零,那麼便把它當成不存在,把該輪盤的花費改成 $C_i \frac {P_i} {P_i - Z_i}$。
     Like  Bookmark
  • 第五週、享受生命的流帶著生命的供應,出於並為著神宏偉的殿,藉此過基督徒的生活 以西結書 第 47 章 祂帶我回到殿門,見水從殿的門檻下流出,往東流去;(原來殿面朝東;)這水從檻下,由殿的南邊,在祭壇的南邊往下流。祂帶我出北門,又領我從外面繞到朝東的外門,見水從南邊流出。 那人手拿準繩往東出去的時候,量了一千肘,使我蹚過水,水到踝子骨。祂又量了一千肘,使我蹚過水,水就到膝。祂再量了一千肘,使我蹚過水,水便到腰。祂又量了一千肘,水便成了河,使我不能蹚過;因為水勢漲起,成為可洑的水,不可蹚的河。 祂對我說,人子阿,你看見了麼?祂就帶我回到河邊。我回到河邊的時候,見在河這邊與那邊的岸上有極多的樹木。祂對我說,這水往東方一帶流出,下到亞拉巴,直到海;所發出來的水流入海時,海水就得醫治。這河所到之處,凡滋生有生命的動物都必生活,並且這水到了那裏,就有極多的魚。海水得了醫治,並且這河所到之處,百物都必生活。必有漁夫站在海邊,從隱基底直到隱以革蓮,都作曬網之處。那魚各從其類,好像大海的魚甚多。只是泥濘之地與窪濕之處不得治好,必留為鹽地。在河這邊與那邊的岸上必生長各類的樹木,其果可作食物;葉子不枯乾,果子不斷絕;每月必結新果子,因為供應樹木的水是從聖所流出來的。樹上的果子必作食物,葉子乃為治病。 這周的內容,主要帶我們看見以西結書四十七章殿和水流的異象。這個異象是十分清晰的,水流從殿流出,水流是以三一神為源頭的生命之流,殿是基督的身體—召會。我們一方面是作為乾焦之地享受這水流的醫治河滋潤,另一方面也要洑在水裡為這水流所限制。最終,都是為著新約建造的職分:神宏偉的殿的擴大。
     Like  Bookmark
  • 樸素的多項式乘法,必須在 $O(n^2)$ 完成 我們可以透過 FFT 的協助,在 $O(nlogn)$ 時間內完成多項式乘法。 點值表達式 可以帶入至少 $n$ 個點來唯一表示 $n-1$ 次多項式。 所以,$n > deg\ f(x)$,$f(x)$ 能以點值表達式表示為 $$(x_0,f(x_0)), (x_1,f(x_1)), \dots, (x_{n-1},f(x_{n-1}))
     Like  Bookmark
  • KMP 用在字串匹配,可以在字串 $S$ 中找到哪些地方出現過字串 $P$。 核心思想是優化樸素的字串匹配過程。匹配可以視作,每個位移過後的 $P$,有哪些與對應的 $S$ 子字串相等: S AABAABAAC P1 AABAAc P2 Aabaac P3 aabaac P4 AABAAC 每個都匹配到失敗為止,並且從匹配失敗之後用小寫表示
     Like  Bookmark
  • 題意 有 $n$ 點 $m$ 邊的帶權無向圖($n\le 10^5; m \le 2\times10^5$)。你可以指定一條 $s-t$ 的最短路使其邊權歸零,求 $u-v$ 的最短路徑。 作法 將無向圖拆成有向圖,可以得到 $stDAG$ 的任何完整路徑(從入度為零的點開始,走到出度為零的點為止)都是 $s-t$ 最短路。 $u-v$ 最短路有兩種可能: 不經過 $s-t$ 最短路,$ans = dis(u,v)$ $u$ 從 $x$ 接入 $stDAG$,從 $y$ 離開 $stDAG$ 前往 $v$,$ans = dis(u,x)+dis(y,v)$
     Like  Bookmark
  • A. 獅子的野望 (yabo) 題目要求求出 $\lceil \frac{L}{K} \rceil$,然後在找出序列 $a$ 中差距最小的元素即可。 #include <bits/stdc++.h> #define int long long using namespace std; const int N = 1e6+10; int n, k, l, a;
     Like  Bookmark
  • 好的演算法? 跑的多快 佔用的記憶體 正確性 我們通常在乎“跑的多快” 那要怎麼知道速度呢? 直接寫出來測量!
     Like  Bookmark
  • 參考資料: ref1 ref2 作法一:兩個 multiset 以兩個動態排序的資料結構 $L$ $R$,分別維護前半小、後半大的,查詢時輸出中間切開的地方就行。 仔細地說,有奇數個元素時,中位數是 $\lceil \frac n 2 \rceil$,偶數個時,中位數是 $\frac n 2$。 使 $L$ 在 $n$ 為奇數時,比 $R$ 多一個,查詢時輸出 $L$ 的最後一個元素。
     Like  Bookmark
  • 差分約束模板 https://www.luogu.com.cn/problem/P5960 Solution $x_i - x_j \leq w$ xi - xj <= w xi <= xj+w 若 xj 已知,則 xi 必須要被縮小至至少 xj+w 以符合不等式
     Like  Bookmark
  • Default Code typedef pair<int,int> vec; vec operator - (vec p){ return {-p.ff, -p.ss}; } vec operator + (vec p, vec q){ return {p.ff+q.ff, p.ss+q.ss}; } vec operator - (vec p, vec q){ return {p.ff+q.ff, p.ss+q.ss}; } vec operator * (vec p, int q){ return {p.ff*q, p.ss*q}; } vec operator / (vec p, int q){ return {p.ff/q, p.ss/q}; } int cross (vec p, vec q){ return p.ff*q.ss - p.ss*q.ff; } int dot (vec p, vec q){ return p.ff*q.ff + p.ss*q.ss; } int abs2 (vec p){ return dot(p,p); }
     Like  Bookmark