haut2023新生周赛题解
先说明一下，对于有些题测试样例不够强，导致一些非正解通过题目感到非常抱歉，收到反馈题目比较抽象.
A 旅行者的抛弃 签到题
根据重量比求出半径比 要注意重量比 是 M + 1
m1是可莉的重量，m2是要求的结果
m1 g1 / 2 = m2 g2
根据万有引力公式 : g = GM / (r * r)
得出 g1 / g2 的值
最后带入 可得 m2
最后直接输出
#include <bits/stdc++.h>
using namespace std;
void solve()
{
double m, M;
cin >> m >> M;
double r = pow(M + 1, 1.0 / 3);
cout << fixed << setprecision(3) << r * r / (M + 1) * m / 2;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int test = 1;
// cin >> test;
while (test--)
{
solve();
}
return 0;
}
B 元素中和之力 简单题
观察发现草或风只有一种中和反应方法，所以从草或风开始依次计算即可 反应时取反应元素中较小的元素值
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
ll x[8] = {0};
int t;
cin >> t;
while (t--)
{
for (int i = 1; i <= 7; ++i)
{
cin >> x[i];
}
ll ans = 0;
swap(x[4], x[7]); // 交换
for (int i = 7; i >= 1; --i)
{
ll mi = min(x[i], x[i - 1]);
if (mi > 0)
{
ans += mi;
x[i - 1] -= mi;
}
}
cout << ans << "\n";
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int test = 1;
// cin >> test;
while (test--)
{
solve();
}
return 0;
}
C 旅行传送门 简单题
因为不会回头，考虑枚举中间点，在两边使用传送门，使用两个大空间数组，记录数字出现的位置，每枚举一次中间点都要将本次标记清除。
#include <bits/stdc++.h>
using namespace std;
const int N = 4e6 + 10;
typedef long long ll;
ll ma1[N], ma2[N];
ll a[N];
void solve() {
int n;
cin>> n;
for(int i = 1; i <= n; ++i)cin>>a[i];
ll ans = 0;
for(int i = 1; i <= n; ++i){
ll l = 0, r = 0;
for(int j = i; j >= 1; --j){
if(ma1[a[j]]==0){
ma1[a[j]] = j;
}
else l = max(l, ma1[a[j]] - j);
}
for(int j = i + 1; j <= n; ++j){
if(ma2[a[j]]==0){
ma2[a[j]] = j;
}
else r = max(r, j - ma2[a[j]]);
}
// 清空数组
for(int j = i; j >= 1; --j){
ma1[a[j]] = 0;
}
for(int j = i + 1; j <= n; ++j){
ma2[a[j]] = 0;
}
ans = max(ans, l + r);
}
cout<< ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int test = 1;
while (test--) {
solve();
}
return 0;
}
D 卡萨的阻拦 中等题
直接计算约数的耗时较大，应该会超时，考虑到一个比较小的数会是多个数的约数，所以直接计算这个数会被计算多少次 。对于输入的n， 对于某个 i ， i <= n, 一共有 n / i 个数 有 i 这个 约数， 其中包括 i 本身 所以要减去 1， 所以单个 i 的贡献为 i * (n / i - 1)， 循环求和即可 。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
int n;
cin>>n;
ll ans = 0;
for(int i = 1; i <= n; ++i){
ans = ans + i * (n / i - 1);
}
cout<<ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int test = 1;
// cin >> test;
while (test--)
{
solve();
}
return 0;
}
E 破碎的未来 中等题
对于地图上的每一个点都对其进行标记， 如果四个方向中有一个点和其颜色相同，并且未被标记，将递归进行标记。
#include <bits/stdc++.h>
using namespace std;
int a[1100][1100];
int n,m;
void dfs(int i,int j,int op){
if(i < 1 ||i > n || j < 1 || j > m )return;
if(a[i][j] == -1)return;
if(a[i][j] != op)return;
a[i][j] = -1;
dfs(i + 1,j, op);
dfs(i -1, j, op);
dfs(i, j + 1,op);
dfs(i,j - 1, op);
}
void solve()
{
cin>>n>>m;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
cin>>a[i][j];
}
}
int ans = 0;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
if(a[i][j] != -1){
dfs(i, j, a[i][j]);
ans++;
}
}
}
cout<<ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int test = 1;
// cin >> test;
while (test--)
{
solve();
}
return 0;
}
F 怎么了，你累啦？ 难题
提前记录对于位置 i 的后面和前面的最大值，如果位置 i 的值比这两个最大值都要小，那么这个值就一定会消失。 也可以用一个队列解决本问题，要注意判别条件
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
int n;
cin>>n;
vector<ll> a(n + 10); // 数组
vector<ll> r(n + 10); // 数组 // 记录后缀最大值
r[n + 1] = 0;
a[0] = 0;
ll ma = 0; // 记录前缀最大值
ll ans = 0;
for(int i = 1; i <= n; ++i){
cin>>a[i];
}
for(int i = n; i >= 1; --i){
r[i] = max(r[i + 1], a[i]);
}
for(int i = 1; i <= n; ++i){
ma = max(ma, a[i - 1]);
if(a[i] >= ma || a[i] >= r[i + 1]){
ans = ans + a[i];
}
}
cout<< ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int test = 1;
// cin >> test;
while (test--)
{
solve();
}
return 0;
}
G 是心碎的声音 中等题
首先如果 k <= 2，所有原石都不会消失，直接输出 其次 将 原石从小到大排序， 如果小的能拿，一定优先拿小的，这将使用一次机会，最后计数即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; ++i)
{
cin >> a[i];
}
if (k <= 2)
{
cout << n << "\n";
return;
}
sort(a.begin(), a.end()); // 排序
ll ans = 0;
ll time = 0;
for (int i = 0; i < n; ++i)
{
ll op = 0;
while (1)
{
a[i] = (1.0 * a[i] / k + 0.5);
op++;
if (op >= time + 1)
break;
if (a[i] == 0)
break;
}
if (op >= time + 1)
{
time++;
ans++;
}
}
cout << ans << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int test = 1;
// cin >> test;
while (test--)
{
solve();
}
return 0;
}
H 你就是被上天选中的人 中等题
对于每次操作1 和 2， 使用额外数组记录改变的值，对与操作3，枚举 x 的约数，因为操作 3 次数 有限制，但要注意枚举到约数 j 时，另一个约数 x / j 也要计算。
#include <bits/stdc++.h>
using namespace std;
const int N = 4e6 + 10;
typedef long long ll;
ll a[N], add[N]; // add 是额外数组
int n, m;
void solve()
{
ll ans = 0;
cin >> n >> m;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
}
for (int i = 1; i <= m; ++i)
{
string s;
int x, y;
cin >> s;
if (s[0] == 'u')
{
cin >> x >> y;
add[x] += y;
}
else if (s[0] == 'd')
{
cin >> x >> y;
add[x] -= y;
}
else
{
cin >> x;
ll ans = a[x];
for (int i = 1; i * i <= x; ++i)
{
if (x % i == 0)
{
ans += add[i];
if(i * i != x){
ans += add[x / i];
}
}
}
cout << ans << "\n";
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int test = 1;
// cin >> test;
while (test--)
{
solve();
}
return 0;
}
投递旷视等公司10个岗位 >