2025/7/9 報(bào)道

報(bào)道，沒什么好說的，坐了一上午的動(dòng)車，下午才到，晚上安排自我介紹，
然后切了點(diǎn)水題。
宿舍6個(gè)人，福建2個(gè)，紹興1個(gè)，杭州2個(gè)，江蘇1個(gè)。

2025/7/10 上課【貪心】

還在舒適圈范圍內(nèi)）
But

目睹六年級巨佬手撕黑題，恐怖如斯
原來是天津第一小學(xué)生，更恐怖了

2025/7/11 上課【計(jì)數(shù)and容斥】

也還在舒適區(qū)。
學(xué)習(xí)總結(jié)寫了，找不到了（

2025/7/12 ?？肌?1】

排名20/20
爆了，剛來太緊張，發(fā)揮失常。

2025/7/13 上課【字符串】

死去的AC自動(dòng)機(jī)重新攻擊我的大腦，
沒怎么聽懂，所以沒有總結(jié)（bushi

2025/7/14 模考【02】

排名12/20
又爆了
02模考總結(jié)被03?？嫉哪？伎偨Y(jié)的總結(jié)覆蓋了（

2025/7/15 模考【03】

連續(xù)兩天模考（
又一次爆了

排名 6/20
分?jǐn)?shù)150/400

賽中時(shí)間記錄 

8:30 開始?？?br>8:30-8:57 想T1
8:57-9:06 寫T2
9:06-10:09 寫T1
10:09-10:38 寫T4
10:38-11:14 繼續(xù)寫T1
11:15-11:16 檢查代碼
11:16-11:24 看T3
11：42-11：58 寫T4
11:50 ?？冀Y(jié)束

T1 

題意：

T 組數(shù)據(jù)，每次詢問給定兩個(gè)數(shù) n,q
初始 n 個(gè)格子有磚， q 次詢問，每個(gè)格子上有 a_i 塊磚（ i>=0，a_i∈{n-1,n,n+1} ）。小G從0號格子開始一格一格往后搬磚，當(dāng)他在第 i 個(gè)格子，設(shè)當(dāng)前所在格子有 x 塊磚，他會(huì)將這 x 塊磚分別拿走放到編號 [max(n,i+1),i+x] 的格子上,每個(gè)格子各一塊磚，多余的磚丟棄。
對于每次詢問給定一個(gè)數(shù) y ，當(dāng)他走到第 y 個(gè)格子的時(shí)候，第 y 個(gè)格子上有多少塊磚

（n≤1e5，T≤10，q≤1e5，n≤y≤1e18）

開局看T1，思考滿分做法，想不到，先做其他題
寫完T2回來繼續(xù)看T1，思考 subtask2 和 subtask3
建 a序列 的 差分?jǐn)?shù)組，O(1) 更新新的磚 ，一直更新到 1e6 ，每到一個(gè)新的位置就把磚數(shù)存到 ans 數(shù)組里，查詢時(shí)直接輸出 ans[x] ，復(fù)雜度O(x)
測樣例的時(shí)候 數(shù)據(jù) 4 and 5 WA了，調(diào)了好久發(fā)現(xiàn)更新區(qū)間[L,R]如果L>R時(shí)不需要更新
TLE50pts

T2 

題意：

定義一個(gè)字符串是好的，當(dāng)且僅當(dāng)可以重排為回文串。給定字符串 s ，求 s 中最長的好子序列的長度

(|s|≤1e6)

幼兒園題，秒了
(11：15檢查代碼時(shí)發(fā)現(xiàn)沒寫freopen，差點(diǎn)掛了)

T3 

題意：

給定 n,k 和 k 顆有 n 個(gè)點(diǎn)的樹。對于每個(gè)點(diǎn)對(i,j)，求出其在每棵樹上的路徑經(jīng)過的點(diǎn)(含端點(diǎn))的交集大小

(1≤n,k≤500)

特殊性質(zhì)：滿足這 k 棵樹均為鏈。注意 1 不一定是鏈的端點(diǎn)。

思考了下特殊性質(zhì)，感覺代碼不怎么好寫，不如去想T4

T4 

題意：

給定一個(gè) n*m 的網(wǎng)格圖，圖上 '$' 表示寶藏，其余都是空地，有兩條大河，一條為縱，一條為橫，長度都是無窮大，寬度至少為1，
小P知道兩條大河經(jīng)過的寶藏個(gè)數(shù)和為 k ，注意兩條大河相交的地方寶藏個(gè)數(shù)被計(jì)算了兩次貢獻(xiàn)，
請求出放置兩條大河的合法方案數(shù)有多少種

(n,k≤1e5，m≤100)

設(shè) hc[i] 和 lc[i] 分別為 行的 和 列 寶藏?cái)?shù)的前綴和
hs[i] 和 ls[i] 分別為 橫河 和 縱河 寶藏?cái)?shù)和為 i 的方案數(shù)
可以通過 hc 和 lc 求出 hs 和 ls

1 for(int a=1;a<=n;a++){
2     for(int b=a;b<=n;b++){
3         hs[hc[b]-hc[a-1]]++;
4    }
5 }

求 ls 同理
枚舉 i 到 k ，所有 hs[ i ]*ls[ k-i ] 的和就是ans

1 for(int i=0;i<=k;i++){
2     ans+=(hs[i])*(ls[k-i]);
3 }

 復(fù)雜度O(n2) ，期望40分，but最后寫掛了（

2025/7/16 休息日【01】

