GESP 5级

B3941 [GESP样题 五级] 小杨的锻炼

提示

// 求n个数的最小公倍数

// 记录下来每个质因子的最高幂次

代码

// 求n个数的最小公倍数
// 记录下来每个质因子的最高幂次

#include <bits/stdc++.h>

using namespace std;

int n;
map<int, int> mp;

int main() {
    cin >> n;
    while (n--) {
        int x;
        cin >> x;

        for (int i = 2; i <= x / i; i++)
            if (x % i == 0) {
                int cnt = 0;
                while (x % i == 0) {
                    x /= i;
                    cnt++;
                }

                mp[i] = max(mp[i], cnt);
            }
        mp[x] = max(mp[x], 1);
    }

    int ans = 1;
    for (auto i : mp) {
//      printf("---%d %d\n", i.first, i.second);
        ans *= (int)pow(i.first, i.second);
    }
    cout << ans;

    return 0;
}

B3951 [GESP样题 五级] 小杨的队列

提示

// 队列中每新增一个数值，看当前数列中有多少个大于自己的数值

// n, m都很小，直接枚举了

// 5级对数的认识比较敏感

代码

// 队列中每新增一个数值，看当前数列中有多少个大于自己的数值
// n, m都很小，直接枚举了
// 5级对数的认识比较敏感

#include <bits/stdc++.h>

using namespace std;

const int N = 2010;

int a[N], n, m;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> m;

    vector<int> A;
    while (m--) {
        int x;
        cin >> x;

        set<int> B;
        for (auto i : A) if (i > a[x]) B.insert(i);

        cout << (int)B.size() << endl;

        A.push_back(a[x]);
    }

    return 0;
}

B3871 [GESP202309 五级] 因数分解

提示

分解质因数模板

代码

#include <iostream>
using namespace std;
int main(){
    long long n;
    cin >> n;
    bool flag = false;

    for(long long i=2; i <= n / i; i++){
        if (n % i == 0) {
            int cnt = 0;
            while(n%i==0){
                n /= i;
                cnt++;
            }

            if (flag) cout << " * ";
            if (cnt == 1) cout << i;
            else cout << i << '^' << cnt;

            flag = true;
        }
    }
    if (n > 1) {
        if (flag) cout << " * ";
        cout << n;  
    }

    return 0;
}

B3872 [GESP202309 五级] 巧夺大奖

提示

// 每个游戏都有自己结束时间，怎么安排，才能获得更多的奖励

// 从后向前枚举时间，这一秒能用的活动中，哪个奖励最多，就做哪个

// 外层循环，枚举时间，从后向前枚举，把能用的活动，都扔到一个堆当中

// 我们每次就从堆当中，拿出最大值选用即可。贪心思路

代码

// 每个游戏都有自己结束时间，怎么安排，才能获得更多的奖励
// 从后向前枚举时间，这一秒能用的活动中，哪个奖励最多，就做哪个
// 外层循环，枚举时间，从后向前枚举，把能用的活动，都扔到一个堆当中
// 我们每次就从堆当中，拿出最大值选用即可。贪心思路

#include <bits/stdc++.h>

using namespace std;

const int N = 510;

pair<int, int> a[N];
int n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].first;
    for (int i = 1; i <= n; i++) cin >> a[i].second;

    sort(a + 1, a + 1 + n);

    int ret = 0;
    priority_queue<int> q;
    for (int time = n, i = n; time >= 1; time--) {
        while (i >= 1 && time <= a[i].first) q.push(a[i--].second);

        if (!q.empty()) {
            ret += q.top();
            q.pop();
        }   
    }

    cout << ret;

    return 0;
}

代码02

// 题解思路，先枚举任务，然后枚举[a[i].time, 1]这个范围，哪个时间位置可以用，就用
// 这种枚举时间的写法，比较经典。记录，学习
// 贪心思路

#include <bits/stdc++.h>

using namespace std;

const int N = 510; 

struct node{
    int time, cost;
}a[N];
int n, ret;
bool vis[N];

bool cmp(node a, node b) {
    return a.cost > b.cost;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].time;
    for (int i = 1; i <= n; i++) cin >> a[i].cost;

    sort(a + 1, a + 1 + n, cmp);

    // 枚举任务
    for (int i = 1; i <= n; i++) {
        for (int j = a[i].time; j >= 1; j--) // 枚举这个时间有没有被占用
            if (!vis[j]) {
                vis[j] = true;
                ret += a[i].cost;
                break;
            }
    }

    cout << ret;

    return 0;
}

