阶段一测评

Algor

2025-12-20 16:18:39

发布于：广东

46阅读

0回复

0点赞

P2097 资料分发 1

#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
vector<int> G[N];
bool vis[N];
void dfs(int u) {
    for(int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if(vis[v]) continue;
        vis[v] = true, dfs(v);
    }
}
int main() {
    int n, m, ans = 0;
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i = 1; i <= n; i++) {
        if(vis[i]) continue;
        ans++, vis[i] = true, dfs(i);
    }
    cout << ans << endl;
    return 0;
}

P1603 斯诺登的密码

#include <bits/stdc++.h>
using namespace std;
map<string, string> mp;
int cnt;
string a[10];
int main() {
    mp["one"] = "01";
    mp["two"] = "04";
    mp["three"] = "09";
    mp["four"] = "16";
    mp["five"] = "25";
    mp["six"] = "36";
    mp["seven"] = "49";
    mp["eight"] = "64";
    mp["nine"] = "81";
    mp["ten"] = "00";
    mp["eleven"] = "21";
    mp["twelve"] = "44";
    mp["thirteen"] = "69";
    mp["fourteen"] = "96";
    mp["fifteen"] = "25";
    mp["sixteen"] = "56";
    mp["seventeen"] = "89";
    mp["eighteen"] = "24";
    mp["nineteen"] = "61";
    mp["twenty"] = "00";
    mp["a"] = "01";
    mp["both"] = "04";
    mp["another"] = "01";
    mp["first"] = "01";
    mp["second"] = "04";
    mp["third"] = "09";
    string s, t;
    while(cin >> s) {
        if(mp.find(s) == mp.end()) continue;
        a[++cnt] = mp[s];
    }
    sort(a + 1, a + 1 + cnt);
    for(int i = 1; i <= cnt; i++) t += a[i];
    bool flag = false;
    for(int i = 0; i < t.size(); i++) {
        if(s[i] != '0') flag = true;
    }
    if(flag == false) {
        cout << 0;
        return 0;
    }
    int be = 0;
    while(t[be] == '0') be++;
    for(int i = be; i < t.size(); i++) cout << t[i];
    return 0;
}

更简单的写法

#include <bits/stdc++.h>
using namespace std;
map<string, string> mp;
int cnt;
string a[10];
int main() {
    mp["one"] = "01";
    mp["two"] = "04";
    mp["three"] = "09";
    mp["four"] = "16";
    mp["five"] = "25";
    mp["six"] = "36";
    mp["seven"] = "49";
    mp["eight"] = "64";
    mp["nine"] = "81";
    mp["ten"] = "00";
    mp["eleven"] = "21";
    mp["twelve"] = "44";
    mp["thirteen"] = "69";
    mp["fourteen"] = "96";
    mp["fifteen"] = "25";
    mp["sixteen"] = "56";
    mp["seventeen"] = "89";
    mp["eighteen"] = "24";
    mp["nineteen"] = "61";
    mp["twenty"] = "00";
    mp["a"] = "01";
    mp["both"] = "04";
    mp["another"] = "01";
    mp["first"] = "01";
    mp["second"] = "04";
    mp["third"] = "09";
    string s, t = "0";
    while(cin >> s) {
        if(mp.find(s) == mp.end()) continue;
        a[++cnt] = mp[s];
    }
    sort(a + 1, a + 1 + cnt);
    for(int i = 1; i <= cnt; i++) t += a[i];
    cout << stoll(t);
    return 0;
}

P1007 独木桥

#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5;
int pos[N];
int main() {
    int L, n, mn = 0, mx = 0;
    cin >> L >> n;
    for(int i = 1; i <= n; i++) cin >> pos[i];
    for(int i = 1; i <= n; i++) {
        if(pos[i] <= L / 2) {
            mn = max(mn, pos[i]);
            mx = max(mx, L - pos[i] + 1);
        }
        else {
            mx = max(mx, pos[i]);
            mn = max(mn, L - pos[i] + 1);
        }
    }
    cout << mn << ' ' << mx << endl;
    return 0;
}

P1843 奶牛晒衣服

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int w[N], n, a, b;
bool check(int x) {
    int tot = 0;
    for(int i = 1; i <= n; i++) {
        int t = w[i] - a * x;
        if(t > 0) tot += (t + b - 1) / b;
    }
    return tot <= x;
}
int main() {
    int l = 1, r = N;
    cin >> n >> a >> b;
    for(int i = 1; i <= n; i++) cin >> w[i];
    while(l < r) {
        int mid = (l + r) / 2;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l;
    return 0;
}

P14635 [NOIP2025] 糖果店 / candy（官方数据）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
#define int long long
int a[N];
signed main() {
    // 只可能最多有一种糖果买多个
    int n, m, sum = 2e9, ans = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        int b;
        cin >> a[i] >> b;
        sum = min(sum, a[i] + b);
    }
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i++) a[i] += a[i - 1];
    for(int i = 0; i <= n; i++) {
        if(a[i] > m) break;
        ans = max(ans, (m - a[i]) / sum * 2 + i);
    }
    cout << ans << endl;
    return 0;
}

P14360 [CSP-J 2025] 多边形

#include <iostream>
#include <ctime>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 5e3 + 5, MOD = 998244353;
int a[N];
long long dp[N][N];
signed main() {
    int n;
    long long ans = 0;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);
    dp[0][0] = 1;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= 5001; j++) {
            (dp[i + 1][j] += dp[i][j]) %= MOD;
            (dp[i + 1][min(5001, j + a[i + 1])] += dp[i][j]) %= MOD;
        }
    }
    // 以 i 为最长的边能凑出的多边形个数
    for(int i = 3; i <= n; i++)
        for(int j = a[i] + 1; j <= 5001; j++)
            (ans += dp[i - 1][j]) %= MOD;
    cout << ans << endl;
    return 0;
}