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

分类:热门推荐日期:2024-03-18浏览:1评论:0

文章目录

  • 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<=r;i++){int x=i;
		int cnt=0;
		sets;
		for(int j=2;j<=x/j;j++){if(x%j==0){while(x%j==0){x/=j;
					s.insert(j);
					cnt++;
				}
			}
		}
		if(x>1) 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;
//    cin>>t;
	while(t--) {solve();
	}
	return 0;
}

    B-爱恨的纠葛

    一开始题目读错了，亲密度看成是和了，后面发觉是最小值

    只要找到两个数差值最小是多少，然后那两个数对应，其它随意排

    利用二分，先将b升序，枚举a中的每一个数，在b中二分出离a最近的数，然后找到差值最小的

    #include #define endl '\n'
#define int long long
using namespace std;
typedef pairPII;
const int N = 1e5 + 10;
int n;
int a[N];
void solve() {cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	vectorans;
	for (int i = 1; i <= n; 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 <= n; i++) {int l=0,r=ans.size()-1;
		while(lint mid=(l+r)/2;
			if(ans[mid].first>=a[i]) r=mid;
			else l=mid+1;
		}
		if(l<(int)ans.size()){aa=abs(ans[l].first-a[i]);
			if(res>aa) res=aa,aaa=i,bbb=l;
		}
		if(l>0){aa=abs(ans[l-1].first-a[i]);
			if(res>aa) 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<=n;i++) cout<ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
//    cin>>t;
	while (t--) {solve();
	}
	return 0;
}

    C-心绪的解剖

    斐波那契数非常的少，第45个就已经超出1e9了，先全部存起来

    然后优先选大的（利用二分），然后选小的，选三个数，并减去，如果最后剩下的数大于0，那么无解

    #include#define endl '\n'
#define int long long
using namespace std;
const int N=1e5+10;
int f[N];
void solve() {f[0]=0;
	f[1]=1;
	for(int i=2;i<=45;i++) f[i]=f[i-1]+f[i-2];
	int q;
	cin>>q;
	while(q--){int n;
		cin>>n;
		vectorans;
		int l=0,r=45;
		while(lint mid=(l+r+1)/2;
			if(f[mid]<=n) l=mid;
			else r=mid-1;
		}
		ans.push_back(f[l]);
		n-=f[l];
		l=0,r=45;
		while(lint mid=(l+r+1)/2;
			if(f[mid]<=n) l=mid;
			else r=mid-1;
		}
		ans.push_back(f[l]);
		n-=f[l];
		l=0,r=45;
		while(lint mid=(l+r+1)/2;
			if(f[mid]<=n) l=mid;
			else r=mid-1;
		}
		ans.push_back(f[l]);
		n-=f[l];
		if(n) cout<<-1<for(auto v:ans) cout<ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=1;
//    cin>>t;
	while(t--) {solve();
	}
	return 0;
}

    D-友谊的套路

    当时就想着小红让2追3，忘记考虑小紫让2追3了

    小红让2追3的概率为 ( 1 − p ) 2 (1-p)^2 (1−p)2* p 3 p^3 p3

    小紫让2追3的概率为 p 2 p^2 p2* ( 1 − p ) 3 (1-p)^3 (1−p)3

    两者概率加起来

    #include#include#define endl '\n'
#define int long long
using namespace std;
double p;
void solve() {cin>>p;
	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;
//    cin>>t;
	while(t--) {solve();
	}
	return 0;
}

    E-未来的预言

    模拟即可

    #include#define endl '\n'
#define int long long
using namespace std;
string s;
string t;
void solve() {cin>>s>>t;
	int x=0;
	for(int i=2;i<(int)s.size();i++){x=x*10+s[i]-'0';
	}
	int cnt=(x+1)/2;
	mapmp;
	for(int i=0;i<(int)t.size();i++){if(t[i]=='R') mp[0]++;
		else mp[1]++;
		if(mp[0]==cnt){cout<<"kou!"<cout<<"yukari!"<ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=1;
//    cin>>t;
	while(t--) {solve();
	}
	return 0;
}

    F-命运的抉择

    gcd(a,b)可以将a质因数分解，将b质因数分解，然后将公共的质因数乘起来

    有公共质因子的两个数应该在同一个集合中

    枚举质因子，把它的倍数都放进同一个集合中

    如果最后全合成一个集合了，那么无解

    集合的合并与查找–>并查集

    #include#define endl '\n'
#define int long long
using namespace std;
const int N=1e6+10;
int p[N];
int find(int x){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<=n;i++){if(!st[i]) prime[cnt++]=i;
		for(int j=0;prime[j]<=n/i;j++){st[prime[j]*i]=true;
			if(i%prime[j]==0) break;
		}
	}
}
int n;
int a[N];
unordered_map>ans;
void solve() {ans.clear();
	cin>>n;
	for(int i=1;i<=n;i++) p[i]=i;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){int x=a[i];
		for(int j=2;j<=x/j;j++){if(x%j==0){while(x%j==0){x/=j;
					ans[j].push_back(i);//含有质因子j的数的下标
				}
			}
		}
		if(x>1){ans[x].push_back(i);
		}
	}
	for(auto v:ans){auto tmp=v.second;
		for(int i=1;i<(int)tmp.size();i++){int a=find(tmp[i]),b=find(tmp[i-1]);
			if(a!=b) p[a]=b;
		}
	}
//	for(int i=1;i<=n;i++) cout<res1,res2;
	int first;
	for(int i=1;i<=n;i++){if(find(i)==i){first=i;
			break;
		}
	}
	for(int i=1;i<=n;i++){if(find(i)==first) res1.push_back(a[i]);
		else res2.push_back(a[i]);
	}
	if(res2.size()==0){cout<<-1<<' '<<-1<ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=1;
    cin>>t;
	while(t--) {solve();
	}
	return 0;
}

    I-时空的交织

    求出数组a连续子段为正的最大，为负的最小，同理，对b

    然后正正得正，负负得负，取max

    如果相乘不能为正，那么特判有没有0，如果有0，答案为0

    如果没有0，那么找一个最小的单元格

    #include#define endl '\n'
#define int long long
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int dp1[N],dp2[N],dp3[N],dp4[N];
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];
	bool ok=false;
	for(int i=1;i<=n;i++){if(a[i]==0) ok=true;
	}
	for(int i=1;i<=m;i++){if(b[i]==0) ok=true;
	}
	dp1[0]=0;
	for(int i=1;i<=n;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<=m;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<=n;i++){ans1=max(ans1,dp1[i]);
		ans2=min(ans2,dp2[i]);
	}
	for(int i=1;i<=m;i++){ans3=max(ans3,dp3[i]);
		ans4=min(ans4,dp4[i]);
	}
	int ans=-2e9;
	if(ans1>0&&ans3>0) ans=max(ans,ans1*ans3);
	if(ans2<0&&ans4<0) ans=max(ans,ans2*ans4);
	if(ans>0){cout<cout<<0<r1,r2,r3,r4;
	for(int i=1;i<=n;i++){if(a[i]>0) r1.push_back(a[i]);
		else r2.push_back(a[i]);
	}
	for(int i=1;i<=m;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;
//    cin>>t;
	while(t--) {solve();
	}
	return 0;
}

    J-绝妙的平衡

    参考2024牛客寒假算法基础集训营6(C,F,G,I,J) - 知乎 (zhihu.com)

    如果一个红点的儿子全是红点，那它必须也是3的倍数，不可能，这样是无解的，因为只能赋值1和2

    当一个红色节点没有子节点或者所有的子节点均为红色时无解。其他情况下可以进行贪心，将所有的节点赋值为1，然后根据红色节点的子节点权值和来修改该红色节点和它的任意一个白色节点

    #include#define endl '\n'
#define int long long
using namespace std;
const int N=1e5+10;
int sum[N],ans[N];
int n;
string s;
vector>e(N);
mapmp;
void dfs(int x){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() {cin>>n>>s;
	for(int i=1;i<=n;i++) e[i].clear();
	mp.clear();
	for(int i=0;iif(s[i]=='R') mp[i+1]=1;
	}
	for(int i=2;i<=n;i++){int x;
		cin>>x;
		e[x].push_back(i);//i的父节点为x
	}
	bool ok;
	for(int i=1;i<=n;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<<-1<ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=1;
//    cin>>t;
	while(t--) {solve();
	}
	return 0;
}

相关推荐

关于我们常见问题广告服务免责声明联系我们
Powered By Z-BlogPHP 1.7.3 Theme By 优美主题
Copyright Your WebSite.Some Rights Reserved. 浙ICP备2023018783号