头像

凌乱之风

$\text{SDUT}\&\&\text{SDSSYZX}$




离线:26分钟前


活动打卡代码 AcWing 3729. 改变数组元素

凌乱之风
1小时前

勿膜,做过原题 QWQ

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 5;
int T, n, x, cf[N];
signed main() {
    scanf("%d", &T);
    while (T --) {
        memset(cf, 0, sizeof cf);
        scanf("%d", &n);
        for (int i = 1; i <= n; i ++) {
            scanf("%d", &x);
            if (x) {
                cf[i + 1] --, cf[max(i - x + 1, 1)] ++;
            }
        }
        for (int i = 1; i <= n; i ++) {
            cf[i] += cf[i - 1];
            if (cf[i] >= 1) {
                printf("1 ");
            } else {
                printf("0 ");
            }
        }
        puts("");
    }
}


活动打卡代码 AcWing 1086. 恨7不成妻

凌乱之风
2小时前

抄的,不写了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int C = 30, MOD = 1e9 + 7;
int t, a[C];
ll ten[C];
struct dp {
    ll cnt, sum, sq_sum;
} f[C][C][C];
void ten_mi(){
    ten[1] = 1;
    for (int i = 2; i <= 18; i ++)
        ten[i] =  ten[i-1] * 10 % MOD;
}
dp dfs(int pos, int sum, int cur, bool limit) {
    if (!pos) {
        int cnt = 0;
        if (cur !=  0 && sum != 0) cnt = 1;
        return f[pos][sum][cur] = (dp){cnt, 0, 0};
    }
    if (!limit && f[pos][sum][cur].cnt != -1) return f[pos][sum][cur];
    int up = limit? a[pos] : 9;
    dp ans{0, 0, 0};
    for (int i = 0; i <= up; i ++) {
        if (i==7)  continue;
        dp tmp = dfs(pos-1, (sum + i) % 7, (cur * 10 + i) % 7,  limit && (i == a[pos]));
        int k = i * ten[pos] % MOD;
        ans.cnt = (ans.cnt + tmp.cnt) %  MOD;
        ans.sum = ((ans.sum + ((tmp.cnt * k) % MOD   +  tmp.sum) % MOD) % MOD) % MOD ;
        ans.sq_sum  += tmp.cnt * k % MOD * k % MOD;
        ans.sq_sum += tmp.sq_sum % MOD;
        ans.sq_sum += 2 * k % MOD * (tmp.sum % MOD) % MOD ;
        ans.sq_sum %= MOD;
    }
    return  limit ? ans : f[pos][sum][cur] = ans;
}
ll solve(ll x) {
    int len = 0;
    while (x) a[++len] = x % 10, x /= 10;
    dp ans = dfs(len, 0, 0, true);
    return ans.sq_sum % MOD;
} 
int main() {
    cin >> t;
    ten_mi();
    for (int i = 0; i < t; i ++) {
        ll l, r;
        cin >> l >> r;
        memset(f, -1, sizeof f);
        int x = solve(r);
        int y = solve(l-1);
        cout << (x - y + MOD) % MOD << endl;
    }
}


活动打卡代码 AcWing 3725. 卖罐头

#include <bits/stdc++.h>
using namespace std;
int T, l, r;
signed main() {
    cin >> T;
    while (T --) {
        cin >> l >> r;
        if (2 * l > r) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
}


活动打卡代码 AcWing 3720. 数组重排

#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int T, n, x, a[N], b[N];
signed main() {
    cin >> T;
    while (T --) {
        int flag = 0;
        cin >> n >> x;
        for (int i = 1; i <= n; i ++) cin >> a[i];
        for (int i = 1; i <= n; i ++) cin >> b[i];
        sort(b + 1, b + 1 + n);
        reverse(b + 1, b + 1 + n);
        for (int i = 1; i <= n; i ++) {
            if (a[i] + b[i] > x) {
                flag = 1;
                break;
            }
        }
        if (flag) {
            cout << "No" << endl;
        } else {
            cout << "Yes" << endl;
        }
    }
}


活动打卡代码 AcWing 393. 雇佣收银员

#include <bits/stdc++.h>
using namespace std;
const int N = 30, M = 100, inf = 0x3f3f3f3f;
int T, n, h[N], ne[M], e[M], w[M], idx, dist[N], cnt[N], r[N], num[N];
bool st[N];
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
bool spfa(int c) {
    memset(h, -1, sizeof h);
    idx = 0;
    add(0, 24, c), add(24, 0, -c);
    for (int i = 1; i <= 7; i ++) add(i + 16, i, r[i] - c);
    for (int i = 8; i <= 24; i ++) add(i - 8, i, r[i]);
    for (int i = 1; i <= 24; i ++) {
        add(i, i - 1, -num[i]);
        add(i - 1, i, 0);
    }
    memset(dist, -0x3f, sizeof dist);
    memset(cnt, 0, sizeof cnt);
    memset(st, 0, sizeof st);
    queue<int> q;
    q.push(0);
    dist[0] = 0;
    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        st[t] = 0;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] < dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= 25) return 0;
                if (!st[j]) {
                    st[j] = 1;
                    q.push(j);
                }
            }
        }
    }
    return 1;
}
signed main() {
    cin >> T;
    while (T --) {
        memset(num, 0, sizeof num);
        for (int i = 1; i <= 24; i ++) cin >> r[i];
        cin >> n;
        for (int i = 0; i < n; i ++) {
            int t;
            cin >> t;
            num[t + 1] ++;
        }
        int flag = 0;
        for (int i = 0; i <= 1000; i ++) {
            if (spfa(i)) {
                cout << i << endl;
                flag = 1;
                break;
            }
        }
        if (!flag) cout << "No Solution" << endl;
    }
}


