头像

懋士月




离线:15小时前


最近来访(1)
用户头像
fml4d1

活动打卡代码 AcWing 797. 差分

懋士月
19小时前
#include <iostream>
using namespace std;
const int N = 100005;
int n, m;
int a[N], d[N];

void insert(int l, int r, int c) {
    d[l] += c;
    d[r + 1] -= c;
}


int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        d[i] = a[i] - a[i - 1];
    }
    for (int i = 0; i < m; i++) {
        int l, r, c;
        cin >> l >> r >> c;
        insert(l, r, c);
    }
    for (int i = 1; i <= n; i++) {
        a[i] = a[i - 1] + d[i];
        cout << a[i] << ' ';
    }
    cout << endl;
    return 0;
}


活动打卡代码 AcWing 173. 矩阵距离

懋士月
20小时前
#include <iostream>
#include <queue>
using namespace std;

typedef pair<int, int> PII;
char A[1005][1005];
int B[1005][1005];

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

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

    queue<PII> q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (A[i][j] == '1') {
                q.push({i, j});
            }
        }
    }

    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int x_ = cur.first + dx[i], y_ = cur.second + dy[i];
            if (x_ >= 0 && x_ < n && y_ >= 0 && y_ < m && B[x_][y_] == 0 && A[x_][y_] == '0') {
                B[x_][y_] = B[cur.first][cur.second] + 1;
                q.push({x_, y_});
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << B[i][j] << ' ';
        }
        cout << endl;
    }
    return 0;
} 


活动打卡代码 AcWing 1455. 招聘

懋士月
22小时前

若每次间隔一定,则为约瑟夫环问题,转移方程:f(n, k) = (f(n - 1, k) + k) mod n
f(n, k): 人数为 n,间隔为 k 时死掉的人的序号
该转移方程的意义为:从当前序号 0 的人开始,杀死第 k 个人,再从杀死的人的下一个人开始(重新标序号,使该人序号为 0),新序号与原序号相差 k

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

int a[1005];

int main(){
    int T;
    cin >> T;
    for (int i = 0; i < T; i++) {
        int n, m;
        cin >> n >> m;
        for (int j = 0; j < m; j++) {
            cin >> a[j];
        }

        int f = 0;
        for (int u = 2; u <= n; u++) {
            int k = (n - u) % m;
            f = (f + a[k]) % u;
        }
        cout << f << endl;
    }
    return 0;
}


活动打卡代码 AcWing 1453. 移掉K位数字

#include <iostream> 
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> PII;
const int N = 100005, M = 18;
PII vals[N];
string num;
int k, n;

int w[N];
int f[N][M];

void init() {
    for (int j = 0; j < M; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            if (!j) f[i][j] = w[i];
            else f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
        }
    }
}

int query(int l, int r) {
    int len = r - l + 1;
    int k = log(len) / log(2);
    return min(f[l][k], f[r - (1 << k) + 1][k]);
}

int bsearch(PII q[], int k, int p) {
    int l = 1, r = n;
    while (l < r) {
        int mid = l + r >> 1;
        if (q[mid].first >= k) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    int st = l;
    r = n;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (q[mid].first < k + 1) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    int ed = l;
    while (st < ed) {
        int mid = st + ed >> 1;
        if (q[mid].second >= p) {
            ed = mid;
        } else {
            st = mid + 1;
        }
    }   
    return q[st].second;
}

int main() {
    cin >> num;
    cin >> k;
    n = num.length();
    int remain = n - k;
    int p = 1, q = n - remain + 1;

    for (int i = 1; i <= n; i++) {
        vals[i] = {num[i - 1] - '0', i};
        w[i] = num[i - 1] - '0';
    }

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

    init();

    string res;
    for(int i = 1; i <= remain; i++) {
        int minval = query(p, q);
        p = bsearch(vals, minval, p) + 1;
        if (res.length() != 0 || minval != 0) {
            res += minval + '0';
        }
        q ++;
    }
    if (res.length() == 0) {
        res = "0";
    }
    cout << res << endl;

    return 0;
}



#include <iostream> 
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> PII;
const int N = 100005, M = 18;
PII vals[N];
string num;
int k, n;

int w[N];
int f[N][M];

void init() {
    for (int j = 0; j < M; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            if (!j) f[i][j] = w[i];
            else f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
        }
    }
}