B3929 [GESP202312 五级] 小杨的幸运数

提示

// 大于等于a的完全平方数都是幸运数，幸运数的倍数也都是幸运数

// n次询问，问x是不是幸运数，如果不是，输出大于x最小的幸运数是多少

// a <= 1e6， x<=1e6，预处理出来所有的幸运数，用upper_bound查找

// 体现了筛法

代码

// 大于等于a的完全平方数都是幸运数，幸运数的倍数也都是幸运数
// n次询问，问x是不是幸运数，如果不是，输出大于x最小的幸运数是多少
// a <= 1e6， x<=1e6，预处理出来所有的幸运数，用upper_bound查找
// 体现了筛法

#include <bits/stdc++.h>
#include <set>

using namespace std;

const int N = 2e6;

int a, n;
set<int> st;

void init() {
    for (int i = ceil(sqrt(a)); i < N / i; i++) {
        for (int j = i * i; j < N; j += i * i) st.insert(j);
    }
}

int main() {
    cin >> a >> n;
    init();

    while (n--) {
        int x;
        cin >> x;

        if (st.count(x)) cout << "lucky" << '\n';
        else cout << *st.upper_bound(x) << '\n';
    }

    return 0;
}

B3930 [GESP202312 五级] 烹饪问题

提示

// n个数，哪两个数按位与之后的结果最大

// 40%数据，n<=1000，可以两层循环

// 100%数据，n<=1e6，ai是32位int，根据二进制，从最高位枚举是1的，然后看下一位是1的，O(1e6 * 31)

代码

// n个数，哪两个数按位与之后的结果最大
// 40%数据，n<=1000，可以两层循环
// 100%数据，n<=1e6，ai是32位int，根据二进制，从最高位枚举是1的，然后看下一位是1的，O(1e6 * 31)
// 维护过程中，可以用vector做临时存储满足第i位是1的所有数字，或者用一个bool数字进行迭代维护
// 过程中，vector a 像一个过滤器一样，把不符合的筛掉了，符合的放到temp中，用temp更新自己

#include <bits/stdc++.h>

using namespace std;

int n;

int main() {
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 30; i >= 0; i--) {
        vector<int> temp;

        for (auto x : a) {
            if (x >> i & 1) temp.push_back(x);
        }

        if (temp.size() < 2) continue;

        a = temp;
    }

    cout << (a[0] & a[1]) << '\n';

    return 0;
}

代码02

// 用bool数组维护
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n, ret;
bool vis[N], vis2[N];

int main() {
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    memset(vis, true, sizeof vis);

    for (int i = 30; i >= 0; i--) {
        memset(vis2, false, sizeof vis2);

        int cnt = 0;
        for (int j = 0; j < n; j++) {
            if (!vis[j]) continue;

            if (a[j] >> i & 1) vis2[j] = true, cnt++;
        }

        if (cnt < 2) continue;

        ret |= (1 << i);

        memcpy(vis, vis2, sizeof vis2);
    }

    cout << ret << '\n';

    return 0;
}

代码03-牛逼

// 官方题解代码的维护过程，比较牛逼。
// 是把快排进行了改编（这种思想，是怎么学来的？我草，狠啊）

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n, ret;
int a[N];

// 一趟快排，做出了分堆处理（原来快排还可以做分堆处理）
int quick_sort(int l, int r, int k) {
    int i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while (a[i] >> k & 1);
        do j--; while (!(a[j] >> k & 1));

        if (i < j) swap(a[i], a[j]);
    }

    // [l, j] 第k位都是1
    // [j + 1, r] 第k位都是0

    return j;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int k = 30; k >= 0; k--) {
        int j = quick_sort(1, n, k);
        if (j >= 2) {
            ret |= (1 << k);
            n = j;
        }

        // 如果我们发现不足够2个数，那么n的值不变，我们枚举的范围不变
        // 下一位我们还是从这个范围内看，这些数字，这位是1
    }

    cout << ret << '\n';

    return 0;
}

B3968 [GESP202403 五级] 成绩排序

提示

// n个同学排名，有并列的情况，按id顺序输出每个人的排名

// sort一下，最后捋一遍排名即可，看是否和前一个人成绩的大小关系

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 10;

struct node {
    int c, m, e;
    int sum;
    int id, rank;
}a[N];

int n;

bool cmp(node a, node b) {
    if (a.sum != b.sum) return a.sum > b.sum;
    if (a.c + a.m != b.c + b.m) return a.c + a.m > b.c + b.m;
    if (max(a.c, a.m) != max(b.c, b.m)) return max(a.c, a.m) > max(b.c, b.m);
    return false;
}

