ABC-277解题报告

发表于 2022-11-12 更新于 2022-11-13 分类于解题报告

B. Playing Cards Validation

题意：有 $n$ 个长度为 $2$ 的字符串，判断是否满足以下条件：

第一个字符为 HDCS 之一。

第二个字符为 A23456789TJQK 之一。

字符串两两不同。

一个模拟题。可以将两个字符可能的选择分别记录下来，循环一遍判断是否为其中之一或调用 count 函数；也可以直接写 if 判断。判断两两不同可以 $n^2$ 枚举，也可以用 set 或排序加 unique 去重。

#include<bits/stdc++.h>
using namespace std;
string a="HDCS",b="A23456789TJQK";
void NO() {puts("No");exit(0);}
set<string> st;
signed main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) {
        string s;
        cin>>s;
        bool flag=0;
        for(char c:a) if(s[0]==c) flag=1;
        if(!flag) NO();
        flag=0;
        for(char c:b) if(s[1]==c) flag=1;
        if(!flag) NO();
        st.insert(s);
    }
    if(st.size()!=n) NO();
    puts("Yes");
    return 0;
}

By yuiop

#include<stdio.h>
int main(){
  int n,h=1,i,j,u[550]={};
  char s[]={"HDCS"},t[]={"A23456789TJQK"};
  scanf("%d",&n);
  while(n--){
    scanf(" %c%c",&s[4],&t[13]);
    for(i=0;s[i]!=s[4 ];i++);
    for(j=0;t[j]!=t[13];j++);
    if(i==4||j==13)h=0;
    if(u[i*100+j])h=0;
    u[i*100+j]=1;
    //printf("%d\n",h);
  }
  printf("%s\n",h?"Yes":"No");
  return 0;
}

这份代码是使用一个指针，一直扫到匹配。然而将待判断字符串与合法字符集混在一起的写法容易产生混淆，并不利于代码可读性和调试难度。写代码时每个部分的用途要尽量明确，不要有一个结构存多个意义的情况。

修改后可以为：

fixed

#include<bits/stdc++.h>
using namespace std;
void NO() {puts("No");exit(0);}
string a="HDCS",b="A23456789TJQK";
set<string> st;
signed main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) {
        string s;
        cin>>s;
        int x=0,y=0;
        while(s[0]!=a[x]&&x<a.size()) x++;
        while(s[1]!=b[y]&&y<b.size()) y++;
        if(x==a.size()||y==b.size()) NO();
        st.insert(s);
    }
    if(st.size()!=n) NO();
    puts("Yes");
    return 0;
}

By hitonanode

void bad() {
    puts("No");
    exit(0);
}

int main() {
    int N;
    cin >> N;
    set<string> se;
    REP(_, N) {
        string s;
        cin >> s;
        const string suit = "HDCS";
        const string num = "A23456789TJQK";
        if (!count(ALL(suit), s.front())) bad();
        if (!count(ALL(num), s.back())) bad();
        se.insert(s);
    }
    if (se.size() < N) bad();
    puts("Yes");
}

这份代码使用 count 函数进一步简化过程。

C. Ladder Takahashi

题意：给你一张 $n$ 个点 $m$ 条边的无向图，问点 $1$ 能到达的点中编号最大的。 $n\le 10^9,m\le 2\times 10^5$ 。

很简单的判断连通性问题，可以 DFS 也可以 BFS。主要需要处理的问题在于，点的编号可以很大，常规存图方式不可行。有以下两种方法处理：

离散化

By SSRS

