头像

Yipxx




离线:2个月前


最近来访(0)

活动打卡代码 AcWing 1855. 愤怒的奶牛

Yipxx
4个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, INF = 2e9;

int n;
int p[N];

int main()
{
    cin >> n;
    p[0] = -INF, p[n + 1] = INF;
    for (int i = 1; i <= n; i ++ ) cin >> p[i];
    sort(p + 1, p + n + 1);

    int res = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int l = 1, r = 1, a = i, b = i;
        while (p[a] - p[a - 1] <= l)
        {
            int k = a - 1;
            while (p[a] - p[k - 1] <= l) k -- ;
            a = k;
            l ++ ;
        }
        while (p[b + 1] - p[b] <= r)
        {
            int k = b + 1;
            while (p[k + 1] - p[b] <= r) k ++ ;
            b = k;
            r ++ ;
        }

        res = max(res, b - a + 1);
    }

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


活动打卡代码 AcWing 1875. 贝茜的报复

Yipxx
4个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

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

    unordered_map<char, int> cnt[2];
    while (n -- )
    {
        char c;
        int x;
        cin >> c >> x;
        cnt[abs(x) % 2][c] ++ ;
    }

    char str[] = "BESIGOM";

    int res = 0;
    unordered_map<char, int> v;
    for (int i = 0; i < 1 << 7; i ++ )
    {
        for (int j = 0; j < 7; j ++ )
            v[str[j]] = i >> j & 1;

        if ((v['B'] + v['I']) * (v['G'] + v['O'] + v['E'] + v['S']) * v['M'] % 2 == 0)
        {
            int sum = 1;
            for (int j = 0; j < 7; j ++ )
                sum *= cnt[i >> j & 1][str[j]];
            res += sum;
        }
    }

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


活动打卡代码 AcWing 1884. COW

Yipxx
5个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n;
string s;

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

    LL a = 0, b = 0, c = 0;
    for (auto ch: s)
    {
        if (ch == 'C')
            a ++ ;
        else if (ch == 'O')
            b += a;
        else
            c += b;
    }
    cout << c << endl;

    return 0;
}


活动打卡代码 AcWing 1904. 奶牛慢跑

Yipxx
5个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, INF = 2e9;

int n;
int v[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        scanf("%*d%d", &v[i]);    //%*d:跳过一个数

    int res = 0, vmin = INF;
    for (int i = n - 1; i >= 0; i -- )
    {
        if (v[i] <= vmin)
            res ++ ;
        vmin = min(vmin, v[i]);
    }
    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 1913. 公平摄影

Yipxx
5个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
const int N = 100010;

int n;
PII q[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        int x;
        char c;
        cin >> x >> c;
        if (c == 'G')
            q[i] = {x, 1};
        else
            q[i] = {x, -1};
    }
    sort(q, q + n);

    unordered_map<int, int> hash;

        int res = 0, sum = 0, last;
    for (int i = 0; i < n; i ++ )
    {
        if (!hash.count(sum)) hash[sum] = q[i].x;
        sum += q[i].y;
        if (hash.count(sum)) res = max(res, q[i].x - hash[sum]);

        if (i == 1 || q[i].y != q[i - 1].y) last = q[i].x;
        res = max(res, q[i].x - last);
    }

    printf("%d\n", res);
    return 0;
}


活动打卡代码 AcWing 1929. 镜子田地

Yipxx
5个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int dfs(int x, int y, int d)
{
    if (x < 0 || x >= n || y < 0 || y >= m)
        return 0;

    if (g[x][y] == '/')
        d ^= 1;
    else
        d ^= 3;

    return dfs(x + dx[d], y + dy[d], d) + 1;
}

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

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        res = max(res, dfs(i, 0, 1));
        res = max(res, dfs(i, m - 1, 3));
    }

    for (int i = 0; i < m; i ++ )
    {
        res = max(res, dfs(0, i, 2));
        res = max(res, dfs(n - 1, i, 0));
    }

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 1934. 贝茜放慢脚步

