专栏文章

Codeforces Round 1003 (Div. 4)

DDing0023
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqaifuf
此快照首次捕获于
2025/12/04 01:37
3 个月前
此快照最后确认于
2025/12/04 01:37
3 个月前
查看原文

A. Skibidus and Amog'u

没啥好说的。
CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
string s;
int t;
void solve(){
	cin >> s;
	for(int i=0;i<s.size()-2;i++) cout << s[i];
	cout << "i" << endl;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> t;
	while(t--) solve();
	return 0;
}

B. Skibidus and Ohio

可以考虑将两个字母合并结果设为−1-1暂时存放，在合并时可将−1-1变为所需要值，然后就贪心的能合就合。
CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int a[maxn];
int b[maxn];
string s;
int t;
void solve(){	
	
	cin >> s;
	for(int i=0;i<(int)s.size();i++) a[i+1]=s[i]-'a'; 
	int cnt1=s.size(),cnt2=0;
	bool flag=true;
	while(flag){
		cnt2=0;
		flag=false;
		for(int i=1;i<cnt1;i++){
			if(a[i]==a[i+1]||a[i]==-1||a[i+1]==-1){
				b[++cnt2]=-1;
				i++;
				flag=true;
				continue;
			}
			b[++cnt2]=a[i];
		} 
		for(int i=1;i<=cnt2;i++) a[i]=b[i];
		cnt1=cnt2;
		//cout << cnt1 << " ";
	}
	cout << cnt1+1 << endl;
	
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> t;
	while(t--) solve();
	return 0;
}

C1,C2. Skibidus and Fanum Tax

贪心的，希望a[i]a[i]为满足限制条件的最小值，可以考虑将bb排序，这样子可以通过二分在logmlogm的复杂度找到满足条件的最小b[j]−a[i]b[j]-a[i]。将b[j]−a[i]b[j]-a[i]和a[i]a[i]的情况进行分类讨论取合法最小即可。
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=3e5+5;
const int inf=1e9+5;
int a[maxn];
int b[maxn];
int t;
int n,m;
void solve(){	
	cin >> n >> m;
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=1;i<=m;i++) cin >> b[i];
	sort(b+1,b+1+m);
	a[0]=-inf;
	for(int i=1;i<=n;i++){
		int l=1,r=m;
		while(l<r){
			int mid=(l+r)>>1;
			if(b[mid]-a[i]<a[i-1]) l=mid+1;
			else r=mid;
		}
		int ans1=b[l]-a[i];
		int ans2=a[i];
		if(ans1>=a[i-1]&&ans2>=a[i-1]){
			a[i]=min(ans1,ans2);
		}else if(ans1>=a[i-1]){
			a[i]=ans1;
		}else if(ans2>=a[i-1]){
			a[i]=ans2;
		}else{
			cout << "NO" << endl;
			return;
		}
	}
	cout << "YES" << endl;
	return;
}
signed main(){
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//	cout.tie(0);
	cin >> t;
	while(t--) solve();
	return 0;
}

D. Skibidus and Sigma

通过交换法发现，最优顺序为按照数组sum降序排序
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=3e5+5;
const int inf=1e9+5;
vector<int> a[maxn];
int sum[maxn];
int t,n,m;
int ans,cnt;
bool cmp(int x,int y){
	return x>y;
} 
void solve(){	
	ans=0;
	cin >> n >> m;
//	cnt=0;
	for(int i=1;i<=n;i++){
		sum[i]=0;
		cnt=0;
		for(int j=1;j<=m;j++){
			int x;
			cin >> x;
			sum[i]=sum[i]+x;
			cnt+=x;
			ans+=cnt; 
		}
	}
 
	sort(sum+1,sum+1+n,cmp);
	cnt=0;
	for(int i=1;i<=n;i++){
		ans+=cnt*m; 
		cnt+=sum[i];
	}
	cout << ans << endl;
	return;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> t;
	while(t--) solve();
	return 0;
}

E. Skibidus and Rizz

按题意构造就好了qwq
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=3e5+5;
const int inf=1e9+5;
int t,n,m,k;
void solve(){	
	cin >> n >> m >> k;
	if(abs(n-m)>k||(n<k&&m<k)) cout << -1;
	else {
		if(n<m){
			for(int i=1;i<=k;i++) cout << 1;
			for(int i=1;i<=max(m-k,n);i++){
				if(i<=n) cout << 0;	
				if(i<=m-k) cout << 1;
			}	
		}else{
			for(int i=1;i<=k;i++) cout << 0;
			for(int i=1;i<=max(m,n-k);i++){
				if(i<=m) cout << 1;	
				if(i<=n-k) cout << 0;
				
				
			}	
		}
	}
	cout << endl;
	return;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> t;
	while(t--) solve();
	return 0;
}

F. Skibidus and Slay

若存在严格众数，则必然存在相同数间长度为1或2的路径，于是枚举每个点，用map维护一下连边值就好了
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=5e5+5;
vector<int> e[maxn];
map<int,bool> s;
int ans[maxn];
int a[maxn];
int t,n;
void solve(){	
	cin >> n;
	for(int i=1;i<=n;i++) e[i].clear();
	for(int i=1;i<=n;i++) ans[i]=0;
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=1;i<n;i++){
		int u,v;
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		s.clear();
		s[a[i]]=true;
		for(auto to:e[i]){
			if(s[a[to]]) ans[a[to]]=true;
			s[a[to]]=true;
		}
	}
	for(int i=1;i<=n;i++) cout << ans[i];
	cout << endl;
	return;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> t;
	while(t--) solve();
	return 0;
}

G. Skibidus and Capping

容易发现，两数最小公倍数为为半素数，只有两种情况
  1. 两数为不相等素数
  2. 其中一数为半素数，另一数为前一数因数（考虑到半素数质因数次数和只有22，可以直接枚举）
可以考虑先用埃筛处理出所有数字的因数个数，然后用桶记录每个数字出现次数，然后扫一遍就好了
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+5;
int t,cnt,n,ans;
int a[maxn];
int p[maxn][30];
int len[maxn];
int Size[maxn];
void init(){
	for(int i=2;i<maxn;i++){
		p[i][++len[i]]=i;
		if(len[i]!=1) continue;
		for(int j=2;i*j<maxn;j++){
			p[i*j][++len[i*j]]=i;
		}
	}
}
void solve(){	
	cnt=0;
	ans=0;
	cin >> n;
	for(int i=1;i<=n;i++) Size[i]=0;
	for(int i=1;i<=n;i++){
		cin >> a[i];
		Size[a[i]]++; 
		if(len[a[i]]==1) cnt++;
	}
	for(int i=1;i<=n;i++){
		if(len[a[i]]==1){
			ans+=cnt-Size[a[i]];
		}else if(len[a[i]]==2){
			if(p[a[i]][1]*p[a[i]][1]!=a[i]) continue;
			ans+=Size[p[a[i]][1]]*2;
			ans+=Size[a[i]]+1;
		}else if(len[a[i]]==3){
			if(p[a[i]][1]*p[a[i]][2]!=a[i]) continue;
			ans+=(Size[p[a[i]][1]]+Size[p[a[i]][2]])*2;
			ans+=Size[a[i]]+1;
		}
	}
	ans/=2; 
	cout << ans << endl;
	return;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> t;
	init();
	while(t--) solve();
	return 0;
}

H. Bro Thinks He's Him

不会(悲

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...