Tommy_clas

摘要： 題目 設(shè)$dp_{i,j}$表示$i$子樹中的邊已經(jīng)全部被覆蓋，且子樹內(nèi)部選擇的路徑最遠可以覆蓋到深度為$j$的點的最小代價。 轉(zhuǎn)移的時候大概類似一個樹上背包： \(dp_{i,j}=\min_{v\in son(i),\min k_v=j}\{\sum_{v\in son(i)}dp_{v,k_v 閱讀全文

摘要： 上一篇寫滿了，又可以再開一篇了。 話說還有三周就要去退役了，真是快啊。 HZOI省選模擬66A 有限空間跳躍理論 考慮對一張$DAG$求拓撲序的過程，我們一次性刪除當前所有入度為$0$的點，并把這個點集記下來，這樣我們就得到一個拓撲序列。這個拓撲序列是一個點集序列，顯然拓撲序列不同，$DAG$一定不 閱讀全文

摘要： 題目 考慮讓直線導(dǎo)軌成為$x$軸，欽定$(x_1,y_1)\(成為坐標原點，其余點的坐標都減去\)(x_1,y_1)\(。之后需要使得\)(x_2,y_2)$落在$x$軸上，求一下$(x_2,y_2)$與$x$軸的夾角$\alpha$，讓所有點都順時針旋轉(zhuǎn)$\alpha$就好了。 點旋轉(zhuǎn)后的坐標變換 閱讀全文

摘要： 題目 枚舉每一個發(fā)射源，對于當前發(fā)射源$S_k$，將激光塔和敵人按照到$S_k$的向量的極角序排序。 如果存在$D_l$在兩個激光塔$T_i,T_j$之間，且$T_i,T_j$的夾角小于$\pi$，那么$(T_i,T_j,S_k,D_l)$就是一組合法的四元組。 于是直接排序后雙指針，對于每一個激光 閱讀全文

摘要： 題目 直接算是非常困難的，因為每填滿一個倉庫之后分母就變了。 但是不難發(fā)現(xiàn)"等概率隨機選一個沒有滿的燃料艙"其實是沒什么用的，直接轉(zhuǎn)化為等概率選取一個位置$+1$，求$\geq a$位置個數(shù)的期望。這樣的話概率就一直是$\frac{1}$。 考慮對于$1$號位置計算在全部位置$\geq b$之前$1 閱讀全文

摘要： "題目" 隨便觀察一下，不難發(fā)現(xiàn)如下的性質(zhì)： 1. 任意兩個極大值點$(x_1,y_1,z_1),(x_2,y_2,z_2)$都存在$x_1\neq x_2,y_1\neq y_2,z_1\neq z_2$，這是因為極大值點必須大于其所在平面上的任意數(shù)。 2. 根據(jù)上面的性質(zhì)不難發(fā)現(xiàn)極大值點的個數(shù)不 閱讀全文

摘要： "題目" 經(jīng)過大力手玩不難發(fā)現(xiàn)存在一個邊集使得每個點的度數(shù)都是奇數(shù)的充要條件是 不存在奇數(shù)個點的聯(lián)通塊 。 考慮證明奇數(shù)個點的聯(lián)通塊一定不合法。剛開始所有點度數(shù)均為偶數(shù)，考慮加入一條邊$(u,v)$的影響： $u,v$度數(shù)均為偶數(shù)，那么加入$(u,v)$后兩點度數(shù)均變?yōu)槠鏀?shù)，奇度點個數(shù)增加$2$。 閱讀全文

摘要： 上完網(wǎng)課后不知怎么就打開了阿駿的博客，懷著一種快樂但想念的心情看完了阿駿的大作《機房人物列傳》。看完后還是很快樂的，很開心能有人將我們所有人那不長的OI時光記錄下來，畢竟這確實是一些非常有意思也非常值得懷念的事情；也會很懷念，尤其是看到其中水群的截圖時會想到CSP前水不完的群和熱鬧的機房，而現(xiàn)在只有 閱讀全文

摘要： 博客寫得太長看得時候會很累，于是再開一篇。順便在這里記一下主席的ZR密碼：xyt1538482243 CF590E Birthday 對于兩個字符串$S_i,S_j$，如$S_i$是$S_j$的子串，那么我們就稱$S_i\leq S_j$。不難發(fā)現(xiàn)$(S,\leq)$構(gòu)成了一個偏序集。我們要找到一個 閱讀全文

摘要： 大概是退役前最后的掙扎了，不過頹了太久估計掙扎了也沒啥用； BZOJ4738汽水 平均值的話我們就二分一下，對于一個需要判斷的$mid$，我們需要找到一條路徑平均值在$[K-mid,K+mid]$之間；分兩種情況討論一下，如果存在一條路徑的滿足$K\leq \frac{\sum w}\leq K+m 閱讀全文