头像

不拿周赛牌不改名

ALL IN




离线:7分钟前


最近来访(717)
用户头像
吾皇_7
用户头像
航_0
用户头像
克里斯保罗
用户头像
一滴绿意
用户头像
Brou_6
用户头像
StarLi9ht
用户头像
Wing_wing_wing
用户头像
_watermelon_
用户头像
lorendw7
用户头像
君故
用户头像
1357649762
用户头像
acwing_2389
用户头像
陈锅陈锅
用户头像
Chaleur
用户头像
xiaoYun_succ
用户头像
Tequila
用户头像
我看青山多妩媚
用户头像
ap-yyyy
用户头像
Kat_
用户头像
yxc的小迷妹

分享 关于二分

二分可以解决问题的共同点

数组中存在一条分界线,使得分界线左边的位置都满足某个条件并且右边的位置都不满足同一个条件。
接着我们要找到一条分界线,满足分界线左边的数字都 < x右边的数字都 >= x

所以现在只有最后一个疑问:分界线怎么找?

一开始,分界线一定是在序列的两个边界,如果数组从1开始存储的话,那么分界线就在0和n + 1的位置;如果数组从0开始存储的话,那么分界线就在-1和n的位置。

两个边界的位置如下图
微信图片_20221125005657.png

注意分界线是在两个方框中间的位置,是指向两个元素之间的位置。
如下图

微信图片_20221125005848.png

例题:a = {1, 4, 7, 9, 9, 11, 12, 15, 17, 19, 21} 在这个数组中查询小于11的数字有多少个。

步骤分解:

微信图片_20221125010224.png

微信图片_20221125010242.png

继续循环

微信图片_20221125010532.png

到目前为止,分界线还有蓝色竖线画出的三种可能的情况
微信图片_20221125010631.png

继续循环

微信图片_20221125010730.png

此时分界线还有最后两种可能的情况
继续循环

微信图片_20221125010929.png

此时L = 5, R = 6,已经满足循环退出条件L + 1 == R,也就找到了我们的分界线。分界线左边的数字都是 < x 的,右边的数字都是 >= x 的

微信图片_20221125011053.png

再来分析一下:

我们看一下[L, R]的中间位置mid = (L + R)/ 2。
如果a[mid] < x,那么分界线会在M的右边,否则分界线会在M的左边。
如果a[mid] <= x, 那么分界线会在M的左边,否则分界线会在M的右边。
经过不断缩减范围,当L + 1 == R时,我们就找到分界线啦!

思考:

1.最后如果L = 0意味着什么?

答:所有数字都 >= x

2.最后如果L = n意味着什么?

答:所有数字都 < x

代码展示:

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 100010;

int n, x;
int a[N];

int main()
{
    cin >> n >> x;
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", &a[i]);
    }
    int l = 0, r = n + 1;
    while(l + 1 < r)
    {
        int mid = (l + r) / 2;
        if(a[mid] < x)
        {
            l = mid;
        }
        else r = mid;
    }
    printf("%d\n", l);
    return 0;
}

测试样例
输入数据
11 11
1 4 7 9 9 11 12 15 17 19 21
输出数据
5




二分答案

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 100010;

int n;
int h[N];

bool col(int x)
{
    int e = x;
    for(int i = 1; i <= n; i ++)
    {
        if(e >= 100000)
            break;
        e = 2 * e - h[i];
        if(e < 0) return false;
    }
    return true;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", &h[i]);
    }
    int l = 1, r = 100000;
    while(l + 1 < r)
    {
        int mid = (l + r) >> 1;
        if(col(mid))
        {
            r = mid;
        }
        else l = mid;
    }
    printf("%d\n", r);
    return 0;
}


活动打卡代码 AcWing 790. 数的三次方根

实数二分

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

double n;

int main()
{
    cin >> n;
    double l = -10000, r = 10000;
    while(r - l > 1e-8)
    {
        double mid = (l + r) / 2;
        if(mid * mid * mid <= n)
        {
            l = mid;
        }
        else r = mid;
    }
    printf("%lf\n", r);
    return 0;
}


