CSP 前加训记录

userId_undefined
古希腊掌管AC和WA的神
出道萌新时间刺客时空双修者空间掌握者荣耀黄金快乐小狗

2026-10-05 17:55:14

发布于：上海

75阅读
0回复
0点赞

rt、
大多数是老师给的题单，还有一部分模拟赛、
大概率会常更、
9/27
模拟赛 1.5h3题
T1 P5661
直接上来暴力，时间复杂度 O(n2)O(n^2)，卡不满，能过、
代码

T2 P1197
我们可以使用并查集快速求解连通块，然而其并不支持删边。
正难则反，我们将删除操作改为复活操作，这样代码就呼之欲出了、
代码

T3 P5021
不会，只能注意到 m=1m=1 的情况下答案为该图的直径，可以获得 20pts。

100+100+0=200，T3没写完代码时间不够了、

题单
来一道水黄，欸你谷咋没原题，简单说一下、
给定一正整数 KK，求满足 K∣N!K \mid N! 的 NN 的最小值、
注意到可以做质因数分解，取可满足条件的最大值。采用二分查找解决。

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll cnt(ll n, ll p) {
    ll c = 0;
    while (n) { n /= p; c += n; }
    return c;
}

ll solve(ll p, ll a, ll k) {
    ll l = 1, r = k, ans;
    while (l <= r) {
        ll mid = (l + r) / 2;
        if (cnt(mid, p) >= a) { ans = mid; r = mid - 1; }
        else l = mid + 1;
    }
    return ans;
}

int main() {
    ll k;
    cin >> k;
    ll ans = 0, t = k;
    for (ll p = 2; p * p <= t; ++p) {
        if (t % p == 0) {
            ll a = 0;
            while (t % p == 0) { t /= p; ++a; }
            ans = max(ans, solve(p, a, k));
        }
    }
    if (t > 1) ans = max(ans, solve(t, 1, k));
    cout << ans;
}

9/28
啥阴啊，都没你姑原题、
题目大意
一共 nn 个位置，可以花费 aia_i 来从 ii 移动到 i+1i + 1。或者花费 bib_i 从 ii 移动到 xix_i。
直接建图跑最短路即可、

#include <bits/stdc++.h>
using namespace std;
#define N 200005
#define int long long
vector <pair <int, int> > g[N];
int dis[N], vis[N];

void Dijkstra(int s) {
    memset(dis, 0x3f, sizeof dis);
	dis[s] = 0;
	priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > pq;
	pq.push({0, s});
	while (pq.size()) {
		auto cur = pq.top();
		pq.pop();
		if (vis[cur.second]) continue;
		vis[cur.second] = 1;
		int w = cur.first, u = cur.second;
		for (auto i : g[u]) {
			if (dis[i.first] > w + i.second) {
				dis[i.first] = w + i.second;
				pq.push({dis[i.first], i.first});
			}
		}
	}
}

signed main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int w, x, y;
        cin >> w >> x >> y;
        g[i].push_back({i + 1, w});
        g[i].push_back({y, x});
    } Dijkstra(1);
    cout << dis[n];
    return 0;
}

10/1
国庆就得写题不是吗、
严肃完成尼姑月赛。

10/2
完了只有 2d 就要上课了咋办。
列车
最短路也能界限突破吗/yi
这个数据范围只能 堆优 dij\mathtt{dij}。
那么显然动态更新边权即可。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100005

vector <tuple <int, ll, ll> > g[N];
int n, m, s, e;
bool vis[N];
ll dis[N];

void Dijkstra(int s) {
    for (int i = 1; i <= n; i++) dis[i] = 4e18;
    dis[s] = 0;
    priority_queue <pair <ll, int>, vector <pair <ll, int> >, greater <pair <ll, int> > > pq;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        if (u == e) return ;
        for (auto [v, t, k] : g[u]) {
            ll w = d + ((d % k == 0) ? 0 : k - d % k) + t;
            if (w < dis[v]) {
                dis[v] = w;
                pq.push({w, v});
            }
        }
    }
}

int main() {
    cin >> n >> m >> s >> e;
    for (int i = 1; i <= m; i++) {
        int u, v;
        ll t, k;
        cin >> u >> v >> t >> k;
        g[u].push_back({v, t, k});
        g[v].push_back({u, t, k});
    }
    Dijkstra(s);
    cout << (dis[e] == 4e18 ? -1 : dis[e]) << '\n';
    return 0;
}

射击王
这能有绿吗。
因为求最大值最小考虑二分答案。
check\mathtt{check} 很容易想，求出每个气球的 deadline，然后排序并判断即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int h[100005], s[100005], dl[100005], n;

bool check(int mid) {
    for (int i = 1; i <= n; i++) {
        if (mid < h[i]) return 0;
        dl[i] = (mid - h[i]) / s[i];
    } sort(dl + 1, dl + n + 1);
    for (int i = 1; i <= n; i++) if (dl[i] < i - 1) return 0;
    return 1;
}

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i] >> s[i];
    int l = 1, r = 1e18, ans;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid - 1, ans = mid;
        else l = mid + 1;
    } cout << ans;
    return 0;
}

10/5
/yi
模拟赛 2h3题
T1 P1013
思路：（赛时没想出来）
法1：注意到 p+k=kp+k=k，u+v=w(w≥10)u+v=w(w\geq 10) 时，p=0p=0，10≤w<2010\leq w<20。
之后用数学方法推导即可。
法2：注意到 对于 00，有 00 个数字可以使其变为两位数。
对于 kk，有 kk 个数字可以使其变为两位数。
所以直接遍历即可。
代码懒得写了、

T2 P1119
开始是用 Dij 做，后来发现可能会 T 就做了卡常，最后差 40ms 遗憾离场。
结果知道 T 了以后在 10min 想出了正解/ll
那么怎么用 Floyd 呢？
首先 Floyd 是采用枚举中转点的方式，那么每次我们根据输入值做数次对于一点作为中转点的 Floyd 即可。
代码

T3 P5021
你咋又来了。
写了一个图的直径，顺利获得 20pts。

40+80+20=140、我拉完了。

userId_undefined
去预览
0/2000

全部评论 7

热门讨论