[题解]（更新中）AtCoder Beginner Contest 393(ABC393) A~E

6个月前更新

A – Poisonous Oyster

如果两人都肚子疼，就是第\(1\)瓶。
如果只有Takahashi肚子疼，就是第\(2\)瓶。
如果只有Aoki肚子疼，就是第\(3\)瓶。
如果都不肚子疼，就是第\(4\)瓶。

时间复杂度\(O(1)\)。

点击查看代码

#include<bits/stdc++.h>
using namespace std;
string a,b;
signed main(){
	cin>>a>>b;
	if(a[0]=='s'&&b[0]=='s') cout<<"1\n";
	else if(a[0]=='s'&&b[0]=='f') cout<<"2\n";
	else if(a[0]=='f'&&b[0]=='s') cout<<"3\n";
	else cout<<"4\n";
	return 0;
}

B – A..B..C

枚举前\(2\)个位置便可以作差得出第\(3\)个位置，判断并计数即可。

时间复杂度\(O(n^2)\)。

点击查看代码

#include<bits/stdc++.h>
using namespace std;
string s;
int n,ans;
signed main(){
	cin>>s;
	n=s.size();
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			int k=2*j-i;
			if(k>=n) continue;
			ans+=(s[i]=='A'&&s[j]=='B'&&s[k]=='C');
		}
	}
	cout<<ans<<"\n";
	return 0;
}

C – Make it Simple

自环直接跳过，重边用set去重。最后保留在set中的边数为\(k\)，则答案为\(m-k\)。

时间复杂度\(O(m\log m)\)，当然也很容易做到\(O(m)\)。

点击查看代码

#include<bits/stdc++.h>
#define N 200010
using namespace std;
int n,m,ans;
vector<int> G[N];
set<pair<int,int>> se;
signed main(){
	cin>>n>>m;
	for(int i=1,u,v;i<=m;i++){
		cin>>u>>v;
		if(u==v) continue;
		if(u>v) swap(u,v);
		se.insert({u,v});
	}
	cout<<m-se.size()<<"\n";
	return 0;
}

D – Swap to Gather

设共有\(m\)个1，第\(i\)个1的位置为\(p_i\)，有两种考虑方式（代码使用第\(1\)种实现）：

设第\(1\)个1最终的位置为\(k\)。则答案为\(\sum\limits_{i=1}^m |p_i-(k+i-1)|=\sum\limits_{i=1}^m |(p_i-i+1)-k|\)。
令\(b_i=p_i-i+1\)，则答案为\(\sum\limits_{i=1}^m |b_i-k|\)，则这是一个典型的货仓选址问题，其中\(k\)取\(b\)的中位数时上式取到最小。
实际上也不一定非得设第\(1\)个位置为\(k\)，比如你可以定义\(b_i=p_i-i+C\)，\(C\)可以是任何常数。
显然最优解一定可以通过保持至少一个1位置不变取到。
假设第\(k\)个1位置不变，则不难发现答案为\(\sum\limits_{i=1}^m |d(i,k)|\)，其中\(d(x,y)\)为\(s[p_x\sim p_y]\)中0的个数。进一步可得\(d(x,y)=(p_y-p_x)-(y-x)=(p_y-y)-(p_x-x)\)。
令\(b_i=p_i-i\)，则答案为\(\sum\limits_{i=1}^m |b_k-b_i|\)。根据定义知道\(d(x,y)\ge 0\)，故\(b\)单调不降。所以这仍然是一个货仓选址问题，\(k\)取中间值即可取到最小（换句话说，我们证明了保留最中间的1不动一定最优）。

注意开long long！

时间复杂度\(O(n)\)。

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,cnt,ans;
vector<int> v;
string s;
signed main(){
	cin>>n>>s,s=' '+s;
	for(int i=1;i<=n;i++){
		if(s[i]=='1') v.emplace_back(i-cnt),cnt++;
	}//因为已经有序的所以不用排序
	int t=v[v.size()/2];
	for(int i:v) ans+=abs(t-i);
	cout<<ans<<"\n";
	return 0;
}

E – GCD of Subset

关注这道题的数据范围：发现我们没法为每个元素分解质因数，更没法枚举每个子序列，但\(V=10^6\)，所以枚举公因数可能会很方便。

具体来说，定义\(s_x\)为\(x\)在\(A\)中的出现次数，\(t_x\)为\(x\)的倍数在\(A\)中的出现次数，那么\(t_x=\sum\limits_{x|n} s_n\)。

\(s\)可以在输入的同时处理出来；\(t\)的计算，仅需我们对于每个\(x\)枚举\(n\)，其时间复杂度是一个调和级数\(O(\frac{V}{1}+\frac{V}{2}+\dots+\frac{V}{V})=O(V\log V)\)。

接下来我们枚举公因数\(x\)，如果\(t_x\ge k\)，就可以对所有\(x\)的倍数产生\(x\)的贡献。

根据上面的描述，令\(u_x\)为\(x\)这个值的答案。\(u\)的计算，仅需我们对于每个\(x\)枚举其倍数\(n\)，然后令\(s_n\leftarrow \max(s_n,d)\)即可。同上，它也是\(O(V\log V)\)的。

最后对于每个\(i\)，依次输出\(s_{a_i}\)即可。

时间复杂度\(O(n+V\log V)\)。

点击查看代码

#include<bits/stdc++.h>
#define N 1200010
#define V 1000010
using namespace std;
int n,k,a[N],s[V],u[V];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i],s[a[i]]++;
	for(int i=1;i<V;i++){
		int t=0;
		for(int j=i;j<V;j+=i) t+=s[j];
		if(t>=k) for(int j=i;j<V;j+=i) u[j]=i;
	}
	for(int i=1;i<=n;i++) cout<<u[a[i]]<<"\n";
	return 0;
}

来源链接：https://www.cnblogs.com/Sinktank/p/18717692

评分

欢迎为Ta评分