A.加训时间！
根据题意,求出数组的最大值x，再*n即可。(第二次每个人都需要补x道题)
#include <bits/stdc++.h>
using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; i ++) {
std::cin >> a[i];
}
std::cout << n * *std::max_element(a.begin(), a.end()) << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
// std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}
B.爆wa种子!
- 由于a >= 0,那么 抛物线的开口向上，最小值为(4 * a * c - b * b )/ 4 / a;
- 若a = 0,b != 0,则方程变为直线，因此最小值为负无穷
- 若a = 0,b = 0,则方程变成平行于x轴的直线
因此只有2才能取到负无穷
注意取最小值时不要忘记与3取min,赛时忘了这个条件狂WA┭┮﹏┭┮
#include <bits/stdc++.h>
using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";
std::string inf = "-1000000000";
void solve() {
int n;
std::cin >> n;
std::cout << std::fixed << std::setprecision(9);
double min = 1e18;
double ans = 1e9;
for (int i = 1; i <= n; i ++) {
int a, b, c;
std::cin >> a >> b >> c;
if (a == 0 and b != 0) {
std::cout << inf << "\n";
return;
} else {
double y = (4 * a * c * 1.0 - b * b) / (4 * a);
ans = std::min(ans,y);
}
ans = std::min(ans,c * 1.0);
}
std::cout << std::fixed << std::setprecision(9) << ans << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
// std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}
C. 晚上不睡觉
输出a*b的错误答案即可
#include <bits/stdc++.h>
using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";
void solve() {
int a, b;
std::cin >> a >> b;
std::cout << a + b << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
// std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}
D. 书生的负数
贪心思考,操作不会时数组和增大或减少,那么我们可以将前n - 1个数通过操作全部变为负数,然后判断最后一个是否为负数即可
#include <bits/stdc++.h>
using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";
void solve() {
int n;
std::cin >> n;
int a = 0;
for (int i = 1; i <= n; i ++) {
int x;
std::cin >> x;
a += x;
}
a += n - 1;
int c = n - 1;
if (a < 0) {
c ++;
}
std::cout << c << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}
E.明天
字符串查找,使用string的API即可
#include <bits/stdc++.h>
using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "yes\n";
#define no std::cout << "no\n";
void solve() {
std::string s;
std::cin >> s;
std::string str = "tomorrow";
if (s == str) {
no
return;
}
if (str.find(s) != -1) {
yes
} else {
no
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}
F.跳棋
通过观察可以发现，只要有两个格子上都有棋子，并且棋子的左边后者右边有空位,那么棋子就可以跳到所有位置上.
分别进行前后遍历,判断是否有满足上述条件的棋子，若没有，则输出棋子的数量
#include <bits/stdc++.h>
using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";
void solve() {
int n;
std::cin >> n;
std::string s;
std::cin >> s;
s = " " + s;
for (int i = 1; i <= n - 1; i ++) {
if (s[i] == 'X' and s[i + 1] == 'X') {
std::cout << n << "\n";
return;
}
}
for (int i = n; i >= 2; i --) {
if (s[i] == 'X' and s[i - 1] == 'X') {
std::cout << n << "\n";
return;
}
}
std::cout << std::count(s.begin(), s.end(),'X') << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
// std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}
G.河流管理
(刚开始写了个线段树丢上去了,后来发现是并查集O(∩_∩)O) 由于每一次打开挡板，都会将这之间的河流合并，所以用并查集进行祖先的修改即可。
#include <bits/stdc++.h>
using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";
struct DSU {
std::vector<int> pre, f, v;//f -> number
DSU(int n) : pre(n), f(n, 1), v(n + 1) { std::iota(pre.begin(), pre.end(), 0); }
DSU(std::vector<i64> init) : DSU(init.size()) {
for (int i = 0; i < init.size(); i ++) {
f.push_back(init[i]);
}
}
int find(int x) {
while (x != pre[x]) x = pre[x] = pre[pre[x]];
return x;
}
bool same(int x, int y) { return find(x) == find(y); }
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
f[y] += f[x];
v[y] = std::max(v[y],v[x]);
pre[x] = y;
return true;
}
int size(int x) { return f[find(x)]; }
};
//DSU dsu(n + 1);
void solve() {
int n, m;
std::cin >> n >> m;
DSU dsu(n + 1);
for (int i = 1; i <= n; i ++) {
std::cin >> dsu.v[i];
}
while (m -- ) {
int op;
std::cin >> op;
if (op == 1) {
int l, r;
std::cin >> l >> r;
for (int i = dsu.find(l); i < dsu.find(r); i ++) {
dsu.merge(i,i + 1);
}
} else {
int x;
std::cin >> x;
std::cout << dsu.v[dsu.find(x)] << "\n";
}
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
// std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}
H. 冒险
以为是背包问题,实则不是
由于每次装进背包后体积会*2,所以我们先拿体积小的即可
#include <bits/stdc++.h>
using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<int> a(n);
for (int i = 0; i < n; i ++) {
std::cin >> a[i];
}
std::sort(a.begin(), a.end());
int v = 0,c = 0;
for (int i = 0; i < n; i ++) {
if (v * 2 + a[i] <= m) {
v *= 2;
v += a[i];
c ++;
}
}
std::cout << c << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
// std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}
I. 妙wa种子！
跟之前写过的一道题很像 由于要划分k段,所以一定有一种方案,能把数组中前k大的数全部包含进去,所以直接取前k大值即可
#include <bits/stdc++.h>
using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<int> a(n);
for (int i = 0; i < n; i ++) {
std::cin >> a[i];
}
std::sort(a.begin(), a.end(),std::greater());
std::cout << std::accumulate(a.begin(), a.begin() + m,0ll) << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
// std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}
J. 货币系统
显然，只要a,b,c三者互质，即可凑出
#include <bits/stdc++.h>
using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";
void solve() {
int a, b, c;
std::cin >> a >> b >> c;
int d = std::gcd(a,b);
d = std::gcd(d,c);
if (d == 1) {
yes
} else {
no
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
// std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}
K.从南到北II
字符串的删除，模拟即可
#include <bits/stdc++.h>
using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";
void solve() {
int n;
std::cin >> n;
std::string s;
std::cin >> s;
if (n < 3) {
std::cout << s << "\n";
return;
}
if (n == 3) {
if (s == "hui" or s == "hen") {
s = " ";
}
std::cout << s << "\n";
return;
}
std::string ans = "";
int i;
for (i = 0; i < n - 2; i ++) {
if (s[i] == 'h' and s[i + 1] == 'u' and s[i + 2] == 'i') {
i += 2;
continue;
}
if (s[i] == 'h' and s[i + 1] == 'e' and s[i + 2] == 'n') {
i += 2;
continue;
}
ans += s[i];
}
if (i != n) {
while (i < n) {
ans += s[i];
i ++;
}
}
if (ans.size() == 0) {
std::cout << " " << "\n";
return;
}
std::cout << ans << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
// std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}
L. 选拔
排序
#include <bits/stdc++.h>
using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<int> a(n + 1);
std::vector<std::vector<int>> adj(n + 1);
std::vector<int> v;
for (int i = 1; i <= n; i ++) {
int k;
std::cin >> k;
for (int j = 1; j <= k; j ++) {
int x;
std::cin >> x;
adj[i].push_back(x);
}
std::sort(adj[i].begin(), adj[i].end(),std::greater());
a[i] = adj[i][0];
}
std::sort(a.begin() + 1, a.end(),std::greater());
if (m <= n) {
std::cout << std::accumulate(a.begin() + 1, a.begin() + 1 + m,0ll);
} else {
int ans = std::accumulate(a.begin() + 1, a.end(),0ll);
for (int i = 1; i <= n; i ++) {
for (int j = 1; j < adj[i].size(); j ++) {
v.push_back(adj[i][j]);
}
}
std::sort(v.begin(), v.end(),std::greater());
m -= n;
ans += std::accumulate(v.begin(), v.begin() + m,0ll);
std::cout << ans << "\n";
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
// std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}
M.远方
只要没有>=x 的建筑即可
#include <bits/stdc++.h>
using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "yes\n";
#define no std::cout << "no\n";
void solve() {
int n, x;
std::cin >> n >> x;
bool ok = true;
for (int i = 0; i < n; i ++) {
int y;
std::cin >> y;
if (y >= x) {
ok = false;
}
}
if (ok) {
yes
} else {
no
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
// std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}
京公网安备 11010502036488号