bool cmp2(node a, node b) {
    return a.id < b.id;
}

int main() {
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> a[i].c >> a[i].m >> a[i].e;

        a[i].sum = a[i].c + a[i].m + a[i].e;
        a[i].id = i;
    }

    sort(a, a + n, cmp);

//  for (int i = 0; i < n; i++) cout << a[i].c << ' ' << a[i].m << ' ' << a[i].e << '\n';   

    int id = 0;
    for (int i = 0; i < n; i++) 
        if (i == 0 || cmp(a[i - 1], a[i])) {
            id = i + 1;
            a[i].rank = id;
        }
        else a[i].rank = id;

//  for (int i = 0; i < n; i++) cout << a[i].c << ' ' << a[i].m << ' ' << a[i].e << ' ' << a[i].rank <<  '\n';  

    sort(a, a + n, cmp2);
    for (int i = 0; i < n; i++) cout << a[i].rank << '\n';

    return 0;
}

B3969 [GESP202403 五级] B-smooth 数

代码

// 最大质因子不超过B
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, B, ans = 0;
    cin >> n >> B;

    for (int j = 1; j <= n; j++) {
        int m = 0, x = j;
        for (int i = 2; i <= x / i; i++)
            if (x % i == 0) {
                while (x % i == 0) x /= i;
                m = max(m, i);
            }
        if (x > 1) m = max(m, x);

//      printf("--%d %d\n", j, m);

        if (m <= B) ans++;
    }

    cout << ans;

    return 0;
}

P10719 [GESP202406 五级] 黑白格-好题

提示

// 至少包含k个1的最小子矩阵包含多少个格子

// n,m <= 100，暴力枚举n^{4维护左上角右下角，n}2维护子矩阵的和，共n^6，过不了，

// 二维前缀和，n^4，之需要维护左上角和右下角，但是也过不了

// 前缀和+双指针，n^3，n2维护首行和末行，中间用竖着的前缀和，转成一维。在一维上做O(n)的双指针

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int n, m, k, a[N][N];
int s_col[N][N], col[N];
char s[N][N];

int main() {
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) scanf("%s", s[i]);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            a[i][j] = s[i - 1][j - 1] - '0';

    for (int j = 1; j <= m; j++)
        for (int i = 1; i <= n; i++)
            s_col[j][i] = s_col[j][i - 1] + a[i][j];

    int ret = 0x3f3f3f3f;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= m; k++) col[k] = s_col[k][j] - s_col[k][i - 1];

            int l = 1, r = 1;
            int sum = 0;
            while (l <= r && r <= m + 1) {
                while (sum < k && r <= m) sum += col[r++];
                if (sum >= k) {
//                  printf("---%d %d %d %d %d\n", i, j, l, r - 1, sum);
                    ret = min(ret, (j - i + 1) * (r - l));
                }

                sum -= col[l++];
            }
        }

    if (ret == 0x3f3f3f3f) ret = 0;
    cout << ret;

    return 0;
}

P10720 [GESP202406 五级] 小杨的幸运数字

提示

// n个正整数，判断每个数的质因子个数，是不是2

// 洛谷上构造了100个测试点，ybt上构造了10个测试点

// 洛谷的专业性，还是权威一点啊。但是洛谷评测机卡爆了

代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    while (n--) {
        int x, cnt = 0;
        cin >> x;

        for (int i = 2; i <= x / i; i++) 
            if (x % i == 0) {
                while (x % i == 0) x /= i;
                cnt++;
            }
        if (x > 1) cnt++;

        if (cnt == 2) cout << 1 << endl;
        else cout << 0 << endl;
    }

    return 0;
}

B4050 [GESP202409 五级] 挑战怪物

提示

// 判断一个数，是不是由一个质数+2的幂次之和构成的

// 从2的1次幂开始枚举，减掉幂次。看剩下的数是不是一个质数，如果发现是，那么立刻结束，得到攻击次数。否则到最后也没有构造出质数，那么就输出-1

代码

#include <bits/stdc++.h>

using namespace std;

bool check(int n) {
    if (n < 2) return false;
    for (int i = 2; i <= n / i; i++)
        if (n % i == 0) return false;

    return true;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int h;
        cin >> h;

        int attack = 1, cnt = 0;
        bool flag = false;
        while (h > 0) {
            if (check(h)) {
                cnt++;
                flag = true;
                break;
            }

            h -= attack;
            attack *= 2;
            cnt++;
        }

        if (h == 0 || flag) cout << cnt << '\n';
        else cout << -1 << '\n';
    }


    return 0;
}

