AC修炼计划（AtCoder Beginner Contest 329）

传送门：Ｓｋｙ Inc, Programming Contest 2023（AtCoder Beginner Contest 329） - AtCoder

A，B，C，D

这四道题比较简单，就不多叙述。

E - Stamp

这题是一道比较经典的涂色问题。

我们可以知道，如果存在覆盖相交的话，要么前面盖住后面，要么后面盖住前面，则他们的首尾一定会留下痕迹。所以我们正反遍历，可以得到答案。

代码如下：

#pragma GCC optimize(3)  //O2优化开启
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int N=998244353;
const int MX=0x3f3f3f3f3f3f3f3f; 
int n,m;
string s,t;
bool pan(string x){for(int i=0;i<m;i++){if(x[i]=='#'||x[i]==t[i])continue;else return 0;}return 1;
}
void icealsoheat(){cin>>n>>m;cin>>s>>t;for(int i=m-1;i<n;i++){if(pan(s.substr(i-m+1,m))){for(int j=i-m+1;j<=i;j++){s[j]='#';}}}for(int i=n-1;i>=m-1;i--){if(pan(s.substr(i-m+1,m))){for(int j=i-m+1;j<=i;j++){s[j]='#';}}}for(int i=0;i<n;i++){if(s[i]!='#'){puts("No");return;}}puts("Yes");
}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _yq;_yq=1;// cin>>_yq;while(_yq--){icealsoheat();}
}

F - Colored Ball

这道题的时间复杂度比较巧妙，我们每次都让最小的去合并最大的，最后的时间复杂度为O(n)。确实让我开拓了眼界。是启发式合并的思想。

代码如下：

#pragma GCC optimize(3)  //O2优化开启
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int N=998244353;
const int MX=0x3f3f3f3f3f3f3f3f; 
int n,q;
int c[1000005];
set<int>s[200005];
int id[200005];
void icealsoheat(){cin>>n>>q;for(int i=1;i<=n;i++){cin>>c[i];id[i]=i;s[i].insert(c[i]);}while(q--){int a,b;cin>>a>>b;int x=id[a];if(s[id[a]].size()>s[id[b]].size()){swap(id[a],id[b]);}for(auto i:s[id[a]]){s[id[b]].insert(i);}s[id[a]].clear();cout<<s[id[b]].size()<<"\n";}
}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _yq;_yq=1;// cin>>_yq;while(_yq--){icealsoheat();}
}