SMUWinter2025div13rd

文章目录 The Third Week一、前言二、算法1.深度优先搜索<1>（Li Hua and Tree）<2>（2025寒假训练4 L3-2） 2.DP<1>（牛客训练营6 B） 3. 构造<1>（Skibidus and Rizz）<2>（Maximum Diameter Graph） 4.并查集<1>（2025暑假训练5 L2-2） 5.广度优先搜索<1>（公平对局） 三、总结

---

The Third Week

人生到处知何似，应似飞鸿踏雪泥。 ————苏轼

一、前言 2.09 牛客周赛 （2h） 4/52.09 CFdiv4（2h）5/62.10 CF训练赛 （2h）3/42.11 牛客训练营 （5h） 5/62.11 CFdiv2 （2h） 1/2.12 CF训练赛 （2h） 3/42.13 PTA （3h） 228/2322.14 CF训练赛（2h）3/32.15 PTA（3h）199/206

rating：

codeforces： 1339 —— 1294牛客：1543 —— 1532

---

二、算法 1.深度优先搜索 <1>（Li Hua and Tree）

题解： 李华有一颗有n个顶点和n-1条边的树，树的根是顶点1，每个顶点有重要性，子树的大小指其中顶点的数量，子树的重要性是其中顶点的重要性之和。非叶子顶点的重儿子是指拥有最大子树大小的儿子。如果存在多个，则重儿子是索引最小的那个。 用dfs搜索最远的叶子节点，对每一个叶子节点计算它的子树的大小和重要性即可，注意此处的dfs必须用俩个变量进行遍历。 代码：

#include<bits/stdc++.h> using namespace std; #define int long long #define PII pair<int,int> const int N = 1e6+10; vector<int>c[N]; int fa[N],so[N]; int re[N]; //子树大小 int le[N];//重要性大小 set<PII>e[N]; int n,m; int a[N]; void dfs(int x,int f) { // fa[x] = f; // if(c[x].size() == 1) { // re[x] = 1; // le[x] = a[x]; // return ; // } // for (auto ma:c[x]) { // if(f == ma) continue; // dfs(ma,x); // re[x] += re[ma]; // le[x] += le[ma]; // e[x].insert({0-re[ma],ma}); // }le[x] += a[x]; // re[x] += 1; le[x] = a[x]; re[x] = 1; fa[x] = f; for (auto ma: c[x]) { if(f == ma) continue; dfs(ma,x); re[x] += re[ma]; le[x] += le[ma]; e[x].insert({-re[ma],ma}); } } bool cmp(int p,int q) { if(re[p] == re[q]) return p < q; return re[p] > re[q]; } void solve() { cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i < n; i++) { int u,v; cin >> u >> v; c[u].push_back(v); c[v].push_back(u); }dfs(1,-1); // for (int i = 1; i <= n; i++) { // cout << le[i] << ' ' << re[i] << endl; // } // for (int i = 1; i <= n; i++) cout << fa[i] << ' '; // for (int i = 1; i <= n; i++) { // sort(c[i].begin(),c[i].end(),cmp); // c[i].erase(c[i].begin()); // } while(m--) { int x; cin >> x; int y; cin >> y; if(x == 1) { // cout << le[y] << endl; cout << le[y] << endl; // for (int i = 1; i <= n; i++) { // cout << le[i] << ' '; // }cout << endl; } else { if(e[y].empty()) continue; int zs = e[y].begin()->second; e[fa[y]].erase({-re[y],y}); e[y].erase({-re[zs],zs}); // if(c[y].size() == 0) continue; // sort(c[y].begin(),c[y].end(),cmp); // c[y].erase(c[y].begin()); // int ly = re[y],lx = le[y]; re[y] -= re[zs]; le[y] -= le[zs]; re[zs] += re[y]; le[zs] += le[y]; // c[zs].push_back(y); // sort(c[zs].begin(),c[zs].end(),cmp); e[zs].insert({-re[y],y}); e[fa[y]].insert({-re[zs],zs}); fa[zs] = fa[y]; fa[y] = zs; } } // return ; } signed main() { int t = 1; // cin >> t; while(t--) solve(); } <2>（2025寒假训练4 L3-2）

题解： 给出一行n个折角点的高度，然后给出m张碎纸，每张的第一个数字k表示碎纸的折角点，其后k个数字代表折角点的高度。给出m张碎纸的正确拼接顺序。 这题的数据量比较小，dfs当前位置有几个能放的碎纸，最后输出答案即可。 代码：