我報(bào)的項(xiàng)目：桌游，電影
早上：先去看《飛屋環(huán)游記》然后去棋牌室玩UNO
下午：先去棋牌室玩三國殺，我超，蒸，然后去看《紅海行動(dòng)》
晚上：自習(xí)

2025/7/17 上課【數(shù)據(jù)結(jié)構(gòu)優(yōu)化】

知識點(diǎn)  

　　1.啟發(fā)式合并，小的結(jié)構(gòu)合并到大的結(jié)構(gòu)上，幾乎適用于所有數(shù)據(jù)結(jié)構(gòu)合并操作
　　2.線段樹合并，合并兩顆線段樹重疊的部分
　　之前只會(huì)用普通線段樹和求區(qū)間最大子段和，今天惡補(bǔ)了其他用法（

B題  

(原CF 洛谷CF600E)：

直接用啟發(fā)式合并暴力從葉子節(jié)點(diǎn)合并到根，   每次合并時(shí)把小的樹合并到大的樹上，用迭代器枚舉map的每個(gè)元素，

如果這個(gè)顏色數(shù)量比原來的答案更多則直接更新，如果相等則加上， 

寫這題的時(shí)候順便學(xué)了下迭代器。

for(map<int,int>::iterator j=ma[pos[to]].begin();j!=ma[pos[to]].end();j++){
     ma[pos[now]][j->first]+=ma[pos[to]][j->first];
     if(ma[pos[now]][j->first]>mx[now]){
         mx[now]=ma[pos[now]][j->first];
         ans[now]=j->first;
     }
     else if(ma[pos[now]][j->first]==mx[now])ans[now]+=j->first;
}    

F題  

(洛谷 4556)

樹上差分優(yōu)化發(fā)放救濟(jì)糧的操作，起點(diǎn)終點(diǎn)差分?jǐn)?shù)組增加，兩點(diǎn)的LCA的父節(jié)點(diǎn)差分?jǐn)?shù)組減少
每個(gè)點(diǎn)建一顆動(dòng)態(tài)開點(diǎn)權(quán)值線段樹，發(fā)放的操作完成后從葉子節(jié)點(diǎn)向上合并線段樹，也可以用和B題相似的做法，計(jì)算答案時(shí)查找最大值，
求LCA只會(huì)用樹剖求的蒟蒻（

2025/7/18 上課【計(jì)算幾何】

emm只聽懂了凸包的部分

知識點(diǎn)   

　　1.凸包，凸包的性質(zhì)，周長最小，面積最小
　　2.斜率優(yōu)化dp
　　3.李超線段樹

Andrew算法   

每個(gè)點(diǎn)按x升序排序，從左到右每加入一個(gè)點(diǎn)
則判斷此時(shí)棧頂?shù)狞c(diǎn)與次棧頂?shù)狞c(diǎn)的斜率和新點(diǎn)與次棧頂?shù)狞c(diǎn)的斜率大小關(guān)系
若棧頂?shù)男甭蚀螅瑒t棧頂?shù)狞c(diǎn)出棧，重復(fù)操作直到棧頂?shù)狞c(diǎn)斜率更小，然后新點(diǎn)入棧，

此時(shí)下凸殼就求完了,上凸殼用相同的方法再跑一遍
就能拼成一個(gè)完整的凸包了

A題   

(凸包模板題 洛谷 2742):

每加入新的一個(gè)點(diǎn)就判斷這個(gè)點(diǎn)與棧頂?shù)狞c(diǎn)的斜率大小，如果加入的點(diǎn)斜率小，
則出棧，直到遇到斜率更小的點(diǎn)，求完下凸殼后求上殼，兩個(gè)凸殼拼起來就是完整的凸包

B題   

(信友隊(duì) 1545)

題意：給定 n 個(gè)點(diǎn)，求圍成的凸包面積

再打一遍凸包模板，設(shè)有 n 個(gè)點(diǎn),則一共能分成 n-2 個(gè)三角形，用海倫公式求出來每個(gè)的面積相加即可，
題目沒說答案要兩位小數(shù)，因?yàn)檫@個(gè)浪費(fèi)我一個(gè)小時(shí)（

D題   

(洛谷 1034)

枚舉每個(gè)點(diǎn)加入的矩陣，用類似狀壓的方式暴力搜索

2025/7/19 模考【04】 

大爆

排名 12/20
分?jǐn)?shù)74/400

賽中時(shí)間記錄    

  8:30 開始?？?br>  8:30-10:02 寫T1
  10:02-10:14 寫T3
  10:14-10:32 寫T2
  10:32-11:02 寫T4
  11:02-12:00 思考T2和T4
  12:00 ?？冀Y(jié)束

T1    

題意：

給定兩個(gè)01串 a 和 b ，對于 a ，可以拿出一個(gè)與 b 長度相同的子串 c ，統(tǒng)計(jì) b 與 c 對于位置字符不同的數(shù)量，記作 f(b,c) 
求所有的 f(b,c) 中是偶數(shù)的數(shù)量

(1≤|b|≤|a|≤1e6)

