深圳-第三期-XP03A-一班-day1

userId_undefined
深圳信奥算法部+林日清
7月全勤卷王出道萌新时间刺客倔强青铜

2026-08-03 18:07:44

发布于：广东

57阅读
0回复
0点赞

A362.抽奖3

暴力代码

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

const ll N = 1e4 + 10;
ll n, sum;
ll ans;
ll a[N];

int main() {
    cin >> n >> sum;
    for (ll i = 1; i <= n; i ++) cin >> a[i];
    sort(a + 1, a + n + 1); 
    for (ll i = 1; i <= n; i ++) {
        // 现在，第一次抽就抽到了 i 号小球
        // 在抽到第 i 号小球的基础上
        // 第 2 次可以怎么抽？
        if (a[i] > sum) break;
        for (ll j = 1; j <= n; j ++) {
            // 现在，第二次抽就抽到了小球 j
            // 在抽到 j 的前提下，第三次可以怎么抽？
            if (a[i] + a[j] > sum) break;
            for (ll k = 1; k <= n; k ++) {
                // 现在，第三抽就抽到了小球 k 了
                if (a[i] + a[j] + a[k] == sum) ans ++;
                else if (a[i] + a[j] + a[k] > sum) break;
            }
        }
    }
    cout << ans;
    return 0;
}

优化

优化方式一

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

const ll N = 1e4 + 10;
ll n, sum;
ll ans;
ll ct[N]; // ct[x] 统计的是 a[i] + a[j] = x 的方案数
ll a[N];

int main() {
    cin >> n >> sum;
    for (ll i = 1; i <= n; i ++) cin >> a[i];
    for (ll i = 1; i <= n; i ++) {
        for (ll j = 1; j <= n; j ++) {
            ll x = a[i] + a[j];
            ct[x] ++;
            // ct[ a[i]+a[j] ] ++;
        }
    }
    for (ll k = 1; k <= n; k ++) {
        // 为了让 a[i] + a[j] + a[k] = sum
        // 那么必须要让：a[i]+a[j] = sum - a[k]
        ll x = sum - a[k];
        if (x < 0) continue;
        // 统计 a[i]+a[j] = x 的出现次数
        // 就是 ct[x]
        ans += ct[x];
    }
    cout << ans;
    return 0;
}

优化方式二

q 提交的代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n,sum;
ll a[1000100],vis[1000100];
const ll N = 100;
ll ans;
int main(){
    cin >> n >> sum;
    for(ll i = 1;i<=n;i++){
        cin >> a[i];
        vis[a[i]]++;
    }
    for(ll i = 1;i<=N;i++){
        for(ll j = 1;j<=N;j++){
            for(ll k = 1;k<=N;k++){
                if(i+j+k==sum&&vis[i]&&vis[j]&&vis[k]){
                    ans+=vis[i]*vis[j]*vis[k];
                }
            }
        }
    }
    cout << ans;
    return 0;
}

基于范围的 for 循环

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

ll a[] = {2, 1, 3, 4, 5};

int main() {
    // for (ll x : a) x = 10; // 因为他是复制给 x
    // // 修改 x 无法影响到数组本身内部的数据
    // for (ll x : a) cout << x << '\n';

    for (ll& x : a) x = 10; 
    // 加一个引用变量，那么 x 就代表拿出来的元素本身
    // 修改 x 相当于修改对应的空间
    for (ll x : a) cout << x << '\n';
    return 0;
}

A29800.小码君抽奖1

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

/**
    决策树、方案树
    遍历树形结构：深度优先搜索（广度优先搜索）
*/

ll a[1000100];
ll n;
vector<ll> vt;

/**
    vector<ll> vt 是动态数组
    会随着末尾添加的元素自动扩容

    在末尾添加元素：vt.push_back(x)
    删除末尾元素：vt.pop_back()
    获取元素格式：vt.size()
    for (ll i = 0; i < vt.size(); i ++) vt[i]
    初始化：
    vector<ll> vt = {1, 2, 3};
    vector<ll> vt = vector<ll>(1000100, -1);

    for (ll x : vt) cout << x << ' ';
    这种循环叫做基于范围的for循环
    比如说就算是普通数组也是支持的：
    ll a[1000100];
    for (ll x : a) cout << x << ' ';

    把数组从头到尾扫一遍
*/

// dfs(p) 表示对第 p 层进行决策
// 枚举 p 层可以选取哪些小球

