Profile Image of the Author
Mkrari
GitHub
统计加载中...
公告
欢迎访问我的博客！这里会分享技术文章和生活感悟。
1279 字
3 分钟
日常算法随记part.3
2026-04-26
日常练习
ACM
统计加载中...

牛客trackertracker是个好东西（），之前打寒假练习的时候就发现上面对对应的专题设置了板块练习，非常适合慢慢刷。这周抽空刷了状压枚举和二分法的题。同时尝试给自己相对较长的时间去独立解题，感觉效果还不错，具体在题目里一一道来。

Bob的蛋糕店#

题目链接：https://www.nowcoder.com/practice/f4f6870953b64e059fdb5f76dc69b46d?channelPut=tracker3
数据很小，是道练习状压枚举的模板题。
大致题意：在横轴上有nn个质点，第ii个质点的质量为mim_i，横坐标为ii，支点位于全部质点的质心 xc=∑mi×i∑mix_c = \frac{\sum_{}{}m_i \times i}{\sum m_i} ，随后拿走kk个质点，判断剩余质点的质心是否依旧位于质点xcx_c处，是输出YesYes，否则输出NoNo。
思路：我们直接枚举取走的所有情况然后计算判断质点是否改变即可。
本题使用了bitsetbitset来将拿走第ii位设置为在对应的位bitset[i−1]bitset[i - 1]设置为11，不取设置为00，（bitsetbitset的第一位是00）来对于2n2^n种情况逐一枚举判断是否满足条件。这里也可以不用bitsetbitset，而是使用位运算操作1&(1≪i)1 \& (1 \ll i)来逐位取。

NOTE

状压枚举：将问题转化成为0101来进行位操作，减少开数组等其他方式的空间开销。对于数据相对较小和比较复杂的实现可以简化。

#include <bits/stdc++.h>


using namespace std;
using ll = long long;
#define endl '\n'
#define mod 998244353


int m[30];


void solved(){
    int n, k;
    cin >> n >> k;
    int sum1 = 0;
    int sum2 = 0;


    for (int i = 1; i <= n; i++){
        cin >> m[i];
        sum1 += m[i] * i;
        sum2 += m[i];
    }
    double zx = sum1 * 1.0 / sum2;
    for (int i = 1; i <= (1 << n) - 1; i++){
        bitset<25> bits(i);
        int sum1 = 0;
        int sum2 = 0;
        if(bits.count() == k){
            for (int i = 0; i < n;i++){
                if(bits[i] == 1){
                    sum1 += m[i + 1] * (i + 1);
                    sum2 += m[i + 1];
                }
            }
        }
        double cd = sum1 * 1.0 / sum2;
        if(cd == zx){
            cout << "Yes" << endl;
            return;
        }
    }
    cout << "No" << endl;
}


int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solved();
    return 0;
}

小红的扫雷游戏#

题目链接：https://www.nowcoder.com/practice/e610b4dac2c747a09b926053df59c958?channelPut=tracker3
这题思路还是比较明确的，我们依旧是通过状压枚举来判断这些格子是否可能为雷。姑且想的出思路，不过实现还真是比较复杂的。
大致题意：给定一个 4×44 \times 4的区域，其中有一些位置已经被翻开，需要根据已有信息判断哪些一定是雷，哪些一定不是雷。对于一个确定的格子，如果是雷就标记为′X′'X'，不是雷则标记为′O′'O'。不确定的格子保留为′.′'.'，已经确定的数字也按数字输出。
思路：我们只需要枚举有数字的周围八格的所有组成情况，最坏情况总数不会超过2162^{16}，依旧非常小。如果枚举的合法条件的一个格子有两种情况，即可能是雷也可能不是雷则在输出时改为′.′'.'。其他格子情况一致的正常输出′X′'X'或′O′'O'。
代码实现主要也是将未知的格子进行状压枚举，只不过将压缩的状态转化为格子状态和判断的时候比较复杂，详细请看注释。

#include <bits/stdc++.h>


using namespace std;
using ll = long long;
#define endl '\n'
#define mod 998244353
typedef pair<int, int> pii;


