头像

发光二极管

KickStart 退役选手 :)


访客:3364

离线:18小时前


活动打卡代码 AcWing 125. 耍杂技的牛

#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

#define w first
#define s second
typedef pair<int, int> PII;
const int N = 1e5 + 10;

PII cows[N];

int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < n; ++i)
    {
        cin >> cows[i].w >> cows[i].s;
    }

    sort(cows, cows + n, [](PII &a, PII &b) {
        return a.w + a.s < b.w + b.s;
    });

    int sum = 0, res = INT_MIN;
    for (int i = 0; i < n; ++i)
    {
        res = max(res, sum - cows[i].s);
        sum += cows[i].w;
    }

    cout << res << endl;
    return 0;
}



活动打卡代码 AcWing 1100. 抓住那头牛

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;
int dst[2 * N], n, k;
int q[2 * N];

int bfs()
{
    memset(dst, -1, sizeof dst);
    int hh = 0, tt = 0;
    q[0] = n;
    dst[n] = 0;

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

        if (t == k) return dst[t];

        if (t + 1 < N && dst[t + 1] == -1)
        {
            q[ ++ tt] = t + 1;
            dst[t + 1] = dst[t] + 1;
        }

        if (t - 1 >= 0 && dst[t - 1] == -1)
        {
            q[ ++ tt] = t - 1;
            dst[t - 1] = dst[t] + 1;
        }

        if (2 * t < N && dst[2 * t] == -1)
        {
            q[ ++ tt] = 2 * t;
            dst[2 * t] = dst[t] + 1;
        }
    }
    return -1;
}

int main()
{
    cin >> n >> k;
    cout << bfs() << endl;
    return 0;
}



活动打卡代码 AcWing 188. 武士风度的牛

#include <iostream>
#include <cstring>
using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second

const int N = 155;
char g[N][N];
int n, m;
PII q[N * N];
int dst[N][N];

int bfs()
{
    int sx, sy;
    int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
    int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (g[i][j] == 'K') 
                sx = i, sy = j;

    memset(dst, -1, sizeof dst);
    int hh = 0, tt = 0;
    q[0] = {sx, sy};
    dst[sx][sy] = 0;

    while (hh <= tt)
    {
        PII t = q[ hh ++ ];
        for (int i = 0; i < 8; ++i)
        {
            int x = t.x + dx[i], y = t.y + dy[i];
            if (x < 0 || x >= n || y < 0 || y >= m) continue;
            if (g[x][y] == '*') continue;
            if (dst[x][y] != -1) continue;
            if (g[x][y] == 'H') return dst[t.x][t.y] + 1;
            q[ ++ tt] = {x, y};
            dst[x][y] = dst[t.x][t.y] + 1;
        }
    }
    return -1;
}

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

    cout << bfs() << endl;
    return 0;
}


活动打卡代码 AcWing 1076. 迷宫问题

#include <iostream>
using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second
const int N = 1010;
int g[N][N], n;
PII q[N * N];
bool st[N][N];
PII pre[N][N];

void bfs()
{
    st[n - 1][n - 1] = true;
    q[0] = {n - 1, n - 1};
    int hh = 0, tt = 0;
    int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    while (hh <= tt)
    {
        PII t = q[hh ++ ];
        for (int i = 0; i < 4; ++i)
        {
            int x = t.x + dirs[i][0], y = t.y + dirs[i][1];
            if (x < 0 || x >= n || y < 0 || y >= n || st[x][y]) continue;
            if (g[x][y] == 1) continue;
            pre[x][y] = t;
            st[x][y] = true;
            q[ ++ tt] = {x, y};
        }
    }

}

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

    bfs();

    PII start(0, 0);
    while (true)
    {
        cout << start.x << " " << start.y << endl;
        if (start.x == n - 1 && start.y == n - 1) break;
        start = pre[start.x][start.y];
    }
    return 0;
}



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

#include <iostream>
using namespace std;

#define x first
#define y second
typedef pair<int, int> PII;
const int N = 1010;

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

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

    while (hh <= tt)
    {
        auto t = q[hh ++ ];
        for (int i = -1; i <= 1; ++i)
            for (int j = -1; j <= 1; ++j)
            {
                int x = t.x + i, y = t.y + j;
                if (x < 0 || x >= n || y < 0 || y >= n) continue;

                if (g[x][y] == g[sx][sy])
                {
                    if (!st[x][y])
                        q[ ++ tt] = {x, y};
                    st[x][y] = true;
                }
                else if (g[x][y] > g[sx][sy]) has_higher = true;
                else has_lower = true;
            }
    }
}

int main()
{
    cin >> n;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> g[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 ;
            }
        }
    }
    cout << peak << " " << valley << endl;
    return 0;
}




时间复杂度$O(N\log{N})$

C++ 代码

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

#define x first
#define y second

const int N = 5e3 + 10;
pair<int, int> arr[N];
int f[N];
int n;