int query(int l, int r) {
    int len = r - l + 1;
    int k = log(len) / log(2);
    return min(f[l][k], f[r - (1 << k) + 1][k]);
}

int bsearch(PII q[], int k, int p) {
    int l = 1, r = n;
    while (l < r) {
        int mid = l + r >> 1;
        if (q[mid].first >= k) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    int st = l;
    r = n;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (q[mid].first < k + 1) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    int ed = l;
    while (st < ed) {
        int mid = st + ed >> 1;
        if (q[mid].second >= p) {
            ed = mid;
        } else {
            st = mid + 1;
        }
    }   
    return q[st].second;
}

int main() {
    cin >> num;
    cin >> k;
    n = num.length();
    int remain = n - k;
    int p = 1, q = n - remain + 1;

    for (int i = 1; i <= n; i++) {
        vals[i] = {num[i - 1] - '0', i};
        w[i] = num[i - 1] - '0';
    }

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

    init();

    string res;
    for(int i = 1; i <= remain; i++) {
        int minval = query(p, q);
        p = bsearch(vals, minval, p) + 1;
        if (res.length() != 0 || minval != 0) {
            res += minval + '0';
        }
        q ++;
    }
    if (res.length() == 0) {
        res = "0";
    }
    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 165. 小猫爬山

懋士月
3个月前
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

int N, W;
int C[20];
int w[20];
int ans = INT_MAX;

bool cmp (int& a, int& b) {
    return a > b;
}

void dfs(int cid, int num) {
    if (num >= ans) {
        return;
    }
    if (cid > N) {
        ans = min(num, ans);
        return;
    }

    for(int i = 0; i < num; i++) {
        if (w[i] + C[cid] > W) {
            continue;
        }
        w[i] += C[cid];
        dfs(cid + 1, num);
        w[i] -= C[cid];
    }

    w[num] += C[cid];
    dfs(cid + 1, num + 1);
    w[num] -= C[cid];

}

int main() {
    cin >> N >> W;
    for(int i = 0; i < N; i++) {
        cin >> C[i];
    }

    sort(C, C + N, cmp);

    dfs(0, 0);

    cout << ans << endl;

    return 0;
}


活动打卡代码 AcWing 164. 可达性统计

懋士月
3个月前
#include <iostream>
#include <queue>
#include <bitset>
using namespace std;

int N, M;
int tot;
int ne[30005], ver[30005], head[30005];
int A[30005];
int deg[30005];
bitset<30005> f[300005];

void add(int x, int y) {
    ver[++tot] = y;
    ne[tot] = head[x];
    head[x] = tot;
}

void topo() {
    int id = 0;
    queue<int> Q;

    for(int i = 1; i <= N; i++) {
        if (deg[i] == 0) {
            Q.push(i);
        }
    }

    while(!Q.empty()) {
        int t = Q.front();
        Q.pop();
        A[++id] = t;
        for(int i = head[t]; i; i = ne[i]) {
            int v = ver[i];
            if (--deg[v] == 0) {
                Q.push(v);
            }
        }
    }
}

int main() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int x, y;
        cin >> x >> y;
        add(x, y);
        deg[y] ++;
    }

    topo();

    for (int i = N; i >= 1; i--) {
        int u = A[i];
        f[u][u] = 1;
        for (int j = head[u]; j; j = ne[j]) {
            f[u] |= f[ver[j]];
        }
    }

    for (int i = 1; i <= N; i++) {
        cout << f[i].count() << endl;
    }

    return 0;
}


活动打卡代码 AcWing 146. 序列

懋士月
4个月前
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

