2024牛客寒假算法基础集训营6
打一半就收拾行李了，不想开学呜呜呜(应该是lzgg出的题)
A.宇宙的终结
思路
数据不大才100，所以模拟完全可以过去
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin()+1,x.end()
std::vector<int> a;
bool prime(int x){
if(x<2){
return false;
}
if(x==2)
return true;
for(int i=2;i<=sqrt(x);i++){
if(x%i==0){
return false;
}
}
return true;
}
void init(){
for(int i=1;i<=100;i++){
if(prime(i)){
a.push_back(i);
}
}
}
void solve(){
int l,r;
cin>>l>>r;
// if(r<42||l>42) cout<<-1<<endl;
if(r<30){
cout<<-1<<endl;
return ;
}
for(int i=l;i<=r;i++){
for(int j=0;j<a.size();j++){
if(i%a[j]==0){
for(int k=0;k<a.size();k++){
if(a[j]!=a[k]){
if((i/a[j])%a[k]==0){
if(prime(i/a[j]/a[k])&&(i/a[j]/a[k])!=a[j]&&(i/a[j]/a[k])!=a[k]){
cout<<i<<endl;
return ;
}
}
}
}
}
}
}
cout<<-1<<endl;
}
signed main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int t=1;
// cin>>t;
init();
while(t--){
solve();
}
return 0;
}
B.爱恨的纠葛
思路
之前在cf也遇到过一个类似的问题，但他是有选择的让总差值最大传送门，这个题就比较简单了，直接让其中一对最小就可以了，这里我们就可以二分处理一下，但是不能只处理二分得到的数字，他的两边也需要处理一下。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin()+1,x.end()
const int N=1e5+10;
int a[N],b[N];
void solve() {
int n;
cin>>n;
int ans = 1e18;
for(int i=1; i<=n; ++i) cin>>a[i];
for(int i=1; i<=n; ++i) cin>>b[i];
sort(a+1, a+n+1);
int i1, i2;
for(int i=1; i<=n; ++i)
{
int x = lower_bound(a+1, a+n+1, b[i]) - a;
if(abs(a[x]-b[i])<ans) {
i1 = i, i2 = x;
ans = abs(a[x]-b[i]);
}
if(abs(a[x-1]-b[i])<ans) {
i1 = i, i2 = x-1;
ans = abs(a[x-1]-b[i]);
}
}
swap(a[i1], a[i2]);
for(int i=1; i<=n; ++i) {
cout<<a[i]<<' ';
}
}
signed main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int t=1;
// cin>>t;
while(t--){
solve();
}
return 0;
}
D.友谊的套路
思路
概率问题,要想出现让二追三,前四场必须是负负胜胜
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin()+1,x.end()
void solve(){
double p;
cin>>p;
double ans=(1.0-p)*(1.0-p)*p*p;
printf("%.6f\n",ans);
return ;
}
signed main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
// ios::sync_with_stdio(false); cin.tie(nullptr);
int t=1;
// cin>>t;
while(t--){
solve();
}
return 0;
}
E.未来的预言
思路
一个模拟而已,但我犯了大忌,我自认为一定是十场以内了,很明显这是不对的,赛时想当然了,大忌啊
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin()+1,x.end()
void solve(){
string s;
cin>>s;
// int x=s[s.size()-1]-'0';
string s1="";
for(int i=2;i<s.size();i++){
s1+=s[i];
}
int x=0;
for(int i=0;i<s1.size();i++){
x=x*10+(s1[i]-'0');
}
// cout<<x<<endl;
int ans1=0;
int ans2=0;
int ans=0;
string s2;
cin>>s2;
for(int i=0;i<s2.size();i++){
char str=s2[i];
ans++;
if(str=='R'){
ans1++;
if(ans1==(x+1)/2){
// cout<<ans<<endl;
cout<<"kou!"<<endl;
cout<<ans<<endl;
return ;
}
}
else if(str=='P'){
ans2++;
if(ans2==(x+1)/2){
// cout<<ans<<endl;
cout<<"yukari!"<<endl;
cout<<ans<<endl;
return ;
}
}
}
// cout<<ans<<endl;
cout<<"to be continued."<<endl;
cout<<ans<<endl;
return ;
}
signed main(){
int t=1;
while(t--){
solve();
}
return 0;
}
C.心绪的解剖
思路:
我们可以预处理一下,我们可以打表发现小于1e9的斐波那契数列长度其实不大,所以我们预处理一下就好了
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin()+1,x.end()
const int N=1e5+10;
int l=0;
struct node
{
int a,b,c;
};
int f[N];
std::map<int, int> mp;
std::map<int, node> mp1;
void chuli(){
f[1]=0;
f[2]=1;
l=2;
for(int i=3;i<=N;i++){
f[i]=f[i-1]+f[i-2];
l++;
if(f[i]>=1e9){
return ;
}
}
}
void init(){
chuli();
for(int i=0;i<l;i++){
for(int j=0;j<l;j++){
for(int k=0;k<l;k++){
mp[f[i]+f[j]+f[k]]++;
mp1[f[i]+f[j]+f[k]]={f[i],f[j],f[k]};
}
}
}
}
void solve(){
int n;
cin>>n;
if(mp[n]){
cout<<mp1[n].a<<" "<<mp1[n].b<<" "<<mp1[n].c<<endl;
return ;
}
else{
cout<<-1<<endl;
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
init();
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
I.时空的交织
思路
前缀和+数学问题
Code
//暂时没有写，开学再补