/* * > CPP Code Snippet < * > Powered by Microsoft Visual Studio Code < * * @Author FrankWKD (wangkedi01) * @Date 2025-07-09 * @Network "https://oj.czos.cn/contest/problem?id=25410&pid=1" * @License GNU General Public License 2.0 * @Platform [Frank]iMac Ubuntu Pro 24.04 LTS * @FileName T2.cpp * @FilePath /media/frank/FrankW/_default/_Mine!/Working/code-spaces/czos/CSP-S_Practise/Lesson1/T2.cpp * @Solution - */
// #pragma GCC optimize(3) #include<bits/stdc++.h> usingnamespace std; constint N = 100005; int a[N], n; boolcmp(int m, int b){ return m > b; } intmain(){ scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } sort(a + 1, a + n + 1, cmp); int ans = n; for (int i = n, j = n; i >= 1; i--) { if (a[i] > a[j]) { j--; ans--; } } printf("%d", ans); return0; }
T3 [CSP-S 2024] 超速检测
题目描述
小 D 新入职了某国的交管部门，他的第一个任务是负责国家的一条长度为 L 的南北主干道的车辆超速检测。为了考考小 D，上司首先需要他解决一个简化的场景。
这个周末，主干道上预计出现 n 辆车，其中第 i 辆车从主干道上距离最南端 di 的位置驶入，以 vi 的初速度和 ai 的加速度做匀加速运动向北行驶。我们只考虑从南向北的车辆，故 vi>0，但 ai 可正可负，也可以为零。当车辆行驶到主干道最北端（即距离最南端为 L 的位置）或速度降为 0（这只可能在 ai<0 时发生）时，我们认为该车驶离主干道。
主干道上设置了 m 个测速仪，其中第 j 个测速仪位于主干道上距离最南端 pj 的位置，每个测速仪可以设置开启或关闭。当某辆车经过某个开启的测速仪时，若这辆车的瞬时速度超过了道路限速 V，那么这辆车就会被判定为超速。注意当车辆驶入与驶出主干道时，如果在对应位置有一个开启的测速仪，这个测速仪也会对这辆车进行测速。
上司首先想知道，如果所有测速仪都是开启的，那么这 n 辆车中会有多少辆车被判定为超速。
其次，为了节能，部门想关闭一部分测速仪。然而，他们不希望漏掉超速的车，也就是说，当 n 辆车里的某辆车在所有测速仪都开启时被判定为超速，他们希望在关闭一部分测速仪以后它依然被判定为超速。上司还想知道在这样的条件下最多可以关闭多少测速仪。
structrange { int b, e; } b[N]; int p[N]; int n, m, len, v; int cnt, T, res;
intpf(int x){ return x * x; } boolcheck(int di, int vi, int ai, int ed){ returnpf(vi) + 2 * ai * (ed - di) > pf(v); } pair<int, int> find(int di, int vi, int ai){ int t = lower_bound(p + 1, p + m + 1, di) - p; if (ai > 0) { int l = t; int r = m; while (l <= r) { int mid = l + r >> 1; if (check(di, vi, ai, p[mid])) r = mid - 1; else l = mid + 1; } return {l, m}; } if (ai < 0) { int l = t, r = m, mid; while (l <= r) { mid = l + r >> 1; if (check(di, vi, ai, p[mid])) l = mid + 1; else r = mid - 1; } return {t, l - 1}; } } boolcmp(range r1, range r2){ return r1.e < r2.e; } intsolve(){ sort(b + 1, b + cnt + 1, cmp); int res = 0, ls = -1; for (int i = 1; i <= cnt; i++) { if (b[i].b > ls) { res++; ls = b[i].e; } } return m - res; }
intmain(){ // freopen("sample.in","r",stdin); // freopen("sample.out","w",stdout); // ios::sync_with_stdio(false); // cin.tie(0); cout.tie(0); cin >> T; while (T--) { cin >> n >> m >> len >> v; for (int i = 1; i <= n; i++) { cin >> a[i].d >> a[i].v >> a[i].a; } for (int i = 1; i <= m; i++) { cin >> p[i]; }
cnt = 0; int c0 = 0, c1 = 0; for (int i = 1; i <= n; i++) { if (a[i].a == 0) c0++; elseif (a[i].a > 0) c1++; if (a[i].d > p[m]) continue; if (a[i].v > v and a[i].a == 0) { int st = lower_bound(p + 1, p + m + 1, a[i].d) - p; b[++cnt] = {st, m}; continue; } if (a[i].v <= v and a[i].a <= 0) continue; if (a[i].a > 0and !check(a[i].d, a[i].v, a[i].a, p[m])) continue; int t = lower_bound(p + 1, p + 1 + m, a[i].d) - p; if (a[i].a < 0and !check(a[i].d, a[i].v, a[i].a, p[t])) continue; pair<int, int> pos = find(a[i].d, a[i].v, a[i].a); cnt++; b[cnt] = {pos.first, pos.second}; } if (c0 == n or c1 == n) { if (cnt == 0) res = m; else res = m - 1; } else res = solve(); cout << cnt << " " << res << endl; } // fclose(stdin); // fclose(stdout); return0; }
/* * > CPP Code Snippet < * > Powered by Microsoft Visual Studio Code < * * @Author FrankWKD * @Date 2025-08-04 * @Network "https://oj.czos.cn/contest/problem?id=25410&pid=3" * @License GNU General Public License 2.0 * @Platform [Frank]iMac Ubuntu Pro 24.04 LTS * @Name T4.cpp * @Path /media/frank/FrankW/_default/Mine/Working/code-spaces/OI/OJ/czos/CSP-S_Practise/Lesson1/T4.cpp * @Sol -- */
// #pragma GCC optimize(3) #define _for(cc, ba, ab) for (int cc = (ba); cc <= (ab); cc++) #define for_(cc, ba, ab) for (int cc = (ba); cc >= (ab); cc--) #include<bits/stdc++.h> usingnamespace std; #define int long long #define i2 __int128 constint N = 1e5 + 10; structtree { int ai, bi, ci, ti, idx; } a[N], b[N]; structnode { int to, nxt; } edge[N * 2]; int pre[N], k = 0; int fa[N]; int n, x, y; bool f[N]; int plant[N]; int poi[N], len = 0; boolcmp(tree n1, tree n2){ return n1.ti < n2.ti; } voidadd(int u, int v){ edge[++k] = {v, pre[u]}; pre[u] = k; } voiddfs(int x, int fath){ fa[x] = fath; for (int i = pre[x]; i; i = edge[i].nxt) { int to = edge[i].to; if (to != fath) { dfs(to, x); } } } i2 height(int x, i2 s, i2 e){ if (a[x].ci >= 0) return a[x].bi * (e - s + 1) + a[x].ci * (s + e) * (e - s + 1) / 2; i2 maxt = (1 - a[x].bi) / a[x].ci; if (maxt < s) return e - s + 1; if (maxt > e) return a[x].bi * (e - s + 1) + a[x].ci * (s + e) * (e - s + 1) / 2; return a[x].bi * (maxt - s + 1) + a[x].ci * (s + maxt) * (maxt - s + 1) / 2 + e - maxt; } intfind(int x, int end_time){ int l = 1, r = n, mid; while (l <= r) { mid = l + r >> 1; if (height(x, mid, end_time) >= a[x].ai) l = mid + 1; else r = mid - 1; } return l - 1; } boolcheck(int mid){ for (int i = 1; i <= n; i++) { if (height(i, 1, mid) < a[i].ai) return0; b[i] = a[i]; int ti = find(i, mid); b[i].ti = ti; plant[i] = ti; f[i] = 0; } sort(b + 1, b + n + 1, cmp); int day = 0, x, p; for (int i = 1; i <= n; i++) { if (f[b[i].idx] == 1) continue; len = 0; x = b[i].idx; poi[++len] = x; while (fa[x] != 0and f[fa[x]] == 0) { x = fa[x]; poi[++len] = x; } for (int j = len; j >= 1; j--) { p = poi[j]; day++; f[p] = 1; if (plant[p] < day) return0; } } return1; }
signedmain(){ // freopen("sample.in","r",stdin); // freopen("sample.out","w",stdout); ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i].ai >> a[i].bi >> a[i].ci; a[i].idx = i; } for (int i = 1; i <= n - 1; i++) { cin >> x >> y; add(x, y); add(y, x); } dfs(1, 0); int l = n, r = 1e9, mid; while (l <= r) { int mid = l + r >> 1; if (check(mid)) r = mid - 1; else l = mid + 1; } cout << l; return0; }
T5 草地上的羊
题目描述
小 A 的牧场里有很多块草地，每块草地上有若干只羊。他的羊经常在草地之间移动。为了确保每块草地的羊都有足够的草，小 A 决定不仅要考虑每块草地本身的羊的数量，还要计算周围草地可能会来到该草地的羊的数量。
牧场包含 N 块草地，这些草地之间通过双向小路相连，总共有 N−1 条小路，连接了所有的草地。
第 i 块草地上有 Ai 只羊，小羊可能通过跨越最多 C 条小路去其他草地。
小 A 希望为每块草地计算出能到达该草地的最多的数量，但他的牧场实在太大了，他不得不求助于聪明的你。
请你编程帮助小 A 计算出，对于每块草地，最多能到达该草地的羊的数量。
