wyy行为

prediction

2026-05-31 21:14:41

发布于：浙江

11阅读

0回复

0点赞

省流：用AI做CSP-S，得了 $41$ 分。

事先声明：本帖使用的代码请大家不要用于提交题目，它没有参考价值，且这种行为并不对

测评在洛谷测的，测试点也是洛谷的，仅供娱乐（在核桃OJ里用的洛谷题目）。

T1 [CSP-S 2025] 社团招新

预计得分 : $100pts$
实际得分 : $10pts$ 。。。

样例没过。

网(zai)开(lai)一(yi)面(ci)

实际得分： $10pts$ 。？

换了个测试点对了，样例验证完对的结果依然错，累了。

T2 [CSP-S 2025] 道路修复

预计得分： $100pts$
实际得分： $15pts$ ？？？

不是豆包你样例都过不去这啥啊？WA&&TLE赞赞。

再给一次机会

我们这次告诉他WA TLE了，看看他能写出啥来。

实际得分: $27pts$ ? ?

依然没过样例。
算了，开T3。

T3 [CSP-S 2025] 谐音替换

这次我说详细点，豆包你加油。

预计得分： $80pts$ ，纯纯被刚刚吓到了，打算降点分
实际得分： $0pts$

小豆包你挺牛逼克拉斯啊。算了不管了开T4吧。

T4 [CSP-S 2025] 员工招聘

预计得分： $0pts$ 豆包准确率太低了，直接 $0pts$ 可能会被我蒙对？！
实际得分： $4pts$ ？？这里还 $4pts$ ？

反正样例没过，豆包你就这么阴吧。

再来一次？

实际得分： $4pts$

放弃吧。

总结

预期总得分： $280pts$
实际总得分： $41pts$

差了 $7$ 倍嘛，看来S组的大佬们强强。

发现 AIGO 的大佬们都严格强于豆包。

%%%

贴个豆包的代码给大家看

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;

const int MAXN = 1e5 + 10;
int a[MAXN][3];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        int lim = n / 2;
        for (int i = 0; i < n; i++)
        {
            cin >> a[i][0] >> a[i][1] >> a[i][2];
        }

        ll sum = 0;
        int cnt[3] = {0};          // 三个部门人数
        priority_queue<ll> heap;  // 大根堆，存 损失(正数)，越小越优先换

        for (int i = 0; i < n; i++)
        {
            int x = a[i][0], y = a[i][1], z = a[i][2];
            int mx = max({x, y, z});
            sum += mx;

            int pos;
            if (mx == x) pos = 0;
            else if (mx == y) pos = 1;
            else pos = 2;
            cnt[pos]++;

            // 计算从pos换到另外两个的最小损失
            ll d1, d2;
            if (pos == 0)
            {
                d1 = x - y;
                d2 = x - z;
            }
            else if (pos == 1)
            {
                d1 = y - x;
                d2 = y - z;
            }
            else
            {
                d1 = z - x;
                d2 = z - y;
            }
            ll min_del = min(d1, d2);
            heap.push(min_del);
        }

        // 不断修正，直到所有部门人数 <= lim
        while (true)
        {
            bool ok = true;
            int over = -1;
            for (int i = 0; i < 3; i++)
            {
                if (cnt[i] > lim)
                {
                    ok = false;
                    over = i;
                    break;
                }
            }
            if (ok) break;

            // 取出损失最小的替换
            ll del = heap.top();
            heap.pop();
            sum -= del;
            cnt[over]--;
            // 被替换的人进入另外某个部门，人数+1（无需精确追踪，只约束上限）
            // 逻辑上：该人离开超标部门，进入其余部门之一，其余部门一定不会瞬间超标
        }
        cout << sum << '\n';
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

// 原城市 + k个乡镇，总关键点 n+k <= 10010
const int MAXN = 10015;
// 原图边最大 1e6
const int MAXM = 1000010;

// 边结构体
struct Edge {
    int u, v;
    ll w;
    Edge(){}
    Edge(int u_, int v_, ll w_) : u(u_), v(v_), w(w_) {}
    bool operator<(const Edge& b) const {
        return w < b.w;
    }
} ori_e[MAXM];