讓人想到異或，思考預(yù)處理出1的個(gè)數(shù)為偶數(shù)的所有數(shù)，異或后查找一下有沒有這個(gè)數(shù)
尋找規(guī)律，發(fā)現(xiàn)一位的數(shù)1的數(shù)量為偶數(shù)數(shù)的數(shù)量為1
兩位的為2，三位的為4，四位的為8，emm沒用,而且2^1e6也存不下
試著求出a的boder，手模一下，發(fā)現(xiàn)好像也沒用，不死心，試著用kmp能不能做
還是不行，再試試哈希，復(fù)雜度也不對，再想著用線段樹，不行，
看了下特殊性質(zhì)，因?yàn)?b 為 a 的循環(huán)節(jié)， 所以答案重復(fù)計(jì)算了(|a|/|b|-1)次，只要求出第一遍，乘|a|/|b|即可，
于是開始往計(jì)數(shù)的方向想，沒想出來
思考O(n2)暴力的優(yōu)化，這樣check的復(fù)雜度必須是O(1)的，根本優(yōu)化不出來，最后只能交個(gè)暴力
(想了一堆方法，早該想到O(1)的check應(yīng)該是像判斷奇偶性這樣的簡單check，整場比賽完全沒有往這個(gè)方面想)

T2    

題意：

給定 n,m,q, 有 n 個(gè)結(jié)點(diǎn)，m 種傳送門，m 個(gè) n*n 的矩陣 w_1~m  , q 次詢問，第 i 種傳送門在結(jié)點(diǎn) u,v 之間的傳送時(shí)間為 w_i,u,v
每次詢問給定 s,t,k
求點(diǎn)s到點(diǎn)t換傳送門次數(shù)不超過k的最小時(shí)間

(n,m≤60，w_i,u,v≤1e6，q≤1e5，k≤1e3)

第一眼分層圖最短路，和P4568很像，復(fù)雜度O( (nm+nm)log₂nm ),應(yīng)該可以，但空間復(fù)雜度巨大，然后就交了個(gè)暴力

T3    

題意：

T次詢問，每次詢問給定一個(gè)長度為 n 的排列 p ，你需要將它分成兩個(gè)不相交的子序列 a,b , 使得 LIS(a)+LDS(b) 最大

(1≤n≤1e5，1≤T≤10)

T1不會(huì)寫快瘋了，直接交暴力

T4    

題意：

給定 n,m,k,w 和一個(gè)長度為 n 的數(shù)列 x ，m 次操作每次操作把第 p 個(gè)元素修改為 v，
記 x₁，x₂，x₃...x_n 經(jīng)過排序的序列為 x₍₁₎，x₍₂₎，x₍₃₎...x_(n)，定義能量指標(biāo)為
∑?x_(i)i^k/w?
每次操作后求出 x 的能量指標(biāo)對998244353取模的結(jié)果

(1≤n,m≤1e5，1≤k≤5，1≤w≤20，1≤x_i,v≤1e9)

先交了暴力，然后開始想，沒什么思路

2025/7/20 上課【數(shù)列&矩陣】

知識點(diǎn)     

　　1.矩陣
　　2.拉格朗日插值，群論，擴(kuò)展歐幾里得定理，其他一些數(shù)論

A題     

(原CF 718C 洛谷CF718C)

因?yàn)橐恍┘?xì)節(jié)，重構(gòu)了好幾次代碼，調(diào)了一整天
導(dǎo)致一天就只寫了一題，直接當(dāng)題解看就行

題意：

有一個(gè)長度為 n 的序列 a ，m 次操作
有兩種操作，第一種是區(qū)間修改
第二種是求區(qū)間里所有的 f(a[i]) 的和
f_(x) 是斐波那契數(shù)列的第 x 項(xiàng)
f₍₁₎=1，f₍₂₎=2
f_(x)=f_(x-1)+f_(x-2)(x>=3)

(1≤n,m≤1e5，1≤a_i≤1e9)

矩陣快速冪板子題
動(dòng)態(tài)開點(diǎn)線段樹維護(hù)矩陣，再用矩陣快速冪求斐波那契數(shù)列

矩陣快速冪可以 log n 求斐波那契數(shù)列的第 n 項(xiàng)
設(shè)

  0 1                 1 1
  1 1                 0 0
矩陣 A            矩陣 B

C = (A*B)ⁿ
則 C_0,1 為斐波那契數(shù)列的第 n 項(xiàng)

事實(shí)上，矩陣快速冪可以 log n 求任何線性函數(shù)。
查詢和修改的操作和普通線段樹一樣，只是維護(hù)對象變成矩陣，可以手寫一個(gè)數(shù)據(jù)類型