#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<int> A(N), B(N);
  for (int i = 0; i < N; i++){
    cin >> A[i] >> B[i];
  }
  vector<int> X;
  X.push_back(1);
  for (int i = 0; i < N; i++){
    X.push_back(A[i]);
    X.push_back(B[i]);
  }
  sort(X.begin(), X.end());
  X.erase(unique(X.begin(), X.end()), X.end());
  int M = X.size();
  for (int i = 0; i < N; i++){
    A[i] = lower_bound(X.begin(), X.end(), A[i]) - X.begin();
    B[i] = lower_bound(X.begin(), X.end(), B[i]) - X.begin();
  }
  vector<vector<int>> E(M);
  for (int i = 0; i < N; i++){
    E[A[i]].push_back(B[i]);
    E[B[i]].push_back(A[i]);
  }
  vector<bool> used(M, false);
  used[0] = true;
  queue<int> Q;
  Q.push(0);
  while (!Q.empty()){
    int v = Q.front();
    Q.pop();
    for (int w : E[v]){
      if (!used[w]){
        used[w] = true;
        Q.push(w);
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < M; i++){
    if (used[i]){
      ans = max(ans, X[i]);
    }
  }
  cout << ans << endl;
}

使用 map 处理

By cxm1024

#include<bits/stdc++.h>
using namespace std;
map<int,vector<int> > a;
map<int,bool> vis;
int ans=0;
void dfs(int now) {
    if(vis[now]) return;
    vis[now]=1,ans=max(ans,now);
    auto &to=a[now];
    for(int v:to) dfs(v);
}
signed main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) {
        int x,y;
        cin>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs(1);
    cout<<ans<<endl;
    return 0;
}

D. Takahashi’s Solitaire

题意：有 $n$ 张卡片，卡片上数字的值域为 $[0,m)$ ，你需要选择若干张卡片放到桌子上，要求放的卡片的数字等于上一次放的数字，或等于上一次放的数字 $+1$ 后 $\bmod m$ 。最小化剩余的卡片的数字和。

转化为最大化放的卡片的数字和。首先将卡片排序。一个显然的结论是，每次选一个数字时必然要全部选完。实现上有以下几种处理方法：

断环为链

由于值域上 $m$ 和 $0$ 连续，可能形成环，所以将排好序的数组复制两遍，断环为链。循环时维护当前尽可能长的连续段和即可。连续段的数字和计算可以使用前缀和加速。无需特判长度是否超过 $n$ ，因为此时数字和也会超过总数字和，只需要将答案和 $0$ 取 $\max$ 即可。

By cxm1024

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[400010];
signed main() {
    int n,m,sum=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=n+1;i<=n+n;i++)
        a[i]=a[i-n],sum+=a[i];
    int now=a[1],ans=0;
    for(int i=2;i<=n+n;i++) {
        if(a[i-1]!=a[i]&&(a[i-1]+1)%m!=a[i]) {
            ans=max(ans,now);
            now=a[i];
        }
        else now+=a[i];
    }
    ans=max(ans,now);
    cout<<max(0ll,sum-ans)<<endl;
    return 0;
}

环上记录断点

直接在环上处理，记录每一个不连续的位置，扫一遍统计答案。相邻两个断点之间即为连续段。

By SSRS

#include <bits/stdc++.h>
using namespace std;
int main(){
  int N, M;
  cin >> N >> M;
  vector<int> A(N);
  for (int i = 0; i < N; i++){
    cin >> A[i];
  }
  sort(A.begin(), A.end());
  long long sum = 0;
  for (int i = 0; i < N; i++){
    sum += A[i];
  }
  vector<int> p;
  for (int i = 0; i < N; i++){
    int j = (i + N - 1) % N;
    if (A[j] != (A[i] + M - 1) % M && A[j] != A[i]){
      p.push_back(i);
    }
  }
  if (p.empty()){
    cout << 0 << endl;
  } else {
    int cnt = p.size();
    long long mx = 0;
    for (int i = 0; i < cnt; i++){
      int r = p[(i + 1) % cnt];
      if (i == cnt - 1){
        r += N;
      }
      long long tmp = 0;
      for (int j = p[i]; j < r; j++){
        tmp += A[j % N];
      }
      mx = max(mx, tmp);
    }
    cout << sum - mx << endl;
  }
}

循环移位

将 $j\to m\to 0\to i$ 的一整个连续段放到最后，从 $i+1$ 开始处理到 $i$ 为止。