#include<bits/stdc++.h> using namespace std; #define int long long int n,m; vector<int> vs; vector<int> vt; vector<int> v[105]; vector<int> ans; bool note[105]; void dfs(int now){ if(ans.size() == m){ vt = ans; return; } int i,j; for(i = 1;i <= m;++i){ if(!note[i]){ for(j = 0;j < v[i].size();++j){ if(v[i][j] != vs[now + j]) break; } if(j == v[i].size()){ ans.push_back(i); note[i] = true; dfs(now + j - 1); note[i] = false; ans.pop_back(); } } } } signed main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n; int p,q; for(int i = 1;i <= n;++i){ cin>>p; vs.push_back(p); } cin>>m; for(int i = 1;i <= m;++i){ cin>>p; for(int j = 1;j <= p;++j){ cin>>q; v[i].push_back(q); } } dfs(0); cout<<vt[0]; for(int i = 1;i < vt.size();++i) cout<<" "<<vt[i]; return 0; }

给出一段26分的代码，用的是字符串匹配的思想，比较简洁，错误情况是俩个字符串都可以匹配到同一位置，无法确定是谁先匹配。如下。

#include<bits/stdc++.h> using namespace std; #define int long long const int N = 1e5+10; vector<int>a[110]; int h[N]; int n,m; vector<pair<int,int>>mp; signed main() { cin >> n; string s; cin >> s; getline(cin,s); // cout << s << endl; cin >> m; string y; getline(cin,y); for (int i = 1; i <= m; i++) { int x; cin >> x; getline(cin,y); int wz = s.find(y); mp.push_back({wz,i}); }sort(mp.begin(),mp.end()); int p = 0; for (auto x: mp) { p++; if(p == m) cout << x.second; else cout << x.second << ' '; } } 2.DP <1>（牛客训练营6 B）

题解：

代码：

#include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 10; void solve() { int n,c1,c2;cin>>n>>c1>>c2; vector<int> a(n+10),b(n+10); for(int i=1;i<=n;i++){ cin>>a[i]>>b[i]; } vector<vector<int>> dp(n+10,vector<int>(2,1e18)); dp[0][0]=0; int ans=1e18; for(int i=1;i<=n;i++){ for(int j=0;j<=i-1;j++){ //ai,bi接到aj,bj if(a[i]>=a[j]&&b[i]>=b[j]){ dp[i][0]=min(dp[i][0],dp[j][0]+c1*(i-j-1)); } //ai,bi接到bj,aj if(a[i]>=b[j]&&b[i]>=a[j]){ dp[i][0]=min(dp[i][0],dp[j][1]+c1*(i-j-1)); } //bi,ai接到aj,bj if(b[i]>=a[j]&&a[i]>=b[j]){ dp[i][1]=min(dp[i][1],dp[j][0]+c2+c1*(i-j-1)); } //bi,ai接到bj,aj if(b[i]>=b[j]&&a[i]>=a[j]){ dp[i][1]=min(dp[i][1],dp[j][1]+c2+c1*(i-j-1)); } } ans=min(ans,min(dp[i][0],dp[i][1])+c1*(n-i)); } cout<<ans<<endl; } signed main() { std::ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int t = 1;cin >> t; while (t--) solve(); return 0; } 3. 构造 <1>（Skibidus and Rizz）

题解： 给定一个二进制字符串t，x表示0的个数，y表示1的个数，平衡值定义为01个数差值，给定n，m，k，要求构造包含n个0和m个1的二进字符串s使得所有子字符串中的最大平衡值恰好为k。如果不可能，输出-1. 假设n大于m，k n都输出-1，输出k个0，然后交替输出01，输出剩余的1。 代码：

#include <bits/stdc++.h> using namespace std; int main(){ int t; cin >> t; while(t--){ int n, m, k; cin >> n >> m >> k; if(max(n, m) - min(n, m) > k || k > max(n, m)){ cout << "-1" << endl; continue; } else{ pair<int, int> use1 = {n, 0}, use2 = {m, 1}; if(m > n) swap(use1, use2); for(int i = 0; i < k; i++){ cout << use1.second; use1.first--; } while(use2.first > 0){ cout << use2.second; use2.first--; swap(use1, use2); } while(use1.first > 0){ cout << use1.second; use1.first--; } cout << "\n"; } } } <2>（Maximum Diameter Graph）