// 并查集：路径压缩 + 按秩合并
int fa[MAXN], rk[MAXN];
int find(int x) {
    if (fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}
bool merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (rk[x] < rk[y]) fa[x] = y;
    else {
        fa[y] = x;
        if (rk[x] == rk[y]) rk[x]++;
    }
    return true;
}

int n, m, k;
ll c[15];          // 每个乡镇改造费用
ll a[15][MAXN];    // 乡镇j到城市i的建路费用
ll dis[15][MAXN];  // dis[j][i] = 选乡镇j后，城市i连通该乡镇的最小代价

// 计算仅修复原有道路的最小代价（不选任何乡镇）
ll calc_ori() {
    for (int i = 1; i <= n; i++) fa[i] = i, rk[i] = 0;
    ll res = 0;
    int cnt = 0;
    for (int i = 0; i < m; i++) {
        int u = ori_e[i].u, v = ori_e[i].v;
        ll w = ori_e[i].w;
        if (merge(u, v)) {
            res += w;
            cnt++;
            if (cnt == n - 1) break;
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        int u, v; ll w;
        cin >> u >> v >> w;
        ori_e[i] = Edge(u, v, w);
    }
    // 原图边只排序一次！核心优化
    sort(ori_e, ori_e + m);
    
    // 读入k个乡镇数据
    for (int j = 0; j < k; j++) {
        cin >> c[j];
        for (int i = 1; i <= n; i++) {
            cin >> a[j][i];
            dis[j][i] = c[j] + a[j][i]; // 改造乡镇+建路总花费
        }
    }

    ll ans = calc_ori(); // 初始答案：不选任何乡镇的情况

    // 状压枚举所有非空乡镇集合 k<=10 → 最多1023种
    int full = 1 << k;
    for (int S = 1; S < full; S++) {
        // 初始化并查集
        for (int i = 1; i <= n; i++) fa[i] = i, rk[i] = 0;
        ll total = 0;
        int conn = 0;

        // 第一步：先连原图的边（Kruskal）
        for (int i = 0; i < m; i++) {
            int u = ori_e[i].u, v = ori_e[i].v;
            ll w = ori_e[i].w;
            if (merge(u, v)) {
                total += w;
                conn++;
                if (conn == n - 1) break;
            }
        }
        if (conn == n - 1) { // 原图已经连通，直接更新答案
            ans = min(ans, total);
            continue;
        }

        // 第二步：对当前选中的乡镇，建立「虚拟节点 + 辅助边」
        // 把每个连通块通过乡镇连通
        vector<pair<ll, int>> link[MAXN];
        // 遍历所有选中的乡镇
        for (int j = 0; j < k; j++) {
            if (!(S & (1 << j))) continue;
            // 对每个城市，用该乡镇作为中转
            for (int i = 1; i <= n; i++) {
                int rt = find(i);
                link[rt].emplace_back(dis[j][i], i);
            }
        }

        // 收集所有连通块的最优中转边，再次Kruskal合并块
        vector<Edge> aux;
        for (int rt = 1; rt <= n; rt++) {
            if (find(rt) != rt) continue;
            for (auto &p : link[rt]) {
                aux.emplace_back(rt, p.second, p.first);
            }
        }
        sort(aux.begin(), aux.end());

        for (auto &e : aux) {
            int u = e.u, v = e.v;
            ll w = e.w;
            if (merge(u, v)) {
                total += w;
                conn++;
                if (conn == n - 1) break;
            }
        }
        ans = min(ans, total);
    }
    cout << ans << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
#include <climits>
using namespace std;

typedef unsigned long long ull;
const int BASE = 131;
const int MAX_LEN = 5e6 + 20;

ull pw[MAX_LEN];

// 预处理幂数组
void pre_pow() {
    pw[0] = 1;
    for (int i = 1; i < MAX_LEN; ++i) {
        pw[i] = pw[i-1] * BASE;
    }
}

// 计算字符串前缀哈希
vector<ull> get_pre_hash(const string &s) {
    int n = s.size();
    vector<ull> h(n+1, 0);
    for (int i = 0; i < n; ++i) {
        h[i+1] = h[i] * BASE + s[i];
    }
    return h;
}

// 求 s[l, r] 子串哈希 (0下标, 闭区间)
ull get_sub(const vector<ull> &h, int l, int r) {
    int len = r - l + 1;
    return h[r+1] - h[l] * pw[len];
}

unordered_map<ull, vector<pair<ull, int>>> mp;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    pre_pow();

    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        string a, b;
        cin >> a >> b;
        auto ha = get_pre_hash(a);
        auto hb = get_pre_hash(b);
        ull h1 = get_sub(ha, 0, a.size()-1);
        ull h2 = get_sub(hb, 0, b.size()-1);
        int len = a.size();
        mp[h1].emplace_back(h2, len);
    }

    while (q--) {
        string t1, t2;
        cin >> t1 >> t2;
        if (t1.size() != t2.size()) {
            cout << "0\n";
            continue;
        }
        int L = INT_MAX, R = INT_MIN;
        int len = t1.size();
        for (int i = 0; i < len; ++i) {
            if (t1[i] != t2[i]) {
                L = min(L, i);
                R = max(R, i);
            }
        }
        // 题目保证 t1 != t2，所以一定有不等位
        int k = R - L + 1;
        auto h1 = get_pre_hash(t1);
        auto h2 = get_pre_hash(t2);
        ull hash1 = get_sub(h1, L, R);
        ull hash2 = get_sub(h2, L, R);

        int ans = 0;
        auto it = mp.find(hash1);
        if (it != mp.end()) {
            for (auto &p : it->second) {
                if (p.second == k && p.first == hash2) {
                    ans++;
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

typedef long long ll;
const int MOD = 998244353;
const int MAXN = 505;

int n, m;
string s;
int c[MAXN];
// cnt0[x]: c_u <= x 的人数（bad=x 时放弃）
// cnt1[x]: c_u > x 的人数（bad=x 时面试）
int cnt0[MAXN], cnt1[MAXN];
ll dp[MAXN][MAXN]; // dp[i][j]: 选了i个人，bad=j 的方案数

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    cin >> s;
    for (int i = 1; i <= n; ++i)
        cin >> c[i];

    // 预处理 cnt0, cnt1
    for (int x = 0; x <= n; ++x)
    {
        int a = 0, b = 0;
        for (int u = 1; u <= n; ++u)
        {
            if (c[u] <= x) a++;
            else b++;
        }
        cnt0[x] = a;
        cnt1[x] = b;
    }

    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;

    for (int i = 0; i < n; ++i) // 已选 i 人，处理第 i+1 位
    {
        for (int j = 0; j <= i; ++j) // 当前 bad = j
        {
            if (!dp[i][j]) continue;
            // 剩余总人数: n - i
            // 全局: 放弃型 cnt0[j]，面试型 cnt1[j]
            // 前面 i 个人中，最多选了 cnt1[j] 个面试型
            int use1 = i - cnt0[j];
            if (use1 < 0) use1 = 0;
            int can1 = cnt1[j] - use1; // 剩余面试型人数
            int can0 = (n - i) - can1; // 剩余放弃型人数

            char op = s[i]; // 第 i+1 场题目

            // 1. 选一个会放弃的人 can0 种
            if (can0 > 0)
            {
                dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j] * can0) % MOD;
            }
            // 2. 选一个会面试的人 can1 种
            if (can1 > 0)
            {
                if (op == '0')
                {
                    // 被拒绝，bad+1
                    dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j] * can1) % MOD;
                }
                else
                {
                    // 被录用，bad 不变
                    dp[i+1][j] = (dp[i+1][j] + dp[i][j] * can1) % MOD;
                }
            }
        }
    }

    // 录用人数 = n - j >= m  --> j <= n - m
    ll ans = 0;
    int lim = n - m;
    for (int j = 0; j <= lim; ++j)
    {
        ans = (ans + dp[n][j]) % MOD;
    }
    cout << ans << endl;
    return 0;
}