活动打卡代码 AcWing 3711. 方格涂色

#include <bits/stdc++.h>
using namespace std;
int T, n, u1, r1, d1, l1;
bool check(int u, int r, int d, int l) {
    if (u < 0 || r < 0 || d < 0 || l < 0){
        return 0;
    } else if (u > n - 2 || r > n - 2 || d > n - 2 || l > n - 2) {
        return 0;
    } else {
        return 1;
    }
}
signed main() {
    cin >> T;
    while (T --) {
        int flag = 0;
        cin >> n >> u1 >> r1 >> d1 >> l1;
        for (int i = 0; i <= 1 << 4; i ++) {
            int u = u1, r = r1, d = d1, l = l1;
            for (int j = 0; j < 4; j ++) {
                if (i >> j & 1) {
                    if (j + 1 == 1) {
                        u --, l --;
                    } else if (j + 1 == 2) {
                        u --, r --;
                    } else if (j + 1 == 3) {
                        r --, d --;
                    } else if (j + 1 == 4) {
                        l --, d --;
                    }
                }
            }
            if (check(u, r, d, l)) flag = 1;
        }
        if (flag) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
}


活动打卡代码 AcWing 1170. 排队布局

#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 1e5 + 5, inf = 0x3f3f3f3f;
int n, m1, m2, u, v, c, h[N], e[M], ne[M], w[M], idx, dist[N], cnt[N];
bool st[N];
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
bool spfa(int s) {
    memset(cnt, 0, sizeof cnt);
    memset(dist, 0x3f, sizeof dist);
    queue<int> q;
    for (int i = 1; i <= s; i ++) {
        q.push(i);
        dist[i] = 0;
    }
    while(!q.empty()) {
        auto t = q.front();
        q.pop();
        st[t] = 0;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if(cnt[j] >= n) return 1;
                if (!st[j]) {
                    q.push(j);
                    st[j] = 1;
                }
            }
        }
    }
    return 0;
}
signed main() {
    memset(h, -1 ,sizeof h);
    cin >> n >> m1 >> m2;
    for (int i = 1; i < n; i ++) add(i + 1, i, 0);
    while (m1 --) {
        cin >> u >> v >> c;
        add(u, v ,c);
    }
    while (m2 --) {
        cin >> u >> v >> c;
        add(v, u, -c);
    }
    if (spfa(n)) {
        cout << -1 << endl;
    } else {
        spfa(1);
        if (dist[n] == inf) {
            cout << -2 <<endl;
        } else {
            cout << dist[n] << endl;
        }
    }
}


活动打卡代码 AcWing 362. 区间

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int a, b, c, m, h[N], e[N], ne[N], w[N], idx, dist[N];
bool st[N];
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void spfa() {
    memset(dist, -0x3f, sizeof dist);
    dist[0] = 0;
    queue<int> q;
    q.push(0);
    while(!q.empty()) {
        auto t = q.front();
        q.pop();
        st[t] = 0;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] < dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) {
                    st[j] = 1;
                    q.push(j);
                }
            }
        }
    }
}
signed main() {
    memset(h, -1, sizeof h);
    cin >> m;
    for (int i = 1; i <= 5e4 + 5; i ++) {
        add(i - 1, i, 0);
        add(i, i - 1, -1);
    }
    while (m --) {
        cin >> a >> b >> c;
        a ++, b ++;
        add(a - 1, b ,c);
    }
    spfa();
    cout << dist[50001] << endl;
}


活动打卡代码 AcWing 1169. 糖果

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5 + 5;
int n, m, h[N], ne[N], e[N], w[N], idx, cnt[N], x, a, b;
LL dist[N], res;
bool st[N];
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
bool spfa() {
    stack<int> s;
    memset(dist, -0x3f, sizeof dist);
    dist[0] = 0;
    s.push(0);
    while (!s.empty()) {
        auto t = s.top();
        s.pop();
        st[t] = 0;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] < dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] > n) return 0;
                if (!st[j]) {
                    st[j] = 1;
                    s.push(j);
                }
            }
        }
    }
    return 1;
}
signed main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while (m --) {
        cin >> x >> a >> b;
        if (x == 1) {
            add(a, b, 0), add(b, a, 0);
        } else if (x == 2) {
            add(a, b, 1);
        } else if (x == 3) {
            add(b, a, 0);
        } else if (x == 4) {
            add(b, a, 1);
        } else {
            add(a, b, 0);
        }
    }
    for (int i = 1; i <= n; i ++) add(0, i, 1);
    if (!spfa()) {
        cout << -1 << endl;
    } else {
        for (int i = 1; i <= n; i ++) res += dist[i];
        cout << res << endl;
    }
}


新鲜事 原文

开始换码风,原因是太丑了太难调了(