头像

Yipxx




离线:14小时前


最近来访(0)


Yipxx
2天前

左闭右开区间

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

using namespace std;

const int N = 1010;

int n;
int a[N];

int checkl(int l, int r, int k, int j)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (a[mid] - a[j] >= k)
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}

int checkr(int l, int r, int k, int j)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (a[mid] - a[j] <= 2 * k)
            l = mid + 1;
        else
            r = mid;
    }
    return l;
}

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

    sort(a, a + n);
    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        for (int j = i + 1; j < n; j ++ )
        {
            int k = a[j] - a[i];
            int l = checkl(j, n, k, j);
            int r = checkr(j, n, k, j);
            if (l < r)
                res += r - l;
        }
    }
    cout << res << endl;

    return 0;
}

左闭右闭区间

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

using namespace std;

const int N = 1010;

int n;
int a[N];

int checkl(int l, int r, int k, int j)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (a[mid] - a[j] >= k)
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}

int checkr(int l, int r, int k, int j)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (a[mid] - a[j] <= 2 * k)
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}

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

    sort(a, a + n);
    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        for (int j = i + 1; j < n; j ++ )
        {
            int k = a[j] - a[i];
            int l = checkl(j + 1, n - 1, k, j);
            int r = checkr(j + 1, n - 1, k, j);
            if (a[l] - a[j] < k || a[r] - a[j] > 2 * k)
                continue;
            if (l <= r)
                res += r - l + 1;
        }
    }
    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 1945. 奶牛棒球

Yipxx
2天前

左闭右开区间

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

using namespace std;

const int N = 1010;

int n;
int a[N];

int checkl(int l, int r, int k, int j)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (a[mid] - a[j] >= k)
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}

int checkr(int l, int r, int k, int j)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (a[mid] - a[j] <= 2 * k)
            l = mid + 1;
        else
            r = mid;
    }
    return l;
}

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

    sort(a, a + n);
    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        for (int j = i + 1; j < n; j ++ )
        {
            int k = a[j] - a[i];
            int l = checkl(j, n, k, j);
            int r = checkr(j, n, k, j);
            if (l < r)
                res += r - l;
        }
    }
    cout << res << endl;

    return 0;
}

左闭右闭区间

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

using namespace std;

const int N = 1010;

int n;
int a[N];

int checkl(int l, int r, int k, int j)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (a[mid] - a[j] >= k)
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}

int checkr(int l, int r, int k, int j)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (a[mid] - a[j] <= 2 * k)
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}

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

    sort(a, a + n);
    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        for (int j = i + 1; j < n; j ++ )
        {
            int k = a[j] - a[i];
            int l = checkl(j + 1, n - 1, k, j);
            int r = checkr(j + 1, n - 1, k, j);
            if (a[l] - a[j] < k || a[r] - a[j] > 2 * k)
                continue;
            if (l <= r)
                res += r - l + 1;
        }
    }
    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 1978. 奶牛过马路

Yipxx
3天前
#include <iostream>
#include <cstring>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 100010, INF = 1e9;

int n;
PII q[N];
int smax[N], smin[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        int x, y;
        cin >> x >> y;
        q[i] = {x, y};
    }
    sort(q + 1, q + n + 1);

    smax[0] = -INF, smin[n + 1] = INF;
    //前缀最大值
    for (int i = 1; i <= n; i ++ )
        smax[i] = max(smax[i - 1], q[i].y);
    //后缀最小值
    for (int i = n; i >= 1; i -- )
        smin[i] = min(smin[i + 1], q[i].y);

    int res = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if (smax[i - 1] < q[i].y && smin[i + 1] > q[i].y)
            res ++;
    }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 1987. 粉刷栅栏

Yipxx
3天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

const int N = 100010;

int n;

int main()
{
    map<int, int> b;
    cin >> n;
    int x = 0;
    while (n -- )
    {
        int y;
        char c;
        cin >> y >> c;
        if (c == 'R')
        {
            b[x] ++ ;
            b[x + y] -- ;
            x += y;
        }
        else
        {
            b[x - y] ++ ;
            b[x] -- ;
            x -= y;
        }
    }
    int res = 0, sum = 0, last;
    for (auto [x, v]: b)
    {
        if (sum >= 2)
            res += x - last;
        sum += v;
        last = x;
    }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 1996. 打乱字母

Yipxx
3天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 50010;

int n; 
string a[N], b[N], c[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        b[i] = c[i] = a[i];
        sort(b[i].begin(), b[i].end(), greater<char>());
        sort(c[i].begin(), c[i].end());
    }

    sort(b + 1, b + n + 1);
    sort(c + 1, c + n + 1);

    for (int i = 1; i <= n; i ++ )
    {
        sort(a[i].begin(), a[i].end());
        int l = 1, r = n;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (b[mid] >= a[i])
                r = mid;
            else
                l = mid + 1;
        }
        cout << r << ' ';
        reverse(a[i].begin(), a[i].end());
        l = 1, r = n;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (c[mid] <= a[i])
                l = mid;
            else
                r = mid - 1;
        }
        cout << r << endl;
    }
    return 0;
}