int main()
{
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i].x >> arr[i].y;
    }

    sort(arr, arr + n);

    int len = 0;
    f[0] = INT_MIN;
    for (int i = 0; i < n; ++i)
    {
        if (arr[i].y >= f[len]) f[++len] = arr[i].y;
        else
        {
            int l = 1, r = len;
            while (l < r)
            {
                int mid = l + r >> 1;
                if (f[mid] >= arr[i].y) r = mid;
                else l = mid + 1;
            }
            f[l] = arr[i].y;
        }
    }
    cout << len << endl;
    return 0;
}


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

#include <iostream>
using namespace std;

#define x first
#define y second
typedef pair<int, int> PII;

const int N = 55;
int g[N][N];
bool st[N][N];
int n, m;
int dirs[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};

int bfs(int sx, int sy)
{
    PII q[N * N];
    int hh = 0, tt = 0, area = 0;
    q[0] = {sx, sy};
    st[sx][sy] = true;

    while (hh <= tt)
    {
        PII p = q[hh ++ ];
        ++area;
        for (int i = 0; i < 4; ++i)
        {
            int x = p.x + dirs[i][0], y = p.y + dirs[i][1];
            if (x < 0 || x >= n || y < 0 || y >= m) continue;
            if (st[x][y]) continue;
            if (g[p.x][p.y] >> i & 1) continue;
            q[ ++ tt] = {x, y};
            st[x][y] = 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])
            {
                ++cnt;
                area = max(area, bfs(i, j));
            }

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


活动打卡代码 AcWing 338. 计数问题

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long LL;

// pos, digit, flag, zero
LL cnt[15][15][2][2];

LL dp(vector<int>& nums, int sum, int pos, int digit, bool issmall, bool zero)
{
    if (pos == nums.size()) return sum;
    if (cnt[pos][sum][issmall][zero] != -1) return cnt[pos][sum][issmall][zero];

    int upper = issmall ? 9 : nums[pos];

    LL res = 0;
    for (int i = 0; i <= upper; ++i)
    {
        res += dp(nums, sum + (digit == i && (!zero || i)), pos + 1, 
                            digit, issmall || (i < upper), zero && (i == 0));
    }

    return cnt[pos][sum][issmall][zero] = res;
}


vector<LL> solve(int n)
{
    vector<int> nums;

    if (n == 0) nums.push_back(0);

    int t = n;
    while (t)
    {
        nums.push_back(t % 10);
        t /= 10;
    }

    reverse(nums.begin(), nums.end());

    vector<LL> ans(10, 0);

    for (int i = 0; i < 10; ++i)
    {
        memset(cnt, -1, sizeof cnt);
        ans[i] = dp(nums, 0, 0, i, false, true);
    }
    return ans;
}

int main()
{
    int a, b;
    while (scanf("%d%d", &a, &b) != EOF && a != 0 && b != 0)
    {
        if (a < b) swap(a, b);
        auto cnt1 = solve(a), cnt2 = solve(b - 1);
        for (int i = 0; i <= 9; ++i)
        {
            cout << cnt1[i] - cnt2[i] << " ";
        }
        cout << endl;
    }
    return 0;
}


活动打卡代码 AcWing 840. 模拟散列表

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

const int N = 1e5 + 3;
int h[N], e[N], ne[N], idx;

bool find(int x)
{
    int k = (x % N + N) % N;
    for (int i = h[k]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == x)
            return true;
    }
    return false;
}

void insert(int x)
{
    int k = (x % N + N) % N;
    e[idx] = x, ne[idx] = h[k], h[k] = idx ++;
}

int main()
{
    int n;
    cin >> n;
    memset(h, -1, sizeof h);
    while (n -- )
    {
        string op;
        int x;
        cin >> op >> x;
        if (op == "I")
        {
            insert(x);
        }
        else
        {
            if (find(x))
            {
                cout << "Yes" << endl;
            }
            else cout << "No" << endl;
        }
    }
    return 0;
}



活动打卡代码 AcWing 839. 模拟堆

#include <iostream>
#include <string>
using namespace std;

const int N = 1e5 + 10;
int h[N], ph[N], hp[N], Size;

void heap_swap(int a, int b)
{
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void up(int u)
{
    while (u / 2 && h[u / 2] > h[u])
    {
        heap_swap(u, u / 2);
        u /= 2;
    }
}

void down(int u)
{
    int t = u;
    if (u * 2 <= Size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= Size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

int main()
{
    int n, m = 0;
    cin >> n;
    while (n -- )
    {
        string op;
        int k, x;
        cin >> op;
        if (op == "I")
        {
            cin >> x;
            ++m, ++Size;
            h[Size] = x;
            ph[m] = Size;
            hp[Size] = m;
            up(Size);
        }
        else if (op == "PM")
        {
            cout << h[1] << endl;
        }
        else if (op == "DM")
        {
            heap_swap(1, Size--);
            down(1);
        }
        else if (op == "D")
        {
            cin >> k;
            k = ph[k];
            heap_swap(k, Size--);
            down(k), up(k);
        }
        else
        {
            cin >> k >> x;
            k = ph[k];
            h[k] = x;
            down(k), up(k);
        }
    }
    return 0;
}