A 宇宙的终结

题目大意

在给定的某个区间内找到一个数，它是3个不同素数的积。

主要思路

这里范围比较小，而且是乘积的形式，如果其中最小的俩个数字分别是2和3，那么第三个数的最大取值也不会超过100/6，所以枚举前面的几个质数，然后暴力查找就可以了。

代码

#include<bits/stdc++.h>
using namespace std;int main()
{int l,r;int a[]={2,3,5,7,11,13,17,19,21};cin>>l>>r;for(int i=0;i<8;++i)for(int j=i+1;j<8;++j)for(int k=j+1;k<8;++k){if(l<=a[i]*a[j]*a[k]&&a[i]*a[j]*a[k]<=r){cout<<a[i]*a[j]*a[k];return 0;}}cout<<-1;return 0;
}

B 爱恨的纠葛

题目大意

给定俩数组，定义了一个叫做亲密度的东西就是ab俩数组一一对应相减取绝对值的最小值，现在对数组a进行排序，求亲密度最小时的a数组

主要思路

我们只需要找到其中一对就可以了，剩下的随便排都可以，可以把数组a预处理排序，然后对于每一个b数组中的数，在a数组钟进行二分查找最接近的那一个做差，然后记录哪一个是最接近的，最后在a数组中直接调换然后输出即可

代码

#include<bits/stdc++.h>
using namespace std;const int N = 1e5+10;
int a[N],b[N];int main()
{int n;cin>>n;for(int i=0;i<n;++i)cin>>a[i];for(int i=0;i<n;++i)cin>>b[i];if(n==1){cout<<a[0];return 0;}sort(a,a+n);
//     for(int i=0;i<n;++i)
//     {
//         cout<<a[i]<<" ";
//     }int minzhi=1e9+10;int minweizhi=0,mubiaoweizhi=0;for(int i=0;i<n;++i){int left=0,right=n-1;while(left<right){int mid=(left+right)>>1;if(a[mid]<b[i])left=mid+1;else right=mid;}int idx=left;int cha=INT_MAX;if(idx==0){if((int)abs(a[0]-b[i])<(int)abs(a[1]-b[i])){cha=(int)abs(a[0]-b[i]);idx=0;}else{cha=(int)abs(a[1]-b[i]);idx=1;}}else if(idx==n-1){if((int)abs(a[n-1]-b[i])<(int)abs(a[n-2]-b[i])){cha=(int)abs(a[n-1]-b[i]);idx=n-1;}else {cha=(int)abs(a[n-2]-b[i]);idx=n-2;}}else {int idx2;if((int)abs(b[i]-a[idx-1])<(int)abs(a[idx]-b[i])){cha=(int)abs(b[i]-a[idx-1]);idx2=idx-1;}else {cha=(int)abs(a[idx]-b[i]);idx2=idx;}if(cha>(int)abs(a[idx+1]-b[i])){cha=(int)abs(a[idx+1]-b[i]);idx2=idx+1;}idx=idx2;}if(cha<minzhi){minzhi=cha;minweizhi=i;mubiaoweizhi=idx;}}swap(a[minweizhi],a[mubiaoweizhi]);for(int i=0;i<n;++i){cout<<a[i]<<" ";}return 0;
}

C 心绪的解剖

题目大意

把一个正整数分解成三个斐波那契数的和

主要思路

简单打表看了一下，最多也就是48个数字，直接暴力枚举注意点技巧就行

代码

#include<bits/stdc++.h>
#define debug(x) cout<<#x<<" = "<<x<<"\n"
using namespace std;long long nums[50]{0,1};
int n=49;void init()
{for(int i=2;i<49;++i){nums[i]=nums[i-1]+nums[i-2];}
}void solve()
{int target;cin>>target;// 枚举 afor (int i = 0; i < n; ++i) {int k = n - 1;for (int j = i ; j < n; ++j) {while (j <= k && nums[i] + nums[j] + nums[k] > target) {--k;}if (nums[i] + nums[j] + nums[k] == target) {cout<<nums[i]<<" "<<nums[j]<<" "<<nums[k]<<"\n";return ;}}}cout<<"-1\n";
}int main()
{init();int t;cin>>t;while(t--){solve();}return 0;
}

D 友谊的套路

题目大意

已知红队每一局获胜的概率为p，请问最终这场对战出现让二追三的概率是多少

主要思路

出现让二追三的局面的时候也就意味着前面四局第一第二输了，第三第四是赢的，后面那一局不用管就好

代码

#include<bits/stdc++.h>
using namespace std;int main()
{double p;cin>>p;printf("%.8lf",pow(p,2)*pow(1-p,2));return 0;
}

E 未来的预言

题目大意

根据比赛信息，判断比赛得出胜负的时候，一共进行了多少局。输出比赛的情况

主要思路

一个简单的模拟，遍历字符串累加计数

代码

#include<bits/stdc++.h>
using namespace std;int main()
{char x;int n;cin>>x;cin>>x;cin>>n;string s;cin>>s;int len=s.size();int r=0,p=0;for(int i=0;i<len;++i){if(s[i]=='R')r++;else p++;if(r==(n+1)/2){cout<<"kou!\n"<<i+1;return 0;}else if(p==(n+1)/2){cout<<"yukari!\n"<<i+1;return 0;}}cout<<"to be continued.\n"<<len;return 0;
}

G 人生的起落

题目大意

形如$(a,b,a),a>b$的三元组称为“v-三元组”。 构造一个长度为n，和为S，且恰好有k个“v-三元组”的正整数数组。

主要思路

