前言

哦豁哦豁，我是fw，如果有错欢迎大家指出。

题解

A.材料打印

彩印花彩印的钱，既可以黑白又可以彩印那就哪个便宜用哪个

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    i64 a, x, b, y;
    std::cin >> a >> b >> x >> y;

    std::cout << b * y + std::min(x, y) * a << '\n';
} 

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    std::cin >> t;
    while (t--) {
        solve();
    }
}

B.%%%

这个东西想操作次数尽可能的多模数要尽可能接近于n/2，就比如的话，第一次我用去作为模数，第二次用，第三次用，这样经过三次取模后才使得5变为1，再举例子想把变为，第一次操作的模数我们会用去作为模数，第二次用或去作为模数，手玩几个样例之后，我们就会发现如果当前数为奇数，我们就会用这个数除二向上取整来作为模数，偶数的话会用这个数除二加一来作为模数进行操作为最优

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    i64 n;
    std::cin >> n;
    
    int cnt = 0;
    while (n) {
        cnt++;
        if (n & 1){
            n = n % ((n + 1) / 2);
        }
        else {
            n = n % (n / 2 + 1);
        }
    }
    

    std::cout << cnt << '\n';
} 

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    std::cin >> t;
    while (t--) {
        solve();
    }
}

C.迷宫

我写的纯暴力，出题人加了两个样例还是没卡掉我，我就没再改。

先从终点跑一遍bfs，把所有能到达终点的位置打上标记，注意与终点那一个连通块相邻的所有墙壁也是可以到达终点的，因为我们会拆墙。然后正着跑bfs就好了，如果想走的位置是墙就试一下能不能走到终点（我直接枚举了，不要向我学习）。优化的做法应该是从终点跑bfs，然后给这一行或列打上标记再正着跑的时候去判是否能到终点（我猜的，毕竟我没写）。最后展示我的暴力代码

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

struct node {
    int x, y, k;
};


void solve() {
    int n, m;
    std::cin >> n >> m;
    
    int sx, sy, tx, ty;
    std::vector<std::vector<char> > mp(n + 1, std::vector<char> (m + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            std::cin >> mp[i][j];
            if (mp[i][j] == 'S') {
                sx = i, sy = j;
            }
            if (mp[i][j] == 'E') {
                tx = i, ty = j;
            }
        }
    }

    std::vector<std::vector<int> > vis1(n + 1, std::vector<int> (m + 1));
    std::queue<std::pair<int,int> > q1;
    q1.push({tx, ty});
    vis1[tx][ty] = 1;

    while(!q1.empty()) {
        auto [x, y] = q1.front();
        if (x == sx && y == sy) {
            std::cout << "YES";
            return;
        }
        q1.pop();
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i], yy = y + dy[i];
            if (xx < 1 || xx > n || yy < 1 || y > m || vis1[xx][yy]) continue;
            vis1[xx][yy] = 1;
            if (mp[xx][yy] == '.') {
                q1.push({xx, yy});
            }
        }
    }

    auto check = [&] (int x, int y, int i) -> bool {
        if (i == 0) {
            for (int j = y; j <= m; j++) {
                if (vis1[x][j]) {
                    std::cout << "YES";
                    return 1;
                }
            }
        }
        else if (i == 1) {
            for (int j = x; j <= n; j++) {
                if (vis1[j][y]) {
                    std::cout << "YES";
                    return 1;
                }
            }
        }
        else if (i == 2) {
            for (int j = y; j >= 1; j--) {
                if (vis1[x][j]) {
                    std::cout << "YES";
                    return 1;
                }
            }
        }
        else {
            for (int j = x; j >= 1; j--) {
                if (vis1[j][y]) {
                    std::cout << "YES";
                    return 1;
                }
            }
        }
        return 0;
    };

    std::queue<node> q;
    std::vector<std::vector<int > > vis(n + 1, std::vector<int> (m + 1));
    q.push({sx, sy});
    vis[sx][sy] = 1;
    while (!q.empty()) {
        auto [x, y, k] = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i], yy = y + dy[i];
            if (xx < 1 || xx > n || yy < 1 || yy > m || vis[xx][yy]) continue;
            if (mp[xx][yy] == '#') {
                if (check(xx, yy, i)) {
                    return;
                }
            }
            else {
                vis[xx][yy] = 1;
                q.push({xx, yy});
            }
        }
    }
    
    std::cout << "NO";
} 

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