By kotatsugame

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N,M;
int A[2<<17];
main()
{
    cin>>N>>M;
    for(int i=0;i<N;i++)cin>>A[i];
    sort(A,A+N);
    int id;
    if((A[N-1]+1)%M!=A[0])id=0;
    else
    {
        id=1;
        while(id<N&&A[id-1]+1>=A[id])id++;
        if(id==N)
        {
            cout<<0<<endl;
            return 0;
        }
    }
    long ans=0;
    for(int i=0;i<N;)
    {
        int j=i+1;
        long now=A[(id+i)%N];
        while(j<N)
        {
            int y=A[(id+j)%N];
            int x=A[(id+j-1)%N];
            if(y==x||y==(x+1)%M)
            {
                now+=y;
                j++;
            }
            else break;
        }
        i=j;
        ans=max(ans,now);
    }
    for(int i=0;i<N;i++)ans-=A[i];
    cout<<-ans<<endl;
}

并查集

用并查集维护连通的值域，维护每个块的数字和，最后找最大的块即可。

By kzyKT

ll p[200001],r[200001],c[200001];
void init(ll n){rep(i,n)p[i]=i,r[i]=0,c[i]=0;}
int find(int x){return (p[x]==x)?x:(p[x]=find(p[x]));}
void unite(int x,int y) {
  x=find(x),y=find(y);
  if(x==y)return;
  ll cx=c[x],cy=c[y];
  if(r[x]<r[y])p[x]=y;
  else{p[y]=x;if(r[x]==r[y])r[x]++;}
  c[find(x)]=cx+cy;
}
bool same(int x,int y){return find(x)==find(y);}

void Main() {
  ll n,m;
  cin >> n >> m;
  ll a[n];
  rep(i,n) R a[i];
  init(n);
  map<ll,vector<ll>> ma;
  rep(i,n) {
    ma[a[i]].pb(i);
  }
  ll sum=0;
  rep(i,n) {
    c[i]=a[i];
    sum+=a[i];
  }
  tr(it,ma) {
    REP(i,1,it->S.size()) unite(it->S[0],it->S[i]);
    if(ma.count((it->F+1)%m)) unite(it->S[0],ma[(it->F+1)%m][0]);
  }
  ll ans=sum;
  rep(i,n) {
    if(find(i)==i) ans=min(ans,sum-c[i]);
  }
  pr(ans);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}

遍历 map

用 map 存下每个数字及出现次数，在 map 上遍历，遇到断点就扫到下一个断点，没有断点特判以下即可。

By waltz

using namespace std;
map<int, long long> ans;
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,m;
    scanf("%d%d",&n,&m);
    int i;
    long long sum_ans = 0;
    for (i=0;i<n;i++)
    {
        int x;
        scanf("%d",&x);
        ans[x % m] += x;
        sum_ans += x;
    }
    long long max_dec = 0;
    map<int, long long>::iterator ii;
    for (ii = ans.begin(); ii != ans.end(); ii++)
    {
        int x = (*ii).first;
        if (ans.find((x-1+m)%m) == ans.end())
        {
            long long dec = (*ii).second;
            map<int, long long>::iterator jj = ii;
            for (;;)
            {
                jj ++;
                if (jj == ans.end())
                {
                    jj = ans.begin();
                }
                if ((*jj).first == ((x + 1) % m))
                {
                    dec += (*jj).second;
                    x = (*jj).first;
                }
                else
                {
                    break;
                }
            }
            max_dec = max(max_dec, dec);
        }
    }
    if (max_dec == 0)
    {
        max_dec = sum_ans;
    }
    printf("%lld\n", sum_ans - max_dec);
    return 0;
}

E. Crystal Switches

题意：有一张图，边有 01 两种颜色，只能走颜色 1 的边。有 $k$ 个特殊点，当你到达特殊点时，可以选择将图中每条边的颜色取反（也可以不取反）。问从 $1$ 号点走到 $n$ 号点的最短路（取反不算一步）。

将图中每条边的颜色取反，可以看成将当前能走的颜色取反，于是在普通最短路的基础上修改一下即可。记录状态的时候不仅要记录当前的点和距离，还要记录当前能走的颜色。转移时，若当前点不为特殊点，则只能通过可走的边转移到下一个点，否则能通过所有边转移到下一个点。用 Dijkstra 和 BFS 均可。

Dijkstra

Dijkstra 的做法比较显然但较难写：