题解：

代码：

4.并查集 <1>（2025暑假训练5 L2-2）

冰岛人 20/25

题解： 用map实现题目要求，要注意calc部分判断五代以内公共祖先，必须找到公共祖先或者找到顶判断，各找五个是行不通的，不应该错。 代码：

#include<bits/stdc++.h> using namespace std; #define int long long const int N = 1e5+10; int n,m; map<string,string>fa; map<string,int>ma; bool calc(string x,string y) { int i = 1; for (string X = x; X != "ABCD"; X = fa[X],i++) { int j = 1; for (string Y = y; Y != "ABCD"; Y = fa[Y],j++) { if(i>=5&&j>=5) return 1; if(X==Y&&(i<5||j<5)) return 0; } }return 1; } void solve() { cin >> n;int p = 0; for (int i = 1; i <= n; i++) { string s1,s2; cin >> s1 >> s2; int q = s2.length()-1; if(s2[q] == 'n') { string ls; for (int j = 0; j <= q-4; j++) { ls += s2[j]; }fa[s1] = ls; ma[s1] = 1; }else if(s2[q] == 'r') { string ls; for (int j = 0; j <= q-7; j++) { ls += s2[j]; }fa[s1] = ls; ma[s1] = 2; } else { fa[s1] = "ABCD"; p++; if(s2[q] == 'm') ma[s1] = 1; else ma[s1] = 2; } }cin >> m; while(m--) { string m1,x1,m2,x2; cin >> m1 >> x1 >> m2 >> x2; if(fa[m1] == "" || fa[m2] == "") { cout << "NA" << endl; continue; } if(fa[m1] != "ABCD" && fa[m1] != x1) { cout << "NA" << endl; continue; } if(fa[m2] != "ABCD" && fa[m2] != x2) { cout << "NA" << endl; continue; } if(ma[m1] == ma[m2]) { cout << "Whatever" << endl; }else { if(calc(m1,m2)) cout << "Yes" << endl; else cout << "No" << endl; } } //cout << "PTA shi3 wo3 jing1 shen2 huan4 fa1 !" ; } signed main() { int t = 1; //cin >> t; while(t--) solve(); } 5.广度优先搜索 <1>（公平对局）

题解： 查找只差一颗就形成最大白色连通块里最大的连通块。考察bfs的运用

代码：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll N=1e3+1,mod=1e9+7,INF=0x3f3f3f3f; ll n,ans; ll vis[N][N],value[N][N]; pair<ll,ll> dire[]={{0,1},{0,-1},{1,0},{-1,0}}; vector<string> mp(N); bool limit(ll x,ll y){ return (x>0&&x<=n&&y>0&&y<=n); } inline array<ll,3> bfs(vector<string> v,ll x,ll y){ queue<pair<ll,ll>> q; vis[x][y]=1; q.push({x,y}); ll cnt=0; set<pair<ll,ll>> blk; while(q.size()){ auto [tx,ty]=q.front(); q.pop(); cnt++; for(auto d:dire){ ll xx=tx+d.first,yy=ty+d.second; if(limit(xx,yy)){ if(mp[xx][yy]=='*'&&!vis[xx][yy]) vis[xx][yy]=1, q.push({xx,yy}); else if(mp[xx][yy]=='.') blk.insert({xx,yy}); } } } if(blk.size()==1){ pair<ll,ll> p=*blk.begin(); return {p.first,p.second,cnt}; } else return {-1,-1,-1}; } signed main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin>>n; for(ll i=1;i<=n;i++) cin>>mp[i], mp[i]=" "+mp[i]; for(ll i=1;i<=n;i++) for(ll j=1;j<=n;j++) if(!vis[i][j]&&mp[i][j]=='*'){ auto [x,y,z]=bfs(mp,i,j); if(x<0)continue; value[x][y]+=z; ans=max(ans,value[x][y]); } cout<<ans<<endl; }

---

三、总结

状态还可以，会做的基本都可以做出来，做题速度不够快，补题不太及时。 比较偏算法的题目都比较生疏了，倒是思维题简单题目前都做得不错，PTA现阶段做得也还可以，加油。 CF和牛客都掉分了，虽然不多但是也不应该，有俩场打的不是很好。补题补题