// 这个 dfs 代码本质上，就是模拟 n 层 for 循环嵌套
void dfs(ll p) {
    if (p == n + 1) {
        // 说明 1~n 次选取都已经决策出来
        // 需要输出当前这一种方案
        for (ll x : vt) cout << x << ' ';
        cout << '\n';
        return;
    }
    // 现在，对第 p 次选取做决策
    for (ll i = 1; i <= 3; i ++) {
        // 当前选取 i 号小球
        vt.push_back(i); // 当前选取了 i 号小球
        // 当前选好后，就轮到下一次选
        dfs(p + 1);
        // 递归回溯，因为是输出所有的方案
        // 所以要还原，并且恢复现场
        vt.pop_back();
    }
}

int main() {
    cin >> n;
    dfs(1);
    return 0;
}

质数判断的标准模版

时间复杂度：O(n)O(\sqrt{n})

// 判断 n 是否是质数
bool is_prime(ll n) {
    if (n < 2) return false;
    for (ll i = 2; i <= n / i; i ++) {
        if (n % i == 0) return false;
    }
    return true;
}

T111578.充满希望的拼接质数1

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

/**
    01 搜索模型（也是一颗决策树）

    每一件物品：都有选、不选两种决策

    可以这样子现象：

    总共有 n 次决策，每次决策都有 0 和 1 两种选法
*/

ll n;
ll a[20];
ll ans; // 统计总和为质数的方案

// 判断 n 是否是质数
bool is_prime(ll n) {
    if (n < 2) return false;
    for (ll i = 2; i <= n / i; i ++) {
        if (n % i == 0) return false;
    }
    return true;
}

ll sum; // 记录当前这种决策方案所积累的总和

// 对 p 号物品做决策（选与不选）
void dfs(ll p) {
    if (p == n + 1) {
        // if (is_prime(sum)) ans ++;
        ans += is_prime(sum);
        return;
    }
    
    // 如果当前 p 号物品选取的话
    sum += a[p]; // 选取第 p 号物品，累加 p 的值
    dfs(p + 1);  // 轮到下一个物品 p+1 做决策
    sum -= a[p]; // 回溯的时候，就轮到决策第 2 种情况，需要恢复现场，
                 // 取消掉当前这种决策的影响

    // 另外一种决策方式：p 号物品不选的情况
    // sum += 0;
    dfs(p + 1);
    // sum -= 0;
}

int main() {
    cin >> n;
    for (ll i = 1; i <= n; i ++) cin >> a[i];
    dfs(1); // 从第 1 个物品开始做决策
    cout << ans;
    return 0;
}

T111790.食堂管理员

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

ll n, k;
ll a[10];
// ll ans; // ans 记录方案数

vector<ll> vt; // vt 记录具体的方案
ll sum;        // sum 记录 vt 这种方案的总和

// dfs(p) 就是对第 p 号学生，吃多少米饭进行决策
void dfs(ll p) {
    if (p == n + 1) {
        if (sum % k == 0) {
            for (ll& x : vt) cout << x << ' ';
            cout << '\n';
        }

        return;
    }

    // 对当前这位 p 学生，吃多少米饭做决策
    for (ll i = 1; i <= a[p]; i ++) {
        // 当前 p 吃了 i 粒大米
        vt.push_back(i); sum += i; 
        dfs(p + 1); // 轮到下一位学生做决策
        vt.pop_back();   sum -= i;
    }
}

int main() {
    cin >> n >> k;
    for (ll i = 1; i <= n; i ++) cin >> a[i];
    dfs(1);
    return 0;
}

U37003.邻接表【模版题】

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

const ll N = 2e5 + 10;
ll n;
/**
 * 给每一个点都分配一个 vector：
 * g[1] 是一个 vector，存放 1 的所有邻居
 * g[2] 是一个 vector，存放 2 的所有邻居
 * ...
 * g[n] 是一个 vector，存放 n 的所有邻居
 */
vector<ll> g[N];

/**
 * vector<ll> vt;
 * vt[0] 的地址是：vt.begin()
 * vt[n] 的地址是：vt.begin() + n
 * vt[i] 的地址是：vt.begin() + i
 * 
 * 假如说 vt 总共有 100 个元素
 * sort(vt.begin() + 0, vt.begin() + 99 + 1)
 * 
 * // 如果我需要对下标 [1 ~ n] 排序的话：
 * sort(vt.begin() + 1, vt.begin() + n + 1)
 * 
 * // 如果我需要对整个 vt 数组排序的话：
 * sort(vt.begin(), vt.begin() + (vt.size() - 1) + 1)
 * 也相当于：sort(vt.begin(), vt.end())
 */