AC代碼

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstdio>
  4 #include<cstring>
  5 using namespace std;
  6 const int maxn=2e5+200;
  7 const int mod=1e9+7;
  8 #define mid (l+r>>1)
  9 #define ls (pos<<1)
 10 #define rs (pos<<1|1)
 11 #define int long long
 12 int n,m,a[maxn];
 13 struct Node{
 14     int m[4][4];
 15     void clear(){
 16         for(int i=0;i<4;i++){
 17             for(int j=0;j<4;j++){
 18                 m[i][j]=0;
 19             }
 20         }
 21     }
 22     void init(){
 23         for(int i=0;i<4;i++)m[i][i]=1;
 24     }
 25     void prt(){
 26         for(int i=1;i<=2;i++){
 27             for(int j=1;j<=2;j++)cout<<m[i][j];
 28         }
 29     }
 30     bool check(){
 31         if(!m[1][1])return 0;
 32         if(m[1][2])return 0;
 33         if(m[2][1])return 0;
 34         if(!m[2][2])return 0;
 35         return 1;
 36     }
 37     Node operator +(const Node &x)const{
 38         Node res;
 39         res.clear();
 40         for(int i=1;i<=2;i++){
 41             for(int j=1;j<=2;j++){
 42                 res.m[i][j]=(m[i][j]+x.m[i][j])%mod;
 43             }
 44         }
 45         return res;
 46     }
 47     Node operator *(const Node &x)const{
 48         Node res;
 49         res.clear();
 50         for(int i=1;i<=2;i++){
 51             for(int j=1;j<=2;j++){
 52                 for(int k=1;k<=2;k++)res.m[i][j]=(res.m[i][j]+m[i][k]*x.m[k][j])%mod;
 53             }
 54         }
 55         return res;
 56     }
 57 }val[maxn<<2];
 58 Node ad[maxn<<2];
 59 Node d,fir;
 60 Node qpow(Node a,int b){
 61     Node res;
 62     res.clear();
 63     res.init();
 64     while(b){
 65         if(b&1){
 66             res=res*a;
 67         }
 68         a=a*a;
 69         b>>=1;
 70     }
 71     return res;
 72 }
 73 void pushdown(int pos,int l,int r){
 74     if(ad[pos].check())return;
 75     val[ls]=val[ls]*ad[pos];
 76     val[rs]=val[rs]*ad[pos];
 77     ad[ls]=ad[ls]*ad[pos];
 78     ad[rs]=ad[rs]*ad[pos];
 79     ad[pos].clear();
 80     ad[pos].init();
 81 }
 82 void build(int pos,int l,int r){
 83     ad[pos].clear();
 84     val[pos].clear();
 85     ad[pos].init();
 86     if(l==r){
 87         val[pos]=fir*qpow(d,a[l]-1);
 88         return;
 89     }
 90     build(ls,l,mid);
 91     build(rs,mid+1,r);
 92     val[pos]=val[ls]+val[rs];
 93 }
 94 void add(int pos,int l,int r,int L,int R,Node z){
 95     if(L<=l&&R>=r){
 96         val[pos]=val[pos]*z;
 97         ad[pos]=ad[pos]*z;
 98         return;
 99     }
100     pushdown(pos,l,r);
101     if(L<=mid)add(ls,l,mid,L,R,z);
102     if(R>mid)add(rs,mid+1,r,L,R,z);
103     val[pos]=val[ls]+val[rs];
104 }
105 Node find(int pos,int l,int r,int L,int R){
106     if(L<=l&&R>=r)return val[pos];
107     pushdown(pos,l,r);
108     Node res;
109     res.clear();
110     if(L<=mid)res=res+find(ls,l,mid,L,R);
111     if(R>mid)res=res+find(rs,mid+1,r,L,R);
112     return res;
113 }
114 inline int read(){
115     int x=0,f=1;
116     char ch=getchar();
117     while(ch<'0'||ch>'9'){
118         if(ch=='-') f=-1;
119         ch=getchar();
120     }
121     while(ch>='0'&&ch<='9'){
122         x=(x<<1)+(x<<3)+(ch^48); 
123         ch=getchar();
124     }
125     return x*f;
126 }
127 signed main(){
128     d.clear();
129     fir.clear();
130     d.m[1][1]=d.m[1][2]=d.m[2][1]=1;
131     fir.m[1][1]=fir.m[1][2]=1;
132     n=read();
133     m=read();
134     for(int i=1;i<=n;i++)a[i]=read();
135     build(1,1,n);
136     while(m--){
137         int tp,l,r,z;
138         tp=read();
139         l=read();
140         r=read();
141         if(tp==1){
142             z=read();
143             add(1,1,n,l,r,qpow(d,z));
144         }
145         else{
146             cout<<find(1,1,n,l,r).m[1][2]%mod<<'\n';
147         }
148     }
149     return 0;
150 }

2025/7/21 統(tǒng)考【01】

教練說是S組難度（差點(diǎn)就信了
根本不是S組的難度啊，T1就是綠的

分?jǐn)?shù)140/400

T1      

(原題洛谷 P2034)

簡單題，直接二分dp，
然后就爆了（怎么沒有大樣例
早知道拍一下了

T2      

題意：

給定一顆 n 個(gè)節(jié)點(diǎn)的樹，這棵樹是以編號為鍵值的二叉樹，
可以任意旋轉(zhuǎn) (既可以轉(zhuǎn)化為任意一顆中序遍歷從 1 到 n 的樹)
小O喜歡從一個(gè)點(diǎn) s 出發(fā)往根節(jié)點(diǎn)走，每次他從點(diǎn) x 走到點(diǎn) y 時(shí)，會(huì)發(fā)生以下事件
1.如果 x 是 y 的左兒子，并且小O的左手上沒有數(shù)字，則他的左手會(huì)被寫上數(shù)字 a_y
2.如果 x 是 y 的右兒子，并且小O的右手上沒有數(shù)字，則他的右手會(huì)被寫上數(shù)字 a_y
在點(diǎn) s 出發(fā)時(shí)，左右手都沒有數(shù)字。如果到根節(jié)點(diǎn)時(shí)某只手沒有數(shù)字，則會(huì)被寫上 1
定義一個(gè)節(jié)點(diǎn)的分?jǐn)?shù)是從它開始往根走，結(jié)束時(shí)左右手的乘積。整棵樹的分?jǐn)?shù)是所有節(jié)點(diǎn)分?jǐn)?shù)的總和。
請找到一顆分?jǐn)?shù)最大的數(shù)，并輸出它的分?jǐn)?shù)。

(3≤n≤500，1≤a_i≤1e7)

