首页 > 其他分享 >ABC-282解题报告

ABC-282解题报告

时间:2023-03-01 16:47:37浏览次数:50  
标签:二分 连通 ABC int long 解题 ans 282 col

比赛传送门

C. String Delimiter

题意:有一个包含字母、双引号(保证有偶数个,相邻两个匹配)和逗号的字符串,将在双引号外的逗号改为句号。

维护当前在双引号里还是外,遇到双引号更改即可。

By SSRS

#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  string S;
  cin >> S;
  bool c = false;
  for (int i = 0; i < N; i++){
    if (S[i] == '"'){
      c = !c;
    }
    if (S[i] == ',' && !c){
      S[i] = '.';
    }
  }
  cout << S << endl;
}

D. Make Bipartite 2

题意:给你一个无向图,判断有多少无序点对 \((x,y)\) 满足之间没有边,且连接之后为二分图。

对于一个连通块,生成二分图的方式是唯一的,且加边不会导致一个非二分图变为二分图。于是只要有一个连通块不是二分图,答案一定为 \(0\)。

对于不为 \(0\) 的情况,可以预处理每个连通块两边的点数,对于连通块内部的边,一定是左边连向右边,方案数为两边点数之积。对于连通块之间的边,任意连边都可以。在第一种情况中,有 \((x,y)\) 之间有边的情况,所以最后减去 \(m\) 即可。正确性容易证明。

By wygz

const int maxn=(2e5)+10;
int n,m,cnt[2];
int col[maxn]; vector<int> g[maxn];
ll C2(ll x) { return x*(x-1)/2; }
ll ans;
void dfs(int u) {
	cnt[col[u]-1]++;
	for (int &v : g[u]) {
		if (col[v]&&col[v]==col[u]) { puts("0"); exit(0); }
		if (col[v]) continue;
		col[v]=3-col[u];
		dfs(v);
	}
}
int main() {
	read(n),read(m);
	int x,y; for (int i=1;i<=m;i++) {
		read(x),read(y);
		g[x].push_back(y),g[y].push_back(x);
	}
	for (int i=1;i<=n;i++) if (!col[i]) {
		cnt[0]=cnt[1]=0;
		col[i]=1,dfs(i);
		ans-=C2(cnt[0]),ans-=C2(cnt[1]);
	}
	ans-=m;
	ans+=C2(n);
	printf("%lld\n",ans);

	return 0;
}

还有一种维护二分图的方法,将一个点 \(i\) 拆成两个点 \(i,i'\)(实现上可以用 \(i+n\)),原图中连一条边 \(u,v\) 时,我们连接 \(u,v'\) 和 \(v,u'\)。此时维护的图中一条边 \(x,y\) 表示 \(x,y\) 异色。如下图:

左边的图为原图,右边为维护的图。容易发现,左边的图为二分图,而右边的图可以拆成红黑两部分。左边红色的点 \(1,4\) 为原二分图中的一边,左边黑色的点 \(2,3\) 为原二分图中的另一边。

显然,如果两个点 \(u,v\) 在二分图的两侧,那么 \(u,v\) 一定不连通,\(u,v'\) 一定连通。于是有点 \(u\) 和 \(u'\) 一定不连通。

什么时候不是二分图呢?如下图,连接 \(2,3\):

加上这条蓝色边后,可以发现维护的图合并成了一部分。此时点 \(u\) 和点 \(u'\) 变得连通,就无法产生二分图。这种二分图的表示可以很容易用并查集维护,加完边最后判断每个 \(u\) 和 \(u'\) 是否连通即可。二分图两边点的个数也可以很容易地用并查集统计(红点之间相连,黑点之间相连)。

By drogskol

#include <bits/stdc++.h>
using namespace std;

#include <atcoder/dsu>
using namespace atcoder;

using ll=long long;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll n,m;cin>>n>>m;
  ll ans=n*(n-1)/2-m;

  dsu uf(n*2);
  while(m--){
    int u,v;cin>>u>>v;u--;v--;
    uf.merge(u,v+n);
    uf.merge(v,u+n);
  }

  map<int,int> mp;
  for(int i=0;i<n;i++){
    if(uf.same(i,i+n)){
      cout<<0<<endl;
      return 0;
    }
    ans-=mp[uf.leader(i)]++;
  }

  cout<<ans<<endl;
}

E. Choose Two and Eat One

题意:有 \(n\) 个有权值的球,每次可以选两个球 \(a_i,a_j\),造成 \(({a_i}^{a_j}+{a_j}^{a_i})\bmod m\) 的贡献,并选择一个球删掉。问剩一个球时的最大贡献。

由于贡献的式子没有规律,所以不能从 \(a_i\) 的角度贪心,而思考一下会发现 DP 状态也设不了,于是考虑其他思路。