B4051 [GESP202409 五级] 小杨的武器

提示

// n种武器，选出最大值

// m个ai中，选出正数，累加到这个最大值

// 就是最后的答案

// 5级为什么出这种题呢？

提示02

// 有特例

// 注意看数据范围，边界小数据

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m;
ll maxn = -2e9, x;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        maxn = max(maxn, x);
    }

    while (m--) {
        cin >> x;
        if (x > 0 || n == 1) maxn += x;
    }

    cout << maxn;

    return 0;
}

B4070 [GESP202412 五级] 奇妙数字

提示

// 对n进行质因子分解，每个质因子的幂次pi

// pi = 1+2+3+.. 拆解成一个等差数列求和，看这个等差数列最多到第几项

// pi = (1 + m) * m / 2，m最大可以去多少

// 对所有的m累加求和

代码

// 在求m的时候，暴力求，获得40分。下面要优化一下

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n, ans;

int main() {
    cin >> n;
    for (ll i = 2; i <= n; i++) {
        if (n % i == 0) {
            ll cnt = 0;
            while (n % i == 0) n /= i, cnt++;

            ll m = 0, now = 0;
            while (now <= cnt) now += ++m;

            ans += m - 1; 
        }
    }

    cout << ans;

    return 0;
}

代码02

// 在求m的时候，暴力求，获得40分。下面要优化一下
// 用二分
// subtask#2，还是TLE

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n, ans;

int main() {
    cin >> n;
    for (ll i = 2; i <= n; i++) {
        if (n % i == 0) {
            ll cnt = 0;
            while (n % i == 0) n /= i, cnt++;

            ll l = 1, r = 2e9, best = -1;
            while (l <= r) {
                ll m = (l + r) / 2;
                if ((1 + m) * m / 2 <= cnt) l = m + 1, best = m;
                else r = m - 1; 
            }

            ans += best; 
        }
    }

    cout << ans;

    return 0;
}

代码03

// 枚举质因子的地方，要改造。这样就可以AC了

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n, ans;

int main() {
    cin >> n;
    for (ll i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            ll cnt = 0;
            while (n % i == 0) n /= i, cnt++;
            ll l = 1, r = 2e9, best = -1;
            while (l <= r) {
                ll m = (l + r) / 2;
                if ((1 + m) * m / 2 <= cnt) l = m + 1, best = m;
                else r = m - 1; 
            }

            ans += best; 
        }
    }
    if (n > 1) ans++;

    cout << ans;

    return 0;
}

代码04

// 在求m的时候，(1 + m) * m / 2 <= cnt
// 这是一个一元二次方程，可以利用求根公式，数学一点

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n, ans;

int main() {
    cin >> n;
    for (ll i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            ll cnt = 0;
            while (n % i == 0) n /= i, cnt++;

            ll m = (-1 + sqrt(1 + 8 * cnt)) / 2;
            ans += m;
        }
    }
    if (n > 1) ans++;

    cout << ans;

    return 0;
}

B4071 [GESP202412 五级] 武器强化-好题

提示

// m种强化材料，第i种可强化第pi种武器

// 第i种材料可花费ci元，变成可以强化第1种武器

// 最少花多少钱，可以使得第1种武器的可强化材料数量，大于其他武器

提示02

当一个问题，贪心，有局限性，可能会被后面的条件背刺。

那就不能用贪心，可能是dp，可能是枚举答案

注意，n, m <= 1000

代码

// 这份代码只有20分

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n, m, pi, ci;
vector<int> h[N];
long long sum;

bool check() {
    for (int i = 2; i <= n; i++) 
        if (h[i].size() >= h[1].size()) return true;

    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> pi >> ci;
        h[pi].push_back(ci);
    }

    for (int i = 1; i <= n; i++) 
        if (h[i].size()) sort(h[i].begin(), h[i].end(), greater<int>());

    while (check()) {
        int maxn = -1, maxp = -1, maxc = -1;
        for (int i = 2; i <= n; i++)
            if ((int)h[i].size() > maxn) maxn = h[i].size(), maxp = i, maxc = h[i].back();
            else if ((int)h[i].size() == maxn && h[i].back() < maxc) maxp = i, maxc = h[i].back();

        sum += h[maxp].back();          
        h[1].push_back(h[maxp].back());
        h[maxp].pop_back();
    }

    cout << sum;

    return 0;
}

代码02

// 这份代码改了一个非空的判断，多对了一个subtask，40分

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n, m, pi, ci;
vector<int> h[N];
long long sum;

