头像

我是java同学




在线 


最近来访(312)
用户头像
有机物
用户头像
Huayang_Yuan
用户头像
Stair
用户头像
源泉
用户头像
WillHou
用户头像
我还是小学生
用户头像
萧瑟灬
用户头像
acwing_1812
用户头像
源泉_4
用户头像
锦木千束
用户头像
一塌糊涂
用户头像
Lucky_Man
用户头像
Xayanium
用户头像
mhmh
用户头像
冠生
用户头像
日川纲坂
用户头像
Paren
用户头像
冷静对待一切
用户头像
Amaryllis_
用户头像
我才不认识这个人


二分 双指针 前缀和

  • 优化问题转化为判定问题
    • 先二分答案。问题转化为:在原序列里是否存在一段连续的子序列所有数的平均值大于等于mid
    • 把所有数都减去一个mid,问题转化为:在原序列里是否存在一段连续的子序列所有数的和是非负的(大于等于0
    • 以某个点为右端点的所有子序列的和可以用前缀和算
    • s = sum[j] - sum[i]jf的距离是大于等于f的,用一个变量minv记录从0i的最小值
    • 最后判断s[j] >= minv
  • 限制:长度大于等于F,和为非负
  • 二分的单调性:如果mid(平均值)满足要求,那么所有小于等于mid的数都是满足要求的.
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int cow[N];
double sum[N];

bool check(double avg)
{
    for (int i = 1; i <= n; i ++ ) sum[i] = sum[i - 1] + cow[i] - avg;

    double minv = 0;
    for (int i = 0, j = m; j <= n; i ++ , j ++ ) 
    {
        minv = min(minv, sum[i]);
        if (sum[j] >= minv) return true;
    }
    return false;
}

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

    double l = 0, r = 2000;
    while (r - l > 1e-5)
    {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }

    printf("%d\n", int(r * 1000));
    return 0;
}



二分

9D2F159DF7D5465F305484DD8809112E.png

#include <iostream>

using namespace std;

const int N = 100010;

typedef long long LL;

int n;
int h[N];

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

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

    int l = 0, r = 100000;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%d\n", r);
    return 0;
}



二分

  • 找出单调性——要隔开的牛数越多,相邻隔间距离越小
  • 假设mid成立,判断答案的位置是在mid的左边还是右边
    • QQ图片20230207214413.jpg
  • check函数的思路:先排序,把隔间的坐标从小到大排列好。从第一个隔间的距离开始找,也就是第一个隔间和第二个隔间的距离,依次枚举每个隔间,如果枚举的隔间的距离大于等于mid,更新牛的数量。最后判断牛的数量是否大于c,更新边界

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, c;
int a[N];

bool check(int mid)
{
    LL sum = 1, k = 0;
    for (int i = 1; i <= n; i ++ ) 
        if (a[i] - a[k] >= mid) 
        {
            k = i;
            sum ++ ;
        }
    return sum >= c;
}

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

    sort(a, a + n);

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

    return 0;
}



二分

  • 本题直接求是非常不好求的,如果用二分相当于 给题目多了一个条件——巧克力能切的最大长度,我们可以二分出巧克力可以切到的最大长度mid,问题转化成:可以切出多少个边长为mid的正方形。
    • QQ图片20230207173613.jpg
  • 每块巧克力都是独立的,所以每块巧克力的能切的最大长度都是不一样的。并且每块巧克力只能裁剪不能拼接。裁剪是分别看每条边长与最大边长的关系,而拼接是用总面积/最大巧克力的面积,两种情况是不一样的。
#include <iostream>

using namespace std;

const int N = 100010;

typedef long long LL;

int n, k;
int h[N], w[N];

bool check(int mid)
{
    LL res = 0;
    for (int i = 0; i < n; i ++ ) 
    {
        res += (LL)(h[i] / mid) * (w[i] / mid);
        if (res >= k) return true;
    }
    return false;
}

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

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

    cout << r << endl;

    return 0;
}



bfs

  • 两个返回值——引用
  • 细节比较多
#include <cstring>
#include <algorithm>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010, M = N * N;

int n;
int h[N][N];
PII q[M];
bool st[N][N];

