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

文章目录

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

  A-宇宙的终结

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

  （）

  #include#define endl '\n'#define int long longusing namespace std;int l,r;void solve() {cin>>l>>r;for(int i=l;iint x=i;int cnt=0;setif(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){coutios::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(lint mid=(l+r)/2;if(ans[mid].first=a[i]) r=mid;else l=mid+1;}if(laa=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;iios::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;iint n;cinn;vectorint 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) coutios::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;ix=x*10+s[i]-'0';}int cnt=(x+1)/2;mapif(t[i]=='R') mp[0]++;else mp[1]++;if(mp[0]==cnt){coutcoutios::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;iif(!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_mapans.clear();cinn;for(int i=1;iint x=a[i];for(int j=2;jif(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;iint a=find(tmp[i]),b=find(tmp[i-1]);if(a!=b) p[a]=b;}}//for(int i=1;iif(find(i)==i){first=i;break;}}for(int i=1;iif(find(i)==first) res1.push_back(a[i]);else res2.push_back(a[i]);}if(res2.size()==0){coutios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;    cint;while(t--) {solve();}return 0;}cinnm;for(int i=1;iif(a[i]==0) ok=true;}for(int i=1;iif(b[i]==0) ok=true;}dp1[0]=0;for(int i=1;idp1[i]=max(a[i],dp1[i-1]+a[i]);dp2[i]=min(a[i],dp2[i-1]+a[i]);}for(int i=1;idp3[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;ians1=max(ans1,dp1[i]);ans2=min(ans2,dp2[i]);}for(int i=1;ians3=max(ans3,dp3[i]);ans4=min(ans4,dp4[i]);}int ans=-2e9;if(ans10&&ans30) ans=max(ans,ans1*ans3);if(ans2coutcoutif(a[i]0) r1.push_back(a[i]);else r2.push_back(a[i]);}for(int i=1;iif(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());}//coutios::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,每个节点最多加1ans[x]++;ans[e[x][0]]++;//自底向上，如果有解的话，红色节点的儿子节点中一定有白色节点，对于红色节点，如果res%3==1，就算儿子节点的红色节点+1，它也会通过递归往下调整}}sum[x]=res;//x节点的子节点的权值之和}void solve() {cinns;for(int i=1;iif(s[i]=='R') mp[i+1]=1;}for(int i=2;iint x;cinx;e[x].push_back(i);//i的父节点为x}bool ok;for(int i=1;isum[i]=1,ans[i]=1;//每个节点先赋值为1ok=false;for(auto v:e[i]){//儿子节点中存在白色节点if(!mp[v]){ok=true;break;}}if(mp[i]&&!ok){//当前节点为红色且儿子节点中不存在白色节点,无解coutios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;//    cint;while(t--) {solve();}return 0;}