牛客小白月赛104（未补）

A 小红购买装备

题意：给定n件装备，每种装备提供ai的攻击和bi的防御，价格为ci，小红已有t的金币和攻击x，防御为y的装备，卖给商店可以回收z金币，最大攻击+防御是多少

分析：枚举即可

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void sol(){ll n,x,y,z,t;cin>>n>>x>>y>>z>>t;ll ans=x+y;ll a,b,c;for(int i=1;i<=n;i++){cin>>a>>b>>c;if(a+b>ans&&c<=z+t){ans=max(ans,a+b);}}cout<<ans<<endl;
}
int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t=1;while(t--)sol();return 0;
}
​

B 小红招募英雄

题意：给定1，2，3，4，5的概率，抽十次，求有4或5两次及以上的概率

分析：用1减去45只出现1次的情况，再减去45都没出现的情况

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void sol(){double a[10];for(int i=1;i<=5;i++)cin>>a[i];double p0=a[1]+a[2]+a[3],p1=a[4]+a[5];printf("%.10f\n",1-10*p1*(pow(p0,9))-pow(p0,10));
​
}
int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t=1;while(t--)sol();return 0;
}
​

C 小红打怪

题意：给定n个怪物，每个回合：所有怪物减一；任选1只减一；对相邻怪物都减一

分析：用二分找出符合条件的最小次数。找符合条件的只要贪心找出每次施法即可。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll a[N],b[N],ma=0,mi=1e9,sum,n;
ll f(ll x){for(int i=1;i<=n;i++)a[i]=b[i];for(int i=1;i<=n;i++){a[i]-=x;if(a[i]<0)a[i]=0;}ll x1=x,x2=x;for(int i=1;i<=n;i++){if(a[i+1]!=0&&a[i]!=0){if(a[i+1]>a[i]){if(x1-a[i]<0){a[i+1]-=x1;a[i]-=x1;x1=0;break;}else{x1-=a[i];a[i+1]-=a[i];a[i]=0;if(x1==0)break;}}else{if(x1-a[i+1]<0){a[i+1]-=x1;a[i]-=x1;x1=0;break;}else{x1-=a[i+1];a[i]-=a[i+1];a[i+1]=0;if(x1==0)break;}   }}}for(int i=1;i<=n;i++){if(a[i]>0){if(x2-a[i]<0){a[i]-=x2;x2=0;}else{x2-=a[i];a[i]=0;}}}ll k=0;for(int i=1;i<=n;i++){k+=a[i];}if(k==0)return 1;else{if(k<=x2+x1)return 1;else return 0;}
}
void sol(){cin>>n;for(int i=1;i<=n;i++)cin>>b[i];ll l=1,r=1e9;while(l<r){ll mid=(l+r)/2;if(f(mid)==1)r=mid;else l=mid+1;}cout<<l<<endl;
​
}
int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t=1;while(t--)sol();return 0;
}
​

D 小红开锁

题意：给定n层锁，每次可以选择一层锁按顺时针移动一个格子，想让某个象限全是X，这个锁最少操作几次可以解开？

分析：用vector存入每一层的字符。共有四种情况，分别是第一二三四象限，判断连续X的最右边的位置，判断到每一个象限的距离，取四个象限的最小值

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
void sol(){int n;cin>>n;char a[300][300];ll k1=0,k2=0,k3=0,k4=0;vector<char>v[2*n];for(int i=1;i<=n*2;i++){for(int j=1;j<=n*2;j++){cin>>a[i][j];}}for(int i=1;i<=n*2;i++){//横 for(int j=i;j<=2*n-i+1;j++){v[i].push_back(a[i][j]);} }for(int i=1;i<=2*n;i++){//右 for(int j=i+1;j<=2*n-i+1;j++){if(2*n-i+1<=2*n&&2*n-i+1>=1&&j<=2*n&&j>=1)v[i].push_back(a[j][2*n-i+1]);}}for(int i=1;i<=2*n;i++){//横 for(int j=i+1;j<=2*n-i+1;j++){if(2*n-i+1>=1&&2*n-j+1>=1&&2*n-i+1<=2*n&&2*n-j+1<=2*n)v[i].push_back(a[2*n-i+1][2*n-j+1]);}}for(int i=1;i<=2*n;i++){//左 for(int j=i+1;j<=2*n-i;j++){if(2*n-j+1>=1&&2*n-j+1<=2*n&&i>=1&&i<=2*n){v[i].push_back(a[2*n-j+1][i]);}}}for(int i=1;i<=n;i++){ll len=v[i].size();ll p=-1;int l=0;for(int j=0;j<len;j++){if(v[i][j]=='X'&&(p==-1||j-1==-1||(v[i][j-1]=='X'&&l==0))){p=j;}if(v[i][j]=='X'&&v[i][j+1]=='O')l=1;} if(len/4/2<p)k1+=len-p+len/4/2;else k1+=len/4/2-p;if(len/4/2+len/4<p)k2+=len-p+len/4/2+len/4;else k2+=len/4/2+len/4-p;if(len/4/2+len/4+len/4<p)k3+=len-p+len/4/2+len/4+len/4;else k3+=len/4/2+len/4+len/4-p;if(len/4/2+len/4+len/4+len/4<p)k4+=len-p+len/4/2+len/4+len/4+len/4;else k4+=len/4/2+len/4+len/4+len/4-p;}cout<<min(min(k1,k2),min(k3,k4))<<endl;
​
}
int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t=1;while(t--)sol();return 0;
}
​