bool check() {
    for (int i = 2; i <= n; i++) 
        if (h[i].size() >= h[1].size()) return true;

    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> pi >> ci;
        h[pi].push_back(ci);
    }

    for (int i = 1; i <= n; i++) 
        if (h[i].size()) sort(h[i].begin(), h[i].end(), greater<int>());

    while (check()) {
        int maxn = -1, maxp = -1, maxc = -1;
        for (int i = 2; i <= n; i++) {
            if ((int)h[i].size() == 0) continue;   // 得判断是否为空，否则.back()有问题
            if ((int)h[i].size() > maxn) maxn = h[i].size(), maxp = i, maxc = h[i].back();
            else if ((int)h[i].size() == maxn && h[i].back() < maxc) maxp = i, maxc = h[i].back();
        }

        sum += h[maxp].back();          
        h[1].push_back(h[maxp].back());
        h[maxp].pop_back();
    }

    cout << sum;

    return 0;
}

代码03

// 这份代码，是可以AC的，照着题解写的

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1010;

int n, m, pi, ci;
vector<int> h[N];
long long ans = 1e18;

ll check(int tar) {
    int now = h[1].size();
    ll cost = 0;
    vector<int> rem;
    for (int i = 2; i <= n; i++) {
        if (!h[i].empty()) {
            int len = h[i].size();
            int num = max(len - tar + 1, 0);

            now += num;
            for (int j = 0; j < num; j++) cost += h[i][j];
            for (int j = num; j < len; j++) rem.push_back(h[i][j]);
        }
    }

    if (now < tar) {
        sort(rem.begin(), rem.end());
        for (auto i : rem) {
            cost += i;
            now++;
            if (now >= tar) break;
        }
    }   

    return cost;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> pi >> ci;
        h[pi].push_back(ci);
    }

    for (int i = 1; i <= n; i++)
        if (!h[i].empty()) sort(h[i].begin(), h[i].end());

    for (int tar = max((int)h[1].size(), 1); tar <= m; tar++) {
        ans = min(ans, check(tar));
    }

    cout << ans;

    return 0;
}

代码04

// 改成priority_queue

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1010;

int n, m, pi, ci;
vector<int> h[N];
long long ans = 1e18;

ll check(int tar) {
    int now = h[1].size();
    ll cost = 0;
    priority_queue<int> rem;

    // 大于等于最终局面的数量，就应该把多余的干掉
    for (int i = 2; i <= n; i++) {
        if (!h[i].empty()) {
            int len = h[i].size();
            int num = max(len - tar + 1, 0);

            now += num;

            // 这些是注定要被干掉的
            for (int j = len - num; j < len; j++) cost += h[i][j];

            // 这些是在基础线之下的，但也可以被干掉的那些
            for (int j = 0; j < len - num; j++) rem.push(-h[i][j]);
        }
    }

    // 最后看，1号武器现在的材料数量和最终局面的期望tar，还有差距
    // 那么就从等待被干掉的这些，挑选最便宜的干
    while (now < tar) {
        int t = -rem.top(); rem.pop();
        cost += t;
        now++;
    }

    return cost;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> pi >> ci;
        h[pi].push_back(ci);
    }

    for (int i = 1; i <= n; i++)
        if (!h[i].empty()) sort(h[i].begin(), h[i].end(), greater<int>());

    // 如果是贪心，可能会被后面的情况背刺
    // 直接枚举最终局面，就把背刺的情况跳过的。这里n,m<=1000，也暗示着可以枚举
    // 枚举最终局面的时候，适配第1种武器的材料数量
    for (int tar = max((int)h[1].size(), 1); tar <= m; tar++) ans = min(ans, check(tar));

    cout << ans;

    return 0;
}

P11960 [GESP202503 五级] 平均分配

提示

// 对delta差值，进行排序，一半一半的拿就可以了

// 差值贪心

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

struct node{
    int b, c, delta;
}a[N];

bool cmp(node a, node b) {
    return a.delta > b.delta;
}

int main() {
    int n;
    cin >> n;

    int m = n * 2;
    for (int i = 0; i < m; i++) cin >> a[i].b;
    for (int i = 0; i < m; i++) cin >> a[i].c;
    for (int i = 0; i < m; i++) a[i].delta = a[i].b - a[i].c;

    sort(a, a + m, cmp);

    long long sum = 0;
    for (int i = 0; i < n; i++) sum += a[i].b;
    for (int i = n; i < m; i++) sum += a[i].c;
    cout << sum;

    return 0;
}

代码02-dp

