牛客练习赛59题解报告
题目链接
A题题意：
给一个字符串
问字符串里有没有出现子序列"XiaoQiao"和“XiaoHuiHui”
题解：
用两个字符串存入，并对给定字符串进行On查询
AC代码
#include
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair pii;
typedef pair pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=2e5+10;
const ll inf=0x3f3f3f3f;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
string t="XiaoQiao";
string s;cin>>s;
int j=0;
for(int i=0;i<s.length();i++){
if(s[i]==t[j])j++;
if(j==t.length())break;
}
if(j<t.length()){cout<<"emm"<<endl;return 0;}
string tt="XiaoHuiHui";
j=0;
for(int i=0;i<s.length();i++){
if(s[i]==tt[j])j++;
if(j==tt.length())break;
}
if(j<tt.length())cout<<"emm"<<endl;
else cout<<"Happy"<<endl;
return 0;
}
B题
题意：
在二维平面中给定n个点，每个点有坐标 xi,yi
需要让这n个点连通
第i个点和第j个点建路所需要的花费为
| xxx2iyyyi — xxx1jyyyj + yyy2i( yyyi — 222xxxi ) — yyy2j( yyyj — 222xxxj ) |
问最少需要花费多少
题解：
将公式的iii和jjj分离开化简，这里只看iii
xxx2i yyyi + yyy2i ( yyyi — 222xxxi )
由此式子化简可得到
yyyi( xxxi — yyyi )2
所以将每个点的值计算出来，排序后让相邻两条建路是最短的
由于 | aaa1 – aaa2 + aaa2 – aaa3 ·············aaan-1 – aaan |
可以推出最后的结果应该是aaan – aaa1
AC代码
#include
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair pii;
typedef pair pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=2e5+10;
const ll inf=0x3f3f3f3f;
vector a;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n;cin>>n;
for(int i=1;i>x>>y;
a.pb(y*(x-y)*(x-y));
}
sort(all(a));
cout<<*(a.end()-1)-*a.begin()<<endl;
return 0;
}
C题
题意：
有xxx件材料aaa yyy件材料bbb 有两种方法合成装备
222件材料aaa和333件材料bbb可以合成一套装备
444件材料aaa和111件材料bbb可以合成一套装备
问最多能合成多少套装备
题解：
官方题解用的是三分
我用的方法是贪心，尽量先用222件材料aaa和333件材料bbb可以合成一套装备，当材料aaa和材料bbb剩余个数是4：1的的时候开始用第二种方法合成装备
设使两个材料之比变成4：1需要用第一种方法合成nnn次
x−2ny−3n=4\frac{x-2n}{y-3n}\quad = 4y−3nx−2n=4
化简可以得到
4y−x=10n4y-x=10n4y−x=10n
所以可以得到
ans={min(x/4,y),4y-x<0d+min(x/4,y),others
ans =
\begin{cases}
min(x/4,y), & \text{4$y$-$x$<$0$} \\
d+min(x/4,y), & \text{others}
\end{cases}
ans={min(x/4,y),d+min(x/4,y),4y-x<0others
（其中ddd表示化成4：1需要多少次）
d=4y−x10d=\frac{4y-x}{10}\quadd=104y−x
当然可能这个值会被整除，所以要通过四舍五入判断是应该多算一次第一种情况还是多算一次第二种情况，所以式子变为
d=4y−x+510d=\frac{4y-x+5}{10}\quadd=104y−x+5
AC代码
#include
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair pii;
typedef pair pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=2e5+10;
const ll inf=0x3f3f3f3f;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int t;cin>>t;
while(t--){
ll x,y;
cin>>x>>y;
if(4*y<x){cout<<y<<endl;continue;}
ll d=(4*y-x+5)/10;
d=min(x/2,d),d=min(y/3,d);
ll ans=0;
ans+=d;
x-=2*d,y-=3*d;
cout<<ans+min(x/4,y)<<endl;
}
return 0;
}
D题
题意：
A和BA和BA和B轮流取石子，一共有nnn个石子，AAA先开始取
假设当前的石子有kkk个
当k=1k=1k=1的时候B获得胜利
当k>=2k>=2k>=2的时候将式子分为 f(k)f(k)f(k) 和 k−f(k)k-f(k)k−f(k)两堆，必须取走其中一堆，f(k)=xf(k)=xf(k)=x为满足x∗2<=kx*2<=kx∗2<=k的最大整数
最后问谁能获得胜利
题解：
由于nnn的范围是1e181e181e18，所以不能采取暴力的方法计算
需要打表找规律
如果AAA上次连续赢的长度为yyy,可以发现BBB会连续赢2∗y−12*y-12∗y−1场
如果BBB上次连续赢的长度为yyy,可以发现AAA会连续赢2∗y+12*y+12∗y+1场
所以可以使用O(log 2 n)O(log~2~n)O(log 2 n)的复杂度去找n在谁获胜的区间里
AC代码
#include
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair pii;
typedef pair pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=2e5+10;
const ll inf=0x3f3f3f3f;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int t;cin>>t;
while(t--){
ll n;
cin>>n;
ll x=1,y=2;
bool f=1;
while(x<n){
if(!f)x+=y,y=2*y+1,f=1;
else x+=y,y=y*2-1,f=0;
}
if(!f)cout<<"XiaoHuiHui"<<endl;
else cout<<"XiaoQiao"<<endl;
}
return 0;
}
E题
题意：
一共有nnn堆石子，每堆有ai ai~ai 个石子，牛牛要把它们搬走
如果一次搬了kkk个石子，会对牛牛产生k2k^2k2的负担
牛牛最多搬mmm趟
牛能每次会将第xxx堆的石子数量变为vvv，所以每次需要重新计算牛牛的最小负担（总共qqq次）
题解：
由于数据较小
n,k,m,q<=400n,k,m,q<=400n,k,m,q<=400
可以采用dpdpdp的方法，但是由于石子的数量是改变的，可以通过线段树来优化dpdpdp
dp[i][j]dp[i][j]dp[i][j]是在线段树的第iii个结点，把第iii组分隔jjj次的最小负担(分隔j次，总共分出j+1组)(分隔j次，总共分出j+1组)(分隔j次，总共分出j+1组)
状态转移方程如下：
先将叶子结点的0到m−n次分割的最小情况计算出来先将叶子结点的0到m-n次分割的最小情况计算出来先将叶子结点的0到m−n次分割的最小情况计算出来
然后通过转移方程推广到各个非终端结点然后通过转移方程推广到各个非终端结点然后通过转移方程推广到各个非终端结点
dp[p][i+j]=min(dp[i][j],dp[lson][i]+dp[rson][j]dp[p][i+j]=min(dp[i][j],dp[lson][i]+dp[rson][j]dp[p][i+j]=min(dp[i][j],dp[lson][i]+dp[rson][j]
最后ans=dp[1][m−n]最后ans=dp[1][m-n]最后ans=dp[1][m−n]
AC代码
#include
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair pii;
typedef pair pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=2e5+10;
const ll inf=0x3f3f3f3f;
ll dp[410<<2][410];
int n,m;
void update(int p,int l,int r,int x,ll v){
if(l==r){
for(int i=0;i>1;
if(x<=mid)update(p<<1,l,mid,x,v);
else update(p<<1|1,mid+1,r,x,v);
for(int i=0;i<=m-n;i++)
dp[p][i]=inf*inf;
for(int i=0;i<=m-n;i++)
for(int j=0;i+j<=m-n;j++)
dp[p][i+j]=min(dp[p][i+j],dp[p<<1][i]+dp[p<>n>>m;
for(int i=1,x;i>x;
update(1,1,n,i,x);
}
int q;cin>>q;
while(q--){
int x,v;
cin>>x>>v;
update(1,1,n,x,v);
cout<<dp[1][m-n]<<endl;
}
return 0;
}
作者：zzugzx
