试题 A: 握手问题
本题总分:\(5\) 分
思路:组合计数,用为 \(50\) 个人握手的总方案数 \(C^{2}_{50}\) ,减去七个人彼此没有握手握手的方案数 \(C^{2}_{7}\) 即为答案。
A: 握手问题
#include <bits/stdc++.h>
#define int long long
#define db long double
#define all(f) f.begin(), f.end()
#define rall(f) f.rbegin(), f.rend()
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define MOD 998244353
#define x first
#define y second
using namespace std;
const int N = 2e5 + 10, M = 1010, S = 25;
typedef pair<int, int> pii;
const db eps = 1e-8;
const db pi = acos(-1);
int f[N], n, m;
inline void solve() {
int ans = 50 * 49 / 2 - 7 * 6 / 2;
cout << ans << '\n';
//1204
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int _ = 1;
cout << fixed << setprecision(8);
// cin >> _;
while(_ --) {
solve();
} return _ ^ _;
}
答案:\(1204\)
试题 B: 小球反弹
本题总分:\(5\) 分
思路:玄学路程 \(sqrt(n * n + m * m / 15 / 15 / 17 / 17)\) ,赛时写的,不一定对 \(QWQ\)
B: 小球反弹
#include <bits/stdc++.h>
#define int long long
#define db long double
#define all(f) f.begin(), f.end()
#define rall(f) f.rbegin(), f.rend()
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define MOD 998244353
#define x first
#define y second
using namespace std;
const int N = 2e5 + 10, M = 1010, S = 25;
typedef pair<int, int> pii;
const db eps = 1e-8;
const db pi = acos(-1);
db ans, n, m;
inline void solve() {
n = 343720, m = 233333;
n = n * n + m * m;
ans = (n / 15 / 15 / 17 / 17);
cout << ans * 4 << '\n';
//10616699.87
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int _ = 1;
cout << fixed << setprecision(2);
// cin >> _;
while(_ --) {
solve();
} return _ ^ _;
}
答案:10616699.87
试题 C: 好数
时间限制: \(1.0s\) 内存限制: \(256.0MB\) 本题总分:\(10\) 分
思路:暴力枚举 \(1->n\) ,把当前数转为字符串,判断j % 2 == s[s.size() - j - 1] % 2
,若成立则不是好数,统计答案
C: 好数
#include <bits/stdc++.h>
#define int long long
#define db long double
#define all(f) f.begin(), f.end()
#define rall(f) f.rbegin(), f.rend()
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define MOD 998244353
#define x first
#define y second
using namespace std;
const int N = 2e5 + 10, M = 1010, S = 25;
typedef pair<int, int> pii;
const db eps = 1e-8;
const db pi = acos(-1);
int ans, n, m;
inline void solve() {
cin >> n;
for(int i = 1; i <= n; i ++) {
string s = to_string(i);
bool ok = true;
for(int j = 0; j < s.size(); j ++) {
if(j % 2 == s[s.size() - j - 1] % 2) {
ok = false;
break;
}
} if(ok) {
ans ++;
}
} cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int _ = 1;
cout << fixed << setprecision(2);
// cin >> _;
while(_ --) {
solve();
} return _ ^ _;
}
试题 D: R 格式
时间限制: \(1.0s\) 内存限制: \(256.0MB\) 本题总分:\(10\) 分
思路:用long double
存储答案,先乘以 \(2\) 的次方倍,在ans = n + 0.5
格式化输出整数
D: R 格式
#include <bits/stdc++.h>
#define int long long
#define db long double
#define all(f) f.begin(), f.end()
#define rall(f) f.rbegin(), f.rend()
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define MOD 998244353
#define x first
#define y second
using namespace std;
const int N = 2e5 + 10, M = 1010, S = 25;
typedef pair<int, int> pii;
const db eps = 1e-8;
const db pi = acos(-1);
db ans, n;
int m;
inline void solve() {
cin >> m >> n;
for(int i = 0; i < m; i ++) {
n *= 2.0;
} n += 0.5;
cout << n << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int _ = 1;
cout << fixed << setprecision(0);
// cin >> _;
while(_ --) {
solve();
} return _ ^ _;
}
试题 E: 宝石组合
时间限制: \(1.0s\) 内存限制: \(256.0MB\) 本题总分:\(15\) 分
思路:公式化简后即为求 \(a, b, c\) 的最大公约数 \(gcd(a, b, c)\),(赛时没化简出来 \(QWQ\) ,写了个排序 + 暴力枚举)
E: 宝石组合
#include <bits/stdc++.h>
#define int long long
#define db long double
#define all(f) f.begin(), f.end()
#define rall(f) f.rbegin(), f.rend()
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define MOD 998244353
#define x first
#define y second
using namespace std;
const int N = 2e5 + 10, M = 1010, S = 25;
typedef pair<int, int> pii;
const db eps = 1e-8;
const db pi = acos(-1);
int n, m, ans;
int aa, bb, cc;
inline int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
inline int lcm(int a, int b) {
return a * b / gcd(a, b);
}
inline void solve() {
cin >> n;
vector<int> f(n);
for(int i = 0; i < n; i ++) {
cin >> f[i];
} sort(all(f));
for(int i = 0; i < n - 2; i ++) {
for(int j = i + 1; j < n - 1; j ++) {
for(int k = j + 1; k < n; k ++) {
int a = f[i], b = f[j], c = f[k];
int s = a * b * c;
int abc = lcm(lcm(a, b), c);
int ab = lcm(a, b);
int bc = lcm(b, c);
int ac = lcm(a, c);
if(ab > bc) {
swap(ab, bc);
} if(bc > ac) {
swap(bc, ac);
} s = s / ac * abc / ab / bc;
if(s > ans) {
ans = s;
aa = a, bb = b, cc = c;
}
}
}
} cout << aa << ' ' << bb << ' ' << cc << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int _ = 1;
cout << fixed << setprecision(0);
// cin >> _;
while(_ --) {
solve();
} return _ ^ _;
}
试题 F: 数字接龙
时间限制: \(1.0s\) 内存限制: \(256.0MB\) 本题总分:\(15\) 分
思路:\(DFS\) + 剪枝,把方向坐标与数字 \(1->8\) 对应初始化,每次递归判断下一个点是否可达 + 是否满足取模后升序 + 是否交叉
,后执行递归,递归时传入下一个能到达的点的坐标(x, y) + 当前走的数字a[nx][ny] + 统计的答案tt
,若到达右下角x == n - 1&&y == n - 1
,则判断并更新答案,答案依旧用long double
存,特判答案为-1
的情况,按照这个思路,代码调麻了,特殊情况没有特判完,应该不会全对
F: 数字接龙
#include <bits/stdc++.h>
#define int long long
#define deb(x) cout << #x << " = " << x << '\n'
#define all(f) f.begin(), f.end()
#define rall(f) f.rbegin(), f.rend()
#define all1(f) f.begin() + 1, f.end()
#define here system("pause")
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define MOD 998244353
#define mod 1000000007
#define endl "\n"
#define x first
#define y second
#ifdef LOCAL
#include "algo/debug.h"
#else
#define dbg(...) "cyh2.2"
#define debug(...) "cyh2.2"
#endif
using namespace std;
template <class T> inline void read(T& x) {x = 0;char c = getchar();bool f = 0;for(; !isdigit(c); c = getchar()) f ^= (c == '-'); for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48); x = f ? -x : x; }
template <class T> inline void write(T x) {if(x < 0) putchar('-'), x = -x;if(x < 10) putchar(x + 48);else write(x / 10), putchar(x % 10 + 48); }
inline int qmi(int a, int b, int p) {int ans = 1 % p;while(b){if(b & 1) ans = ans * a % p;a = a * a % p;b >>= 1;} return ans;}
inline int inv(int a, int p) {return qmi(a, p - 2, p) % p;}
const int N = 2e5 + 10, M = 150, maxn = 20;
const double pi = acos(-1);
const long double E = exp(1);
const double eps = 1e-8;
typedef pair<int, int> pii;
int a[M][M];
int ne[8][2] = {-1, 0, -1, 1, 0, 1, 1, 1, 1, 0, 1, -1, 0, -1, -1, -1};
int n, m;
double ans;
bool st[M][M];
inline void dfs(int x, int y, int t, double tt) {
if(x == n - 1&&y == n - 1) {
string s = to_string(tt);
int x = 0;
for(int i = 0; i < s.size(); i ++) {
if(s[i] == '.') {
x = i;
}
} if(x == n * n - 1) {
ans = min(ans, tt);
} //cout << tt << ' ';
return;
} for(int i = 0; i < 8; i ++) {
int nx = x + ne[i][0];
int ny = y + ne[i][1];
if(nx >= 0&&nx < n&&ny >= 0&&ny < n&&!st[nx][ny]&&((t == m - 1&&a[nx][ny] == 0)||(t < m - 1&&a[nx][ny] == t + 1))) {
bool ok = true;
if(st[nx][y]&&st[x][ny]) {
ok = false;
} if(ok) {
st[nx][ny] = true;
dfs(nx, ny, a[nx][ny], tt * 10 + i);
st[nx][ny] = false;
}
}
}
}
inline void solve() {
ans = 1e27;
cin >> n >> m;
for(int i = 0; i < n; i ++) {
for(int j = 0; j < n; j ++) {
cin >> a[i][j];
}
} if(a[0][0]) {
cout << -1 << '\n';
return ;
} st[0][0] = true;
dfs(0, 0, 0, 0);
if(ans > 1e26) {
ans = -1;
} cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int _ = 1;
// cin >> _;
cout << fixed << setprecision(0);
while(_ --) {
solve();
}
return _ ^ _;
}
试题 G: 爬山
时间限制: \(1.0s\) 内存限制: \(256.0MB\) 本题总分:\(20\) 分
思路:优先队列 + 贪心,用大根堆存储山的高度 \(h_i\),每次取出队头元素,判断 \(sqrt(x)\) 和 \(⌊\frac {x}{2}⌋\) 的大小,若可以操作则取最小值,若相等则优先用 \(sqrt(x)\) ,最后累加答案
有网友说大根堆+贪心
容易被 Hack
,后面官方题解也是用的这个思路,没办法,再拭目以待吧
G: 爬山
#include <bits/stdc++.h>
#define int long long
#define db long double
#define all(f) f.begin(), f.end()
#define rall(f) f.rbegin(), f.rend()
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define MOD 998244353
#define x first
#define y second
using namespace std;
const int N = 2e5 + 10, M = 1010, S = 25;
typedef pair<int, int> pii;
const db eps = 1e-8;
const db pi = acos(-1);
int f[N];
int n, p, q, ans;
inline void solve() {
cin >> n >> p >> q;
priority_queue<int, vector<int>, less<int> > qq;
for(int i = 1; i <= n; i ++) {
cin >> f[i];
qq.push(f[i]);
} while(q||p) {
int x = qq.top();
qq.pop();
int t = x, a = x, b = x;
if(p > 0) {
a = sqrt(x);
} if(q > 0) {
b = x / 2;
} if(a <= b&&p > 0) {
t = a;
p --;
} else if(q > 0) {
t = b;
q --;
} qq.push(t);
} while(qq.size()) {
int x = qq.top();
qq.pop();
ans += x;
} cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int _ = 1;
cout << fixed << setprecision(2);
// cin >> _;
while(_ --) {
solve();
} return _ ^ _;
}
试题 H: 拔河
时间限制: \(1.0s\) 内存限制: \(256.0MB\) 本题总分:\(20\) 分
思路:赛时看数据范围+样例说明
后直接前缀和 - 后缀和
出结果,但数据不一定保证两组成员人数之和必为 \(n\) ,一眼障目了 \(QWQ\) ,队友用的是前缀和 + 二维二分
暴力,但边界情况得处理好,不然也是容易被Hack
H: 拔河
#include <bits/stdc++.h>
#define int long long
#define db long double
#define all(f) f.begin(), f.end()
#define rall(f) f.rbegin(), f.rend()
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define MOD 998244353
#define x first
#define y second
using namespace std;
const int N = 2e5 + 10, M = 1010, S = 25;
typedef pair<int, int> pii;
const db eps = 1e-8;
const db pi = acos(-1);
int f[N], f1[N], f2[N];
int n, ans;
inline void solve() {
cin >> n, ans = 1e18;
for(int i = 1; i <= n; i ++) {
cin >> f[i];
f1[i] = f1[i - 1] + f[i];
} for(int i = n; i >= 1; i --) {
f2[i] = f2[i + 1] + f[i];
} for(int i = 1; i <= n; i ++) {
ans = min(ans, abs(f2[i] - f1[i - 1]));
} cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int _ = 1;
cout << fixed << setprecision(2);
// cin >> _;
while(_ --) {
solve();
} return _ ^ _;
}