A-获得木头_牛客小白月赛92 (nowcoder.com)
void solve()
{
cin>>n;
cout<<n*2*4<<endl;
}
B-采矿时间到!_牛客小白月赛92 (nowcoder.com)
思路:先把矿道两边的矿石挖走,在把里面的矿石挖走即可
void solve()
{
cin>>n>>m;
for(int i=1;i<=5;i++)
for(int j=1;j<=n;j++)cin>>s[i][j];
int res=0,ans=0;
for(int i=1;i<=n;i++)
{
if(s[2][i]=='*')res++;
if(s[4][i]=='*')res++;
}
if(res>=m)
{
cout<<min(res,m)<<endl;
return;
}
int cnt=0;
for(int i=1;i<=n;i++)
{
if(s[2][i]=='*'&&s[1][i]=='*')cnt++;
if(s[4][i]=='*'&&s[5][i]=='*')cnt++;
if(s[2][i]=='#'&&s[1][i]=='*')ans++;
if(s[4][i]=='#'&&s[5][i]=='*')ans++;
}
int t=m-res;
if(t<=cnt)cout<<res+min(t,cnt)<<endl;
else cout<<res+cnt+min(ans,(t-cnt)/2)<<endl;
}
C-耕种时间到!_牛客小白月赛92 (nowcoder.com)
思路:模拟,因为每次所有的种子都要操作所有种子的等级都会变成
⌊
a
i
3
⌋
\left \lfloor \frac{a_{i}}{3}\right \rfloor
⌊3ai⌋所以只要看最大的
a
i
a_{i}
ai,发现最多模拟
l
o
g
3
1
0
9
log_{3}{10^{9}}
log3109即可把所有情况枚举出来。
bool cmp(const pair<int, int> left,const pair<int,int> right){
return left.x < right.x;
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
cin>>x;
map<int,int>mp;
for(int i=1;i<=n;i++)
mp[a[i]]++;
auto t=max_element(mp.begin(),mp.end(),cmp);
int res=max(0ll,mp[x]);
for(int i=1;i<=40;i++)
{
map<int,int>cnt;
for(auto x:mp)
cnt[(x.first+2)/3]=cnt[(x.first+2)/3]+2*x.second;
auto t=max_element(cnt.begin(),cnt.end(),cmp);
if(t->first<x)break;
res=max(res,cnt[x]);
mp=cnt;
}
cout<<res<<endl;
}
D-探索的时光_牛客小白月赛92 (nowcoder.com)
思路:把题目给的公式
f
(
i
)
=
(
i
−
x
)
2
∗
a
i
f(i)=(i-x)^{2}*a_{i}
f(i)=(i−x)2∗ai拆开变成
f
(
i
)
=
i
2
∗
a
i
+
x
2
∗
a
i
−
2
∗
i
∗
x
∗
a
i
f(i)=i^{2}*a_{i}+x^{2}*a_{i}-2*i*x*a_{i}
f(i)=i2∗ai+x2∗ai−2∗i∗x∗ai
然后就会变成
∑
i
=
1
n
f
(
i
)
=
x
2
∗
∑
i
=
1
n
a
i
+
∑
i
=
1
n
i
2
∗
a
i
−
2
∗
x
∗
∑
i
=
1
n
i
∗
a
i
\sum_{i=1}^{n}f(i)=x^{2}*\sum_{i=1}^{n}a_{i}+\sum_{i=1}^{n}i^{2}*a_{i}-2*x*\sum_{i=1}^{n}i*a_{i}
∑i=1nf(i)=x2∗∑i=1nai+∑i=1ni2∗ai−2∗x∗∑i=1ni∗ai
然后对
∑
i
=
1
n
a
i
\sum_{i=1}^{n}a_{i}
∑i=1nai,
∑
i
=
1
n
i
2
∗
a
i
\sum_{i=1}^{n}i^{2}*a_{i}
∑i=1ni2∗ai,
∑
i
=
1
n
i
∗
a
i
\sum_{i=1}^{n}i*a_{i}
∑i=1ni∗ai预处理,之后只要枚举
x
x
x的位置即可
void solve()
{
cin>>n;
int s=0,ss=0,tt=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
s+=a[i];
ss+=i*i*a[i];
tt+=2*i*a[i];
}
int res=0x3f3f3f3f3f3f3f3f;
for(int i=1;i<=n;i++)
{
res=min(res,i*i*s+ss-i*tt);
}
cout<<res<<endl;
}