省流： \(100+100+70+55\to100+100+70+0,325\to270\)
[CSP-S2020] 儒略日
乱搞。这道题太恶心了，场上用了 \(1h\) 才做出来。
代码过于抽象，不放了。
[CSP-S2020] 动物园
非常简单的黄题。
#include <bits/stdc++.h>
using namespace std;
unsigned long long n, m, c, k, b, a;
unsigned long long ans = 0;
bool vis[100];
int main()
{
scanf("%llu%llu%llu%llu", &n, &m, &c, &k);
ans = k;
for (unsigned long long i = 1; i <= n; i++)
{
scanf("%llu", &a);
b |= a;
}
for (unsigned long long i = 0; i < m; i++)
{
unsigned long long x, y;
scanf("%d%d", &x, &y);
vis[x] = 1;
}
for (unsigned long long i = 0; i < k; i++)
if (vis[i])
if (!(b & (1ull << i)))
ans--;
if (ans == 64 && !n)
puts("18446744073709551616");
else if (ans == 64)
{
printf("%llu\n", -n);
}
else
{
printf("%llu\n", (1ull << ans) - n);
}
}
[CSP-S2020] 函数调用
暴力 + 线段树模板 2 \(=70pts\)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int M = 4e5 + 10;
int l[M], r[M], sum[M], add[M], mul[M]; // Segment tree arrays
int n, q, m, mod, arr[N];
void pushdown(int o)
{
sum[o << 1] = (sum[o << 1] * mul[o] + add[o] * (r[o << 1] - l[o << 1] + 1)) % mod;
sum[o << 1 | 1] = (sum[o << 1 | 1] * mul[o] + add[o] * (r[o << 1 | 1] - l[o << 1 | 1] + 1)) % mod;
mul[o << 1] = mul[o << 1] * mul[o] % mod;
mul[o << 1 | 1] = mul[o << 1 | 1] * mul[o] % mod;
add[o << 1] = (add[o << 1] * mul[o] + add[o]) % mod;
add[o << 1 | 1] = (add[o << 1 | 1] * mul[o] + add[o]) % mod;
mul[o] = 1;
add[o] = 0;
}
void build(int o, int L, int R)
{
l[o] = L, r[o] = R;
add[o] = 0;
mul[o] = 1;
if (L == R)
{
sum[o] = arr[L];
return;
}
int mid = (L + R) >> 1;
build(o << 1, L, mid);
build(o << 1 | 1, mid + 1, R);
sum[o] = (sum[o << 1] + sum[o << 1 | 1]) % mod;
}
void update1(int o, int L, int R, int x)
{
if (max(L, l[o]) > min(R, r[o]))
return;
if (L <= l[o] && r[o] <= R)
{
mul[o] = mul[o] * x % mod;
sum[o] = sum[o] * x % mod;
add[o] = add[o] * x % mod;
return;
}
pushdown(o);
update1(o << 1, L, R, x);
update1(o << 1 | 1, L, R, x);
sum[o] = (sum[o << 1] + sum[o << 1 | 1]) % mod;
}
void update2(int o, int L, int R, int x)
{
if (max(L, l[o]) > min(R, r[o]))
return;
if (L <= l[o] && r[o] <= R)
{
add[o] = (add[o] + x) % mod;
sum[o] = (sum[o] + (r[o] - l[o] + 1) * x) % mod;
return;
}
pushdown(o);
update2(o << 1, L, R, x);
update2(o << 1 | 1, L, R, x);
sum[o] = (sum[o << 1] + sum[o << 1 | 1]) % mod;
}
int query(int o, int L, int R)
{
if (max(L, l[o]) > min(R, r[o]))
return 0;
if (L <= l[o] && r[o] <= R)
{
return sum[o];
}
pushdown(o);
return (query(o << 1, L, R) + query(o << 1 | 1, L, R)) % mod;
}
int T[N], v[N], p[N];
vector<int> Fun[N];
void F(int x)
{
// Iterative approach using a stack
stack<int> st;
st.push(x);
while (!st.empty())
{
int u = st.top();
st.pop();
if (T[u] == 1)
{
update2(1, p[u], p[u], v[u]);
}
else if (T[u] == 2)
{
update1(1, 1, n, v[u]);
}
else
{
for (int i = Fun[u].size() - 1; i >= 0; --i)
st.push(Fun[u][i]);
}
}
}
signed main()
{
mod = 998244353;
scanf("%lld", &n);
for (int i = 1; i <= n; ++i)
scanf("%lld", &arr[i]);
build(1, 1, n);
scanf("%lld", &m);
for (int i = 1; i <= m; ++i)
{
int op;
scanf("%lld", &op);
T[i] = op;
if (op == 1)
scanf("%lld%lld", &p[i], &v[i]);
else if (op == 2)
scanf("%lld", &v[i]);
else
{
int x;
scanf("%lld", &x);
while (x--)
{
int y;
scanf("%lld", &y);
Fun[i].push_back(y);
}
}
}
scanf("%lld", &q);
for (int i = 1; i <= q; ++i)
{
int x;
scanf("%lld", &x);
F(x);
}
for (int i = 1; i <= n; ++i)
printf("%lld ", query(1, i, i));
}
[CSP-S2020] 贪吃蛇
？
VP 后感觉暴力能拿 50pts。
赛事没看懂样例 2.2。
// 赛后补题
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int main()
{
int _;
scanf("%d", &_);
int n;
for (int cas = 1; cas <= _; cas++)
{
if (cas == 1)
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
}
else
{
int k;
scanf("%d", &k);
while (k--)
{
int x, y;
scanf("%d%d", &x, &y);
a[x] = y;
}
}
deque<pair<int, int>> q1, q2;
for (int i = 1; i <= n; i++)
q1.push_back({a[i], i});
int ans;
while (1)
{
if (q1.size() + q2.size() == 2)
{
ans = 1;
break;
}
int x, id, y;
y = q1.front().first, q1.pop_front();
if (q2.empty() || !q1.empty() && q1.back() > q2.back())
x = q1.back().first, id = q1.back().second, q1.pop_back();
else
x = q2.back().first, id = q2.back().second, q2.pop_back();
pair<int, int> now = make_pair(x - y, id);
if (q1.empty() || q1.front() > now)
{
ans = q1.size() + q2.size() + 2;
int cnt = 0;
while (1)
{
cnt++;
if (q1.size() + q2.size() + 1 == 2)
{
if (cnt % 2 == 0)
ans--;
break;
}
int x, id;
if (q2.empty() || !q1.empty() && q1.back() > q2.back())
x = q1.back().first, id = q1.back().second, q1.pop_back();
else
x = q2.back().first, id = q2.back().second, q2.pop_back();
now = {x - now.first, id};
if ((q1.empty() || now < q1.front()) && (q2.empty() || now < q2.front()))
;
else
{
if (cnt % 2 == 0)
ans--;
break;
}
}
break;
}
else
q2.push_front(now);
}
printf("%d\n", ans);
}
return 0;
}