沒思路，暴力+特殊性質(zhì)跑了
特殊性質(zhì)因?yàn)樯衩卦驅(qū)憭炝?/p>

T3      

題意：

給定一個(gè)長度為 n 的序列 a ，m 次詢問，每次詢問給定兩個(gè)數(shù) l,r ，
求出這個(gè)序列區(qū)間 [l,r] 里所有數(shù)字兩兩之間的最大公約數(shù)的最大值

(1≤n,m,a_i≤2e5)

思考區(qū)間合并，考慮建權(quán)值線段樹，然后從下往上合并區(qū)間，顯然是不可行的，
當(dāng)時(shí)腦抽了一直想怎么合并，最后交了個(gè)暴力

T4      

題意：

給定一顆起始只有編號為 1 的根節(jié)點(diǎn)的樹和 n 個(gè)操作
操作有兩種
1. Add x d 添加一個(gè)編號為 節(jié)點(diǎn)數(shù)+1 的節(jié)點(diǎn)，掛在編號為 x 的結(jié)點(diǎn)下方，兩點(diǎn)距離為 d
2.Query f t 表示求從編號 f 的節(jié)點(diǎn)，到編號為 t 的子樹中所有節(jié)點(diǎn)的路徑所有邊權(quán)異或值的最大值

(n≤2e5，0≤d≤2³⁰)

異或的重要性質(zhì)：異或兩遍等于沒有異或
每加入一個(gè)新點(diǎn)就記錄到根節(jié)點(diǎn)的異或路徑，查詢時(shí)兩個(gè)結(jié)點(diǎn)的到根節(jié)點(diǎn)的異或路線異或一下就是兩個(gè)結(jié)點(diǎn)的異或路徑
然后暴力枚舉子樹
期望70分，寫掛了

2025/7/22 ?？肌?5&06】

排名13/20
分?jǐn)?shù) 60/400

賽中時(shí)間記錄       

8:00 開始?？?
8:00-9:37 寫05?？?
9:37 換06?？?
9:37-10:14 寫T1
10:14-12:05 想T4
12:15 ?？冀Y(jié)束

本來是05?？?，結(jié)果05?？嫉腡1 T2 T3都有問題，
老師到教室之后開始改題，改完之后還是有問題
一氣之下直接把05?？缄P(guān)了
讓我們考06?？?，難繃

T1       

題意：

給定一張 n 個(gè)節(jié)點(diǎn) m 條邊的有向圖，共有 p 個(gè) 邊集合，
用 u,v,c,w 表示一條邊的起點(diǎn) u ，終點(diǎn) v ，權(quán)值 c ，屬于集合 w
Q 次詢問，每次詢問給定 s,t,k ，求出從 s 到 t 走過的邊不超過 k 個(gè)不同集合的最短路徑長度

(n≤100，p≤6，m≤p*n*(n-1)，c≤1e4，q≤1e5)

一眼 Floyd 啊，zd[i][j][k] 為只走 k 公司 i 到 j 的最短路徑，F(xiàn)loyd 處理出來，設(shè) dp[i][j][w] 為從i走到j(luò)換公司次數(shù)不超過 w 次（埋下伏筆）
直接枚舉斷點(diǎn)轉(zhuǎn)移即可

 1  for(int w=1;w<=n;w++){
 2      for(int k=1;k<=n;k++){
 3       for(int i=1;i<=n;i++){
 4            for(int j=1;j<=n;j++){
 5                zd[i][j][w]=min(zd[i][j][w],zd[i][k][w]+zd[k][j][w]);
 6            }
 7          }
 8      }
 9  }
10  for(int i=1;i<=n;i++){
11      for(int j=1;j<=n;j++){
12         for(int k=1;k<=n;k++){
13              dp[i][j][0]=min(dp[i][j][0],zd[i][j][k]);
14          }
15      }
16  }
17  for(int w=1;w<=n;w++){
18      for(int k=1;k<=n;k++){
19          for(int i=1;i<=n;i++){
20            for(int j=1;j<=n;j++){
21                dp[i][j][w]=min(dp[i][j][w],dp[i][k][w-1]+dp[k][j][0]);
22             }
23         }
24     }
25 }

但是題目是不超過 w 個(gè)不同集合，沒看到，我寫的是轉(zhuǎn)換集合次數(shù)不超過 w 次，寄（ 

T2       

題目描述：

有一堆牌共 2n 張，自上而下第 i 張上的數(shù)字為 ai。
?初始時(shí)，最上面 n 張牌已解鎖，下面 n 張牌未解鎖。
接下來做 2n 輪操作：
首先，小 W 會(huì)在牌堆中所有已經(jīng)解鎖的牌中等概率隨機(jī)選擇一張，加入自己的手牌。他的得分會(huì)加上現(xiàn)在手牌中所有數(shù)字之和。
然后，如果仍有未解鎖的卡牌，則解鎖最上面那一張。
請你求出游戲結(jié)束之后，小W得分的期望對 998244353 取模的結(jié)果。

(2≤n≤2e5，1≤a_i≤998244353)

看了一眼，感覺不會(huì)，去看T3

T3       

題目描述：

