2024牛客寒假算法基础集训营6

文章目录

• A-宇宙的终结
• B-爱恨的纠葛
• C-心绪的解剖
• D-友谊的套路
• E-未来的预言
• F-命运的抉择
• I-时空的交织
• J-绝妙的平衡

  A-宇宙的终结

  用试除法分解质因数，判断是否刚好分解为三个不同的质数

  
  （图片来源网络，侵删）

  #include
  #define endl '\n'
  #define int long long
  using namespace std;
  int l,r;
  void solve() {
  	cin>>l>>r;
  	for(int i=l;i
  		int x=i;
  		int cnt=0;
  		set
  			if(x%j==0){
  				while(x%j==0){
  					x/=j;
  					s.insert(j);
  					cnt++;
  				}
  			}
  		}
  		if(x1) cnt++,s.insert(x);
  		if(cnt==3&&(int)s.size()==3){
  			cout
  	ios::sync_with_stdio(false);
  	cin.tie(0);
  	cout.tie(0);
  	int t=1;
  //    cint;
  	while(t--) {
  		solve();
  	}
  	return 0;
  }
  
  	cin  n;
  	for (int i = 1; i 
  		int x;
  		cin  x;
  		ans.push_back({x, i});
  	}
  	sort(ans.begin(), ans.end());
  	int res = 2e9;
  	int aa;
  	int aaa, bbb;
  	for (int i = 1; i 
  		int l=0,r=ans.size()-1;
  		while(l
  			int mid=(l+r)/2;
  			if(ans[mid].first=a[i]) r=mid;
  			else l=mid+1;
  		}
  		if(l
  			aa=abs(ans[l].first-a[i]);
  			if(resaa) res=aa,aaa=i,bbb=l;
  		}
  		if(l0){
  			aa=abs(ans[l-1].first-a[i]);
  			if(resaa) res=aa,aaa=i,bbb=l-1;
  		}
  	}
  	//a[aaa]和b[ans[bbb].second]对应
  	swap(a[aaa],a[ans[bbb].second]);
  	for(int i=1;i
  	ios::sync_with_stdio(false);
  	cin.tie(0);
  	cout.tie(0);
  	int t = 1;
  //    cint;
  	while (t--) {
  		solve();
  	}
  	return 0;
  }
  
  	f[0]=0;
  	f[1]=1;
  	for(int i=2;i
  		int n;
  		cinn;
  		vector
  			int mid=(l+r+1)/2;
  			if(f[mid]
  			int mid=(l+r+1)/2;
  			if(f[mid]
  			int mid=(l+r+1)/2;
  			if(f[mid]
  			for(auto v:ans) cout
  	ios::sync_with_stdio(false);
  	cin.tie(0);
  	cout.tie(0);
  	int t=1;
  //    cint;
  	while(t--) {
  		solve();
  	}
  	return 0;
  }
  
  	cinp;
  	double ans1=pow(p,3)*pow(1-p,2);
  	double ans2=pow(p,2)*pow(1-p,3);
  	double ans=ans1+ans2;
  	printf("%.10f\n",ans);
  }
  signed main() {
  //	ios::sync_with_stdio(false);
  //	cin.tie(0);
  //	cout.tie(0);
  	int t=1;
  //    cint;
  	while(t--) {
  		solve();
  	}
  	return 0;
  }
  
  	cinst;
  	int x=0;
  	for(int i=2;i
  		x=x*10+s[i]-'0';
  	}
  	int cnt=(x+1)/2;
  	map
  		if(t[i]=='R') mp[0]++;
  		else mp[1]++;
  		if(mp[0]==cnt){
  			cout
  			cout
  	ios::sync_with_stdio(false);
  	cin.tie(0);
  	cout.tie(0);
  	int t=1;
  //    cint;
  	while(t--) {
  		solve();
  	}
  	return 0;
  }
  
  	if(p[x]!=x) p[x]=find(p[x]);
  	return p[x];
  }
  bool st[N];
  int prime[N];
  int cnt;
  //欧拉筛
  void get_prime(int n){
  	for(int i=2;i
  		if(!st[i]) prime[cnt++]=i;
  		for(int j=0;prime[j]
  			st[prime[j]*i]=true;
  			if(i%prime[j]==0) break;
  		}
  	}
  }
  int n;
  int a[N];
  unordered_map
  	ans.clear();
  	cinn;
  	for(int i=1;i
  		int x=a[i];
  		for(int j=2;j
  			if(x%j==0){
  				while(x%j==0){
  					x/=j;
  					ans[j].push_back(i);//含有质因子j的数的下标
  				}
  			}
  		}
  		if(x1){
  			ans[x].push_back(i);
  		}
  	}
  	for(auto v:ans){
  		auto tmp=v.second;
  		for(int i=1;i
  			int a=find(tmp[i]),b=find(tmp[i-1]);
  			if(a!=b) p[a]=b;
  		}
  	}
  //	for(int i=1;i
  		if(find(i)==i){
  			first=i;
  			break;
  		}
  	}
  	for(int i=1;i
  		if(find(i)==first) res1.push_back(a[i]);
  		else res2.push_back(a[i]);
  	}
  	if(res2.size()==0){
  		cout
  	ios::sync_with_stdio(false);
  	cin.tie(0);
  	cout.tie(0);
  	int t=1;
      cint;
  	while(t--) {
  		solve();
  	}
  	return 0;
  }
  
  	cinnm;
  	for(int i=1;i
  		if(a[i]==0) ok=true;
  	}
  	for(int i=1;i
  		if(b[i]==0) ok=true;
  	}
  	dp1[0]=0;
  	for(int i=1;i
  		dp1[i]=max(a[i],dp1[i-1]+a[i]);
  		dp2[i]=min(a[i],dp2[i-1]+a[i]);
  	}
  	for(int i=1;i
  		dp3[i]=max(b[i],dp3[i-1]+b[i]);
  		dp4[i]=min(b[i],dp4[i-1]+b[i]);
  	}
  	int ans1=0,ans2=0,ans3=0,ans4=0;
  	for(int i=1;i
  		ans1=max(ans1,dp1[i]);
  		ans2=min(ans2,dp2[i]);
  	}
  	for(int i=1;i
  		ans3=max(ans3,dp3[i]);
  		ans4=min(ans4,dp4[i]);
  	}
  	int ans=-2e9;
  	if(ans10&&ans30) ans=max(ans,ans1*ans3);
  	if(ans2
  		cout
  		cout
  		if(a[i]0) r1.push_back(a[i]);
  		else r2.push_back(a[i]);
  	}
  	for(int i=1;i
  		if(b[i]0) r3.push_back(b[i]);
  		else r4.push_back(b[i]);
  	}
  	if(r1.size()) sort(r1.begin(),r1.end());
  	if(r2.size()){
  		sort(r2.begin(),r2.end());
  		reverse(r2.begin(),r2.end());
  	}
  	if(r3.size()) sort(r3.begin(),r3.end());
  	if(r4.size()){
  		sort(r4.begin(),r4.end());
  		reverse(r4.begin(),r4.end());
  	}
  //	cout
  	ios::sync_with_stdio(false);
  	cin.tie(0);
  	cout.tie(0);
  	int t=1;
  //    cint;
  	while(t--) {
  		solve();
  	}
  	return 0;
  }
  
  	int res=1;
  	for(auto v:e[x]){
  		dfs(v);
  		if(!mp[v]) res+=sum[v];//加上白色节点上的数字,红色节点不用管,因为已经是3的倍数了
  	}
  	if(mp[x]){
  		if(res%3==2) ans[x]++;//权值和加1变为3的倍数
  		else if(res%3==1){//权值和加2为3的倍数
  			//将节点x加1,以及它的一个子节点加1,一开始赋值为1,每个节点最多加1
  			ans[x]++;
  			ans[e[x][0]]++;//自底向上，如果有解的话，红色节点的儿子节点中一定有白色节点，对于红色节点，如果res%3==1，就算儿子节点的红色节点+1，它也会通过递归往下调整
  		}
  	}
  	sum[x]=res;//x节点的子节点的权值之和
  }
  void solve() {
  	cinns;
  	for(int i=1;i
  		if(s[i]=='R') mp[i+1]=1;
  	}
  	for(int i=2;i
  		int x;
  		cinx;
  		e[x].push_back(i);//i的父节点为x
  	}
  	bool ok;
  	for(int i=1;i
  		sum[i]=1,ans[i]=1;//每个节点先赋值为1
  		ok=false;
  		for(auto v:e[i]){//儿子节点中存在白色节点
  			if(!mp[v]){
  				ok=true;
  				break;
  			}
  		}
  		if(mp[i]&&!ok){//当前节点为红色且儿子节点中不存在白色节点,无解
  			cout
  	ios::sync_with_stdio(false);
  	cin.tie(0);
  	cout.tie(0);
  	int t=1;
  //    cint;
  	while(t--) {
  		solve();
  	}
  	return 0;
  }