// 用01背包写一版本，会超时，也会炸数组
// 这个dp写法，对状态的初始化，有细节

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 2e3 + 10;

int n, b[N], c[N];
ll dp[N][N]; // dp[i][j]表示前i个物品，分配j个买b，可以获得的最大价值，答案是dp[2n][n]

int main() {
    cin >> n;
    for (int i = 1; i <= n * 2; i++) cin >> b[i];
    for (int i = 1; i <= n * 2; i++) cin >> c[i];

    memset(dp, 0xcf, sizeof dp);
    dp[0][0] = 0;
    for (int i = 1; i <= n * 2; i++) {
        dp[i][0] = dp[i - 1][0] + c[i]; // 前i件物品全给c

        for (int j = 1; j <= min(i, n); j++) 
            dp[i][j] = max(dp[i - 1][j - 1] + b[i], dp[i - 1][j] + c[i]);
    }

    cout << dp[n * 2][n];

    return 0;
}

P11961 [GESP202503 五级] 原根判断

P13013 [GESP202506 五级] 奖品兑换-好题

提示

// 用(a,b)或者(b,a)换奖品。总共有(n,m)个卷，最多能换多少

// 注意看取值范围 n, m <= 1e9

提示02

// 二分答案，猜整体购买k个奖品，是否可行

// 如果 k 份能兑换，那少兑换一些一定也能兑换，所以可行性对 k 是单调的

代码

// n取1e9，a取1，那就肯定超时了
// 这样写可得65pts

#include <bits/stdc++.h>

using namespace std;

int n, m, a, b, maxn;

int main() {
    cin >> n >> m >> a >> b;

    // 枚举(a,b)的方案数
    for (int i = 0; i <= n / a; i++) {  
        int nn = n - i * a, mm = m - i * b;
        maxn = max(maxn, i + min(nn / b, mm / a));
    }

    cout << maxn;

    return 0;
}

代码02

// 用(a,b)或者(b,a)换奖品。总共有(n,m)个卷，最多能换多少
// 二分答案，猜整体购买k个奖品，是否可行
// 如果 k 份能兑换，那少兑换一些一定也能兑换，所以可行性对 k 是单调的，

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
ll n, m, a, b;

// ax+b(k-x)<=n, x*(a-b)≤n-b*k
// bx+a(k-x)<=m, x*(b-a)≤m-a*k, x>=(m-a*k)/(b-a), x>=(a*k-m)/(a-b)
// check x的取值区间是否合法
bool check(ll k) {
    ll L = ceil(1.0 * (a * k - m) / (a - b));
    ll R = floor(1.0 * (n - b * k) / (a - b));

    L = max(L, 0ll), R = min(R, k);

    return L <= R;
}

int main() {
    cin >> n >> m >> a >> b;

    if (a == b) {
        cout << min(n, m) / a;
        return 0;
    }
    if (a < b) swap(a, b);

    ll l = 0, r = (n + m + a + b - 1) / (a + b), best = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) l = mid + 1, best = mid;
        else r = mid - 1;
    }

    cout << best;

    return 0;
}

P13014 [GESP202506 五级] 最大公因数

提示

动态的求，gcd(a1 + i, a2 + i, ..., an + i)

提示02

https://www.luogu.com.cn/problem/solution/P13014

这道题，考场上拿60分，属于正常分数了。这个性质，想不到

本质上，手玩样例，多搓几轮，也是可以发现这个gcd的规律的

代码

// q次询问，每次直接for一遍。超时，60pts
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int a[N], n, q;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= q; i++) {
        int x = a[1] + i;

        for (int j = 2; j <= n; j++) {
            x = gcd(x, a[j] + i);
            if (x == 1) break;
        }

        cout << x << endl;
    }


    return 0;
}

代码02

// 正确的性质是，gcd(x, y) = gcd(x, y - x)，就是辗转相减

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int a[N], n, q;

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];

    int m = 0;  // 这个地方是0，这样第一次调用，m就直接是a[2]-a[1]
    for (int i = 2; i <= n; i++) m = __gcd(m, abs(a[i] - a[i - 1]));

    for (int i = 1; i <= q; i++) {
        cout << __gcd(m, a[1] + i) << endl;
    }

    return 0;
}

P14073 [GESP202509 五级] 数字选取

提示

质数

筛法

线性筛

代码

// 1~n之内有多少个质数，最后再添加上数字1，就是答案
// 因为互质
// 用判断质数模板 O(n*sqrtn), n<=1e5
// 可以AC

#include <bits/stdc++.h>

using namespace std;

int cnt = 1, n;