By cxm1024

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,bool> > a[200010];
bool swt[200010];
struct node {
    int x,val,flag;
    bool operator<(const node &o)const {
        return val>o.val;
    }
};
priority_queue<node> q;
bool done[200010][2];
int ans[200010][2];
void dijkstra() {
    q.push({1,0,0});
    while(!q.empty()) {
        auto [u,w,flag]=q.top();q.pop();
        if(done[u][flag]) continue;
        done[u][flag]=1,ans[u][flag]=w;
        for(auto v:a[u]) {
            if(done[v.first][1-v.second]) continue;
            if(v.second^flag) q.push({v.first,w+1,flag});
            else if(swt[u]) q.push({v.first,w+1,1-flag});
        }
    }
}
signed main() {
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++) {
        int u,v,x;
        cin>>u>>v>>x;
        a[u].push_back({v,x});
        a[v].push_back({u,x});
    }
    for(int i=1;i<=k;i++) {
        int x;
        cin>>x;
        swt[x]=1;
    }
    dijkstra();
    if(!done[n][0]&&!done[n][1]) cout<<-1<<endl;
    else if(done[n][0]&&done[n][1]) cout<<min(ans[n][0],ans[n][1])<<endl;
    else cout<<ans[n][0]*done[n][0]+ans[n][1]*done[n][1]<<endl;
    return 0;
}

01BFS

用 01BFS 来处理最短路。对于特殊点，我们可以看做该点向自己连一条权值为 $0$ 的边，作用为翻转当前能走的颜色。在实现中即为 push_front “翻转颜色后的自己”到队列首。

By kotatsugame

#include<iostream>
#include<vector>
#include<deque>
using namespace std;
int N,M,K;
bool S[2<<17];
int D[2<<17][2];
vector<int>G[2<<17][2];
main()
{
    cin>>N>>M>>K;
    for(int i=0;i<M;i++)
    {
        int u,v,a;cin>>u>>v>>a;
        u--,v--;
        G[u][a].push_back(v);
        G[v][a].push_back(u);
    }
    for(int i=0;i<K;i++)
    {
        int s;cin>>s;
        S[s-1]=true;
    }
    for(int i=0;i<N;i++)D[i][0]=D[i][1]=1e9;
    D[0][1]=0;
    deque<pair<int,int> >Q;
    Q.push_back(make_pair(0,1));
    while(!Q.empty())
    {
        int u=Q.front().first,f=Q.front().second;
        Q.pop_front();
        if(S[u])
        {
            if(D[u][!f]>D[u][f])
            {
                D[u][!f]=D[u][f];
                Q.push_front(make_pair(u,!f));
            }
        }
        for(int v:G[u][f])if(D[v][f]>D[u][f]+1)
        {
            D[v][f]=D[u][f]+1;
            Q.push_back(make_pair(v,f));
        }
    }
    int ans=min(D[N-1][0],D[N-1][1]);
    if(ans==(int)1e9)ans=-1;
    cout<<ans<<endl;
}

Dijkstra+虚点

我们对于每个点 $i$ 建立一个对应点 $i+n$ ，为翻转当前颜色后的点。对于颜色为 1 的边，只能在初始颜色的情况下走，所以连接两个点 $i,j$ 。对于颜色为 0 的边，只能在翻转颜色后的图上走，所以连接 $i+n,j+n$ 。于是我们得到了两个完全独立的图。而特殊点的作用就是连接这两个图。对于每个特殊点 $i$ ，连接 $i,i+n$ ，权值为 0 即可。

By hitonanode

int main() {
    int N, M, K;
    cin >> N >> M >> K;

    shortest_path<int> graph(N * 2);
    REP(e, M) {
        int u, v, a;
        cin >> u >> v >> a;
        --u, --v;
        if (a) {
            graph.add_bi_edge(u, v, 1);
        } else {
            graph.add_bi_edge(u + N, v + N, 1);
        }
    }
    while (K--) {
        int s;
        cin >> s;
        --s;
        graph.add_bi_edge(s, N + s, 0);
    }

    graph.solve(0);
    int ret = min(graph.dist[N - 1], graph.dist[N * 2 - 1]);
    if (ret > 1 << 25) ret = -1;
    cout << ret << endl;
}