struct U {
    public:
    int i1, i2, v1, v2;
    U(int i1, int i2, int v1, int v2):i1(i1), i2(i2), v1(v1), v2(v2){}

};

bool operator<(const U& a, const U& b) {
    return a.v1 + a.v2 > b.v1 + b.v2;
}

void compute(vector<int>& a, vector<int>& b) {
    sort(a.begin(), a.end());
    priority_queue<U> q;

    int n = a.size();

    vector<int> c;

    for(int i = 0; i < n; i++) {
        q.push(U(0, i, a[0], b[i]));
    }

    for(int i = 0; i < n; i++) {
        auto u = q.top();
        c.push_back(u.v1 + u.v2);
        q.pop();
        if (i != n - 1) {
            q.push(U(u.i1 + 1, u.i2, a[u.i1 + 1], b[u.i2]));
        }
    }

    b.swap(c);
}

int main() {
    int T;
    scanf("%d", &T);
    for (int i = 0; i < T; i++) {
        int m, n;
        scanf("%d %d", &m, &n);
        vector<vector<int>> a;
        for(int j = 0; j < m; j++) {
            a.push_back(vector<int>());
            for(int k = 0; k < n; k++) {
                int num;
                scanf("%d", &num);
                a[j].push_back(num);
            }
        }

        if (m > 1) {
            for(int j = 0; j < m - 1; j++) {
                compute(a[j], a[j + 1]);
            }
        }
        else {
            sort(a[0].begin(), a[0].end());
        }

        for(int j = 0; j < n; j++) {
            printf("%d ", a[m - 1][j]);
        }
        printf("\n");

    }
    return 0;
}


活动打卡代码 AcWing 145. 超市

懋士月
4个月前
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int, int> PII;

struct cmp {
  public:
  bool operator()(const PII& a, const PII& b) {
      return a.second > b.second;
  }
};

bool cmp2(const PII& a, const PII& b) {
    if (a.first != b.first) {
        return a.first < b.first;
    } else {
        return a.second > b.second;
    }
}

int main() {
    int n;
    while (scanf("%d", &n) != -1) {
        priority_queue<PII, vector<PII>, cmp> q;
        vector<PII> a;
        for (int i = 0; i < n; i++) {
            int p, d;
            scanf("%d %d", &p, &d);
            a.push_back(PII(d, p));
        }
        sort(a.begin(), a.end(), cmp2);


        for(int i = 0; i < n; i++) {
            if(a[i].first > q.size()) {
                q.push(a[i]);
            } else if(a[i].second > q.top().second){
                q.pop();
                q.push(a[i]);
            }
        }
        int ans = 0;
        while(!q.empty()) {
            ans += q.top().second;
            q.pop();
        }
        printf("%d\n", ans);
    }
    return 0;
}


活动打卡代码 AcWing 135. 最大子序和

懋士月
4个月前
#include <cstdio>
#include <deque>
#include <algorithm> 
#include <limits.h>
using namespace std;

int m, n;
int s[300005];
deque<int> q;

int main() {

    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++) {
        int tmp = 0;
        scanf("%d", &tmp);
        s[i] = s[i - 1] + tmp;
    }

    int i = 1, j = 1, ans = INT_MIN;

    while (j <= m) {
        while(!q.empty() && q.back() < s[j]) {
            q.pop_back();
        }
        q.push_back(s[j]);
        ans = max(ans, q.front() - s[i - 1]);
        j++;
    }

    while (j <= n) {
        if (q.front() == s[i]) {
            q.pop_front();
        }
        while(!q.empty() && q.back() < s[j]) {
            q.pop_back();
        }
        q.push_back(s[j]);
        i++, j++;
        ans = max(ans, q.front() - s[i - 1]);
    }

    while (i < n) {
        if (q.front() == s[i]) {
            q.pop_front();
        }
        i++;
        ans = max(ans, q.front() - s[i - 1]);
    }
    printf("%d\n", ans);


    return 0;
}