bool is_prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0) return false;

    return true;
}

int main() {
    cin >> n;
    for (int i = 2; i <= n; i++)
        if (is_prime(i)) cnt++;

    cout << cnt;

    return 0;
}

代码02

// 1~n之内有多少个质数，最后再添加上数字1，就是答案
// 因为互质
// 用筛法

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

bool vis[N];
int cnt, n, primes[N];

void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            primes[cnt++] = i;
            for (int j = i + i; j <= n; j += i) vis[j] = true;
        }
    }
}

void get_primes02(int n) {
    for (int i = 2; i <= n; i++) {
        if (vis[i]) continue;
        primes[cnt++] = i;

        for (int j = i * 2; j <= n; j += i) vis[j] = true;
    }
}

int main() {
    cin >> n;
    get_primes(n);

    cout << cnt + 1;

    return 0;
}

代码03

// 1~n之内有多少个质数，最后再添加上数字1，就是答案
// 因为互质
// 用线性筛

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

bool vis[N];
int cnt, n, primes[N];

void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) primes[cnt++] = i;

        for (int j = 0; primes[j] <= n / i; j++) {
            vis[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main() {
    cin >> n;
    get_primes(n);

    cout << cnt + 1;

    return 0;
}

P14074 [GESP202509 五级] 有趣的数字和-好题

提示

// 二进制下，含有奇数个1，就是有趣的

// 统计[l,r]有趣的数字之和

代码

// 二进制下，含有奇数个1，就是有趣的
// 统计[l,r]有趣的数字之和
// 可以枚举32位，也可以用bitset
// 这么写40pts，TLE

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll L, R, sum;

int main() {
    cin >> L >> R;

    for (ll i = L; i <= R; i++) {
        ll k = i;

        int cnt = 0;
        for (int j = 0; j < 31; j++)
            if ((k >> j) & 1) cnt++;

        if (cnt & 1) sum += i;
    }

    cout << sum;

    return 0;
}

代码02

// 这么写60pts，还是TLE
// 因为 1<=l,r<=1e9
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll L, R, sum;

int main() {
    cin >> L >> R;

    for (ll i = L; i <= R; i++) {
        bitset<64> bt(i);
        int cnt = bt.count();
        if (cnt & 1) sum += i;
    }

    cout << sum;

    return 0;
}

提示02

// https://blog.csdn.net/m0_65608962/article/details/153474893

// https://www.luogu.com.cn/article/nni8mnkh

// 这两个题解，结合一下看，就能理解了

// 首先发现规律 4n, 4n+1, 4n+2, 4n+3

// 每4个数，奇偶性的出现是有规律的

// 要么4n,4n+3是奇的，要么4n+1,4n+2是奇的

// 和都是8n+3

// 所以就每4个每4个看

// 分块求和

// 这道题目，部分分可以先拿上，然后打表模拟找规律，是一个很好的分析过程

代码03

// 首先发现规律 4n, 4n+1, 4n+2, 4n+3
// 每4个数，奇偶性的出现是有规律的
// 要么4n,4n+3是奇的，要么4n+1,4n+2是奇的
// 和都是8n+3
// 所以就每4个每4个看

// 分块求和
// 这道题目，部分分可以先拿上，然后打表模拟找规律，是一个很好的分析过程

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll L, R;

ll f(int n) {
    ll sum = 0;

    // 每4个一组的看
    for (ll i = 0; i < n / 4; i++) sum += 8 * i + 3;

    // 零头部分
    for (ll i = n / 4 * 4; i <= n; i++) {
        bitset<64> bt(i);
        if (bt.count() & 1) sum += i;
    }

    return sum;
}

int main() {
    cin >> L >> R;
    cout << f(R) - f(L - 1);    

    return 0;
}

P14917 [GESP202512 五级] 数字移动-好题

提示

// 将相同的数字放在一起，每次移动的花费是交换两个数中的较小值

// 每次移动的花费的最大值，最小可以是多少

// 从最小的数字开始，(1, x) 我们看另一个x在哪里，用1换过来，这次移动的花费是1

// 两个1都换完了，然后用2换。直到所有数字都相邻

提示02

// 我的暴力思路是，从1开始找

// 找到两个1的位置，然后看1旁边的数字，是什么

// 找这个数字的另一半在哪，然后用1交换回来

// 如果1是奇数位置，看p+1位置；如果是偶数位置，看p-1位置

// 这样实现起来，太麻烦

提示03

// 经过AI的指导，确实可以用二分

// 我之前看数据范围，考虑过二分，但是不指导check怎么搞

// check的思路是，把不能移动的元素，放到一个vector中，看这个vector中的内容

// 是否满足按顺序两两一对，如果ok，check就成立

// 那么无论能移动的Ai​怎么移动，都不会改变不能移动的Ai的相对顺序。

// 这个题目的check思路，是有一定的思维量的

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int a[N], n;

bool check(int x) {
    vector<int> A;
    for (int i = 1; i <= n; i++) 
        if (a[i] > x) A.push_back(a[i]);

    for (int i = 0, len = A.size(); i < len; i += 2)
        if (A[i] != A[i + 1]) return false;

    return true;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    int l = 0, r = 1e5, best = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid - 1, best = mid;
        else l = mid + 1;
    }

    cout << best;

    return 0;
}

P14918 [GESP202512 五级] 相等序列

提示

// 每个数字分解质因子

// 把出现过的每个质因子，在每个数字中的幂次，放到一个序列中

// 对这个序列，求中位数，就是要平衡之后的幂次

// 然后for一遍，维护差值

// 就是这个质因子角度，需要的cost

代码

// 这样写，60分。剩下的超时
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int a[N], n;
vector<int> h[N];
int pmax, ans;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];

        int t = a[i];
        for (int j = 2; j <= t / j; j++) {
            if (t % j == 0) {
                int cnt = 0;
                while (t % j == 0) {
                    t /= j;
                    cnt++;
                }

                h[j].push_back(cnt), pmax = max(pmax, j);
            }
        }
        if (t > 1) h[t].push_back(1), pmax = max(pmax, t);
    }

    for (int i = 2; i <= pmax; i++) {
//      cout << i << ": ";
//      for (auto x : h[i]) cout << x << ' ';
//      cout << endl;

        if (h[i].empty()) continue;

        int m = n - h[i].size();
        while (m--) h[i].push_back(0);
        sort(h[i].begin(), h[i].end());

        if (n % 2 == 1) {
            int mid = h[i][n / 2 + 1];
            int cost = 0;

            for (auto x : h[i]) cost += abs(x - mid);
            ans += cost;
        }
        else {
            int mid1 = h[i][n / 2], mid2 = h[i][n / 2 + 1];
            int cost1 = 0, cost2 = 0;

            for (auto x : h[i]) cost1 += abs(x - mid1), cost2 += abs(x - mid2);
            ans += min(cost1, cost2);        
        }
    }

    if (n == 1) ans = 0; 
    cout << ans;

    return 0;
}