vector<string> grid(5);


vector<pii> blanks;   //收集未知格子"."的坐标


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


void solved(){
    for (int i = 1; i <= 4;i++){
        cin >> grid[i];
        grid[i] = " " + grid[i];
    }


    // 保留原始棋盘
    vector<string> orig = grid;


    for(int i = 1; i <= 4;i++){
        for (int j = 1; j <= 4; j++){
            if(grid[i][j] == '.'){
                blanks.push_back({i, j});
            }
        }
    }
    int cnt = blanks.size();


    vector<int> state(cnt, -1);  //-1为初始，0为"O", 1为"X",2为不确定




    //对于所有未知格子我们填入当前情况下的对应的确定值
    for (int i = 0; i <= (1 << cnt) - 1; i++){
        grid = orig;
        bitset<20> bits(i);
        for (int b = 0; b < cnt; b++){
            if(bits[b] == 1){
                grid[blanks[b].first][blanks[b].second] = 'X';
            }
            if(bits[b] == 0){
                grid[blanks[b].first][blanks[b].second] = 'O';
            }
        }
        bool f = true;
        //判断这个组合是否合法（满足数字对周围格子的雷数量的要求）
        for (int j = 1; j <= 4 && f; j++){
            for (int k= 1; k <= 4 && f; k++){
                if (grid[j][k] - '0' >= 0 &&grid[j][k] - '0' <= 9) {
                    int cnt1 = 0;
                    for (int l = 0; l <= 7; l++){
                        int x = j + dx[l];
                        int y = k + dy[l];
                        if(x >= 1 && x <= 4 && y >= 1 && y <= 4 && grid[x][y] == 'X'){
                            cnt1++;
                        }
                    }
                    if(cnt1 != grid[j][k] - '0'){
                        f = false;
                    }
                }
            }
        }
    //如果合法就计入state用以判断最终结果
        if(f == true){
            bitset<20> bits(i);
            for (int b = 0; b < cnt; b++){
                if(bits[b] == 1){
                    grid[blanks[b].first][blanks[b].second] = 'X';
                }
                else if(bits[b] == 0){
                    grid[blanks[b].first][blanks[b].second] = 'O';
                }
                if(state[b] == -1){
                    state[b] = bits[b];
                }
                else if(state[b] != bits[b]){
                    state[b] = 2;
                }
            }
        }
    }


    vector<string> ans = orig;   //记录结果，并按照state的状态修改对应的格子


    //对于未确定的格子判断（都存在blanks里）
    for (int b = 0; b < cnt; b++){
        int x = blanks[b].first, y = blanks[b].second;
        if(state[b] == 1){
            ans[x][y] = 'X';
        }
        else if(state[b] == 0){
            ans[x][y] = 'O';
        }
        else{
            ans[x][y] = '.';
        }
    }


    for (int i = 1; i <= 4; i++){
        for (int j = 1; j <= 4; j++){
            cout << ans[i][j];
        }
        cout << endl;
    }
}


int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solved();
    return 0;
}

整数域二分#

题目链接：https://www.nowcoder.com/practice/ee70e343d1bf4646b6eace9957f697c9?channelPut=tracker3
正如其名，是一道模板，我独立解题时主要是搞错了数据的范围。应该是数组下标作最大值而不是数组元素的最大值。 大致题意：给长度为nn的数组ana_n，每次操作输出数组中大于ll且小于等于rr的元素个数。一共需要操作qq次。
思路：我们利用二分查找分别找到最小的左端位置和最大的右端位置即可。
二分法就是我们中学数学提到的折半查找（注意二分要满足单调性），应该不用过多赘述了。这里我们可能要注意一下我们搜索的是什么，最大值应该如何取，还有对应搜索的应该尽可能左搜还是右搜。

#include <bits/stdc++.h>


using namespace std;
using ll = long long;
#define end '\n'
typedef pair<int,int> pii;


ll a[200010];


ll l, r;


