369
A - 369
给你两个整数
有多少个整数
- 条件:可以将三个整数
、 和 按一定顺序排列,组成一个算术序列。
当且仅当
void solve() {
int a, b;cin >> a >> b;
if (a == b) {
cout << "1\n";return;
}
int ans = 3;
if ((a - b) & 1) {
ans--;
}
cout << ans << '\n';
}
B - Piano 3
高桥有一架钢琴,上面有
他会逐个按下 R
.
开始演奏前,他可以将双手放在任何他喜欢的键上,此时他的疲劳度为 0。在演奏过程中,如果他将一只手从
找出表演结束时可能的最低疲劳度。
直接放在第一次弹的位置即可。
void solve() {
int n;cin >> n;
int l = 0, r = 0, ok1 = 0, ok2 = 0;
int ans = 0;
for (int i = 1;i <= n;i++) {
int a;char ch;cin >> a >> ch;
if (!ok1 && ch == 'L') {
l = a;ok1 = 1;
} else if (!ok2 && ch == 'R') {
r = a;ok2 = 1;
}
if (ch == 'L') {
ans += abs(l - a);l = a;
} else if (ch == 'R') {
ans += abs(r - a);r = a;
}
}
cout << ans << '\n';
}
C - Count Arithmetic Subarrays
给你一个由
求满足
长度为
注:需要 long long
#define int long long
void solve() {
int n;cin >> n;
vector<int> a(n + 1), suf(n + 2);
for (int i = 1;i <= n;i++)cin >> a[i];
for (int i = 2;i <= n;i++) {
suf[i] = a[i] - a[i - 1];
}
suf[n + 1] = 2e9;
int ans = 0, cnt = 1, p = 0;
for (int i = 2;i <= n;i++) {
if (suf[i + 1] != suf[i]) {
ans += (cnt + 1) * (cnt + 2) / 2;cnt = 1;p++;
} else {
cnt++;
}
}
cout << ans - p + 1 << '\n';
}
D - Bonus EXP
高桥依次会遇到
对于每只怪物,他都可以选择放走或打败它。
每次行动都会获得以下经验值:
- 如果放走一只怪物,他将获得
点经验值。 - 如果他以
的力量击败了怪物,则会获得 点经验值。
如果击败的是偶数怪物 (第 2 个、第 4 个......),则额外获得点经验值。
求他能从
Solution
有三种状态:
- 选择当前位置且当前位置是第奇数个
- 选择当前位置且当前位置是第偶数个
- 不选当前位置
则
- 若当前位置不选,则可能从前一个位置的任意一个状态转移而来
- 若选择当前位置且是第奇数个,则前一个位置可能不选,也可能从偶数个转移而来
- 若选择当前位置且是第偶数个,则前一个位置可能不选,也可能从奇数个转移而来(注意:当下标为 1 时,则不可能是从奇数个转移而来)
转移方程:
#define int long long
void solve() {
int n;cin >> n;
vector<int> a(n + 1);
for (int i = 1;i <= n;i++) {
cin >> a[i];
}
vector<array<int, 3>> dp(n + 1);
for (int i = 1;i <= n;i++) {
dp[i][0] = max({dp[i - 1][1], dp[i - 1][2],dp[i - 1][0]});
dp[i][1] = max(dp[i - 1][2], dp[i - 1][0]) + a[i];
if (i != 1)dp[i][2] = max(dp[i - 1][1], dp[i - 1][0]) + a[i] * 2;
}
cout << max({dp[n][0],dp[n][1],dp[n][2]}) << '\n';
}
E - Sightseeing Tour
有
大桥
没有一座桥将一个岛屿与自己连接起来,但是两个岛屿有可能被不止一座桥直接连接起来。
人们可以通过一些桥梁来往于任意两个岛屿之间。
给你
给你
个不同的桥:桥 。
求从岛屿到岛屿 所需的最少时间,每座桥梁至少使用一次。
只考虑过桥的时间。
你可以以任何顺序和方向通过给定的桥梁。
Solution
floyed 算法
...
F - Gather Coins
有一个网格,网格中有
在这个网格中有
您的目标是从
请找出您能拾取的最大硬币数以及能达到最大值的路径之一。