代码02

// 这样写，还是超时。关键就在，求中位数这块
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int a[N], n;
vector<int> h[N];
int pmax, ans;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];

        int t = a[i];
        for (int j = 2; j <= t / j; j++) {
            if (t % j == 0) {
                int cnt = 0;
                while (t % j == 0) {
                    t /= j;
                    cnt++;
                }

                h[j].push_back(cnt), pmax = max(pmax, j);
            }
        }
        if (t > 1) h[t].push_back(1), pmax = max(pmax, t);
    }

    for (int i = 2; i <= pmax; i++) {
        if (h[i].empty()) continue;

        int m = n - h[i].size();
        h[i].insert(h[i].end(), m, 0);
        sort(h[i].begin(), h[i].end());

        int mid = h[i][(n + 1) / 2], cost = 0;
        for (auto x : h[i]) cost += abs(x - mid);
        ans += cost;
    }

    if (n == 1) ans = 0; 
    cout << ans;

    return 0;
}

代码03

// 这样就可以AC了

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int a[N], n;
vector<int> h[N];
int pmax;
long long ans;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];

        int t = a[i];
        for (int j = 2; j <= t / j; j++) {
            if (t % j == 0) {
                int cnt = 0;
                while (t % j == 0) {
                    t /= j;
                    cnt++;
                }

                h[j].push_back(cnt), pmax = max(pmax, j);
            }
        }
        if (t > 1) h[t].push_back(1), pmax = max(pmax, t);
    }

    for (int i = 2; i <= pmax; i++) {
        if (h[i].empty()) continue;
        sort(h[i].begin(), h[i].end(), greater<int>());

        int k = (n + 1) / 2, len = h[i].size(), mid;
        long long cost = 0;
        if (len < k) {
            mid = 0;
        }
        else {
            mid = h[i][k - 1];
        }

        for (auto x : h[i]) cost += abs(x - mid);

        ans += 1ll * (n - len) * mid;  // 将所有的0，变成中位数
        ans += cost;
    }

    if (n == 1) ans = 0; 
    cout << ans;

    return 0;
}