某一天小 C 所在的公司發(fā)生了流感。公司里總共有 n 個(gè)人，編號為1,…,n。
在這天開始時(shí)，恰好有一個(gè)人感染了流感，每個(gè)人感染的概率都是 1/n。
在這一整天中，小 C 公司的人按時(shí)間順序發(fā)生了
m 次接觸，第 i 次接觸發(fā)生在編號為 x_i 和 y_i 的人之間。
如果它們其中一個(gè)人感染了流感，而另一個(gè)人沒有，那么沒有感染流感的那個(gè)人會(huì)有恰好 1/2 的概率感染流感。
在這天結(jié)束時(shí)，小 C 得知編號為 k 的人感染了流感。
現(xiàn)在他想要知道，在已知條件下，每個(gè)人感染流感的概率分別是多少？你需要用形如 a/b 的最簡分?jǐn)?shù)表示答案。

(2≤n≤15，1≤k≤n，1≤m≤50)

看了一會(huì)，感覺T4更有前途，去看T4

T4       

題意：

給定一個(gè)長度為 n 的序列 a 和一個(gè)數(shù) k，
把序列 a 劃分成若干區(qū)間使得每個(gè)區(qū)間的長度不超過 k 且所有子區(qū)間對應(yīng)序列的 mex 和最大
即找到 0=p₀<p₁<p₂...<p_m = n 且p_i<=p_i-1+k，使得

的值最大，輸出這個(gè)值

(1≤k≤n≤2e5，0≤a_i≤n)

看完題目后先想1e3的做法，1e3很明顯是O（n2）的做法，思考區(qū)間dp
枚舉左右端點(diǎn)，再枚舉斷點(diǎn)，做法是O（n3）
復(fù)雜度不對，開始轉(zhuǎn)換思路，看了100%的數(shù)據(jù)，應(yīng)該帶個(gè)log或者直接線性，
手摸了半天沒真做法，最后交了個(gè)暴力

2025/7/23 休息日【02】

整天都在玩三國殺...

2025/7/24 上課【圖論建圖】

知識點(diǎn)        

1.差分約束
2.Boruvka算法
3.同余最短路
4.一些構(gòu)造

A題         

題意：

給定一個(gè)圖和 s ,t ，求 點(diǎn)s 到 點(diǎn)t 的最短路，并輸出路徑（按字典序輸出最小的一條）
如果存在負(fù)權(quán)回路輸出You show me the wrong map!

為什么會(huì)有模板題啊，
把每條邊按指向的結(jié)點(diǎn)的字典序排序，用一個(gè)鏈表維護(hù)路徑，跑一遍spfa即可

C題         

題意：

給定一張圖，可以使一條邊邊權(quán)減半，求 s 到 t 的最短路徑

怎么又是板子題，建兩層的圖跑一遍最短路即可

2025/7/25 ?？肌?7】

爆爆爆

排名 8/20
分?jǐn)?shù)170/400

賽中時(shí)間記錄         

8:00 開始?？?br>8:00-9:02 寫T1
9:02-9:50 寫T1
9:50-10:27 寫T4
12:00 ?？冀Y(jié)束

T1          

題意：

給定兩個(gè)整數(shù) N,T 和 N 個(gè) S_i、E_i，
一天有 T 個(gè)時(shí)段，共有 N 個(gè)人，第 i 個(gè)人可以在 [S_i,E_i] 打掃衛(wèi)生，
為至少安排幾個(gè)人可以覆蓋全部的 [1,T] 時(shí)段打掃衛(wèi)生。
無解則輸出 -1

(1≤N≤25000，1≤T≤1e6，1≤S_i≤E_i≤T)

按S排序，遍歷每一個(gè)點(diǎn)，做一些判斷

 1 if(i==1){
 2      if(a[i].s>1){
 3          cout<<-1;
 4          return 0;
 5      }
 6      else{
 7          q[r]=a[i].e;
 8      }
 9  }
10 else{
11      if(q[r]>=a[i].e)continue;
12      if(q[r]+1<a[i].s){
13          cout<<-1;
14          return 0;
15      }
16      while(l<r&&q[r-1]+1>=a[i].s)r--;
17      q[++r]=a[i].e;
18  }

就可以AC

T2          

題目描述：

(n≤3e5)

樸素的dp是O(n2)的，寫完之后感覺像斜率優(yōu)化，推了一會(huì)式子沒推出來，
又想了一下，發(fā)現(xiàn)可以用線段樹，開始寫，一直調(diào)不出來，寄，去看T4

T3          

題目描述：

(m≤n≤200，T≤10)

好困，懶得看了

T4          

題目描述：

保登心愛擅長算數(shù)。
某天，心愛拿到了一個(gè)長度為 n 的序列 a_i ，她很快就求出了這個(gè)序列的每個(gè)子區(qū)間的平均數(shù)。
但是，子區(qū)間一共有 C²_n+1 個(gè)。
為了證明你也能求出所有平均數(shù)，你需要把所有 C²_n+1 個(gè)平均數(shù)從小到大排序后，
把第 k 個(gè)數(shù)告訴心愛。

(1≤n,k≤5e5，k≤C²_n+1，1≤a_i≤1e7)

O(n2)的區(qū)間dp，能拿20，又思考了一會(huì)沒什么思路，
昨天晚上沒睡好，后面基本在發(fā)呆

2025/7/26 上課【DP專題】

知識點(diǎn)           

1.斜率優(yōu)化
2.單調(diào)隊(duì)列/單調(diào)棧優(yōu)化
3.DDP（帶修D(zhuǎn)P）

課內(nèi)的作業(yè)太難了，只能自己先找點(diǎn)基礎(chǔ)的做（

T1(不是xyd的作業(yè))

(洛谷P3195)

樸素dp是O(n2)的，把方程化成y=kx+b的一次函數(shù)的形式，觀察在圖上的性質(zhì)，
維護(hù)一個(gè)下凸殼即可，復(fù)雜度O(n)