void bfs(int sx, int sy, bool &has_higher, bool &has_lower)
{
    int hh = 0, tt = -1;
    q[++ tt] = {sx, sy};
    st[sx][sy] = true;

    while (hh <= tt)
    {
        auto t = q[hh ++ ];

        for (int i = t.x - 1; i <= t.x + 1; i ++ )
            for (int j = t.y - 1; j <= t.y + 1; j ++ ) 
            {
                if (i == t.x && j == t.y) continue;
                if (i < 0 || i >= n || j < 0 || j >= n) continue;
                if (h[i][j] != h[t.x][t.y])
                {
                    if (h[i][j] > h[t.x][t.y]) has_higher = true;
                    else has_lower = true;
                }
                else if (!st[i][j])//细节
                {
                    q[ ++ tt] = {i, j};
                    st[i][j] = true;
                }
            }
    }
}

int main()
{
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ ) 
        for (int j = 0; j < n; j ++ )
            scanf("%d", &h[i][j]);

    int peak = 0, valley = 0;
    for (int i = 0; i < n; i ++ ) 
        for (int j = 0; j < n; j ++ ) 
            if (!st[i][j])
            {
                bool has_higher = false, has_lower = false;
                bfs(i, j, has_higher, has_lower);
                if (!has_higher) peak ++ ;
                if (!has_lower) valley ++ ;
            }
    printf("%d %d\n", peak, valley);

    return 0;
}


活动打卡代码 AcWing 1106. 山峰和山谷

bfs

  • 两个返回值——引用
#include <cstring>
#include <algorithm>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010, M = N * N;

int n;
int h[N][N];
PII q[M];
bool st[N][N];

void bfs(int sx, int sy, bool &has_higher, bool &has_lower)
{
    int hh = 0, tt = -1;
    q[++ tt] = {sx, sy};
    st[sx][sy] = true;

    while (hh <= tt)
    {
        auto t = q[hh ++ ];

        for (int i = t.x - 1; i <= t.x + 1; i ++ )
            for (int j = t.y - 1; j <= t.y + 1; j ++ ) 
            {
                if (i == t.x && j == t.y) continue;
                if (i < 0 || i >= n || j < 0 || j >= n) continue;
                if (h[i][j] != h[t.x][t.y])
                {
                    if (h[i][j] > h[t.x][t.y]) has_higher = true;
                    else has_lower = true;
                }
                else if (!st[i][j])//细节
                {
                    q[ ++ tt] = {i, j};
                    st[i][j] = true;
                }
            }
    }
}

int main()
{
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ ) 
        for (int j = 0; j < n; j ++ )
            scanf("%d", &h[i][j]);

    int peak = 0, valley = 0;
    for (int i = 0; i < n; i ++ ) 
        for (int j = 0; j < n; j ++ ) 
            if (!st[i][j])
            {
                bool has_higher = false, has_lower = false;
                bfs(i, j, has_higher, has_lower);
                if (!has_higher) peak ++ ;
                if (!has_lower) valley ++ ;
            }
    printf("%d %d\n", peak, valley);

    return 0;
}



bfs

  • 输入问题
    • 二进制枚举
    • QQ图片20230207091549.jpg
    • 依次枚举每一位数看是否有墙壁,1、2、4、8表示四面方向是否有墙,1表示西,10表示北,100表示东,1000表示南
    • eg11 = 8 + 2 + 111的二进制数是1011,表示西北南都有墙,东没有墙。
#include <iostream>
#include <cstring>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 55, M = N * N;

int n, m;
int g[N][N];
bool st[N][N];
PII q[M];

int bfs(int sx, int sy)
{
    int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};

    int hh = 0, tt = -1;
    int area = 0;

    q[++ tt] = {sx, sy};
    st[sx][sy] = true;

    while (hh <= tt)
    {
        auto t = q[hh ++];
        area ++ ;

        for (int i = 0; i < 4; i ++ )
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (st[a][b]) continue;
            if (g[t.x][t.y] >> i & 1) continue;

            q[ ++ tt] = {a, b};
            st[a][b] = true;
        }
    }
    return area;
}

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

    int cnt = 0, area = 0;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if (!st[i][j])
            {
                area = max(area, bfs(i, j));
                cnt ++ ;
            }

    cout << cnt << endl;
    cout << area << endl;

    return 0;
}


活动打卡代码 AcWing 1098. 城堡问题

