比赛链接:Here
很可惜,如果再强一点,就可以拿牌子了。
5道即可金牌尾 or 银首
F. Kobolds and Catacombs (思维)
真不难,只是理解错了题意
如果原数组 \(a\) 和 排序后的数组 \(b\) 在某个位置前缀和相同和可以划分为一组
const int N = 1e6 + 10;
ll a[N], b[N];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n; cin >> n;
for (int i = 1 ; i <= n; ++i) cin >> a[i], b[i] = a[i];
sort(a + 1, a + 1 + n);
ll sa = 0, sb = 0, cnt = 0;
for (int i = 1; i <= n; ++i) {
sa += a[i], sb += b[i];
if (sa == sb) cnt ++;
}
cout << cnt;
}
G. The Witchwood (签到)
递减排序然后累加前 \(k\) 个即可
H. The Boomsday Project
淦,很考验细节处理的单调队列优化DP,当初没学过,不知道怎么处理
const int N = 5e2 + 10;
int d[N], k[N], c[N];
struct Node {int p, q;} node[100005];
bool cmp(Node a, Node b) {return a.p < b.p;}
int t[100005 * 3]; //第几次是在第几天
ll dp[100005 * 3];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, m, r;
cin >> n >> m >> r;
for (int i = 1; i <= n; ++i) cin >> d[i] >> k[i] >> c[i];
int w = 0;
for (int i = 1; i <= m; ++i) cin >> node[i].p >> node[i].q;
sort(node + 1, node + 1 + m, cmp);
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= node[i].q; ++j) t[w + j] = node[i].p;
w += node[i].q;
}
t[0] = t[1];
dp[0] = 0;
for (int i = 1; i <= w; ++i) dp[i] = dp[i - 1] + r;
deque<int>q[n + 1];
for (int i = 1; i <= n; ++i) q[i].push_back(0);
for (int i = 1; i <= w; ++i) {
for (int j = 1; j <= n; ++j) {
while (!q[j].empty() and (t[i] - t[q[j].front() + 1] >= d[j] || i - q[j].front() > k[j]))
q[j].pop_front();
dp[i] = min(dp[i], dp[q[j].front()] + c[j]);
}
for (int j = 1; j <= n; ++j) {
while (!q[j].empty() and dp[i] <= dp[q[j].back()]) q[j].pop_back();
q[j].push_back(i);
}
}
cout << dp[w] << '\n';
}
I. Rise of Shadows
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
ll h, m, a;
cin >> h >> m >> a;
ll d = __gcd(h - 1, m);
cout << min(d * (2 * (a / d) + 1), h * m);
}
K . Scholomance Academy
真 · 阅读理解题
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n; cin >> n;
int s1 = 0, s2 = 0;
vector<int>v1, v2;
for (int i = 1; i <= n; ++i) {
char c; int x;
cin >> c >> x;
if (c == '+') s1++, v1.push_back(x);
else s2++, v2.push_back(x);
}
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
double ans = 0;
for (int i = 0; i < s1; ++i) {
ans += lower_bound(v2.begin(), v2.end(), v1[i]) - v2.begin();
}
ans = ans / s1 / s2;
cout << fixed << setprecision(10) << ans;
}