活动打卡代码 AcWing 789. 数的范围

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int q[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    for (int i = 0; i < m; i ++ )
    {
        int x;
        scanf("%d", &x);
        // 二分x的左端点
        int l = 0, r = n - 1;   // 确定区间范围
        while (l < r)
        {
            int mid = l + r >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }

        if (q[r] == x)
        {
            cout << r << ' ';

            // 二分x的右端点
            r = n - 1;  // 右端点一定在[左端点, n - 1] 之间
            while (l < r)
            {
                int mid = l + r + 1 >> 1;   // 因为写的是l = mid,所以需要补上1
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }
            cout << r << endl;
        }
        else cout << "-1 -1" << endl;
    }

    return 0;
}


活动打卡代码 AcWing 116. 飞行员兄弟

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
typedef pair<int, int> PII;

const int N = 5;

char g[N][N];
vector<PII> ans, tmp;

void turn_all(int x, int y)
{
    for(int i = 0; i < 4; i ++)
    {
        if(g[x][i] == '+') g[x][i] = '-';
        else if(g[x][i] == '-') g[x][i] = '+';
    }
    for(int i = 0; i < 4; i ++)
    {
        if(g[i][y] == '+') g[i][y] = '-';
        else if(g[i][y] == '-') g[i][y] = '+';
    }

    //g[x][y]的那个点要改变三次
    if(g[x][y] == '+') g[x][y] = '-';
    else if(g[x][y] == '-') g[x][y] = '+';

    return ;
}

void dfs(int x, int y)
{
    //所有把手操作完了, 看看能不能打开
    if(x == 3 && y == 4)
    {
        bool has_off = false;
        for(int i = 0; i < 4; i ++)
        {
            for(int j = 0; j < 4; j ++)
            {
                if(g[i][j] == '+')
                {
                    has_off = true;
                    return ;
                }
            }
        }
        if(!has_off)
        {
            if(ans.empty() || ans.size() > tmp.size())
            {
                ans = tmp;
            }
        }
        return ;
    }

    //边界
    if(y == 4) x++, y = 0;

    //改变把手状态
    turn_all(x, y);
    tmp.push_back({x, y});
    dfs(x, y + 1);

    //恢复现场
    tmp.pop_back();
    turn_all(x, y);

    //不改变把手状态
    dfs(x, y + 1);
}

int main()
{
    for(int i = 0; i < 4; i ++)
    {
        cin >> g[i];
    }

    dfs(0, 0);

    cout << ans.size() << endl;
    for(int i = 0; i < ans.size(); i ++)
    {
        printf("%d %d\n", ans[i].first + 1, ans[i].second + 1);
    }
    return 0;
}


活动打卡代码 AcWing 1208. 翻硬币

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 110;

char start[N];
char end1[N];

void turn(int i)
{
    if(start[i] == '*') start[i] = 'o';
    else start[i] = '*';
    return ;
}