T2(不是xyd的作業(yè))

(洛谷P6563)

O(n3) 的區(qū)間DP，轉(zhuǎn)移方程 dp[l][r]=min{max{dp[l][k],dp[k+1][r]}+a[k]}
把 max 分類討論，隨著 k 增大, dp[l][k] 遞增，dp[k+1][r] 遞減，找到 dp[l][p+1]>dp[p][r]dp[p][r]>=dp[l]][p-1] 的分界點(diǎn) p
分別考慮 max 的兩種情況

2025/7/27 ?？肌?8】

emm,還是爆

排名 5/20
分?jǐn)?shù)125/400

賽中時(shí)間記錄            

8:30 開始模考
8:30-10:37 寫T1
10:37-11:24 寫T1
11:24-12:00 寫T1和T3的暴力
12:00 ?？冀Y(jié)束

T1            

題目描述：

(1≤n≤5e4，1≤m≤1e5，p_i∈[75,100]，1≤u_i,v_i≤n)

第一眼感覺像最大生成樹之類的問題，可以給每個(gè)點(diǎn)賦一個(gè)值 g ，表示一號點(diǎn)到這個(gè)點(diǎn)不被發(fā)現(xiàn)的最大概率，
全圖能 聯(lián)通當(dāng)前還沒聯(lián)通的點(diǎn) 的邊的最大值記為 mx ，g值最大的點(diǎn)的最大邊的權(quán)值記為 mxe ，則 mx>=mxe，
如果 mx==mxe ，那么加入 mxe 這條邊，否則加入 mx 這條邊，更新連接后的 g 值
建完圖之后跑一遍搜索計(jì)算答案
手模了一些數(shù)據(jù)，沒問題，寫寫寫
寫了1快個(gè)小時(shí)，將近兩百行，寫成一坨了，4個(gè)自定義數(shù)據(jù)結(jié)構(gòu)，7個(gè)庫,變量數(shù)不清了，變量名還亂標(biāo)的，樣例沒過，開始調(diào)代碼，
調(diào)了一個(gè)多小時(shí)放棄了，已經(jīng)忘記自己在寫啥了，比賽快結(jié)束的時(shí)間幾分鐘寫了個(gè)暴力，最后3分鐘的時(shí)候發(fā)現(xiàn)暴力是錯(cuò)的
只會(huì)輸出-1，時(shí)間不夠不想調(diào)，結(jié)果拿了20（不可以，總司令
跟室友說我寫 T1 的過程給他們笑成大奮了

T2            

題目描述：

(n,m≤200)

暴力 O(n^4) 用二分優(yōu)化成 O(n3 log n) ，加了一點(diǎn)優(yōu)化之后感覺能過 n,m<=500,
其實(shí)不是 O(n3 log n) 這個(gè)復(fù)雜度，加了一些奇怪的剪枝，復(fù)雜度玄學(xué)，應(yīng)該小了很多，常數(shù)也小
直接過了19個(gè)點(diǎn)，沒開 long long WA了一個(gè)，變成90了

T3            

題目描述：

(1≤T≤10，0≤S≤1e18，1≤M≤1e18，1≤N≤200，0≤a_i≤1e5)

沒時(shí)間了，暴力

T4            

題目描述：

(k≤n,pos≤1e9，q≤2e5)

第一遍題目沒看懂，只剩十幾分鐘了，不如去寫 T1 的暴力

2025/7/28 統(tǒng)考【02】

排名9/20
沒時(shí)間，so沒寫模考總結(jié)

2025/7/29 模考【09】

排名8/20
也沒時(shí)間，沒寫?？伎偨Y(jié)

2025/7/30 休息日【03】

今天普通班結(jié)營，不能玩了（
只能呆在班里自習(xí)

2025/7/31 上課【分治思想】

知識點(diǎn)             

1.分治的基本思想
2.CDQ分治

CDQ分治

解決形如求出xxx性質(zhì)的點(diǎn)對 (i,j) 的數(shù)量
參考o(jì)iwiki
可以把點(diǎn)對分成三類

1.i,j<=mid
2.i<=mid,j>mid
3.mid<i,j

可以往下遞歸區(qū)間把一和三類轉(zhuǎn)化成二類，然后用人類智慧求解二類點(diǎn)

B題             

(luogu 7115)

先考慮 n=2 的情況，也就是只有0和1，充分發(fā)揮人類智慧想出 n=2 的解法后考慮擴(kuò)大問題規(guī)模，
對于值為 [l,r] 內(nèi)的球，設(shè)一個(gè) mid=l+r>>1
值小于等于 mid 的為 0 ，大于 mid 的為 1，然后按 n=2 的方法求出所有值在 [l,r] 的答案，
遞歸求解 [l,mid] 和 [mid+1,r] 的答案

2025/8/1 上課【樹上專題】

知識點(diǎn)              

1.樹剖求 LCA
2.重鏈剖分+線段樹（樹剖完全體）
3.長鏈剖分 O(n log n) - O(1) 求 k 級祖先

B題              

(洛谷 P1967)

kruskal重構(gòu)樹求最大生成樹，對于詢問的每對點(diǎn)求其LCA即可

F題              

 (洛谷 P2486)

樹剖板子題，重鏈剖分+線段樹，線段樹維護(hù)區(qū)間左端點(diǎn)和右端點(diǎn)的顏色，
如果左子區(qū)間的右端點(diǎn)顏色和右子區(qū)間的左端點(diǎn)顏色相同，那么顏色段為左右子區(qū)間顏色段之和減一
其他的完全是樹剖板子

