SMU Winter 2025 div1 3rd

文章目录

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/5
2.09 CFdiv4（2h）5/6
2.10 CF训练赛 （2h）3/4
2.11 牛客训练营 （5h） 5/6
2.11 CFdiv2 （2h） 1/
2.12 CF训练赛 （2h） 3/4
2.13 PTA （3h） 228/232
2.14 CF训练赛（2h）3/3
2.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 longint 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 longconst 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 longconst 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,ajif(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,bjif(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,ajif(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 longconst 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;
}