int main()
{
    cin >> start >> end1;
    int n = strlen(start);
    int res = 0;
    for(int i = 0; i < n - 1; i ++)
    {
        if(start[i] != end1[i])
        {
            res ++;
            turn(i), turn(i + 1);
        }
    }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 95. 费解的开关

开关问题共同点: 1.每个开关只按一次 2.按得顺序无关

枚举第一行的意义是:不需要在意第一行的灯是灭是暗,只需把第一行开关的32种按法枚举一遍,也就是我们说的 “操作”,每个位置都有两种选择,按(用1表示)或者不按(用0表示),遍历这32种操作引发的情况,每一次再通过
res = min(res, step);把最小步数存一下,就能找到最优解

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 6;

int T;
char g[N][N], backup[N][N];

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

void turn(int x, int y)
{
    for(int i = 0; i < 5; i ++)
    {
        int a = x + dx[i];
        int b = y + dy[i];
        if(a < 0 || a >= 5 || b < 0 || b >= 5) continue;
        if(g[a][b] == '1')
            g[a][b] = '0';
        else if(g[a][b] == '0')
            g[a][b] = '1';     //或者直接g[a][b] ^= 1;   //异或,不同的时候就变成相反的数
    }
}

int main()
{
    cin >> T;
    for(int i = 0; i < T; i ++)
    {
        for(int i = 0; i < 5; i ++)
        {
            cin >> g[i];
        }

        int res = 10; //最大步数为6, 定义个比6大的数

        //直接枚举第一排的所有可能按开关的可能性, 2^5 = 32, 不必考虑第一排初始是什么
        for(int op = 0; op < 32; op ++)
        {
            memcpy(backup, g, sizeof g); //备份
            int step = 0;
            for(int i = 0; i < 5; i ++)
            {
                //第一排有2^5种按法,枚举每种开关的按法(用二进制来枚举)
                //这是枚举按还是不按那个开关,而不是选择第一排一开始是什么状态的。
                //这里1表示按了,0表示不按。
                if(op >> i & 1)  //看二进制的第i位是不是1
                {
                    step ++;
                    turn(0, i);
                }
            }

            //枚举前四排
            for(int i = 0; i < 4; i ++)
            {
                for(int j = 0; j < 5; j ++)
                {
                    //如果是'0', 则改变下一排开关的状态
                    if(g[i][j] == '0')
                    {
                        step ++;
                        turn(i + 1, j);
                    }
                }
            }

            //遍历最后一排, 如果有黑(0)的,则说明该方案行不通
            int dark = 0;
            for(int i = 0; i < 5; i ++)
            {
                if(g[4][i] == '0')
                {
                    dark = 1;
                    break;
                }
            }

            if(!dark) res = min(res, step);

            //开关复原
            memcpy(g, backup, sizeof g);
        }

        if(res > 6) res = -1;
        cout << res << endl;
    }

    return 0;
}


活动打卡代码 AcWing 717. 简单斐波那契

递推

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 50;

int n;

int main()
{
    cin >> n;
    int a = 0;
    int b = 1;
    int tmp = 0;
    for(int i = 0; i < n; i ++)
    {
        printf("%d ", a);
        tmp = a + b;
        a = b;
        b = tmp;
    }
    return 0;
}


活动打卡代码 AcWing 1209. 带分数

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 10;

int n;  //要求的数
int num[N]; //保留全排列的结果
bool st[N];  //标记
int cnt;  //答案数量

//计算num数组中一段的数是多少
int cal(int l, int r)
{
    int res = 0;
    for(int i = l; i <= r; i ++)
    {
        res = res * 10 + num[i];
    }
    return res;
}

void dfs(int x)
{
    if(x == 9)
    {
    for(int i = 0; i < 7; i ++)
    {
        for(int j = i + 1; j < 8; j ++)
        {
            //全排列分为三段, 插两个板
            int a = cal(0, i);
            int b = cal(i + 1, j);
            int c = cal(j + 1, 8);

            // 注意判断条件,因为C++中除法是整除,所以要转化为加减乘来计算
            if(a * c + b == c * n)
            {
                cnt ++;
            }
        }
    }
    }

    //全排列
    for(int i = 1; i <= 9; i ++)
    {
        if(!st[i])
        {
            num[x] = i;
            st[i] = 1;
            dfs(x + 1);
            st[i] = 0;
        }
    }
}

int main()
{
    cin >> n;
    dfs(0);
    printf("%d\n", cnt);
    return 0;
}



剪枝:为什么是x + n - start < m?

(x - 1)  +  (n - start + 1)  <  m
已选的  +  空位(还没选数字的) <  剩下位置数

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 30;

int n, m;
int way[N];

void dfs(int x, int start)
{
    //剪枝儿~
    if(x + n - start < m) 
        return ;

    if(x == m + 1)
    {
        for(int i = 1; i <= m; i ++)
        {
            printf("%d ", way[i]);
        }
        cout << endl;
        return ;
    }

    for(int i = start; i <= n; i ++)
    {
        way[x] = i;
        dfs(x + 1, i + 1);
        way[x] = 0; //可省略, 恢复现场
    }
    return ;
}

int main()
{
    scanf("%d %d", &n, &m);
    dfs(1, 1);
    return 0;
}