int main() {
    cin >> n;
    for (ll i = 1; i < n; i ++) {
        ll u, v; cin >> u >> v;
        // u - v 之间有一条边相连
        // u 是 v 的邻居，v 也是 u 的邻居
        // 双向
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (ll i = 1; i <= n; i ++) {
        // 先输出邻居的个数：g[i].size()
        // 因为 g[i] 本身就是一个 vector
        // 那么他就具有 size() 函数
        // 对 g[i] 这个 vector 从小到大排序
        cout << g[i].size() << ' ';
        sort(g[i].begin(), g[i].end());
        for (ll x : g[i]) cout << x << ' ';
        cout << '\n';
    }
    return 0; 
}

T112335.连通块问题(DFS)

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

const ll N = 1e5 + 10;
ll n, m;
vector<ll> g[N];
ll x, y;

ll flag; // flag 判断是否能从 x 出发抵达 y
ll cnt;  // 统计连通块的点数量
ll vis[N]; // vis[i] = 1，表示 i 号点已经走过了

/**
 * 用 dfs 从 x 出发，遍历 x 所在的连通块
 * 如果遇到新的点，就标记为已访问，并且计数器 cnt++
 * 如果遇到的新点，是 y 的话，就说明能从 x 出发走到 y，flag = true
 * 继续搜索所有的邻居
 */
// 用 u 号点出发
void dfs(ll u) {
    if (vis[u]) return;
    // 否则说明当前这个点是第一次来的点，是新点
    vis[u] = 1; // 标记为已访问
    cnt ++;     // 遇到新的点，统计点的数量
    if (u == y) flag = true;
    for (ll x : g[u]) dfs(x); // 用深度优先搜索遍历所有的邻居
}

int main() {
    cin >> n >> m;
    for (ll i = 1; i <= m; i ++) {
        ll u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cin >> x >> y;
    dfs(x); // 从 x 点出发搜索
    if (flag == 0) cnt = 0;
    cout << cnt;
    return 0;
}

机器人能源模块

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

ll v;
ll need[50];
ll g;
ll a[50][50];

vector<ll> ans; // 记录最优方案

// dfs(p) 是对第 p 个能源模块做决策
// 第 p 个能源模块到底是选还是不选
vector<ll> vt; // vt 表示当前的选取方案
ll sum[50];
void dfs(ll p) {
    if (p == g + 1) {
        // ...
        for (ll i = 1; i <= v; i ++) {
            if (sum[i] < need[i]) return;
        }
        if (ans.size() == 0 || vt.size() < ans.size()) ans = vt;
        // if (vt.size() == ans.size() && vt < ans) ans = vt;
        return;
    }
    // 选与不选
    // 先选择小，再不选择小，这样就可以保证字典序最小化
    vt.push_back(p);
    for (ll i = 1; i <= v; i ++) sum[i] += a[p][i];
    dfs(p + 1);
    vt.pop_back();
    for (ll i = 1; i <= v; i ++) sum[i] -= a[p][i];

    dfs(p + 1);
}

int main() {
    cin >> v;
    for (ll i = 1; i <= v; i ++) {
        cin >> need[i];
    }
    cin >> g;
    for (ll i = 1; i <= g; i ++) {
        for (ll j = 1; j <= v; j ++) cin >> a[i][j];
    }
    dfs(1);
    cout << ans.size() << ' ';
    for (ll x : ans) cout << x << ' ';
    return 0;
}

星际质数密码

埃氏筛法

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

ll n, l, r;

vector<bool> isp;
void init_isp() {
    isp[0] = isp[1] = 0;
    for (ll i = 2; i <= r; i ++) {
        for (ll j = i * i; j <= r; j += i) {
            isp[j] = 0;
        }
    }
}



int main() {
    cin >> n;
    l = pow(10, n - 1);
    r = pow(10, n) - 1;
    isp = vector<bool>(r + 1, 1);
    init_isp();
    for (ll i = l; i <= r; i ++) {
        if (isp[i] == 0) continue;
        ll t = i;
        while (isp[t]) {
            t /= 10;
            if (t == 0) break;
        }
        if (t == 0) cout << i << '\n';
    }
    return 0; 
}

正解

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

ll n, l, r;

vector<bool> isp;
void init_isp() {
    isp[0] = isp[1] = 0;
    for (ll i = 2; i <= r; i ++) {
        for (ll j = i * i; j <= r; j += i) {
            isp[j] = 0;
        }
    }
}

void dfs(ll p, ll sum) {
    if (p == n + 1) {
        if (isp[sum]) cout << sum << '\n';
        return;
    }
    for (ll i = 0; i <= 9; i ++) {
        if (p == 1 && i == 0) continue;
        if (isp[sum * 10 + i] == 0) continue;
        dfs(p + 1, sum * 10 + i);
    }
}

int main() {
    cin >> n;
    l = pow(10, n - 1);
    r = pow(10, n) - 1;
    isp = vector<bool>(r + 1, 1);
    init_isp();
    dfs(1, 0);
    return 0; 
}
userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论