emmmmm, 这次比赛就3个小时, 前两个小时都是我和圣元在打, 过了6题, 其实如果我们在前面没有过多的讨论I题的话罚时可能更少, 名次应该会更靠前,所以下次即使有有思路的难题还是放在简单题后面好
D
当时我们大概讨论出来了方案,f[i][j]表示前i个人, 第二排有j个人的方案数(显然j <= i - j), 但我在写的时候有几个误区:
1 不应该去枚举人, 而是枚举身高, 身高相同的人是等效的, 最后乘以阶乘即可
2 显然f[i][j]更新的时候, 需要加上上一种情况一个区间内的方案数, 那不如在开一个数组做前缀和, O(1)求答案
细节还是挺多的, 还需要好好思考
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 5e3 + 10;
template < typename T > inline void read(T &x) {
x = 0; T ff = 1, ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') ff = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= ff;
}
int n, a[N], jc[N], b[N], f[N][N], g[N][N];
inline void pre() {
jc[0] = 1;
for (int i = 1; i <= n; ++i)
jc[i] = (ll )jc[i - 1] * i % mod;
}
int main() {
read(n);
pre();
for (int i = 1; i <= n; ++i) {
read(a[i]);
++b[a[i]];
}
int u = 0;
f[0][0] = 1, g[0][0] = 1;
for (int i = 1; i <= n; ++i) {
if (b[i]) {
int v = u + b[i];
for (int j = 0; j <= v / 2; ++j) {
int r = min(u / 2, j);
int l = max(0, j - b[i]);
if (l) f[v][j] = (g[u][r] - g[u][l - 1] + mod) % mod;
else f[v][j] = g[u][r];
}
g[v][0] = f[v][0];
for (int j = 1; j <= v / 2; ++j)
g[v][j] = (g[v][j - 1] + f[v][j]) % mod;
u = v;
}
}
ll ans = f[n][n / 2];
for (int i = 1; i <= n; ++i)
ans = ans * (ll) jc[b[i]] % mod;
cout << ans << endl;
return 0;
}
J
在比赛中A掉的题, 假如Alive选的总和为A(可正可负),那么原式就是|A|-|sum - A|, 那我们就想怎么把绝对值去掉, 那就要讨论sum和A的关系, 计算的A的最大值与sum比较,但是, 赛后我竟然把自己hack了, 或许人数据比较水, 上题解吧:
如果sum是负数的话把所有的数全部取负即可, 错解就不说了, 这数据。。。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 5e3 + 10;
template < typename T > inline void read(T &x) {
x = 0; T ff = 1, ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') ff = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= ff;
}
ll n, k = 1, a[N];
ll sum = 0, s1 = 0, s2;
int main() {
read(n);
for (int i = 1; i <= n; ++i) read(a[i]);
sort(a + 1, a + n + 1);
for (int i = n; i >= 1; --i) {
if (k == 1) s1 += a[i];
if (i & 1) s2 += a[i];
sum += a[i];
k ^= 1;
}
if (sum < 0) sum = -sum, s1 = -s2;
cout << abs(s1) - abs(sum - s1);
return 0;
}
H
emmmmmm, 赛场上写一个玄学算法一直RE, 不理解。 考场上我傻掉了, 直接两两比较了, 但是, 一个车如果相撞, 肯定先和旁边的车撞呀, 所以, 每个车考虑它的邻居即可, 当然, 是编号不相等的邻居, 由题意得, 我们可以二分答案, 每次都以当前的位置排序, 判断相对位置是否发生变化, 当然, 也有很多细节, 比如0和1也是一个相对位置, 最后还要检验是否无解, 还是挺难调的。。。。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int mod = 998244353;
const int N = 1e6 + 10;
template < typename T > inline void read(T &x) {
x = 0; T ff = 1, ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') ff = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= ff;
}
int n, k;
struct node {
int p, v, t;
int id, pre;
}a[N], b[N];
inline bool cmp(node x, node y) {
return x.p < y.p;
}
inline bool check(int t) {
for (int i = 1; i <= n; ++i)
b[i] = a[i], b[i].p = a[i].p + a[i].v * t;
sort(b + 1, b + n + 1, cmp);
for (int i = 1; i <= n; ++i) {
if (b[i].t == b[i - 1].t) continue;
if (b[i].p == b[i - 1].p) return true;
if (b[i].pre != b[i - 1].id) return true;
}
return false;
}
signed main() {
read(n), read(k);
for (int i = 1; i <= n; ++i)
read(a[i].p), read(a[i].v), read(a[i].t);
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; ++i) {
if (a[i].t == a[i - 1].t) {
a[i].id = a[i - 1].id;
a[i].pre = a[i - 1].pre;
} else {
a[i].id = a[i - 1].id + 1;
a[i].pre = a[i - 1].id;
} }
int l = 0, r = 2e9;
while (l < r) {
ll mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
if (!check(r)) puts("-1");
else cout << l - 1 << endl;
return 0;
}