H題              

(洛谷 P2680)

二分答案，然后樹上差分維護(hù)路徑和大于mid的路徑經(jīng)過的邊，枚舉每一條邊，
如果大于mid的路徑都經(jīng)過這條邊且最大的路徑減去這條邊的邊權(quán)小于等于mid，那么返回true
否則如果所有邊都沒法滿足條件，則為flase
二分的左端點(diǎn) l 要初始化成0（

2025/8/2 統(tǒng)考【03】

排名13/20
沒時(shí)間寫總結(jié)

2025/8/3 統(tǒng)考【04】

排名 2/20
分?jǐn)?shù)150/400

T1               

題目描述：

小信獲得了一種魔法積木：
這是一種方格圖，要求方格連續(xù)，且左邊界對齊，下一行不能比上一行長。
現(xiàn)在我們可以往里面填1?n的數(shù)字，要求每個(gè)格子中的數(shù)字要大于等于左邊格子，嚴(yán)格大于上方格子。
現(xiàn)在給定每一行的格子數(shù)量，求可能滿足條件的圖形數(shù)量。
(k≤7)

開局看完題目直接寫，決定記憶化，先寫了一個(gè)暴搜，測了下樣例，發(fā)現(xiàn)不對勁
又測了
7 7 6 5 4 3 2 1
7
的最極端數(shù)據(jù)，發(fā)現(xiàn)只有 2e7 的復(fù)雜度，懷疑暴力寫錯(cuò)了，找了幾分鐘沒發(fā)現(xiàn)有什么錯(cuò)的，認(rèn)定這是水題

T2               

題意：

給定 n 和一個(gè)數(shù)列 a ，每種數(shù)字可以變成 “A” 或 “B” 或 “C”，且每個(gè)數(shù)字都要變。
問有多少種變法使得產(chǎn)生的字符串的所有子序列至少包含一個(gè)“ABC”，答案對1e8+7取模。

(n≤3000)

想T2想了挺久，想%40的數(shù)據(jù)點(diǎn)，一堆假做法DP，最后只交了暴力

T3               

題目描述：

(n≤1e6)

測試點(diǎn)編號 1~3 ，n<=5? 打表！
只跑出來 n=4 的，n=5 的跑到考試結(jié)束都沒跑出來（
賽后 mwl大佬 告訴我直接暴力 n=5 大概是 10^43

T4               

(n,q≤2e5，a_i≤1e6)

直接暴力了

2025/8/3 統(tǒng)考【05】

排名5/20

2025/8/3 娛樂賽【最后一天！】

題目挺好玩的，隨便寫了
反正是娛樂賽
第一次拿倒一有一種爽感

2025/8/4 結(jié)營

早上大家在班級念結(jié)營總結(jié)，
下午結(jié)營儀式，還有節(jié)目，挺有意思的，
結(jié)營儀式結(jié)束就可以走了

我班里念的結(jié)營總結(jié)是deepseek寫的，
這里重新寫一份

結(jié)營總結(jié)

以前從來沒接觸過這種訓(xùn)練方式，每天都要寫一篇學(xué)習(xí)總結(jié)，
模考都要補(bǔ)完題，寫模考總結(jié)，
剛開始感覺挺累的，但是堅(jiān)持下來就沒事了，
和自己學(xué)校的訓(xùn)練相比，嚴(yán)格了很多，但成長速度也快得多，
我提高組的算法原來學(xué)的很不扎實(shí)，都是自己亂學(xué)的，
感覺自己不應(yīng)該在這個(gè)班，第一次?？伎剂说挂灰矝]有很意外，
記不清當(dāng)時(shí)怎么想的了，居然堅(jiān)持下來了。
我覺得大部分是因?yàn)橥瑢W(xué)都很友善，
大家會(huì)互相解答問題，互相討論題目，氛圍很好，
他們的觀念是別人有疑惑時(shí)幫忙解答也會(huì)發(fā)現(xiàn)自己哪里掌握不扎實(shí)，
對自己也有很大幫助，我現(xiàn)在也認(rèn)為如此，營地期間也有幫別的同學(xué)解答上課的知識點(diǎn)，
會(huì)發(fā)現(xiàn)以為已經(jīng)完全掌握的算法其實(shí)也有一些地方掌握的不是很好，然后再繼續(xù)針對性地學(xué)習(xí)。
大家總是稱呼別人“巨佬”，說自己是“蒟蒻”，甚至說自己是“傻*”，都很謙虛，
?？伎疾盍耍牭阶疃嗟脑捠恰皼]事，你只是失誤了，你是個(gè)巨佬，我是蒟蒻”之類的。
在這樣的環(huán)境里面進(jìn)步神速，這非?？少F，從來沒有感受過。
我可以理解為什么到外省訓(xùn)練是福建省的選手水平上升的原因了。
(結(jié)營總結(jié)到這里結(jié)束了)

關(guān)于現(xiàn)在我對信奧的看法

它不只是升學(xué)的工具，對現(xiàn)在的我來說，學(xué)信奧不為升學(xué)，而是為了證明它不比其他競賽學(xué)科差，
它有自己獨(dú)特的魅力，絕不是某些人口中在機(jī)房打游戲。信奧路上能獲得很多樂趣、友誼，它讓我感受到屬于學(xué)習(xí)的快樂，我會(huì)堅(jiān)持下去。