活动打卡代码 AcWing 2005. 马蹄铁

Yipxx
4天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 6;

int n;
char g[N][N];
bool st[N][N];
int ans;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void dfs(int x, int y, int l, int r)
{
    st[x][y] = true;

    if (l == r)
    {
        ans = max(ans, l + r);
        st[x][y] = false;
        return;
    }

    for (int i = 0; i < 4; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < n && b >= 0 && b < n && !st[a][b])
        {
            if (g[x][y] == ')' && g[a][b] == '(')
                continue;
            if (g[a][b] == '(')
                dfs(a, b, l + 1, r);
            else
                dfs(a, b, l, r + 1);
        }
    }
    st[x][y] = false;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        cin >>g[i];
    if (g[0][0] == '(')
        dfs(0, 0, 1, 0);
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 2014. 岛

Yipxx
4天前
#include <iostream>
#include <cstring>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n;
int h[N];
PII q[N];

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

    n = unique(h + 1, h + n + 1) - h - 1;    //判重,将相邻的相同的数删掉
    h[n + 1] = 0;    // 后续代码可能会用到第n + 1个位置,需要把第n + 1个位置清空

    for (int i = 1; i <= n; i ++ )
        q[i] = {h[i], i};

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

    int res = 1, cnt = 1;
    for (int i = 1; i <= n; i ++ )
    {
        int k = q[i].y;
        if (h[k - 1] < h[k] && h[k + 1] < h[k])
            cnt -- ;
        else if (h[k - 1] > h[k] && h[k + 1] > h[k])
            cnt ++ ;
        if (q[i].x != q[i + 1].x)
            res = max(res, cnt);
    }
    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 2019. 拖拉机

Yipxx
5天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010;

bool g[N][N];
int dist[N][N];
bool st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int bfs(int sx, int sy)
{
    deque<PII> q;
    q.push_back({sx, sy});
    memset(dist, 0x3f, sizeof(dist));
    dist[sx][sy] = 0;

    while (q.size())
    {
        auto t = q.front();
        q.pop_front();

        if (st[t.x][t.y])
            continue;
        st[t.x][t.y] = true;

        if (!t.x && !t.y)
            break;

        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 < N)
            {
                int w = 0;
                if (g[a][b])
                    w = 1;
                if (dist[a][b] > dist[t.x][t.y] + w)
                {
                    dist[a][b] = dist[t.x][t.y] + w;
                    if (!w)
                        q.push_front({a, b});
                    else
                        q.push_back({a, b});
                }
            }
        }
    }
    return dist[0][0];
}

int main()
{
    int n, sx, sy;
    cin >> n >> sx >> sy;
    while (n -- )
    {
        int x, y;
        cin >> x >> y;
        g[x][y] = true;
    }

    cout << bfs(sx, sy) << endl;

    return 0;
}


活动打卡代码 AcWing 2060. 奶牛选美

Yipxx
5天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 55;

typedef pair<int, int> PII;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n, m; 
char g[N][N];
vector<PII> points[2];

void dfs(int x, int y, vector<PII>& ps)
{
    g[x][y] = '.';
    ps.push_back({x, y});
    for (int i = 0; i < 4; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == 'X')
            dfs(a, b, ps);
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
        cin >> g[i];
    for (int i = 0, k = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            if (g[i][j] == 'X')
                dfs(i, j, points[k ++]);
        }
    }
    int res = 1e9;
    for (auto x: points[0])
    {
        for (auto y: points[1])
            res = min(res, abs(x.first - y.first) + abs(x.second - y.second) - 1);
    }
    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 2041. 干草堆

Yipxx
5天前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1000010;

int n, k;
int a[N], b[N];

int main()
{
    cin >> n >> k;
    while (k --)
    {
        int l, r;
        cin >> l >> r;
        b[l] ++;
        b[r + 1] --;
    }
    for (int i = 1; i <= n; i ++ )
        a[i] = a[i - 1] + b[i];

    nth_element(a + 1, a + 1 + n / 2, a + 1 + n);

    cout << a[n / 2 + 1] << endl;

    return 0;
}