這只是一個對未來的計劃
因為現在距離CSP-S第二輪只剩76天了，真的該好好抓一把，能在最后的兩個多月在提升一點就好了，我覺得肯定知識點不會有巨大的漏洞了，所以我只會去通過我們校隊給出的題單，來檢查一遍，可能一個知識點就只刷個2.3道題來檢驗扎不扎實，然后會在這個博客上寫一些自己對自己不掌握的知識點的理解和看法，然后接下來就是比賽，我可能打的很多就都是復現賽，因為沒有固定時間去打同步賽，可能一般的比賽來源會在cf,mx,ht,foi,luogu中，就主打一個明確薄弱，一一擊破，這些我不掌握的知識點或者trick都是我總結的重點，還有要積累/訓練的就是思維，思維不提上去，就是只把例題換一種說法，你就不會做了，把題面一一拆解，再交給學過的知識點變成熟練掌握的代碼，融合最后打出來，這就是思維的作用及其重要性，不過這些思維上的積累我覺得只要體現在題目上就好了，沒必要單獨分離，這種東西脫離題目就太虛幻了，很難整理，理解，掌握，所以，下面就是我的知識點看法，題目理解，比賽總結，不過現在還沒寫就是了,后面就會慢慢有了哈
有好題的推薦推薦唄，就放到評論區那
知識點
DP
先是對DP的總結哈，其實就只有4道例題，應該還可以
1. P3558 [POI 2013] BAJ-Bytecomputer
題面的意思大概就是說，給了 \(a_1 \dots a_n\) \(n\) 個數，每個數是 {-1， 0， 1} 中的一個，每次可以將一個數加上前一個數，問至少要多少步才能使序列變成單調不降序列？
首先你要發現一個性質，我們無論如何都不會讓一個數變成{-1， 0， 1}以外的別的數，這也很好證明，因為原本只有{-1， 0， 1} 如果讓一個數大于1，那么后面的數都一定要操作，那么如果在{-1, 0, 1}中操作那么一定就不劣，所以一定能找得到一個小于等于2的一定不劣！如果一個數小于-1也同理，一定可以找到一個數大于等于-1的數不比它劣，綜上，一定能找得到一個只包含{-1，0，1}三種數的數列，它的答案最優。
這一步什么用呢？這是個好問題，你想一下，我們考慮最暴力的dp——\(f_{i,j}\) 表示考慮到了前 \(i\) 位，且最后一位（即第 \(i\) 位）上的數是 \(j\) 使前\(i\)位單調不降的最小操作數，很明顯，如果是沒有前面的性質，他就只能是一個有無窮個狀態的DP,這完全不可能實現，但是加上這個性質后，就只有 \(3 \times n\) 個狀態，接下來就是一個狀態機的板子了，哦對了，記得狀態中的 \(j\) 要加 1 ,不能以負數為下標 QwQ
核心代碼在下面：
if(a[i] == -1)
{
f[i][0] = f[i - 1][0];
f[i][1] = 0x3f3f3f3f;
f[i][2] = f[i - 1][2] + 2;
}
if(a[i] == 0)
{
f[i][0] = f[i - 1][0] + 1;
f[i][1] = min(f[i - 1][0], f[i - 1][1]);
f[i][2] = f[i - 1][2] + 1;
}
if(a[i] == 1)
{
f[i][0] = f[i - 1][0] + 2;
f[i][1] = f[i - 1][0] + 1;
f[i][2] = min(f[i - 1][0], min(f[i - 1][1], f[i - 1][2]));
}
2.P4395 [BalticOI 2003] Gem 氣墊車 / P5765 [CQOI2005] 珠寶
一道比較經典的樹形dp,簡要題面如下：
給出一棵樹，要求你為樹上的結點標上權值，權值可以是任意的正整數，唯一的限制條件是相鄰的兩個結點不能標上相同的權值，要求一種方案，使得整棵樹的總價值最小。
我們最暴力的做法就是 \(f_{u,val}\) 表示以 \(u\) 為根的的子樹，且 \(u\) 上的權值為 \(val\) 的合法子樹和最小值，因為有關系的只有每條邊的兩個點，條件約束它們不能相同，所以只有 \(u\) 和其兒子會產生約束，而兒子之間有兩條邊，所以他們是獨立的，我們只要找到兒子中不存在的權值最小值，給 \(u\) 附上就好了，但是有個問題，這樣子的模型的確沒有問題，但是狀態數是 \(n ^ 2\) 的，轉移是 \(n\) 的，時間復雜度是 \(O(n^3)\) 很明顯不行啊，那我們想一想能不能和上面一樣，把狀態減少一點，接下來，我們就是要證點權最大值不會超過 \(log_2n\),一下比較口胡，不太嚴謹，見諒哈，見諒
先來考慮什么情況是不優的，當然是這其中的葉子節點的數量大于父親的數量。這樣便需要引入權值。也就是說，如果有n個父親節點，那么葉子必須要n+1個才可以。我們還知道，這些葉子必須掛在一個節點上才行，所以每個節點的子節點數應該>=2。這樣至多會有logn層。我們又知道權值是跟層數是一個數量級的。所以權值也在logn級別。
這樣就口胡完了，感性理解一下，反正不是錯的QwQ,這樣子就只有 \(nlog_2n\) 個狀態，轉移也順帶變優了， 每次轉移的時間復雜度減少成了 \(log_2n\) 總時間復雜度就是 \(nlog^2n\) 了。
核心代碼如下：
void dfs(int u, int fa)
{
for(int i = 1 ; i <= max_ ; i ++ ) f[u][i] = i;
for(int i = h[u] ; i != -1 ; i = ne[i])
{
int j = e[i];
if(j == fa) continue;
dfs(j, u);
for(int k = 1 , min_ = 1e18; k <= max_ ; f[u][k] += min_, k ++ , min_ = 1e18)
for(int l = 1 ; l <= max_ ; l ++ )
if(k != l)
min_ = min(min_, f[j][l]);
}
}
接下來就是斜率優化dp
斜率優化dp
我這里真的講的不太清楚，畢竟我自己也學得不怎么好，所以，我就先口胡一下
先把例題擺上，最經典的 玩具裝箱 ，題面如下：
P 教授要去看奧運，但是他舍不下他的玩具，于是他決定把所有的玩具運到北京。他使用自己的壓縮器進行壓縮，其可以將任意物品變成一堆，再放到一種特殊的一維容器中。
P 教授有編號為 \(1 \cdots n\) 的 \(n\) 件玩具，第 \(i\) 件玩具經過壓縮后的一維長度為 \(C_i\)。
為了方便整理，P 教授要求：
-
在一個一維容器中的玩具編號是連續的。
-
同時如果一個一維容器中有多個玩具，那么兩件玩具之間要加入一個單位長度的填充物。形式地說，如果將第 \(i\) 件玩具到第 \(j\) 個玩具放到一個容器中，那么容器的長度將為 \(x=j-i+\sum\limits_{k=i}^{j}C_k\)。
制作容器的費用與容器的長度有關，根據教授研究，如果容器長度為 \(x\)，其制作費用為 \((x-L)^2\)。其中 \(L\) 是一個常量。P 教授不關心容器的數目，他可以制作出任意長度的容器，甚至超過 \(L\)。但他希望所有容器的總費用最小。
先列出最基本的樸素dp方程，先用前綴和優化，再將固定的元素提出來，最后就只要算
， 在轉化成一次函數的截距式 \(y=kx+b\) 最后帶回原式，一一得出 \(y,k,b,x\)
就轉化成了選定一個點，使截距最小化，這里維護一個凸包就好了，這怎么維護一個凸包呢，用隊列來維護，維護的時候看一下和隊尾的點哪個優，隊尾不優就彈出來，一直到比當前的數優為止，再加入到隊尾中，這就是一個凸包了，我在下面給個簡要的過程：
最后就是代碼了：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e4 + 10;
int n, l;
int Clac[N], sum[N], f[N], g[N], h, t, Q[N];
inline double clac(int j1, int j2)
{
return (double)(Clac[j2] + g[j2] - Clac[j1] - g[j1]) / (f[j2] - f[j1]);
}
signed main()
{
cin >> n >> l;
for(int i = 1 ; i <= n ; i ++ )
{
cin >> sum[i];
sum[i] += sum[i - 1];
f[i] = sum[i] + i;
g[i] = (f[i] + l + 1) * (f[i] + l + 1);
}
g[0] = (l + 1) * (l + 1);
for(int i = 1 ; i <= n ; i ++ )
{
while(h < t && clac(Q[h], Q[h + 1]) <= 2 * f[i]) h ++ ;
Clac[i] = Clac[Q[h]] + (f[i] - f[Q[h]] - l - 1) * (f[i] - f[Q[h]] - l - 1);
while(h < t && clac(Q[t], i) < clac(Q[t - 1], Q[t])) t -- ;
Q[ ++ t] = i;
}
cout << Clac[n];
return 0;
}
4.旅游路線
我們從答案往后倒推，如果我們要求最多可以剩下多少錢，發現 \(T \le 10^5\) 那一定就是預處理每個點有 \(k\) 元錢能走多遠， 我們就設 \(f_{i,cost}\) 來表示從 \(i\) 開始走，花 \(cost\) 最多能走多遠，我們就可以有一個轉移：
\(f_{i,cost} = \max(f_{i,cost}, f_{j, cost - p[i]} + 從 i 處加油開始走到 j 的最遠距離)\)
給一下代碼：
for(int cost = 0 ; cost <= n * n ; cost ++ )
for(int i = 1 ; i <= n ; i ++ )
if(p[i] <= cost)
for(int j = 1 ; j <= n ; j ++ )
f[i][cost] = max(f[i][cost], f[j][cost - p[i]] + g[i][j]);
所以我們要再列一個輔助數組 \(g_{i,j}\) 來表示在 \(i\) 處加油后走到 \(j\) 的最遠距離，我們還是沒法一下子就求出 \(g\)， 又得再列幾個輔助輔助轉移數組的數組(bushi，考慮按位處理 \(c_i\) 對于每一位用倍增距離來維護轉移，可能有點懵，我們把他抽象化：對于每一位的 \(c_i\) 設立兩個子輔助數組 \(tmp1\) 和 \(tmp2\) ，\(tmp2\) 表示還沒有更新完的 \(g_i\)， \(tmp1\) 表示更新以后的 \(tmp2\) , 顯然有 \(tmp1_j = \max(tmp1_j, tmp2_k + dist_{k, j, u})\) 轉移一輪完 \(tmp2 = tmp1\) 最終轉移完 \(g_i = tmp2\), 其中 \(dist_{i, j, u}\) 表示從 \(i\) 到 \(j\) 走了 \(2^u\) 條邊的最長距離。
這是維護 \(g\) 的代碼：
for(int i = 1 ; i <= n ; i ++ )
{
for(int j = 1 ; j <= n ; j ++ ) tmp2[j] = tmp1[j] = -1e18;
tmp2[i] = 0;
for(int u = 18 ; u >= 0 ; u -- )
if(c[i] & (1 << u))
{
for(int j = 1 ; j <= n ; j ++ )
for(int k = 1 ; k <= n ; k ++ )
tmp1[j] = max(tmp1[j], tmp2[k] + dist[k][j][u]);
for(int j = 1 ; j <= n ; j ++ ) tmp2[j] = tmp1[j];
}
for(int j = 1 ; j <= n ; j ++ ) g[i][j] = tmp2[j];
}
最后，你會發現 \(dist\) 已經不用再用其他的數組來維護了，直接倍增Floyd就好了， 下放代碼：
for(int u = 0 ; u <= 18 ; u ++ )
for(int i = 1 ; i <= n ; i ++ )
for(int j = 1 ; j <= n ; j ++ )
dist[i][j][u] = -1e18;
for(int i = 1 ; i <= n ; i ++ ) dist[i][i][0] = 0;
for(int i = 1 ; i <= m ; i ++ )
{
int a, b, l;
cin >> a >> b >> l;
dist[a][b][0] = max(dist[a][b][0], l);
}
for(int u = 1 ; u <= 18 ; u ++ )
for(int k = 1 ; k <= n ; k ++ )
for(int i = 1 ; i <= n ; i ++ )
for(int j = 1 ; j <= n ; j ++ )
dist[i][j][u] = max(dist[i][k][u - 1] + dist[k][j][u - 1], dist[i][j][u]);
這道題目就是很經典的倒推思想，從答案推到給出的信息，倒著推很絲滑，但如果你正著推就無從下手，以上只是我的看法，大佬們可能還會有其他的更簡單的，或者是可以從正著想的方法，反正我不會 QwQ
圖論
這是割點的例題
新年的毒瘤
辭舊迎新之際，喜羊羊正在打理羊村的綠化帶，然后他發現了一棵長著毒瘤的樹。
這個長著毒瘤的樹可以用 \(n\) 個結點 \(m\) 條無向邊的無向圖表示。這個圖中有一些結點被稱作是毒瘤結點，即刪掉這個結點和與之相鄰的邊之后，這個圖會變為一棵樹。樹也即無簡單環的無向連通圖。
現在給你這個無向圖，喜羊羊請你幫他求出所有毒瘤結點。
輸入格式
第一行兩個正整數 \(n\), \(m\)，表示有 \(n\) 個點 \(m\) 條邊。保證 \(2 \le n\)
接下來 \(m\) 行，每行兩個整數 \(v,u\)，表示 \(v\) 和 \(u\) 之間有一條無向邊。\(1 \le v,u \le n\)。保證沒有重邊和自環。
input
6 6
1 2
1 3
2 4
2 5
4 6
5 6
output
3
4 5 6
首先呢，是一棵樹，那么得聯通，所以呢我們刪掉的這個點一定不能是割點， 這直接用點雙來求割點就好了，其次呢，就是不能有環，也就是刪完之后得剩 \(n-2\) 條邊，就直接判斷就好了。很簡單，給一個丑陋的代碼：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int M = 2e5 + 10;
int n, m;
vector<int> edge[N];
int dfn[N], low[N], timestamp;
bool st[N];
void tarjan(int u, int fa)
{
dfn[u] = low[u] = ++ timestamp;
int son_cnt = 0;
for (int i = 0 ; i < edge[u].size() ; i ++ )
{
int j = edge[u][i];
if (!dfn[j])
{
son_cnt ++ ;
tarjan(j, u);
low[u] = min(low[u], low[j]);
if(low[j] >= dfn[u]) st[u] = true;
}else if (dfn[j] < dfn[u] && j != fa) low[u] = min(low[u], dfn[j]);
}
if (fa < 0 && son_cnt == 1) st[u] = 0;
}
signed main()
{
cin >> n >> m;
for(int i = 0 ; i < m ; i ++ )
{
int a, b;
cin >> a >> b;
a -- ;
b -- ;
edge[a].push_back(b);
edge[b].push_back(a);
}
tarjan(0, -1);
vector<int> ans;
for(int i = 0 ; i < n ; i ++ )
if(st[i] == false && m - edge[i].size() == n - 2)
ans.push_back(i + 1);
sort(ans.begin(), ans.end());
cout << ans.size() << endl;
for(int i = 0 ; i < ans.size() ; i ++ ) cout << ans[i] << " ";
return 0;
}
數學
接下來就是數學，按理來說S組不會考多難的，所以就簡略的過一下
1. P1414 又是畢業季II
簡要題意就是給了 \(n\) 個數， 求 \(k=1\dotsn\) 時在 \(n\) 個數中任選 \(k\) 個數的最大公約數的最大值，這其實和我剛考的 \(Htoj\) 的 S T1 很像，這是那道題的鏈接 只不過就是把 k 固定成了 2 而已，其實我們如果時枚舉 k 個數，求最大公約數再取最大值，這時間復雜度直接爆表，所以這樣肯定是不行滴，我們可以先將題目轉化一下，k 個數的最小公約數是 max ， 那是不是意味著至少有 k 個數包含 max 這個因子？那這就引導著我們，去將每個數的因子分出來，\(cnt_x\) 記錄有多少個數包含因子 x，切記不是這么多個數總共有多少個因子 x，一個數只貢獻 1 ， 處理完之后我們先看弱化版，k=2的時候就只要從大到小枚舉因子，看一下有沒有至少兩個數出現這個因子，有的話就直接輸出就好了，我們在看這個原題，不難再發現一個性質, \(k = x\) 的答案一定比 \(k > x\) 的答案來的大，所以能，我們只要維護一個指針，k從小到大算就好了，下面給個代碼
for(int i = 1 ; i <= n ; i ++ )
{
max_ = max(max_, a[i]);
for(int j = 1 ; j <= sqrt(a[i]) ; j ++ )
if(a[i] % j == 0)
{
cnt[j] ++ ;
if(a[i] != j * j) cnt[a[i] / j] ++ ;
}
}
int op = max_;
for(int i = 1 ; i <= n ; i ++ )
{
while(cnt[op] < i)
op -- ;
cout << op << endl;
}
2. 票數統計
妹滋滋是一個善于編程的女孩子。
但是某一天，她一不小心把 UOJ 后臺的票數統計程序寫錯了。
本來嘛在這種根本沒有什么用的功能上出了 bug 也沒有什么大關系，但是又有某一天，UOJ 突然就開始搞全民公投了。
這可怎么辦呢？如果這個消息讓別人知道的話自己肯定會被查表，更不要說讓所有用戶重新來投一次票了。
作為一個要強的女孩子，妹滋滋決定自力更生。
通過一些奧妙重重的方式，妹滋滋知道了一些關于這次全民公投的信息。
- 這次全民公投一共有 \(n\) 位用戶排隊參加，編號為 \(1\) 到 \(n\)。每一位用戶要么投了通過，要么投了不通過。
- 有 \(m\) 個二元組 \((x_i,y_i)\)，每個二元組給出這樣一個信息： “前 \(x_i\) 位用戶中，恰好 \(y_i\) 位投了通過” 和 “后 \(y_i\) 位用戶中，恰好有 \(x_i\) 位投了通過” 這兩句話中，至少有一句是成立的。
作為分析的第一步，她想要知道有多少種投票情況是滿足她所得到的信息的。當然，可能所有投票情況都不滿足條件。
解法：考慮組合數
當 \(x>y\) 時條件為前綴限制，\(x<y\) 時條件為后綴限制。
既有前綴限制，又有后綴限制的情況下，我們枚舉總共1的個數，把后綴限制轉化為前綴限制。
如果所有限制均有 \(x \not= y\) 則可以直接使用組合數計算。預處理組合數，單次計算的時間復雜度是 \(O(n)\) 的。
當有 \(x=y\) 時，顯然只需要考慮所有 \(x = y\) 限制中 \(x\) 最大的限制即可，總方案數為滿足前綴+滿足后綴-滿足前綴和后綴。時間復雜度 \(O(n^2)\)。
代碼：
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int M = 5010;
const int mod = 998244353;
int n;
int ax[N], ay[N], at;
int bx[N], by[N], bt;
int c[M][M], v[M];
int solve(int x)
{
int last = 0 , ans = 1;
memset(v , -1 , sizeof(v));
v[0] = 0 , v[n] = x;
for(int i = 1 ; i <= at ; i ++ )
{
if(v[ax[i]] != -1 && v[ax[i]] != ay[i]) return 0;
v[ax[i]] = ay[i];
}
for(int i = 1 ; i <= bt ; i ++ )
{
if(v[n - bx[i]] != -1 && v[n - bx[i]] != x - by[i]) return 0;
v[n - bx[i]] = x - by[i];
}
for(int i = 1 ; i <= n ; i ++ )
{
if(v[i] != -1)
{
if(v[i] < v[last]) return 0;
ans = 1ll * ans * c[i - last][v[i] - v[last]] % mod , last = i;
}
}
return ans;
}
int main()
{
int T;
cin >> T;
while(T -- )
{
at = bt = 0;
int m , p = 0 , max_ = 0 , ans = 0;
cin >> n >> m;
for(int i = 1 ; i <= m ; i ++ )
{
int x, y;
cin >> x >> y;
max_ = max(max_, min(x, y));
if(x > y)
{
at ++ ;
ax[at] = x;
ay[at] = y;
}else if(x < y)
{
bt ++ ;
bx[bt] = y;
by[bt] = x;
}else p = max(p , x);
}
c[0][0] = 1;
for(int i = 1 ; i <= n ; i ++ )
{
c[i][0] = 1;
for(int j = 1 ; j <= i ; j ++ )
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
for(int i = max_ ; i <= n ; i ++ )
{
at ++ ;
ax[at] = ay[at] = p ;
ans = (ans + solve(i)) % mod;
bt ++ ;
bx[bt] = by[bt] = p ;
ans = (ans - solve(i) + mod) % mod;
at -- ;
ans = (ans + solve(i)) % mod ;
bt -- ;
}
printf("%d\n" , ans);
}
return 0;
}
At-hoc
1. 生產的手機
由于電信技術的發展，人人都可以通過手機互相聯系。
有一位電信大佬最近想生產一大批手機，然而從生產線上一臺一臺地生產實在太慢了，于是他想出了一個辦法 —— 讓手機自我復制。
于是他給手機加上了一個內置的函數 fork()。手機的程序如果調用這個函數，那么手機會生產出一臺完全一模一樣的手機（包括程序運行狀態），并且自己這臺的函數返回值為 \(1\) ，新手機的函數返回值為 \(0\) ，然后兩臺手機都繼續執行程序。（請注意黑體字內容）
初始時，只有一臺手機。接著，大佬讓手機計算形如這樣的表達式：
fork() <op> fork() <op> ... <op> fork()
其中
fork() && fork() || fork() && fork() && fork() || fork()
兩個運算都是左結合的，且 && 的優先級比 || 高，所以上面的那個表達式相當于：
((fork() && fork()) || ((fork() && fork()) && fork())) || fork()
對于表達式 \(a\) && \(b\)，手機會先計算 a 的值，如果為 \(0\) 那么不計算 \(b\) 的值（因為很重要所以說兩遍，請注意這里不計算 \(b\) 的值），該表達式值為 \(0\)；否則計算 \(b\) 的值并將其值作為該表達式的值。
對于表達式 \(a\) || \(b\)，手機會先計算 \(a\) 的值，如果為 \(1\) 那么不計算 \(b\) 的值（因為很重要所以說兩遍，請注意這里不計算 \(b\) 的值），該表達式值為 \(1\)；否則計算 \(b\) 的值并將其值作為該表達式的值。
表達式計算完成后，大佬制造出了數量驚人的手機，人類終于叩開了指數級工業制造的大門。
一萬萬年后，一位考古學家調查了此次事件。他得到了大佬讓手機計算的表達式。他想知道大佬當年究竟制造出了多少臺手機。（包括初始的那臺手機）
你可以參照樣例解釋來更好地理解題意。
輸入格式
第一行一個正整數 \(n\)，表示表達式中的 \(fork()\) 的數量。
接下來一行 \(n?1\) 個用空格隔開的字符串，每個字符串為 "&&” 或者 “||”，依次表示表達式中對應位置的運算符。
輸出格式
一行，一個整數表示制造出的手機的數量，你只用輸出答案對 \(998244353\) 取模后的結果。
樣例一
input
2
&&
output
3
explanation
共生產 \(3\) 臺手機，過程如下：
第 \(1\) 臺手機開始計算 \(fork()\) && \(fork()\)。
第 \(1\) 臺手機開始計算 \(fork()\)，產生了第 \(2\) 臺手機。
第 \(1\) 臺和第 \(2\) 臺的 \(fork()\) 計算完成，第 \(1\) 臺返回 \(1\)，第 \(2\) 臺返回 \(0\) 。
第 \(1\) 臺手機由于 \(fork()\) 返回值為 \(1\)，開始計算 \(fork()\) && \(fork()\) 右邊的 \(fork()\)，產生了第 \(3\) 臺手機。
第 \(2\) 臺手機由于 \(fork()\) 返回值為 \(0\) ，于是 \(fork()\) && \(fork()\) 值為 \(0\)（跳過右邊的 \(fork\) 的計算），程序結束。
第 \(1\) 臺和第 \(3\) 臺的 \(fork()\) 計算完成，第 \(1\) 臺返回 \(1\)，第 \(3\) 臺返回 \(0\)。
第 \(1\) 臺手機由于 \(fork()\) 返回值為 \(1\)，于是 \(fork()\) && \(fork()\) 值為 \(1\)，程序結束。
第 \(3\) 臺手機由于 \(fork()\) 返回值為 \(0\)，于是 \(fork()\) && \(fork()\) 值為 \(0\)，程序結束。
樣例二
input
6
&& || && && ||
output
15
限制與約定: \(n \le 10^5\)
題解
因為 && 的優先級高于 || 就將 || 作為分割線，每一塊 && 依次處理。
觀察題目，如果是 && 那么前面是 \(0\) 就停止，如果是 || 那么前面是 1 就停止
只有當手機返回值為1時才能造出手機。而且在當前這塊中復制出的手機，在下一塊中才能造出其他的手機。
所以就引導出了答案等于塊長的前綴乘加在一起。
接下來就是最簡單的實現了：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int mod = 998244353;
int n;
string str;
int cont[N], cnt = 0, idx = 0;
signed main()
{
cin >> n;
cnt = 1;
for(int i = 1 ; i < n ; i ++ )
{
cin >> str;
if(str[0] == '|') cont[ ++ idx] = cnt, cnt = 1;
else cnt ++ ;
}
cont[ ++ idx] = cnt;
int now = 1, ans = 1;
for(int i = 1 ; i <= idx ; i ++ )
{
now = (now * cont[i]) % mod;
ans = (ans + now) % mod;
}
cout << ans;
return 0;
}
2.關羽愛下象棋
關羽喜歡下象棋！
不過這次，他下膩了傳統象棋，并叫來了你做他的對手。你們將在一張 \(100\) 行 \(100\) 列的象棋棋盤格點上對弈。關羽一身傲骨，給你了一輛大幅加強的車，自己則操縱一個小過河卒東躲西藏。具體規則如下：
-
卒初始在第 \(x_1\) 行第 \(y_1\) 列的格點上，車初始在第 \(x_2\) 行第 \(y_2\) 列的格點上。
-
卒每次可以在左、右、下三種移動方向中選擇一種，然后移動一格（但是不能往上）。即，若記第 \(x\) 行第 \(y\) 列的格點為 \((x,y)\)，則卒可以從 \((x,y)\) 移動到 \((x+1,y),(x,y+1),(x,y?1)\)。
-
車可以向左向右移動多格，也可以向上向下移動多格，也可以不動。即，車可以從 \(x,y\) 移動到 \((x,y′)(x,y′) 或(x′,y)(x′,y)\)，其中 \(1 \le x′,y′ \le 100\)
-
卒和車均不可以走到棋盤外。
-
這輛車經過現代科技改造，會沿路散發毒氣，車經過的格點都會被毒霧覆蓋，卒不能停留。例如，如果車從 \((x,y)\) 向右移動到 \((x,y′)（y′>y)\)，則 \((x,y),(x,y+1),…,(x,y′)\) 都會帶毒。其余三種移動方向類似。
-
這輛車不可被摧毀，即卒不能吃車，也不能移動到車占據的位置。
聰明的你發現你可以因此吊打武神關羽！于是你非常好奇，你最快幾步可以擊敗關羽。這個特殊的象棋分為若干回合，每回合是這樣進行的：
- 你操控車移動一次，也可以選擇不動。
- 如果車吃掉了卒（即車占據了卒所在位置），游戲結束。
- 卒移動一步。當且僅當卒沒有可移動方向時，卒才可以選擇不動（即左、右、下三個方向均為車、毒氣、棋盤邊界中的一種）。例如，如果進行到某一輪前，\((1,2)\) 有毒霧，且該回合車從 \((2,2)\) 移動到 \((2,1)\)，那么卒無可移動方向，故卒該輪不進行移動。
游戲總回合數定義為車決策的次數。
當然武神也很聰明，他希望游戲回合數盡可能多，而你希望游戲回合數盡可能少，并且你們都足夠聰明。你想提前知道，游戲將會進行幾回合？
樣例一
input
4
1 1 2 2
1 2 2 4
100 50 3 3
50 2 49 4
output
2
3
2
3
explanation
對于第一組數據，車可以選擇停在原地，而輪到卒的時候卒必須移動。無論向下還是向右，都會立馬被車吃掉。
注意這里只畫了棋盤左上角。
對于第二組數據，車可以先在卒下方灑出一行毒霧，然后再走到卒所在的第一行，即可必殺。
對于第三組數據，車移動到 \((100,3)\)，即可下一輪必殺。
對于第四組數據，答案是 \(3\)，這是為什么呢？
一道很有意思的題，我們要先控制一下，答案的最大值，我們可以考慮怎樣關羽必輸？觀察到關羽不能往后走，所以只要把關羽的前一行弄滿
毒氣，這樣就把關羽鎖在了一行里，最后直接走到關羽的那一行就好了，那最少要多少步呢？
事實證明，最多只要四步就能完成，接下來就只要爆搜亦或者分類討論就好了，我寫的是分類討論 :
#include <bits/stdc++.h>
#define int long long
using namespace std;
int T;
signed main()
{
cin >> T;
while(T -- )
{
int a, b, c, d;
cin >> a >> b >> c >> d;
if(a == c || b == d) cout << 1 << endl;
else
{
if(b > d) b = 100 - b + 1, d = 100 - d + 1;
if(a == 100) cout << 2 << endl;
else if(b == 1)
{
if(c == a + 1 || d == 2) cout << 2 << endl;
else cout << 3 << endl;
}else if(b == 2)
{
if(c == a + 1 || d == 3) cout << 3 << endl;
else if(c <= a && d == 4) cout << 3 << endl;
else{
if(c == a + 1) cout << 3 << endl;
else if(a == 99) cout << 3 << endl;
else cout << 4 << endl;
}
}else{
if(c == a + 1) cout << 3 << endl;
else if(a == 99) cout << 3 << endl;
else cout << 4 << endl;
}
}
}
return 0;
}
比賽總結
比賽不太會總結，就只能把每道題的正解說一遍，有的可能講的不清楚
1. 2025.8.12 暑期校隊集訓 #1
T1
先說題面，就是每次會選擇兩個權值最小且下標最小的兩個數，將第一個數刪掉，將第二個數 \(\times 2\), 問最后的局面是怎樣的，最多有 \(1.5 \times 10^5\) 個數 ，最大 \(10^9\).
一層一層的來說是怎么想到的，首先我們要看到題面中的是將第二個數 \(\times 2\), 為啥不是 $ \div 2$, 亦或者是 \(- 2\) 呢，為什么要讓一個數變大呢？這就是為了能讓我們的一個性質成立：如果最小的數只有一個，那么這個數就一定沒有用了，為什么？因為一個數只能變大不能變小，不可能會在最后的操作使一個數變小，更別說和目前最小值一樣小了，所以這時候我們就直接把這個數扔出堆，放到最終序列里就好了，接下來就只是堆的模擬就完了,給一個碼風極度不良好的代碼：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n;
int a[N], idx;
struct node
{
int w, id;
bool operator<(const node &t) const
{
if(w == t.w) return id > t.id;
return w > t.w;
}
}ans[N];
priority_queue<node> heap;
bool cmp(node a, node b)
{
return a.id < b.id;
}
signed main()
{
freopen("monsters.in", "r", stdin);
freopen("monsters.out", "w", stdout);
cin >> n;
for(int i = 1 ; i <= n ; i ++ ) cin >> a[i];
for(int i = 1 ; i <= n ; i ++ ) heap.push({a[i], i});
while(heap.size())
{
auto u = heap.top();
heap.pop();
if(heap.size() == 0)
{
ans[ ++ idx] = u;
break;
}
auto v = heap.top();
if(u.w != v.w) ans[ ++ idx] = u;
else heap.pop(), heap.push({u.w + v.w, v.id});
}
sort(ans + 1, ans + 1 + idx, cmp);
cout << idx << endl;
for(int i = 1 ; i <= idx ; i ++ ) cout << ans[i].w << " ";
return 0;
}
T2
題意如下，給定兩個長度都是 \(n\) 的數組 a, b, b可以調換順序，問調整完之后組成 \(c=(a+b)%n\) 的字典序最小的 \(c\).
我們做一個顯而易見的貪心，因為如果第 \(i\) 位 \(c_1 > c_2\)，無論第 \(i+1\) 位 \(c_1\) 有多小，都不可能整體比 \(c_2\) 小，所以我們前面無論怎樣都要讓 \(c\) 最小，這就讓我們想到了二分，找到了就要刪除，這刪除就直接用 \(multiset\) 來維護就好了，獻上丑的一批的代碼：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n;
int a[N], b[N];
multiset<int> s;
signed main()
{
freopen("array.in", "r", stdin);
freopen("array.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1 ; i <= n ; i ++ ) cin >> a[i];
for(int i = 1 ; i <= n ; i ++ ) cin >> b[i];
for(int i = 1 ; i <= n ; i ++ ) s.insert(b[i]);
for(int i = 1 ; i <= n ; i ++ )
{
auto it = s.lower_bound((n - a[i]) % n);
if(it == s.end()) cout << (a[i] + *s.begin()) % n << " ", s.erase(s.begin());
else cout << (a[i] + *it) % n << " ", s.erase(it);
}
return 0;
}
T3
題面太長了，直接截屏
這題的話就有點抽象了，我們要分成兩種不同的連通塊來討論
- 第一種，這種連通塊是一棵樹，那么我們只要在葉子上打標記就好了，就是葉子節點和其父親的那條邊靠近葉子節點打標記
- 第二種，這種連通塊就不是一棵樹，我們就是要去找橋，就是邊雙，但這種方法不夠簡單，所以我換了一種方法來求橋——不斷的把度數為一的點刪去，沒法刪之后，沒被刪的點和被刪了的點所連的邊就是橋了。
代碼中的奇怪數字請別放在心上
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 10;
const int M = N << 1;
int n, m;
int in[N], tot;
int p[N];
set<int> s;
queue<int> q;
vector<int> edge[N], leaf;
int h[N], e[M], ne[M], idx;
pair<int, int> ans[N];
bool st[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u, int fa)
{
s.insert(u);
st[u] = true;
if(in[u] == (int)(1.025042617))
{
leaf.push_back(u);
q.push(u);
}
for(int i = h[u] ; i != -(int)(1.025042617) ; i = ne[i])
{
int j = e[i];
if(st[j] == true) continue;
dfs(j, u);
}
}
signed main()
{
freopen("deadend.in", "r", stdin);
freopen("deadend.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
memset(h, -(int)(1.025042617), sizeof h);
cin >> n >> m;
for(int i = 1 ; i <= m ; i ++ )
{
int a, b;
cin >> a >> b;
edge[a].push_back(b);
edge[b].push_back(a);
add(a, b);
add(b, a);
in[a] += (int)(1.025042617);
in[b] += (int)(1.025042617);
}
for(int i = (int)(1.025042617) ; i <= n ; i ++ )
if(st[i] == false)
{
while(q.size()) q.pop();
s.clear();
leaf.clear();
dfs(i, i);
while(q.size())
{
auto t = q.front();
q.pop();
s.erase(t);
for(int j = h[t] ; j != -(int)(1.025042617) ; j = ne[j])
if( -- in[e[j]] == (int)(1.025042617))
q.push(e[j]);
}
if(s.size() == 0)
for(auto t : leaf)
ans[ ++ tot] = {t, edge[t].front()};
else
for(auto t : s)
for(int j = h[t] ; j != -(int)(1.025042617) ; j = ne[j])
if(s.count(e[j]) == 0)
ans[ ++ tot] = {t, e[j]};
}
sort(ans + (int)(1.025042617), ans + (int)(1.025042617) + tot);
cout << tot << endl;
for(int i = (int)(1.025042617) ; i <= tot ; i ++ ) cout << ans[i].first << " " << ans[i].second << endl;
return 0;
T4
最后一題復雜度不是最優，但是也跑的飛快，就是分塊加樹狀數組，啥也不用講，沒了，這里要吐槽一下本來亂搞卡卡常就過了，結果考場最后幾分鐘去拼正解，最后沒卡常都有 \(50pts\) 的代碼被我改成了 \(20pts\) 恨吶~
放比較新奇的思路的代碼：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int M = 2e5 + 10;
int n, q, a[N];
int tr[M];
int lowbit(int x)
{
return x & -x;
}
void add(int x, int c)
{
for (int i = x; i < M; i += lowbit(i)) tr[i] += c;
}
int sum(int x)
{
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
void Add(int x, int t)
{
for(int i = x ; i < M ; i += x ) add(i, t);
}
signed main()
{
freopen("tab.in", "r", stdin);
freopen("tab.out", "w", stdout);
cin >> n >> q;
for(int i = 1 ; i <= n ; i ++ )
{
cin >> a[i];
Add(a[i], a[i] - 1);
}
while(q -- )
{
int op, p, x;
cin >> op;
if (op == 1)
{
cin >> p >> x;
Add(a[p], 1 - a[p]);
a[p] = x;
Add(a[p], a[p] - 1);
} else
{
cin >> x;
cout << n * x - sum(x) << endl;
}
}
return 0;
}
浙公網安備 33010602011771號