Educational Codeforces Round 146 (Rated for Div. 2)
A. Coins
题目大意
给你两个整数n和k,问你是否存在两个非负整数x和y,使得 2⋅x+k⋅y=n 成立
思路
裴蜀定理秒了,记得开long long
ac代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 inf = 8e18;
typedef pair<int, int> pii;
void solve() {
i64 n, k;
cin >> n >> k;
if (n % __gcd(2ll, k) == 0 && n >= min(2ll, k)) cout << "YES\n";
else cout << "NO\n";
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1;
cin >> t;
while (t --) solve();
return 0;
}
B. Long Legs
题目大意
一个机器人被放置在一个无限网格的 \((0, 0)\) 单元中。该机器人有可调节长度的腿。最初,它的腿长为 \(1\) 。
假设机器人当前位于 \((x, y)\) 单元,其腿长为 \(m\) 。在一次移动中,它可以执行以下三个动作之一:
- 跳入 \((x + m, y)\) 单元
- 跳入 \((x, y + m)\) 单元;
- 将腿的长度增加 \(1\) ,即设置为 \(m + 1\) 。
机器人到达 \((a, b)\) 单元格的最小移动次数是多少?
思路
枚举\(m\)的最大值
ac代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 inf = 8e18;
typedef pair<int, int> pii;
void solve() {
int a, b;
cin >> a >> b;
int ans = a + b;
for (int i = 1; i <= 100000; i ++)
ans = min(ans, i - 1 + (a + i - 1) / i + (b + i - 1) / i);
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1;
cin >> t;
while (t --) solve();
return 0;
}
C. Search in Parallel
题目大意
假设你有 \(n\) 个盒子。 \(i\) -th盒子里有无数个颜色为 \(i\) 的球。有时你需要得到一个特定颜色的球,但你又懒得自己动手。
你买了两个机器人来帮你取球。现在你必须给它们编程。为了给机器人编程,你必须构造两个列表 \([a_1, a_2, \dots, a_k]\) 和 \([b_1, b_2, \dots, b_{n-k}]\) ,其中列表 \(a\) 代表分配给第一个机器人的盒子,列表 \(b\) 代表分配给第二个机器人的盒子。从 \(1\) 到 \(n\) 的每个整数必须正好出现在其中一个列表中。
当您需要一个颜色为 \(x\) 的小球时,机器人的工作方式如下。每个机器人按照列表中出现的顺序,查看分配给该机器人的盒子。第一个机器人花 \(s_1\) 秒分析盒子里的东西,第二个机器人花 \(s_2\) 秒。只要其中一个机器人找到装有颜色为 \(x\) 的小球的盒子(并分析其内容),搜索就结束。搜索时间是指从搜索开始到其中一个机器人分析完 \(x\) /th盒子中的内容所需的秒数。如果一个机器人分析完了分配给它的所有盒子的内容,那么它就停止搜索。
思路
先根据取出的次数进行排序,如何根据当前查询时间的大小排进数组里
ac代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 inf = 8e18;
typedef pair<int, int> pii;
void solve() {
int n, s1, s2;
cin >> n >> s1 >> s2;
std::vector<pii> p(n);
for (int i = 0; i < n; i++) {
cin >> p[i].first;
p[i].second = i;
}
sort(p.begin(), p.end(), greater<pii>());
vector<int> ans[2];
int t1 = s1, t2 = s2;
for (int i = 0; i < n; i++) {
int j = i;
while (t1 <= t2 && j < n) ans[0].push_back(p[j ++].second + 1), t1 += s1;
while (t2 <= t1 && j < n) ans[1].push_back(p[j ++].second + 1), t2 += s2;
i = j - 1;
}
cout << ans[0].size() << ' ';
for (auto i : ans[0]) cout << i << ' ';
cout << '\n' << ans[1].size() << ' ';
for (auto i : ans[1]) cout << i << ' ';
cout << endl;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1;
cin >> t;
while (t --) solve();
return 0;
}
D. Balancing Weapons
太难了不想写
标签:146,Educational,盒子,int,机器人,long,i64,补题,using From: https://www.cnblogs.com/kichuan/p/17852822.html