我们将每个球 \(i\) 被删掉的时候与别的球 \(j\) 造成的贡献看为一条从 \(i\) 连向 \(j\) 的边,显然每个 \(i\)(除了最后一个点)有一条出边,但可能有多个入边。容易发现此为一个树形结构。而两个球的贡献同样可以在图上表示出来,为一个完全图。所以,答案即为图上最大生成树的权值。将最小生成树算法反向操作即可。

By SSRS

#include <bits/stdc++.h>
using namespace std;
long long modpow(long long x, long long y, long long M){
  long long ans = 1;
  while (y > 0){
    if (y % 2 == 1){
      ans *= x;
      ans %= M;
    }
    x *= x;
    x %= M;
    y /= 2;
  }
  return ans;
}
struct unionfind{
  vector<int> p;
  unionfind(int N){
    p = vector<int>(N, -1);
  }
  int root(int x){
    if (p[x] < 0){
      return x;
    } else {
      p[x] = root(p[x]);
      return p[x];
    }
  }
  bool same(int x, int y){
    return root(x) == root(y);
  }
  void unite(int x, int y){
    x = root(x);
    y = root(y);
    if (x != y){
      if (p[x] < p[y]){
        swap(x, y);
      }
      p[y] += p[x];
      p[x] = y;
    }
  }
};
int main(){
  int N, M;
  cin >> N >> M;
  vector<int> A(N);
  for (int i = 0; i < N; i++){
    cin >> A[i];
  }
  vector<tuple<int, int, int>> E;
  for (int i = 0; i < N; i++){
    for (int j = i + 1; j < N; j++){
      E.push_back(make_tuple((modpow(A[i], A[j], M) + modpow(A[j], A[i], M)) % M, i, j));
    }
  }
  sort(E.begin(), E.end(), greater<tuple<int, int, int>>());
  unionfind UF(N);
  long long ans = 0;
  for (int i = 0; i < N * (N - 1) / 2; i++){
    int c = get<0>(E[i]);
    int u = get<1>(E[i]);
    int v = get<2>(E[i]);
    if (!UF.same(u, v)){
      UF.unite(u, v);
      ans += c;
    }
  }
  cout << ans << endl;
}

标签:二分,连通,ABC,int,long,解题,ans,282,col
From: https://www.cnblogs.com/cxm1024/p/17168387.html

相关文章

  • ABC-280解题报告
    D.FactorialandMultiple题意:给你一个\(k\),求最小的\(n\)使得\(k|n!\)。\(k\le10^{12}\)。做法一考虑将\(k\)分解质因数,对于每项\(p^r\),都要求\(n!\)中含......
  • ABC-279解题报告
    比赛传送门C.RANDOM题意:给你两个01矩阵\(S,T\),问是否可以将\(S\)以列为单位重新排列得到\(T\)。判断\(S,T\)的每列是否可以一一对应即可做法一以列为单位......
  • ABC-288解题报告
    比赛传送门D.RangeAddQuery题意:有一个序列\(A\)和正整数\(k\),每次询问给定\(l,r\),你可以在\([l,r]\)内选择一段长度为\(k\)的子段,统一加减,问是否能将\([l,r......
  • ABC-271解题报告
    C.Manga题意:有一本书有\(n\)卷,你需要从第一卷开始依次看,一旦没有某一卷就停止。在看之前你可以进行若干次操作,每次卖掉任意两卷并买新的任意一卷。问操作结束后最多能......
  • AGC-059解题报告
    比赛传送门A.MyLastABCProblem题意:有一个只含ABC字符串\(s\),每次询问一段区间\([l,r]\),问至少需要多少次操作能将这段区间变得完全相同。每次操作可以选一段区......
  • ABC275D-Yet-Another-Recursive-Function题解
    题目传送门题意:定义一个\(\mathbb{N}\to\mathbb{N}\)的函数\(f(x)=\begin{cases}1&x=0\\f(\lfloor\frac{x}{2}\rfloor)+f(\lfloor\frac{x}{3}\rfloor)&\text{otherwis......
  • CFR-826-Div-3解题报告
    F.Multi-ColoredSegments题意:数轴上有\(n\)个线段,每个区间有一个颜色\(c\),对于每个线段,求与它颜色不同的线段中与它的最短距离。距离定义为两个线段中的点集最近的......
  • CFR-832-Div-2解题报告
    B.BANBAN题意:给你一个\(n\),生成一个字符串为BAN重复\(n\)遍。每次操作可以选择两个位置进行交换,问至少多少次交换后可以使该串不存在BAN的子序列。输出方案。......
  • CFR-755-Div-2解题报告
    比赛传送门赛时AC三道,补题做出一道。A.MathematicalAddition{%noteinfono-iconProblem%}给你两个正整数\(u,v\),求一对合法的\(x,y\)使得\(\frac{x}{u}+\fra......
  • CFR-844-Div-1-2解题报告
    比赛传送门A.ParallelProjection题意:有一个\(w\timesd\timesh\)的长方体,顶面和底面有两个点,只能走直线且不能穿过长方体,求最短距离。显然曼哈顿距离必须要走。......