牛客小白月赛43补题（1/6）
第三次打小白月赛了，还是签完到就不会了，跟nm傻比一样，从这次开始补题，备战2022蓝桥杯，do it ^ ^
A.满意的数字
心理：
就这题还给我卡了17分钟带俩罚时的，主要原因还有T个询问，每个询问的n都是1~n，输入输出有点蒙，最后代码写出来了不敢交，推半天，好像好多数都是满意的数字呢，150内竟然都是，整的不敢交了，犹豫是不是(1+m)/2不能整除的数字就不是满意的数字呢，sb。磨磨唧唧还是过了吧，从此这次比赛就一题没过过。
我的代码：
#include<bits/stdc++.h>
using namespace std;
int a[1010];
int main()
{
int n;
cin >> n;
while (n --)
{
int t, cnt = 0;
cin >> t;
for (int j = 1;j <= t;j ++)
{
int p = 0;
for (int i = 1;i <= j;i ++)
{
if (j % i == 0) a[++ p] = i;
}
for (int i = 1;i <= p;i ++)
{
if (a[p] % a[(1+p)/2] == 0)
{
cnt ++;
break;
}
}
}
cout << cnt << endl;
}
return 0;
}
补题dalao代码：
我草真是离谱，原来每个数都是满意的数字，qwq，直接裂开，排名前几的dalao都推出来了.....
卧槽！！！我是傻逼，第m个因子不就是它本身吗，第(1+m)/2的下取整个因子首先一定存在，且一定是这个数的因子，它的本身指定能整除它的因子啊啊啊啊啊啊，草！吃一堑，长一智吧qwq
码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t --)
{
int n;
cin >> n;
cout << n << endl;
}
return 0;
}
B.牛牛变魔术
感觉已经推出来了，但是没敢写，以为要递归，很复杂呢，事实证明有鸡毛复杂的啊
补题代码:
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n;
cin >> n;
while (n --)
{
long long a, b, t;
cin >> a >> b >> t;
if (a == t || b == t) cout << 0 << endl;
else if (t & 1) cout << -1 << endl;
else
{
long long sum = a+b;
int cnt = 1;
while (sum < t/2)
{
cnt ++;
sum *= 2;
}
cout << cnt << endl;
}
}
return 0;
}
备注：
1.一个数&1，如果是奇数就返回1，是偶数就返回0，这一操作用于判断一个数是否是奇数，dalao们爱用，咱也学学hh
2.切记范围大小问题，这题的大小到了1e18，int最大为2.1e9，long long最大为9.2e18，所以要开到long long级别补题的时候这还卡了我半天cao
C.木棍游戏
自己写了个纯暴力，但是没考虑到不用木棍的情况，只是所有的木棍直接排列组合都试一遍，略显智障
纯暴力代码，只能过72%的点：
#include<bits/stdc++.h>
using namespace std;
int a[10];
double x,y,z;
int main()
{
int n;
cin >> n;
for (int i = 1;i <= n;i ++) cin >> a[i];
double ma = 0;
bool flag = false;
for (int i = 1;i <= n-2;i ++)
{
x = 0;
for (int j = 1;j <= i;j ++) x += a[j];
for (int k = i + 1;k <= n-1;k ++)
{
y = 0;
for (int q = i + 1;q <= k;q ++) y += a[q];
z = 0;
for (int e = k + 1;e <= n;e ++) z += a[e];
if (x+y<=z||x+z<=y||y+z<=x)
{
continue;
}
else
{
double p = (x+y+z)/2;
double S = sqrt(p*(p-x)*(p-y)*(p-z));
if (S >= ma) ma = S;
flag = true;
}
}
}
if (flag) printf("%.1lf",ma);
else cout << -1;
return 0;
}
wocao，有的dalao的dfs我看不懂，我看懂了一个超级diao的随机排列的暴力做法，草，好牛！！！
补题代码：
#include<bits/stdc++.h>
using namespace std;
int a[10],b[5]; // a数组储存每条边，b数组储存随机的4组数
double res; // 因为题意有可能有的边不使用，所以使用4组数字，
// 返回回函数进行计算的只有3组,第4组储存不使用的边
double cal(int a,int b, int c)
{ // 计算abc三条边组成的三角形是否成立，若成立则返回面积，否则返回0
if (c > a) swap(c, a);
if (b > a) swap(b, a);
if (c > b) swap(c, b);
if (b + c <= a) return 0; // 两条小边若小于等于最大边，则三角形不成立
double p = (a + b + c) / 2.0; // 海伦公式求三角形面积
double s = sqrt(1.0 * p * (p-a) * (p-b) * (p-c));
return s; // 否则返回三角形面积
}
int main()
{
int n;
cin >> n;
for (int i = 0;i < n;i ++) cin >> a[i]; // 储存每条边
int sum = 1;
for (int i = 0;i < n;i ++) sum *= 4; // 计算随机的次数
for (int i = 0;i < sum;i ++)
{
int s = i;
for (int j = 0;j < n;j ++) // 将每个值都随机赋值进b数组
{
b[s%4] += a[j]; // b数组随机元素 += a数组的每个值， += 很重要别写错
s /= 4; // s%4 和 s/=4 保证了随机
}
res = max(res, cal(b[0],b[1],b[2])); // res 取最大值
b[0] = b[1] = b[2] = b[3] = 0; // b数组清0，便于下一次随机取值
}
if (!res) cout << -1; // 若res = 0，则所给边无法构成三角形
else printf("%.1lf", res); // 否则就输出保留一位小数的面积值
return 0;
}
牛客网确实diao，可以学习dalao的代码，强！！学会一招牛逼的hh
D.有趣的区间
刚开始不会按位或、按位与、按位异或啥的题，又好好学习了一下，差不多了
补题代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int a[N];
long long cal(int a)
{
return 1LL*a*(a+1)/2;
}
int main()
{
int n;
cin >> n;
for (int i = 0;i < n;i ++) cin >> a[i];
long long sum = cal(n);
int cnt = 0;
for (int i = 0;i < n;i ++)
{
if (a[i] % 2 == 0)
{
cnt ++;
}
else
{
sum -= cal(cnt);
cnt = 0;
}
}
sum -= cal(cnt);
cout << sum;
return 0;
}
cal函数返回a个数一共有多少个区间，一共有a*(a+1)/2个区间，因为a的值很大，所以结果返回longlong类型，计算中乘1LL即可自动转换为longlong类型。
可知，奇数的二进制最后一位为1，偶数的二进制最后一位为0。奇数按位或奇数，则二进制最后一位1|1答案为1，即答案为一个奇数；奇数按位或偶数，则二进制最后一位1|0答案为1，即答案为一个奇数；奇数按位或偶数，则二进制最后一位0|0答案为0，即答案为一个偶数。所以，若区间内有一个奇数，则与它按位或的结果均为奇数。所以可以从反面计算。有趣的区间 = 所有区间 - 无趣的区间。 而无趣的区间即为出现偶数的区间，若出现一个偶数，则总区间数-1；若出现两个连续的偶数，则总区间数-3，因为奇数按位或偶数结果为奇数，所以连续的偶数并不影响包含它的大区间的有趣的区间数。只需减去连续的偶数区间，即无趣的区间即可。
腾讯云智研发成长空间 5057人发布