CSP认证
202203-1 未初始化警告
模拟
Sample Code (C++)
#include
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int n, k;
cin >> n >> k;
vector ok(n + 1, 0);
ok[0] = 1;
int ans = 0;
for(int i = 0; i < k; ++ i) {
int x, y;
cin >> x >> y;
if(ok[y] == 0) ans ++;
ok[x] = 1;
}
cout << ans << "\n";
return 0;
}
202203-2 出行计划
\(t - c + 1 <= q + k <= t\), 偏移一下，做差分前缀和
Sample Code (C++)
#include
using namespace std;
int sum[500010];
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
int dlt = 200000;
for(int i = 0; i < n; ++ i) {
int t, c;
cin >> t >> c;
sum[t - c + 1 + dlt] += 1;
sum[t + 1 + dlt] -= 1;
}
for(int i = 0; i < 500010; ++ i) sum[i] += sum[i - 1];
for(int i = 0, x; i < m; ++ i) {
cin >> x;
cout << sum[x + k + dlt] << "\n";
}
return 0;
}
202203-3 计算资源调度器
按题意模拟，写的巨丑无比
Sample Code (C++)
#include
using namespace std;
const int N = 1010;
int n, m, k, l[N];
int f, a, na, pa, paa, paar;
int cnt[N];
map> region;
map> point;
vector Filter(int a, int na, int pa, int paa, int paar) {
vector ans(n);
for(int i = 0; i < n; ++ i) ans[i] = i + 1;
if(na) {
vector res;
for(int &x : ans)
if(l[x] == na)
res.push_back(x);
ans = res;
}
if(pa) {
vector res;
map t;
for(int &x : region[pa]) {
t[x] = 1;
}
for(int &x : ans)
if(t.count(l[x])) {
res.push_back(x);
}
ans = res;
}
if(paa) {
vector res;
map t;
for(int &x : point[paa]) {
t[x] = 1;
}
for(int &x : ans)
if(!t.count(x)) {
res.push_back(x);
}
if(paar == 0 and res.size() == 0) return ans;
ans = res;
}
return ans;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
for(int i = 1; i <= n; ++ i) cin >> l[i];
cin >> k;
for(int i = 1; i <= k; ++ i) {
cin >> f >> a >> na >> pa >> paa >> paar;
for(int j = 1; j <= f; ++ j) {
vector ans = Filter(a, na, pa, paa, paar);
if(ans.size() == 0) {
cout << "0" << " \n"[j == f];
continue;
}
sort(ans.begin(), ans.end(), [&](const int &x, const int &y) {
if(cnt[x] != cnt[y])
return cnt[x] < cnt[y];
return x < y;
});
cout << ans[0] << " \n"[j == f];
cnt[ans[0]] ++;
region[a].push_back(l[ans[0]]);
point[a].push_back(ans[0]);
}
}
return 0;
}
202203-4 通信系统管理
set或者可删除堆维护一下，维护“通信对”细节较多
Sample Code (C++)
#include
using namespace std;
using LL = long long;
const int N = 100010;
struct Node {
LL w;
int v;
bool operator < (const Node& t) const {
if(w != t.w) return w < t.w;
return v > t.v;
}
};
struct Query {
int u, v, w;
};
int n, m, cnt1, cnt2;
vector del[N];
unordered_map mp;
unordered_map pp;
set S[N];
void _add(int u, int v, int w) {
LL st = 1LL * (u - 1) * n + v;
int L = S[u].size();
S[u].erase({mp[st], v});
mp[st] += w;
if(mp[st] != 0)
S[u].insert({mp[st], v});
int R = S[u].size();
if(L && !R) cnt1 ++;
if(!L && R) cnt1 --;
if(S[u].size() == 0) {
if(pp.count(pp[u]) && pp[pp[u]] == u) cnt2 --;
pp.erase(u);
}
if(S[u].size() && pp[u] != S[u].rbegin()->v) {
if(pp.count(pp[u]) && pp[pp[u]] == u) cnt2 --;
pp.erase(u);
int to = S[u].rbegin()->v;
if(S[to].size() && S[to].rbegin()->v == u) {
pp[to] = u;
pp[u] = to;
cnt2 ++;
}
}
if(S[u].size() && S[v].size() && S[u].rbegin()->v == v and S[v].rbegin()->v == u)
if(pp[u] != v) pp[u] = v, pp[v] = u, cnt2 ++;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
cnt1 = n;
for(int i = 0; i < m; ++ i) {
int k; cin >> k;
for(auto &q: del[i]) _add(q.u, q.v, q.w), _add(q.v, q.u, q.w);
for(int j = 0; j < k; ++ j) {
int u, v, x, y; cin >> u >> v >> x >> y;
_add(u, v, x), _add(v, u, x);
if(i + y < m) del[i + y].push_back({u, v, -x});
}
int l; cin >> l;
for(int j = 0, x; j < l; ++ j) {
cin >> x;
if(S[x].size() == 0) cout << "0" << "\n";
else cout << (S[x].rbegin()->v) << "\n";
}
int p, q; cin >> p >> q;
if(p) cout << cnt1 << "\n";
if(q) cout << cnt2 << "\n";
}
return 0;
}
202112-1 序列查询
模拟
Sample Code (C++)
#include
using namespace std;
using LL = long long;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int n, N;
cin >> n >> N;
vector A(n + 2);
for(int i = 1; i <= n; ++ i) cin >> A[i];
A[n + 1] = N;
LL ans = 0;
for(int i = 0; i <= n; ++ i)
ans += 1LL * (A[i + 1] - A[i]) * i;
cout << ans << "\n";
return 0;
}
202112-2 序列查询新解
搞成两组区间，在重叠的地方计算
Sample Code (C++)
#include
using namespace std;
using LL = long long;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int n, N;
cin >> n >> N;
vector A(n + 2), B;
for(int i = 1; i <= n; ++ i) cin >> A[i];
A[n + 1] = N;
int t = 0;
while(t <= N) {
B.push_back(t);
t += N / (n + 1);
}
if(B.back() != N) B.push_back(N);
LL ans = 0;
for(int i = 0, j = 0; i <= n; ++ i) {
while(j + 1 < B.size() && B[j + 1] < A[i + 1]) {
ans += 1LL * abs(j - i) * (B[j + 1] - max(A[i], B[j]));
j ++;
}
ans += 1LL * abs(j - i) * (A[i + 1] - max(A[i], B[j]));
}
cout << ans << "\n";
return 0;
}
202112-3 登机牌条码
前几个点按题意模拟，后半部分模拟多项式除法、乘法，过程中取模
Sample Code (C++)
#include
using namespace std;
const int P = 929;
int _type(char &x) {
if(x >= '0' && x <= '9') return 0;
if(x >= 'A' && x <= 'Z') return 1;
if(x >= 'a' && x <= 'z') return 2;
}
int _val(char &x) {
if(_type(x) == 0) return x - '0';
if(_type(x) == 1) return x - 'A';
if(_type(x) == 2) return x - 'a';
}
int _tran(char &x, char &y) {
int tx = _type(x), ty = _type(y);
if(tx == ty) return 0;
if(tx == 0 && ty == 1) return 28;
if(tx == 2 && ty == 0) return 28;
if(tx == 1 && ty == 0) return 28;
if(tx == 1 && ty == 2) return 27;
if(tx == 0 && ty == 2) return 27;
if(tx == 2 && ty == 1) return 56;
}
using poly = vector;
int power(int a, int b) {
int res = 1;
for(; b; b >>= 1, a = a * a % P)
if(b & 1) res = res * a % P;
return res;
}
poly _mul(poly &a, poly &b) {
poly c(a.size() + b.size() - 1);
for(int i = 0; i < (int)a.size(); ++ i)
for(int j = 0; j < (int)b.size(); ++ j)
c[i + j] = (c[i + j] + a[i] * b[j] % P) % P;
return c;
}
poly _div(poly &a, poly &b, int k) {
poly c(k);
int na = a.size(), nb = b.size();
for(int i = na - 1; i >= 0; -- i) {
int bs = i - nb + 1;
if(bs < 0) break;
int xs = a[i] * power(b.back(), P - 2) % P;
for(int j = 0; j < nb; ++ j)
a[j + bs] = (a[j + bs] - xs * b[j] % P + P) % P;
}
for(int i = 0; i < k; ++ i) c[i] = a[i];
while(c.back() == 0) c.pop_back();
return c;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cin.tie(nullptr);
int w, s;
string str;
cin >> w >> s >> str;
vector v;
char START = 'A';
for(int i = 0; i < (int)str.size(); ++ i) {
int tr;
if(i) tr = _tran(str[i - 1], str[i]);
else tr = _tran(START, str[i]);
if(tr) {
if(tr == 56) v.push_back(28), v.push_back(28);
else v.push_back(tr);
}
v.push_back(_val(str[i]));
}
if(v.size() & 1) v.push_back(29);
vector ans;
int k = 0;
if(s != -1) k = (1 << (s + 1));
ans.push_back((v.size() / 2 + w - 1) / w * w);
for(int i = 0; i < (int)v.size(); i += 2) ans.push_back(v[i] * 30 + v[i + 1]);
while((ans.size() + k) % w) ans.push_back(900);
ans[0] = ans.size();
for(int &x : ans) cout << x << "\n";
if(s != -1) {
poly g(1, 1);
for(int i = 1, th = 1; i <= k; ++ i) {
th = th * 3 % P;
poly t = {-th, 1};
g = _mul(g, t);
}
poly d(ans.size() + k);
for(int i = 0; i < ans.size(); ++ i) d[ans.size() - 1 - i + k] = ans[i];
poly r = _div(d, g, k);
reverse(r.begin(), r.end());
for(int &x : r) cout << (-x % P + P) % P << "\n";
}
return 0;
}
202112-4 磁盘文件操作
离散化的时候记录两侧的点，线段树维护权值、编号、状态即可，不难写
Sample Code (C++)
#include
#define tm (tl + tr >> 1)
#define ls (u << 1)
#define rs (ls | 1)
#define FF 0
#define OO 1
#define RR 2
using namespace std;
using PII = pair;
const int N = 1000010;
struct Query {
int op, id, l, r, x, p;
};
int n, m, k;
int w[N << 2], idx[N << 2], sta[N << 2];
void pushup(int u) {
w[u] = (w[ls] == w[rs] ? w[ls] : INT_MAX);
idx[u] = (idx[ls] == idx[rs] ? idx[ls] : INT_MAX);
sta[u] = (sta[ls] == sta[rs] ? sta[ls] : INT_MAX);
}
void pushdown(int u) {
if(w[u] != INT_MAX) w[ls] = w[rs] = w[u];
if(idx[u] != INT_MAX) idx[ls] = idx[rs] = idx[u];
if(sta[u] != INT_MAX) sta[ls] = sta[rs] = sta[u];
}
void build(int u, int tl, int tr) {
if(tl == tr) return;
build(ls, tl, tm);
build(rs, tm + 1, tr);
pushup(u);
}
int query_pos(int u, int tl, int tr, int l, int id) {
if(sta[u] == FF || sta[u] == RR || idx[u] == id) return tr;
if(sta[u] == OO && idx[u] != INT_MAX) return -1;
pushdown(u);
if(l <= tm) {
int L = query_pos(ls, tl, tm, l, id);
if(L < tm) return L;
int R = query_pos(rs, tm + 1, tr, l, id);
return R == -1 ? L : R;
}
return query_pos(rs, tm + 1, tr, l, id);
};
void write_val(int u, int tl, int tr, int l, int r, int id, int x) {
if(tl >= l and tr <= r) {
sta[u] = OO;
idx[u] = id;
w[u] = x;
return;
}
pushdown(u);
if(l <= tm) write_val(ls, tl, tm, l, r, id, x);
if(r > tm) write_val(rs, tm + 1, tr, l, r, id, x);
pushup(u);
}
bool query_del(int u, int tl, int tr, int l, int r, int id) {
if(tl >= l and tr <= r) {
if(sta[u] == OO && idx[u] == id) return true;
else return false;
}
pushdown(u);
bool res = true;
if(l <= tm) res &= query_del(ls, tl, tm, l, r, id);
if(r > tm) res &= query_del(rs, tm + 1, tr, l, r, id);
return res;
}
bool query_rec(int u, int tl, int tr, int l, int r, int id) {
if(tl >= l and tr <= r) {
if(sta[u] == RR && idx[u] == id) return true;
else return false;
}
pushdown(u);
bool res = true;
if(l <= tm) res &= query_rec(ls, tl, tm, l, r, id);
if(r > tm) res &= query_rec(rs, tm + 1, tr, l, r, id);
return res;
}
void del(int u, int tl, int tr, int l, int r, int id) {
if(tl >= l and tr <= r) {
sta[u] = RR;
return;
}
pushdown(u);
if(l <= tm) del(ls, tl, tm, l, r, id);
if(r > tm) del(rs, tm + 1, tr, l, r, id);
pushup(u);
}
void rec(int u, int tl, int tr, int l, int r, int id) {
if(tl >= l and tr <= r) {
sta[u] = OO;
return;
}
pushdown(u);
if(l <= tm) rec(ls, tl, tm, l, r, id);
if(r > tm) rec(rs, tm + 1, tr, l, r, id);
pushup(u);
}
pair query_ans(int u, int tl, int tr, int p) {
if(tl == p and tr == p) return {sta[u], {idx[u], w[u]}};
pushdown(u);
if(p <= tm) return query_ans(ls, tl, tm, p);
else return query_ans(rs, tm + 1, tr, p);
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m >> k;
vector Q(k);
vector nums;
for(int i = 0; i < k; ++ i) {
int op = 0, id = 0, l = 0, r = 0, x = 0, p = 0;
cin >> op;
if(op == 0) cin >> id >> l >> r >> x;
if(op == 1 || op == 2) cin >> id >> l >> r;
if(op == 3) cin >> p;
Q[i] = {op, id, l, r, x, p};
if(op != 3) {
nums.push_back(l);
nums.push_back(r);
if(l != 1) nums.push_back(l - 1);
if(r != m) nums.push_back(r + 1);
}
else nums.push_back(p);
}
nums.push_back(0);
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
m = nums.size();
for(int i = 0; i < k; ++ i) {
if(Q[i].op != 3) {
Q[i].l = lower_bound(nums.begin(), nums.end(), Q[i].l) - nums.begin();
Q[i].r = lower_bound(nums.begin(), nums.end(), Q[i].r) - nums.begin();
}
else Q[i].p = lower_bound(nums.begin(), nums.end(), Q[i].p) - nums.begin();
}
build(1, 1, m - 1);
for(int i = 0; i < k; ++ i) {
if(Q[i].op == 0) {
Q[i].r = min(Q[i].r, query_pos(1, 1, m - 1, Q[i].l, Q[i].id));
if(Q[i].r != -1) write_val(1, 1, m - 1, Q[i].l, Q[i].r, Q[i].id, Q[i].x);
cout << (Q[i].r == -1 ? -1 : nums[Q[i].r]) << "\n";
}
if(Q[i].op == 1) {
if(query_del(1, 1, m - 1, Q[i].l, Q[i].r, Q[i].id)) {
del(1, 1, m - 1, Q[i].l, Q[i].r, Q[i].id);
cout << "OK\n";
}
else cout << "FAIL\n";
}
if(Q[i].op == 2) {
if(query_rec(1, 1, m - 1, Q[i].l, Q[i].r, Q[i].id)) {
rec(1, 1, m - 1, Q[i].l, Q[i].r, Q[i].id);
cout << "OK\n";
}
else cout << "FAIL\n";
}
if(Q[i].op == 3) {
pair ans = query_ans(1, 1, m - 1, Q[i].p);
if(ans.first == OO) cout << ans.second.first << " " << ans.second.second << "\n";
else cout << "0 0\n";
}
}
return 0;
}