L3067545513

摘要： 前言 情人節寫的這道題，題目名稱好符合我當時的心情。 題目鏈接 Luogu:P4921 解法 容斥 我們發現最后要求的結果是恰好 $k$ 對情侶坐在一起的方案數，我們就不難想到去計算恰好 $n-k$ 對沒坐在一起的方案數。那么我們很自然的得到最后答案： $ans = C_n^k \times A_n 閱讀全文

摘要： 題目鏈接： luogu cf 題目大意： 給定一個 $n \times n$ 的矩形，在里面填充三種顏色，求使得至少一行或至少一列同色的方案數。 解法 容斥 我們不去考慮反演，直接開始容斥，我們不難將問題進行轉化，去計算此時答案的補集，那么最后的答案就是 $3^{n\times n} -$ 補集。我 閱讀全文

摘要： 題目鏈接： luogu cf 題目大意： 給定一個矩形，在其中填數，要滿足每一行，每一列的最小值都為1。 解法 一.容斥解法 1.解法I 我們先單獨考慮每一行，先計算出每一行的合法方案數，再去計算整個問題的合法方案數，這樣就從一個直接從二維解決的問題變成了一個一維的問題。 那么對于每一行的方案數，我 閱讀全文

摘要： 點擊查看代碼 struct Splay { int ch[M][2] , val[M] , size[M] , cnt[M] , fa[M] , T , root; inline void init(int p) {size[p] = cnt[p] = 1; ch[p][0] = ch[p][1] 閱讀全文

摘要： A 合并的 LIS 可以看成一些區間和的 LIS。 考慮經典 LIS 的 DP 之一，$f_{i,j}$ 為前 $i$ 個數，選擇了 $j$ 個，最后一個的最小值。 這個 DP 是可以沿用的，轉移有兩種。 $f_{i-1,j}$，即 $i$ 不在 LIS 中。 $\sum_\limits{x=k}^ 閱讀全文

摘要： 2022.11.16 模擬賽總結 $T1$ 看起來對于我不是很可做，就大概看了一下 $50$ 的做法，然后光速跳到 $T2$, $T2$ 打了個表把規律看出來了，然后又套了個組合意義，大概 $15min$ 就切了，不過沒注意 $2$ 倍空間，掛了 $60pts$。$T3$，$T4$感覺暴力都不可打， 閱讀全文

摘要： CEOI 2021 $pts$：64 + 0 + 4 $T1 : 64pts$ 首先我們肯定知道對于相同的數，一定是放在一起才是最優的，隨意我們對于每段查詢的區間要保證有序，然后我們發現，每個數出現的位置不同，他對答案的貢獻也就不同，我們的想法是讓答案最小，那么我們對于每個位置對答案的貢獻一定要均攤 閱讀全文

該文被密碼保護。 閱讀全文

摘要： 2022.10.11 CSP-S 2021 測試總結 這場打的好心累， $T1$ 想了 $1$ 個多小時才想出來的， $T2$，$T4$題意賽時還沒讀明白。 $T1$：廊橋分配 $T1$ 感覺是這幾道題里最水的一道題，暴力都能踩過，然而卻想了 $1$ 個多小時的優化。首先我們考慮它是按照先來后到的順 閱讀全文

摘要： P2467 [SDOI2010]地精部落 題目傳送門 題目大意：略 題目分析： 首先一眼可以知道這個是個計數類的問題，我們可以考慮使用組合數學和 $dp$ ，由于題目讓我們求奇數項都高于或低于偶數項的排列數，我們觀察題目所讓求的這種排列，發現將原來符合的排列倒過來之后仍然符合。然后我們可以考慮使用 閱讀全文