AtCoder Beginner Contest 264（D-E）

D – “redocta”.swap(i,i+1)

题意: 给一个字符串，每次交换相邻两个字符，问最少多少次变成”atcoder”

题解: 从左到右依次模拟

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const int N=2e5+5;
const ll inf=1e18;
const ll mod=998244353;
ll a[N];
ll minn[N];
signed main(){
   ios::sync_with_stdio(false);
   cin.tie(0);cout.tie(0);
   string s;cin>>s;
   string p="atcoder";
   ll ans=0;
   for(ll i=0;i<=6;i++){
      if(s[i]==p[i]) continue;
      ll j=i;
      while(s[j]!=p[i]){
         j++;
      }
      ans+=j-i;
      for(ll z=j;z>=i;z--) s[z]=s[z-1];
      s[i]=p[i];
   }
   cout<<ans;
}

E – Blackout 2

题意: 给出N个城市，M个发电厂，K个电线，然后Q次操作 ，每次剪断一根电线，问每次操作之后，有几个城市是有点的，只有到一个城市与发电厂是连通的，才是有电的。

题解: 我们可以把这个问题换位思考。

• 开始有K根电线，然后每次剪断一根，问剪断之后有多少城市有电
• 开始有K-Q根电线，每次加上一根，问加上之后有多少城市有电

我们可以发现，上面这两个问题他们最后得出的答案刚好是相反的，所以，我们可以通过第二种方法求出答案然后逆序输出，明显第二种方法简单。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const int N=5e5+5;
const ll inf=1e18;
const ll mod=998244353;
ll pre[N];
pll q[N];
ll sum[N],flag[N];
ll p[N],vis[N],vp[N];
ll find(ll x){
   if(pre[x]==x) return x;
   return pre[x]=find(pre[x]);
}
signed main(){
   ios::sync_with_stdio(false);
   cin.tie(0);cout.tie(0);
   ll n,m,k;cin>>n>>m>>k;
   for(ll i=1;i<=k;i++){
      cin>>q[i].first>>q[i].second;
   }
   ll t;cin>>t;
   for(ll i=1;i<=t;i++){ cin>>p[i];vis[p[i]]=1;}//记录那些电线是剪断的
   for(ll i=1;i<=n+m;i++) pre[i]=i;
   for(ll i=1;i<=k;i++){
      if(vis[i]) continue;//遍历开始没有剪断的电线
      ll fx=find(q[i].first);
      ll fy=find(q[i].second);
      pre[fx]=fy;
   }
   for(ll i=1;i<=n;i++){
      ll fx=find(i);
      sum[fx]++;
   }
   ll ans=0;
   for(ll i=n+1;i<=m+n;i++){//求出开始的时候有多少城市有电
      ll fx=find(i);
      ans+=(flag[fx]==0?sum[fx]:0);
      flag[fx]=1;
   }
   stack<ll> lm;
   for(ll i=t;i>=1;i--){
      lm.push(ans);
      ll fx=find(q[p[i]].first);
      ll fy=find(q[p[i]].second);
      if(fx==fy) continue;//如果是连通的，就没必要处理
      if(!flag[fx]&&flag[fy]){//如果第一个是没电，第二个有电，就答案加上没电的
         flag[fx]=1;ans+=sum[fx];
      }
      else if(flag[fx]&&!flag[fy]){//同理
         flag[fy]=1;ans+=sum[fy];
      }
      else if(!flag[fx]&&!flag[fy]){//如果都没电，就让他们合并
         sum[fy]+=sum[fx];
      }
      pre[fx]=fy;
   }
   while(lm.size()){
      cout<<lm.top()<<endl;//逆序输出
      lm.pop();
   }
}