AC修炼计划（AtCoder Regular Contest 165）

传送门：AtCoder Regular Contest 165 - AtCoder

本次习题参考了樱雪猫大佬的题解，大佬的题解传送门如下：Atcoder Regular Contest 165 - 樱雪喵 - 博客园 (cnblogs.com)

A - Sum equals LCM

第一题不算特别难

B - Sliding Window Sort 2

对于这道题而言，我们不难看出，如果想让该字符串尽可能的大，那最好的方式就是不改变，如果改变了，尽可能的向右边改变，同时尽可能的少改变。我们不如从前向后进行枚举，从而筛选出是第一个交换尽可能向右的下标，并记录。代码如下：

#include<bits/stdc++.h>
using namespace std;
// #define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int N=998244353;
int n,k;
int b[5000005];
void icealsoheat(){cin>>n>>k;for(int i=1;i<=n;i++){cin>>b[i];}set<int>q;for(int i=1;i<=k;i++)q.insert(b[i]);vector<int>c(n+5,0);int id=0;int mx=0;for(int i=1;i<=n-k+1;i++){if(i-1)q.erase(b[i-1]),q.insert(b[i+k-1]);if(c[i])continue;int l=0;auto it=q.begin();for(int j=i;j<i+k;j++){if((*it)!=b[j]){l=j;break;}it++;}if(!l){id=0;break;}for(int j=i;j<=l;j++)c[j]=1;if(l>mx){mx=l;id=i;}}if(id)sort(b+id,b+id+k);for(int i=1;i<=n;i++)cout<<b[i]<<" ";}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _=1;// cin>>_;while(_--){icealsoheat();}}

C - Social Distance on Graph

首先，没有重边，没有环，简单的无向图。最开始我想到了最小生成树，但是没搞出来，后来看佬的码，惊讶的发现确实是最小生成树，只是我想的还是太浅了，不够深入。

既然我们想让最小值最大，那么我们尽可能的让最小的边通过涂色和其他边和在一起。如果是不同的颜色的两个点，则这条边不存在，无法相连。所以我们可以用最小生成树来将最小的顶点优先考虑。并且将其进行染色，将这两个点儿染成不同的颜色。同时并继续向后慢慢更新，这里可以通过并查集来进行实现。在最后，我们比较出最小值即可。

代码如下：

#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,k,m;
int c[5000005];
int pre[1000005];
struct we{int l,r,w;bool operator <(const we &k)const{return w<k.w;}
}hh[1000005];
int find(int x){if(pre[x]==x)return x;return pre[x]=find(pre[x]);
}
bool cmp(PII ax,PII bx){return ax.second<bx.second;
}
void icealsoheat(){cin>>n>>m;for(int i=1;i<=n;i++){pre[i]=i;c[i]=-1;}vector<vector<PII>>ve(n+5);for(int i=1;i<=m;i++){int l,r,w;cin>>l>>r>>w;hh[i].l=l;hh[i].r=r;hh[i].w=w;}sort(hh+1,hh+1+m);for(int i=1;i<=m;i++){int xx=find(hh[i].l);int yy=find(hh[i].r);if(xx==yy){continue;}pre[xx]=yy;ve[hh[i].l].push_back({hh[i].r,hh[i].w});ve[hh[i].r].push_back({hh[i].l,hh[i].w});}auto dfs=[&](auto self,int x,int fa)->void{for(auto [i,j]:ve[x]){if(i==fa||c[i]!=-1)continue;c[i]=c[x]^1;self(self,i,x);}};for(int i=1;i<=n;i++){if(pre[i]==i){c[i]=0;dfs(dfs,i,-1);break;}}int ans=MX;for(int i=1;i<=m;i++){if(c[hh[i].l]==c[hh[i].r]){ans=min(ans,hh[i].w);}}for(int i=1;i<=n;i++){sort(ve[i].begin(),ve[i].end(),cmp);}for(int i=1;i<=n;i++){if(ve[i].size()>1){ans=min(ans,ve[i][0].second+ve[i][1].second);}}cout<<ans;}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _=1;// cin>>_;while(_--){icealsoheat();}}

D - Substring Comparison

本题对于算法的考察比较多，我认为是一道比较好的题。这题我没有一点思路，是直接看佬的代码和思路的，让我恍然大悟。既然n是2000，那就支持双重循环了。首先，如果a=c并且d>=b的话，那一定是输出no的，我们可以优先排前面的，最开始让a<c，当出现了环的情况的时候，才能确定出a==c，那就让下一位数作为比较，直到最后跳出。（思路不知道咋讲，但上面大佬樱雪喵的题解里讲的很清楚了）代码如下：

#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;
bool f=0;
int b[1000005];
int pre[100005];
int dfn[10000];
int low[10000];
vector<int>ve[10000];
int find(int x){if(x==pre[x])return x;else return pre[x]=find(pre[x]);
}
struct we{int a,b,c,d;
}hh[20005];
int num;
int top,col;
int a[10000];
int c[10000];
void tarjan(int u){dfn[u]=low[u]=++num;a[++top]=u;for(auto i:ve[u]){if(dfn[i]==0){tarjan(i);low[u]=min(low[u],low[i]);// pre[find(i)]=find(u);}else{if(!c[i]){low[u]=min(low[u],dfn[i]);}}}if(low[u]==dfn[u]){c[u]=++col;while(a[top]!=u){if(find(a[top])!=find(u)){pre[find(a[top])]=find(u);}f=1;c[a[top]]=col;top--;}top--;}
}void icealsoheat(){cin>>n>>m;for(int i=1;i<=m;i++){cin>>hh[i].a>>hh[i].b>>hh[i].c>>hh[i].d;}for(int i=1;i<=n;i++)pre[i]=i;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){ve[j].clear();}for(int j=1;j<=m;j++){while(find(hh[j].a)==find(hh[j].c)&&hh[j].a<=hh[j].b&&hh[j].c<=hh[j].d){hh[j].a++;hh[j].c++;}if(hh[j].c>hh[j].d){cout<<"No";return;}if(hh[j].a<=hh[j].b){ve[find(hh[j].a)].push_back(find(hh[j].c));// ve[find(hh[j].c)].push_back(find(hh[j].a));               }}for(int j=1;j<=n;j++){dfn[j]=0;low[j]=0;c[j]=0;a[j]=0;}top=col=num=0;f=0;for(int j=1;j<=n;j++){if(!dfn[j]){tarjan(j);}}if(!f){cout<<"Yes";return;}}cout<<"Yes";}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _=1;// cin>>_;while(_--){icealsoheat();}}