D.又是一年毕业季

这个题意说我们要确保我们拍照的时候所有人都不能闭眼睛，比如第一个样例，在第的时候不能眨眼睛，也就是说我们选择的拍照时间的因子中不能存在是某个人眨眼睛的时间，因子？所有人？灵光乍现，这不就是要找个最小的没有出现过的素数嘛，一共才个数，那我们直接素数筛出来最小的个素数遍历一遍看最小的没出现过的素数是哪个不就好了吗

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

std::bitset<10000005>st;//定义方式，这里就相当于定义bool数组
//st[i]==0,则i为素数
std::vector<int>Prime(2e5 + 5);//存质数,下标从1开始输出第几个质数就输出prime(n)；
void pri(int M)
{
    int cnt = 0;
    for (int i = 2; i <= M; i++)
    {
        if (st[i] == 0)    Prime[++cnt] = i;
        if (cnt > 2e5) break;
        for (int j = 1; j <= cnt; j++)
        {
            if (i * Prime[j] > M)break;// 如果超出给出的范围，那么就退出循环 
            st[i * Prime[j]] = 1;//素数的倍数不是素数，进行标记。
            if (i % Prime[j] == 0)break;//超级关键的只标记一次
        }
    }
}

void solve() {
    int n;
    std::cin >> n;

    std::unordered_map<int, int> mp;
    for (int i = 1; i <= n; i++) {
        int a;
        std::cin >> a;
        mp[a] = 1;
    }
    for (int i = 1; i <= 200001; i++) {
        if (!mp[Prime[i]]) {
            std::cout << Prime[i] << '\n';
            return;
        }
    }
} 

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    pri(10000000);
    i64 t = 1; 
    std::cin >> t;
    while (t--) {
        solve();
    }
}

E.多米诺骨牌

区间合并的板子题吧，刚开始我竟然在贪心，认为下一个只能由上一个推倒，我是rz，那我们就把每个骨牌能覆盖的区间求出来，然后像并查集那种思想，看有哪些骨牌不能被前面推倒只能手动推倒，记录一下这其中的每一个骨牌倒下后能一口气推倒多少记录一下，最后取能推倒最多的块骨牌就好了。有可能我们推倒了第一个骨牌就把所有的连锁反应推倒了，所以记得要把和你要推倒的骨牌数取个以防越界，我这个是离散化差分了一下，大家可以去网上学习一下区间合并。

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    int n, m;
    std::cin >> n >> m;

    std::unordered_map<int, int> mp;
    std::vector<int> h(n + 1), x(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> h[i];
    }
    for (int i = 1; i <= n; i++) {
        std::cin >> x[i];
        mp[x[i]] = h[i];
    }

    std::sort(x.begin() + 1, x.end());

    std::vector<int> c(n + 2);
    for (int i = 1; i <= n; i++) {
        int pos = std::upper_bound(x.begin() + 1, x.end(), x[i] + mp[x[i]]) - x.begin() - 1;
        c[i] += 1;
        c[pos + 1] -= 1;
    }

    for (int i = 1; i <= n; i++) {
        c[i] += c[i - 1];
    }

    std::vector<int> v;
    int num = 0;
    for (int i = n; i >= 1; i--) {
        num++;
        if (c[i] == 1) {
            v.push_back(num);
            num = 0;
        }
    }

    std::sort(v.begin(), v.end(), std::greater<int>());
    
    int ans = 0;
    for (int i = 0; i < std::min((int)v.size(), m); i++) {
        ans += v[i];
    }

    std::cout << ans << '\n';
} 

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    std::cin >> t;
    while (t--) {
        solve();
    }
}

F.自爆机器人

