牛客小白月赛81
A. 小辰打比赛
解题思路:
遍历找到小于\(x\)的数累加即可。
代码:
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n,x;
int ans = 0;
cin >> n >> x;
for(int i = 1;i<=n;i++)
{
int k = 0;
cin >> k;
if(k < x)
{
ans += k;
}
}
cout << ans;
}
int main()
{
int t = 1;
while(t--)
{
solve();
}
return 0;
}
B. 小辰的圣剑
解题思路:
两层循环枚举左右区间累加判断计算即可。
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
ll n,m,u;
cin >> n >> m >> u;
vector<ll> a(n + 1),b(n + 1);
for(int i = 1;i<=n;i++)
{
cin >> a[i];
}
for(int i = 1;i<=n;i++)
{
cin >> b[i];
}
ll ans = 0;
for(int i = 1;i<=n;i++)
{
ll res = 0;
ll t = 0;
ll cnt = 0;
for(int j = i;j<=n;j++)
{
res += a[j];
t += b[j];
cnt ++;
if(res > m || t > u)
{
break;
}
ans = max(ans,cnt);
}
}
cout << ans << endl;
}
int main()
{
int t = 1;
while(t--)
{
solve();
}
return 0;
}
C. 陶陶学算术
解题思路:
如果直接模拟，那么数据会很大。
对于每次操作，分解操作数的质因子进行统计。如果最后二者质因子和符号都完全一样，那么就是一样的。
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
int primes[N];
bool st[N];
int minp[N];
int cnt = 0;
bool f1 = true;
bool f2 = true;
int p1[N];
int p2[N];
void init(int n)
{
for(int i = 2;i<=n;i++)
{
if(!st[i])
{
primes[cnt++] = i;
st[i] = true;
minp[i] = i;
}
for(int j = 0;i <= n / primes[j];j ++)
{
st[i * primes[j]] = true;
minp[i * primes[j]] = primes[j];
if(i % primes[j] == 0)
{
break;
}
}
}
}
void find(int x,int t,int op)
{
if(t == 1)
{
if(x < 0)
{
f1 ^= 1;
x = abs(x);
}
if(op)
{
while(x != 1)
{
int p = minp[x];
p1[p] ++;
x = x / p;
}
}
else
{
while(x != 1)
{
int p = minp[x];
p1[p] --;
x = x / p;
}
}
}
else
{
if(x < 0)
{
f2 ^= 1;
x = abs(x);
}
if(op)
{
while(x != 1)
{
int p = minp[x];
p2[p] ++;
x = x / p;
}
}
else
{
while(x != 1)
{
int p = minp[x];
p2[p] --;
x = x / p;
}
}
}
}
void solve()
{
int n;
cin >> n;
for(int i = 1;i<=n;i++)
{
int x,y;
cin >> x >> y;
if(x == 1)
{
find(y,1,0);
}
else
{
find(y,1,1);
}
}
cin >> n;
for(int i = 1;i<=n;i++)
{
int x,y;
cin >> x >> y;
if(x == 1)
{
find(y,2,0);
}
else
{
find(y,2,1);
}
}
for(int i = 1;i<=1e5;i++)
{
if(p1[i] != p2[i])
{
puts("NO");
return;
}
}
if(f1 != f2)
{
puts("NO");
}
else
{
puts("YES");
}
}
int main()
{
init(100000);
int t = 1;
while(t--)
{
solve();
}
return 0;
}
D. 小辰的借钱计划
解题思路:
按照题意直接计算期望即可。
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
int m,a;
cin >> m >> a;
ll len = 0;
ll sum = 0;
for(int i = 1;i <= m - a;i++)
{
if(i % a == 0 || a % i == 0)
{
len ++;
sum += i;
}
}
double res = (double)sum / len;
if(res > a)
{
puts("YES");
}
else
{
puts("NO");
}
}
int main()
{
int t = 1;
cin >> t;
while(t--)
{
solve();
}
return 0;
}
E. 小辰的智慧树
解题思路:
我们假设将一棵树从高度\(r\)砍到\(l\)。\(c = r - l = a + b\),我们可以直接砍\(c\)，也可以先砍\(a\),再砍\(b\)。
\[\begin{align*}
\Delta h &= c * (2 * r - c)\\
&= a * (2 * r - a) + b * (2 * ( r - a) - b) \\
&= 2 * r *(a + b) - (a^2 + 2ab - b^2)\\
&= 2rc - (a + b)^2\\
&= 2rc -c^2 \\
&= c*(2r - c)
\end{align*}
\]
由上可知，一大刀切和一小刀一小刀切并无不同。
所以可以\(1\)单位\(1\)单位地切分，取最大的\(m\)小刀即可。
我们可对值域进行差分计算。
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
ll n,m;
cin >> n >> m;
vector<ll> s(1e6 + 10,0);
for(int i = 1;i <= n;i ++)
{
ll l,r;
cin >> r >> l;
l ++;
r ++;
s[l] ++;
s[r] --;
}
for(int i = 1;i<s.size();i++)
{
s[i] += s[i - 1];
}
ll ans = 0;
for(int i = 1e6;i >= 0;i--)
{
ll cur = min(m,s[i]);
ans += cur * (2 * i - 1);
m -= cur;
}
cout << ans << endl;
}
int main()
{
int t = 1;
while(t--)
{
solve();
}
return 0;
}