ll check1(ll x){
    if(a[x] >= l){
        return true;
    }
    return false;
}
ll check2(ll x){
    if(a[x] <= r){
        return true;
    }
    return false;
}
void solved(){
    int n, q;
    cin >> n >> q;


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


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


    while(q--){
        ll index1 = 1, index2 = n;
        cin >> l >> r;
        ll left = 1, right = n;


        //二分找左边端点
        while(left <= right){
            ll mid = left + (right - left) / 2;
            if(check1(mid)){
                index1 = mid;
                right = mid - 1;    //尽可能左搜
            }
            else{
                left = mid + 1;
            }
        }
        left = 1, right = n;


        //二分找右边的端点
        while(left <= right){
            ll mid = left + (right - left) / 2;
            if(check2(mid)){
                index2 = mid;
                left = mid + 1;   //尽可能右搜
            }
            else{
                right = mid - 1;
            }
        }
        cout << index2 - index1 + 1 << endl;
    }
}


int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solved();
    return 0;
}

不想做二分题#

题目链接：https://www.nowcoder.com/practice/3732bf4e88704ab49b8010f42edc7e63?channelPut=tracker3
也算是一类经典的贪心＋二分的题目了，独立解题的时候主要是卡在了不知道怎么思考贪心的实现上。确实要多练了。。。
大概题意：一排上有nn个怪，每回合都可以进行一次1.1.所有怪扣一滴血的AOEAOE，和2.2.选择一个单体扣一滴血，和3.3.一次对相邻的两个怪各扣一滴血（可对死去的怪使用）。求击杀所有怪物最少需要多少回合。
思路：我们使用二分答案，每次都对一个答案进行贪心判断是否能击杀所有怪，能就继续向左搜找最小满足条件的回合数。
这里贪心的思路是先全体AOEAOE，因为能够打到最多的单位。其次是双打。双打要保证不存在相邻的怪存活才能最优解化，所以我们双打的时候是两两进行取最小值来打。最后是记录还没被击杀的怪物的血量，看点杀的次数够不够。这里注意kk，kk记录了双打时是否还有次数剩余，有的话我们可以用来点杀（题目说可以对失去的怪物释放技能。）

#include <bits/stdc++.h>


using namespace std;
using ll = long long;
#define endl '\n'
#define mod 998244353
typedef pair<int, int> pii;


const double pi = 3.14159265358;


ll a[200010];
ll b[200010];
int n;


ll check(ll x){
    //优先全体AOE
    for (int i = 1; i <= n; i++){
        b[i] = a[i];
        b[i] = max(0LL, b[i] - x);
    }
    ll k = 0;  //记录双打的使用次数。
    //接着是双打
    for (int i = 1; i < n;i++){
        ll d = min(b[i], b[i + 1]);  //每次都保证选择的两者其中有一个被击杀
        d = min(d, x - k);
        b[i] -= d;
        b[i + 1] -= d;
        k += d;
        if(k == x) break;
    }
    //最后逐一点杀
    ll final_blood = 0;
    for (int i = 1; i <= n;i++){
        final_blood += b[i];
    }
    return final_blood <= 2 * x - k;   //没使用完的双打可以用来点杀
}


void solved(){
    cin >> n;
    ll ma = 0;
    for (int i = 1; i <= n;i++){
        cin >> a[i];
        if(ma < a[i]){
            ma = a[i];
        }
    }
    ll ans = ma;
    ll left = 1, right = ma;
    while(left <= right){
        ll mid = left + (right - left) / 2;
        if(check(mid)){
            ans = mid;
            right = mid - 1;
        }
        else{
            left = mid + 1;
        }
    }
    cout << ans << endl;
}


    int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solved();
    return 0;
}
分享

如果这篇文章对你有帮助，欢迎分享给更多人！

日常算法随记part.3
https://mkrari.cn/posts/algorithmrecord_3/
作者
Mkrari
发布于
2026-04-26
许可协议
CC BY-NC-SA 4.0
2026方班杯PWN_loginin
2026蓝桥杯省赛C++B组部分复盘(1,3,4,7)
© 2026 Mkrari. All Rights Reserved. / RSS / Atom / Sitemap
Powered by Astro & Mizuki  Version 8.2