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

ABC-277解题报告

时间:2023-03-01 17:33:39浏览次数:55  
标签:ABC int 277 back cin 解题 ans push include

比赛传送门

B. Playing Cards Validation

题意:有 \(n\) 个长度为 \(2\) 的字符串,判断是否满足以下条件:

  1. 第一个字符为 HDCS 之一。
  2. 第二个字符为 A23456789TJQK 之一。
  3. 字符串两两不同。

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

By cxm1024

#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;
}

标签:ABC,int,277,back,cin,解题,ans,push,include
From: https://www.cnblogs.com/cxm1024/p/17168381.html

相关文章

  • ABC-282解题报告
    比赛传送门C.StringDelimiter题意:有一个包含字母、双引号(保证有偶数个,相邻两个匹配)和逗号的字符串,将在双引号外的逗号改为句号。维护当前在双引号里还是外,遇到双引......
  • 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......