21212121这样够了后面全部放1，然后在考虑剩下数字，如果不够是-1，相同直接输出，如果还有剩余又看看还有没有空位，如果有就把剩下全给最前面（实际上是开头插入，如果给末尾可能刚刚好凑多一个212），没有空位就看看能不能对2集体加1，如果不能就-1，不然就一直+1直到不能操作，然后剩下数字丢给1(思路来自黄大师)

代码

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define pb push_back
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t;cin>>t;while(t--){int n,s,k;cin>>n>>s>>k;if(n==1&&k==0){cout<<s<<endl;continue;}else if( (n==1&&k!=0)||(n==2&&k!=0) ){cout<<-1<<endl;continue;}else if(n==2&&k==0){cout<<1<<" "<<s-1<<endl;continue;}else if(k==0){for(int i=1;i<n;i++) cout << "1" << ' ';cout << s-n+1 << endl;continue;}else if(n<2*k+1) {cout<<-1<<endl;continue;}else if(k&&s<n+k+1) {cout<<-1<<endl;continue;}else {ll t=(s-(n-(k+1)))/(k+1);vector<ll> ans;for(int i=1;i<=k;i++){ans.pb(t);ans.pb(1);s-=t+1;}ans.pb(t); s-=t;if(ans.size()==n){t=s/(n/2);for(int i=0;i<=n/2-1;i++){ans[i*2+1]+=t;s-=t;}t=0;while(s){ans[t*2+1]++;s--;t++;}if(n>1&&ans[1]==ans[0]) {cout << "-1\n";continue;}}else{t=ans.size();while(ans.size()<n){ans.pb(1);s--;}ans[t]+=s;}for(int i=0;i<=n-1;i++) cout << ans[i] << " \n"[i==n-1];}}return 0;
}

I 时空的交织

题目大意

选择一个子矩形，使得该子矩形所有元素的和尽可能大。

主要思路

假设选定的矩阵区间为 (r_i, r_j) : (c_i, c_j)，则子矩阵的和为：

问题转化为求数组 a 和 b 的一个非空连续子数组和乘积的最大值。

此外，a 数组和 b 数组的元素可以为负数，因此同时求出区间和的最大值和最小值，两两相乘取最大即可。

代码

#include<bits/stdc++.h>
#define debug(x) cout<<#x<<" = "<<x<<"\n"
using namespace std;const int N = 1e5+10;
long long a[N],b[N];int main()
{int n,m;long long maxzhi1=INT_MIN,maxzhi2=INT_MIN;cin>>n>>m;long long minzhi1=INT_MAX,minzhi2=INT_MAX;for(int i=0;i<n;++i){cin>>a[i];}for(int i=0;i<m;++i){cin>>b[i];}long long sum=0;long long sum2=0;for(int i=0;i<n;++i){if(sum+a[i]>0){sum+=a[i];maxzhi1=max(maxzhi1,sum);}else {sum=0;maxzhi1=max(maxzhi1,a[i]);}//if(sum2+a[i]<0){sum2+=a[i];minzhi1=min(minzhi1,sum2);}else {sum2=0;minzhi1=min(minzhi1,a[i]);}}
///sum=0;sum2=0;for(int i=0;i<m;++i){if(sum+b[i]>0){sum+=b[i];maxzhi2=max(maxzhi2,sum);}else {sum=0;maxzhi2=max(maxzhi2,b[i]);}/if(sum2+b[i]<0){sum2+=b[i];minzhi2=min(minzhi2,sum2);}else {sum2=0;minzhi2=min(minzhi2,b[i]);}}long long ans=INT_MIN;ans=max(ans,minzhi1*minzhi2);ans=max(ans,maxzhi1*maxzhi2);ans=max(ans,minzhi1*maxzhi2);ans=max(ans,maxzhi1*minzhi2);cout<<ans;return 0;
}

J 绝妙的平衡

题目大意

给定一棵有根树，若干个节点为红色。 为每个节点赋值1或2，使得每个以红色节点为根的子树，其节点值之和为3的倍数。

主要思路

对于每个红色节点，如果它没有白色子节点，则它的子树除它以外的和已经是的倍数，它为或都不可能再使它的子树和为的倍数。

如果它至少有1个白色子节点，则它和白色子节点可以配合使得它的子树和为的倍数。

因此，按DFS逆序遍历，白色节点先赋值为。若红色节点除其本身外，和不是的倍数，则用它补上；否则将任一白色子节点改为，它赋为。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=100010;
vector<int> fa[N];
bool flag=1;
int sum[N];//每个根节点的子树权值之和
int tri[N]; //每个节点的值
char color[N];
int n;
void dfs(int u)
{bool st=0;if(color[u]=='R') st=1; //如果是红树先假设子树全为红树for(auto k:fa[u])  //遍历他的所有子树{dfs(k);  //搜索他的子树 if(color[k]=='W')  // 如果是白色假设条件不成立并且将这棵树的权值加到他的根节点  {st=0;sum[u]+=sum[k];  }}if(st) flag=0; //如果该节点为红色并且该结点的子树全为红色则不满足条件
}
void dfs1(int u)
{if(color[u]=='R'){if(sum[u]%3==1){tri[u]=2;for(auto k:fa[u]){if(color[k]!='R'){tri[k]=2;break;}}}else if(sum[u]%3==2){tri[u]=2;}}for(auto k:fa[u]) dfs1(k);
}
int main()
{cin>>n;cin>>color+1;for(int i=1;i<=n;i++){tri[i]=1;sum[i]=1;}int p;for(int i=1;i<=n-1;i++){cin>>p;fa[p].push_back(i+1);}dfs(1);  //判断是有解并且将每个根节点的权值计算出来if(!flag){cout<<"-1"<<endl;return 0;}dfs1(1);for(int i=1;i<=n;i++)cout<<tri[i];
}