【标题全解】ACGO巅峰赛#15
ACGO 巅峰赛#15 - 标题解析
距离四个月再战 ACGO Rated，鉴于最近学业繁忙，竞赛打得都不是很频频。尽管这次没有 AK 排位赛（我能够说是因为周末太忙，没有足够的时刻考虑标题…（好吧，其实或许是因为我把 T5 给想杂乱了））。
本文仍旧供给每道题的完好解析（因为我在赛后把标题做出来了）。
T1 - 高塔
标题链接跳转：点击跳转
插一句题外话，这道题的标题编号挺风趣的。
没有什么特别难的点，循环读入每一个数字，读入后跟第一个输入的数字比较巨细，假如读入的数字比第一个读入的数字要大（即 \(a_i > a_1\)），直接输出 \(i\) 并完毕主程序即可。
本题的 C++ 代码如下：
#include <iostream>
using namespace std;
int n, arr[105];
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i=1; i<=n; i++){
cin >> arr[i];
if (arr[i] > arr[1]){
cout << i << endl;
return 0;
}
}
cout << -1 << endl;
return 0;
}
本题的 Python 代码如下：
n = int(input())
arr = list(map(int, input().split()))
for i in range(1, n + 1):
if arr[i - 1] > arr[0]:
print(i)
break
else:
print(-1)
T2 - 养分均衡
标题链接跳转：点击跳转
也是一道入门标题，没有什么比较难的当地，要点是把标题读清楚了。
咱们设置一个数组 \(\tt{arr}\)，其间 \(\tt{arr_i}\) 表明种养分元素还需求的摄入量。那么，假如 \(\tt{arr_i} \le 0\) 的话，就表明该种养分元素的摄入量现已达到了 “健康饮食” 的所需规范了。依照题意模仿一下即可，最终遍历一整个数组判别是否有无法满意的元素。换句话说，只需有恣意的 \(\forall i\)，满意 \(\tt{arr_i} > 0\) 就需求输出 No。
本题的 C++ 代码如下：
#include <iostream>
using namespace std;
int n, m;
long long arr[1005];
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i=1; i<=m; i++)
cin >> arr[i];
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++){
int t; cin >> t;
arr[j] -= t;
}
}
for (int i=1; i<=m; i++){
if (arr[i] > 0){
cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;
return 0;
}
本题的 Python 代码如下：
n, m = map(int, input().split())
arr = list(map(int, input().split()))
for _ in range(n):
t = list(map(int, input().split()))
for j in range(m):
arr[j] -= t[j]
if any(x > 0 for x in arr):
print("No")
else:
print("Yes")
T3 - ^_^ 仍是 😦
标题链接跳转：点击跳转
一道简略的思想标题，难度定在【遍及-】还算是合理的。不过 USACO 的 Bronze 组别特别喜爱考这种相似的思想标题。
一般算法
考虑选用贪心的思路，先把序列依照从大到小的准则排序。暴力枚举一个节点 \(i\)，判别是否有或许满意挑选前 \(i\) 个数字 \(-1\)，剩余的数字都至少 \(+1\) 的状况下一切的数字都大于零。
那么该怎么快速的判别是否一切的数字都大于零呢？首要能够必定的是，后 \(n - i\) 个数字一定是大于零的，因为这些数字只会添加不会削减。所以咱们把要点放在前 \(i\) 个数字上面。因为数组现已是有序的，因而假如第 \(i\) 个数字是大于 \(1\) 的，那么前 \(i\) 个数字在减去 \(1\) 之后也一定是正整数。
因为运用了排序算法，本算法的单次查询时刻杂乱度在 \(O(N \log_2 N)\) 等级，总时刻杂乱度为 \(O(N^2 \log_2 N)\)，能够在 \(\tt{1s}\) 内经过一切的测试点。
本题的 C++ 代码如下：
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <cmath>
using namespace std;
int n;
int arr[1005];
void solve(){
cin >> n;
long long sum = 0;
for (int i=1, t; i<=n; i++){
cin >> arr[i];
}
sort(arr+1, arr+1+n, greater<int>());
if (n == 1) {
cout << ":-(" << endl;
return ;
}
// 暴力枚举，挑选前 i 个数字 - 1，剩余的一切数字都至少 + 1。
bool flag = 0;
for (int i=1; i<=n; i++){
sum += arr[i];
if (arr[i] == 1) break;
if (sum - (n - i) >= i) flag = 1;
}
cout << (flag ? "^_^" : ":-(") << endl;
return ;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T; cin >> T;
while(T--) solve();
return 0;
}
本题的 Python 代码如下：
def solve():
n = int(input())
arr = list(map(int, input().split()))
# 对数组降序排序
arr.sort(reverse=True)
if n == 1:
print(":-(")
return
# 暴力枚举前 i 个数字 - 1，剩余的数字 +1
sum_ = 0
flag = False
for i in range(1, n + 1):
sum_ += arr[i - 1]
if arr[i - 1] == 1:
break
if sum_ - (n - i) >= i:
flag = True
print("^_^" if flag else ":-(")
def main():
T = int(input())
for _ in range(T):
solve()
if __name__ == "__main__":
main()
二分答案优化
留意到答案是单调的，因而能够运用二分答案的算法来恰当优化。尽管作用微乎其微，但在全体时刻运转上体现杰出。
优化后的 C++ 代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int arr[1005];
void solve() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> arr[i];
sort(arr + 1, arr + 1 + n, greater<int>());
if (n == 1) {
cout << ":-(" << endl;
return;
}
int left = 1, right = n, res = -1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] > 1) {
res = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
cout << (res != -1 ? "^_^" : ":-(") << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T; cin >> T;
while (T--) solve();
return 0;
}
优化后的 Python 算法如下：
def solve():
n = int(input())
arr = list(map(int, input().split()))
# 对数组降序排序
arr.sort(reverse=True)
if n == 1:
print(":-(")
return
left, right, res = 0, n - 1, -1
while left <= right:
mid = (left + right) // 2
if arr[mid] > 1:
res = mid
right = mid - 1
else:
left = mid + 1
print("^_^" if res != -1 else ":-(")
def main():
T = int(input())
for _ in range(T):
solve()
if __name__ == "__main__":
main()
T4 - Azusa的方案
标题链接跳转：点击跳转
这道题的难度也不是很高，略微考虑一下即可。
任何事情时刻 \(t\) 对 \((a + b)\) 取模后，事情能够映射到一个固定的周期内。这样，问题就转化为一个固定长度的区间查看问题。
因而，在读入数字后，将一切的数字对 \((a + b)\) 取模并排序，假如数字散布（序列的最大值和最小值的差值天数）在 \(a\) 范围内即可满意将一切的日程安排在歇息日傍边。但需求留意的是，两个日期的差值天数不能单纯地运用数字相减的办法求得。以正常 \(7\) 天为一周作为典范，周一和周日的日期差值为 \(1\) 天，而不是 \(7 - 1 = 6\) 天。这也是本题最难的部分。
假如做过 区间 DP 的用户应该能十分快速地想到假如数据是一个 “环状” 的状况下该怎么解决问题（参阅标题：石子兼并（规范版））。咱们能够运用 “剖环成链” 的办法，将环中的元素仿制一遍并将每个数字添加 \((a + b)\)，拼接在原数组的结尾，这样一个长度为 \(n\) 的环就被扩展为一个长度为 \(2n\) 的线性数组。
最终只需求遍历这个数组内一切长度为 \(n\) 的区间 \([i, n + i - 1]\)，判别是否有恣意一个区间的最大值和最小值的差在 \(a\) 以内即可判别是否能够讲一切的日程安排都分不在歇息日中。
本题的时刻杂乱度为 \(O(N \log_2 N)\)。
本题的 C++ 代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
int n, a, b;
int arr[500005];
int maximum, minimum = 0x7f7f7f7f;
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> a >> b;
for (int i=1; i<=n; i++){
cin >> arr[i];
arr[i] %= (a + b);
}
sort(arr+1, arr+1+n);
for (int i=1; i<=n; i++){
arr[i+n] = arr[i] + (a + b);
}
bool flag = 0;
for (int i=1; i+n-1<=2*n; i++) {
if (arr[i+n-1] - arr[i] < a)
flag = 1;
}
cout << (flag ? "Yes" : "No") << endl;
}
本题的 Python 代码如下：
def main():
import sys
input = sys.stdin.read
data = input().split()
n, a, b = map(int, data[:3])
arr = list(map(int, data[3:]))
mod_value = a + b
arr = [x % mod_value for x in arr]
arr.sort()
arr += [x + mod_value for x in arr]
flag = False
for i in range(n):
if arr[i + n - 1] - arr[i] < a:
flag = True
break
print("Yes" if flag else "No")
if __name__ == "__main__":
main()
T5 - 前缀和问题
标题链接跳转：点击跳转
我个人认为这道题比最终一道题要难，或许是因为这类标题做的比较少的原因，看到标题后不知道从哪下手。
运用分类评论的办法，设置一个阈值 \(S\)，考虑暴力枚举一切 \(b > S\) 的状况，并离线优化 \(b \le S\) 的状况。将 \(S\) 设置为 \(\sqrt{N}\)，则有：
- 关于大步长 \(b > S\)，恣意一次查询只需求最多遍历 \(550\)（即 \(\sqrt{N}\)）次就能够算出答案，因而暴力枚举这部分。
- 关于小步长 \(b \le S\)，按 \(b\) 分组批量离线查询。
关于大步长部分，每一次查询的时刻杂乱度为 \(O(\sqrt{N})\)，在最坏状况下总时刻杂乱度为 \(O(N \times \sqrt{N})\)。关于小步长的部分，每一次查询的时刻杂乱度约为 \(O(n)\)，在最坏状况下的时刻杂乱度为 \(O(N\times \sqrt{N})\)，因而本题在最坏状况下的渐进时刻杂乱度为：