bfs

  • 输入问题
    • 二进制枚举
    • QQ图片20230207091549.jpg
    • 依次枚举每一位数看是否有墙壁,1、2、4、8表示四面方向是否有墙,1表示西,10表示北,100表示东,1000表示南
    • eg11 = 8 + 2 + 111的二进制数是1011,表示西北南都有墙,东没有墙。
    • 计算偏移量要按顺序——西北东南
#include <iostream>
#include <cstring>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 55, M = N * N;

int n, m;
int g[N][N];
bool st[N][N];
PII q[M];

int bfs(int sx, int sy)
{
    int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};

    int hh = 0, tt = -1;
    int area = 0;

    q[++ tt] = {sx, sy};
    st[sx][sy] = true;

    while (hh <= tt)
    {
        auto t = q[hh ++];
        area ++ ;

        for (int i = 0; i < 4; i ++ )
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (st[a][b]) continue;
            if (g[t.x][t.y] >> i & 1) continue;

            q[ ++ tt] = {a, b};
            st[a][b] = true;
        }
    }
    return area;
}

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

    int cnt = 0, area = 0;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if (!st[i][j])
            {
                area = max(area, bfs(i, j));
                cnt ++ ;
            }

    cout << cnt << endl;
    cout << area << endl;

    return 0;
}



bfs

  • bfs特点
    • 可以求最小
    • 基于迭代,不会爆栈
  • 洪水灌溉算法
    • 可以在线性时间复杂度内,找到某个点所在的连通块
  • 连通类型
    • 四连通——偏移量
    • 八连通——两重循环,特判中间格子
  • 思路:从前往后扫描,当扫描到一片水,且水还没有被标记过,那么从这个点开始做,把周围是水的区域标记】
  • 下标的存储:pair
#include <iostream>
#include <algorithm>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010;

int n, m;
char g[N][N];
bool st[N][N];
PII q[N * N];

void bfs(int sx, int sy)
{
    int hh = 0, tt = -1;
    q[ ++ tt] = {sx, sy};
    st[sx][sy] = true;

    while (hh <= tt)
    {
        auto t = q[hh ++ ];

        for (int i = t.x - 1; i <= t.x + 1; i ++ )
            for (int j = t.y - 1; j <= t.y + 1; j ++ )
            {
                if (i == t.x && j == t.y) continue;
                if (i < 0 || i >= n || j < 0 || j >= m) continue;
                if (g[i][j] == '.' || st[i][j]) continue;

                q[ ++ tt] = {i, j};
                st[i][j] = true;
            }
    }
}

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

    int cnt = 0;
    for (int i = 0; i < n; i ++ ) 
        for (int j = 0; j < m; j ++ )
            if (g[i][j] == 'W' && !st[i][j])
            {
                bfs(i, j);
                cnt ++ ;
            }

    cout << cnt << endl;
    return 0;
}


活动打卡代码 AcWing 1097. 池塘计数

bfs

  • bfs特点
    • 可以求最小
    • 基于迭代,不会爆栈
  • 洪水灌溉算法
    • 可以在线性时间复杂度内,找到某个点所在的连通块
  • 连通类型
    • 四连通——偏移量
    • 八连通——两重循环,特判中间格子
  • 思路:从前往后扫描,当扫描到一片水,且水还没有被标记过,那么从这个点开始做,把周围是水的区域标记】
  • 下标的存储:pair
#include <iostream>
#include <algorithm>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010;

int n, m;
char g[N][N];
bool st[N][N];
PII q[N * N];

void bfs(int sx, int sy)
{
    int hh = 0, tt = -1;
    q[ ++ tt] = {sx, sy};
    st[sx][sy] = true;

    while (hh <= tt)
    {
        auto t = q[hh ++ ];

        for (int i = t.x - 1; i <= t.x + 1; i ++ )
            for (int j = t.y - 1; j <= t.y + 1; j ++ )
            {
                if (i == t.x && j == t.y) continue;
                if (i < 0 || i >= n || j < 0 || j >= m) continue;
                if (g[i][j] == '.' || st[i][j]) continue;

                q[ ++ tt] = {i, j};
                st[i][j] = true;
            }
    }
}

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

    int cnt = 0;
    for (int i = 0; i < n; i ++ ) 
        for (int j = 0; j < m; j ++ )
            if (g[i][j] == 'W' && !st[i][j])
            {
                bfs(i, j);
                cnt ++ ;
            }

    cout << cnt << endl;
    return 0;
}