这个观察题意可知，如果 那么就输出，否则我们进行，表示是否可以对怪物造成点伤害，我们分析题目，该机器人如果想多走几步使得伤害更高，他一定会在任意两个相邻的墙壁之前来回碰撞来回走，不可能去中间隔一个，比如我们有三堵墙在我们单独看他们之间的距离为，走一个来回的距离为，再看，他们间距离为，走一个来回距离为，最后看，他们间距离为，走一个来回距离为，如果我们想要多造成点伤害，不需要在之间走一个来回，我们可以分两步，在走，在走，这样的话我们只需要处理出来任意两堵相邻的墙走一个来回的路程作为背包的物品，把机器人最长的爆炸时间t作为背包容量进行背包操作就可以了！

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    i64 n, m, t;
    std::cin >> n >> m >> t;
    
    std::vector<i64> a(m + 1);
    for (i64 i = 1; i <= m; i++) {
        std::cin >> a[i];
    }

    t -= n;
    if (t < 0) {
        std::cout << 0 << '\n';
        return;
    }

    std::sort(a.begin() + 1, a.end());

    std::set<int> st;
    for (int i = 1; i < m; i++) {
        st.insert(2 * (a[i + 1] - a[i]));
    }

    std::vector<bool> dp(t + 1, 0);
    dp[0] = 1;
    for (auto it : st) {
        for (int i = it; i <= t; i++) {
            dp[i] = dp[i] | dp[i - it];
        }
    }

    for (int i = t; i >= 0; i--) {
        if (dp[i]) {
            std::cout << i + n << '\n';
            return;
        }
    }
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    std::cin >> t;
    while (t--) {
        solve();
    }
}

G.大鱼吃小鱼

也算是很典的一道题吧，离散化+树状数组，把所有区间按左端点排序，然后枚举右端点，算出当前右端点前所有区间的贡献和是多少，这里我们用树状数组维护前缀和，然后去暴力跳点，看当前体重能吃多少，然后加到体重上，再去看吃完上一波的体重又能吃多少，直到吃的不能再吃为止，某个学长曾经告诉我，这东西类似于斐波那契数列，跳的很快，不要太担心T，所以最终也就是枚举了一遍左端点和右端点，2n的复杂度再加上暴力跳点的复杂度。具体细节看代码吧，如果有不懂的地方欢迎评论和私信。

#include<bits/stdc++.h>
#define lowbit(x) x & (-x)

using i64 = long long;
using u64 = unsigned long long;

struct node {
    int l, id;
};

struct Fenwick {
    int n;
    std::vector<i64> tr;
    std::stack<std::pair<int,int>> sta;
    void reset(int m) {
        n = m;
        tr.clear();
        tr.resize(n + 1);
    }
    void modify(int u, int x) {
        sta.push(std::make_pair(u, x));
        for (int i = u + 1; i <= n; i += lowbit(i))
            tr[i] += x;
    }
    i64 query(int u) {
        i64 x = 0;
        for (int i = u + 1; i >= 1; i -= lowbit(i))
            x += tr[i];
        return x;
    }
    i64 query(int l, int r) { // [l, r]
        return query(r) - query(l - 1);
    }
    void clear() {
        while(!sta.empty()) {
			auto cur = sta.top();
			int x = cur.first, v = cur.second;
			for (int i = x + 1 ;i <= n; i += lowbit(i))
				tr[i] -= v;
			sta.pop();
		}
    }
}tr;

void solve() {
    int n, x;
    std::cin >> n >> x;

    std::vector<node> a(n + 1);
    std::vector<int> l(n + 1), r(n + 1), y(n + 1), v;
    std::set<int> st;
    for (int i = 1; i <= n; i++) {
        std::cin >> l[i] >> r[i] >> y[i];
        a[i].l = l[i];
        a[i].id = i;
        st.insert(r[i] - 1);
        v.push_back(y[i]);
    }

    std::sort(a.begin() + 1, a.end(), [&](node &x, node &y) {
        return x.l < y.l;
    });

    std::sort(v.begin(), v.end());
    int m = std::unique(v.begin(), v.end()) - v.begin(), now = 1;
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > > q;
    tr.reset(m + 1);
    i64 ans = x;

    for (auto it : st) {
        while (now <= n && a[now].l <= it) {
            q.push({r[a[now].id], a[now].id});
            int id = a[now].id;
            int dy = y[id];
            int pos = std::lower_bound(v.begin(), v.begin() + m, dy) - v.begin() + 1;
            tr.modify(pos, dy);
            now++;
        }

        while (!q.empty() && q.top().first <= it) {
            int id = q.top().second;
            int dy = y[id];
            int pos = std::lower_bound(v.begin(), v.begin() + m, dy) - v.begin() + 1;
            tr.modify(pos, -dy);
            q.pop();
        }

        i64 num = 0, lst = x;
        while(num != lst) {
            num = lst;
            int pos = std::upper_bound(v.begin(), v.begin() + m, lst) - v.begin();
            lst = x + tr.query(pos);
        }
        
        ans = std::max(ans, lst);
    }
    std::cout << ans << '\n';
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    std::cin >> t;
    while (t--) {
        solve();
    }
}