Yipxx
5个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 10010;

int n;
vector<int> a, b;

int main()
{
    cin >> n;

    char c;
    int x;
    while (n -- )
    {
        cin >> c >> x;
        if (c == 'T')
            a.push_back(x);
        else
            b.push_back(x);
    }

    b.push_back(1000);
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    double t = 0, s = 0, v = 1;    //v是速度的倒数
    int i = 0, j = 0;
    while (i < a.size() || j < b.size())
    {
        if (j == b.size() || i < a.size() && a[i] - t < (b[j] - s) * v)
        {
            s += (a[i] - t) / v;
            t = a[i];
            v ++ ;
            i ++ ;
        }
        else
        {
            t += (b[j] - s) * v;
            s = b[j];
            v ++ ;
            j ++ ;
        }
    }
    printf("%.0lf\n", t);

    return 0;
}


活动打卡代码 AcWing 1922. 懒惰的牛

Yipxx
5个月前
#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, k;
PII q[N];

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

    sort(q, q + n);

    int res = 0, sum = 0;
    for (int i = 0, j = 0; i < n; i ++ )
    {
        sum += q[i].y;
        while (q[i].x - q[j].x > 2 * k)
            sum -= q[j ++ ].y;
        res = max(res, sum);
    }
    cout << res << endl;

    return 0;
}



Yipxx
5个月前

写法1:map

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

using namespace std;

const int INF = 2e9;

int n, x, y, z;

int main()
{
    map<int, int> b;
    cin >> n >> x >> y >> z;
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        cin >> l >> r;
        b[-INF] += x;
        b[l] += y - x;
        b[r + 1] += z - y;
        b[INF] -= z;
    }
    int res = 0, sum = 0;
    for (auto [x, y]: b)
    {
        sum += y;
        res = max(res, sum);
    }
    cout << res << endl;

    return 0;
}

手写离散化

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

using namespace std;

const int N = 20010, INF = 2e9;

int n, x, y, z;
vector<int> xs;
int l[N], r[N], b[N * 2];

int find(int v)
{
    int l = 0, r = xs.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (xs[mid] >= v) r = mid;
        else l = mid + 1;
    }
    return r;
}

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

    xs.push_back(-INF), xs.push_back(INF);
    for (int i = 0; i < n; i ++ )
    {
        scanf("%d%d", &l[i], &r[i]);
        xs.push_back(l[i]);
        xs.push_back(r[i] + 1);
    }

    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());

    for (int i = 0; i < n; i ++ )
    {
        int L = find(l[i]), R = find(r[i] + 1);
        b[0] += x;
        b[L] += y - x;
        b[R] += z - y;
        b[xs.size() - 1] -= z;
    }

    int res = 0, sum = 0;
    for (int i = 0; i < xs.size(); i ++ )
    {
        sum += b[i];
        res = max(res, sum);
    }

    printf("%d\n", res);
    return 0;
}


活动打卡代码 AcWing 1960. 闪烁

Yipxx
5个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1 << 16;

int n;
LL m;
int p[N];    //记录每个状态是第几步走到的

int update(int state)
{
    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int j = (i - 1 + n) % n;    //找到上一位
        int x = state >> i & 1, y = state >> j & 1;
        res |= (x ^ y) << i;
    }
    return res;
}

void print(int state)
{
    for (int i = 0; i < n; i ++ )
        cout << (state >> i & 1) << endl;
}

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

    int state = 0;
    for (int i = 0; i < n; i ++ )
    {
        int x;
        cin >> x;
        state |= x << i;
    }

    memset(p, -1, sizeof p);
    p[state] = 0;

    for (int i = 1; ; i ++ )
    {
        state = update(state);
        if (i == m)
        {
            print(state);
            break;
        }
        else if (p[state] == -1)
            p[state] = i;
        else
        {
            int len = i - p[state];
            int r = (m - i) % len;
            while (r -- )
                state = update(state);
            print(state);
            break;
        }
    }
    return 0;
}