【一本通 贪心】塔

单调队列优化版。优于题目所需复杂度。

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
#define int long long
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

const int N = 1e5 + 5;
int a[N], sum[N], f[N], g[N];

deque<int> Q;
signed main() {
#ifdef LOCAL
    file();
#endif
    int n = rd();
    for(int i = 1; i <= n; i++) a[i] = rd();
    for(int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + a[i];
    }

    int lst = 0;
    for(int i = 1; i <= n; i++) {
        while(!Q.empty() && sum[i] >= g[Q.front()] + sum[Q.front()]) lst = Q.front(), Q.pop_front();
        f[i] = f[lst] + i - lst - 1;
        g[i] = sum[i] - sum[lst];
        while(!Q.empty() && g[Q.back()] + sum[Q.back()] >= g[i] + sum[i]) Q.pop_back();
        Q.push_back(i);
    }

    cout << f[n] << endl;
    return 0;
}

SGU 495 Kids and Prizes

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}
const int N = 1e6 + 6;
double f[N];

signed main() {
#ifdef LOCAL
    file();
#endif
    int n = rd(), m = rd();
    for(int i = 1; i <= m; i++) {
        f[i] = f[i - 1] + 1 - f[i - 1] / n;
    }
    printf("%.9lf\n", f[m]);
    return 0;
}

UVA11021 Tribles

每只麻球的死亡是独立事件。设一只麻球在 i 天后死光的概率为 f_i。

那么有， f_i = p_0 + p_1\times (f_{i-1}) + p_2 \times (f_{i-1})^2 + ... + p_{n}\times (f_{i-1})^n

最后的答案即为 f_m^k

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

double qpow(double a, int b) {
    double res = 1, base = a;
    while(b) {
        if(b & 1) res = res * base;
        base = base * base; b >>= 1;
    }
    return res;
}

const int N = 1e3 + 5;
double a[N], f[N];
void solve(int T) {
    ms(a); ms(f);
    int n = rd(), k = rd(), m = rd();
    for(int i = 0; i < n; i++) scanf("%lf", a + i);
    f[0] = 0;
    for(int i = 1; i <= n; i++) {
        double t = 1;
        for(int j = 0; j < n; j++) {
            f[i] += a[j] * t;
            t *= f[i - 1];
        }
    }
    printf("Case #%d: %.7lf\n", T, qpow(f[m], k));
}

signed main() {
#ifdef LOCAL
    file();
#endif
    int T = rd();
    for(int i = 1; i <= T; i++) solve(i);
    return 0;
}

CF1462A - Favorite Sequence

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ "] on line " << __LINE__ << endl
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

vector<int> a, b;

void solve() {
    int n = rd();
    a.resize(n + 1);
    for(int i = 1; i <= n; i++) {
        a[i] = rd();
    }
    b.resize(n + 1);
    int cnt = 0;
    for(int i = 1; true; i++) {
        b[++cnt] = a[i];
        if(cnt == n) break;
        if(i != n - i + 1) {
            b[++cnt] = a[n - i + 1];
        }
        if(cnt == n) break;
    }

    for(int i = 1; i <= n; i++) {
        printf("%d ", b[i]);
    }

    puts("");
}

signed main() {
#ifdef LOCAL
    file();
#endif
    int T = rd();
    while(T--) solve();
    return 0;
}

CF1462B - Last Year's Substring

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ "] on line " << __LINE__ << endl
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

int judge(int l, int r, string tt, string &ori) {
    int cnt = 0;
    while(l <= r) {
        if(tt[cnt++] != ori[l]) return false;
        ++l;
    }
    return cnt;
}

void solve() {
    int n; cin >> n; --n;
    string str;
    cin >> str;
    if(str == "2020") return puts("YES"), void();
    if((judge(0, 0, "2", str) && judge(n - 2, n, "020", str)) ||
            (judge(n - 3, n, "2020", str)) ||
            (judge(0, 1, "20", str) && judge(n - 1, n, "20", str)) ||
            (judge(0, 2, "202", str) && judge(n, n, "0", str)) ||
            (judge(0, 3, "2020", str))) puts("YES");
    else puts("NO");
}

signed main() {
#ifdef LOCAL
    file();
#endif
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while(T--) solve();
    return 0;
}

CF1462C - Unique Number

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ "] on line " << __LINE__ << endl
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

void solve() {
    int n = rd();
    if(n > 45) return puts("-1"), void();
    int ans = 0, cnt = 1;
    for(int u = 9; u; u--) {
        if(n > u) {
            n -= u; 
            ans += cnt * u;
            cnt *= 10;
        }
        else {
            ans += cnt * n;
            break;
        }
    }
    printf("%d\n", ans);
}

signed main() {
#ifdef LOCAL
    file();
#endif
    int T = rd();
    while(T--) solve();
    return 0;
}

CF1462D - Add to Neighbour and Remove

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ "] on line " << __LINE__ << endl
using namespace std;
#define int long long

int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

vector<int> a, sum;
int n;

int judge(int x) {
    int lst = 0, cnt = 0;
    for(int i = 1; i <= n; i++) {
        lst += a[i];
        if(lst > x) return 0x3f3f3f3f;
        else if(lst == x) lst = 0;
        else if(lst != 0) ++cnt;
    }
    return cnt;
}

void solve() {
    n = rd(); a.resize(n + 1);
    sum.resize(n + 1); sum[0] = 0;
    for(int i = 1; i <= n; i++) {
        a[i] = rd();
    }

    for(int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + a[i];
    }

    int ans = 0x3f3f3f3f;
    for(int i = 1; i <= sqrt(sum[n]) + 1; i++) {
        if(sum[n] % i == 0) {
            ans = min(ans, judge(i));
            if(i * i != sum[n]) {
                ans = min(ans, judge(sum[n] / i));
            }
        }
    }
    if(ans == 0x3f3f3f3f) printf("%lld", n - 1);
    else printf("%lld\n", ans);
}

signed main() {
#ifdef LOCAL
    file();
#endif
    int T = rd();
    while(T--) solve();
    return 0;
}

CF1462E1 - Close Tuples (easy version)

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ "] on line " << __LINE__ << endl
using namespace std;
#define int long long
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

vector<int> a, num;

void solve() {
    int n = rd(); a.resize(n + 1); num.resize(n + 1);
    std::fill(a.begin(), a.end(), 0);
    std::fill(num.begin(), num.end(), 0);
    for(int i = 1; i <= n; i++) a[i] = rd();
    for(int i = 1; i <= n; i++) num[a[i]]++;
    int ans = 0;
    for(int i = n; i; i--) {
        int tot = 0;
        if(i - 1 >= 1) tot += num[i - 1]; 
        if(i - 2 >= 1) tot += num[i - 2];
        ans += num[i] * (num[i] - 1) * tot / 2;
        ans += num[i] * (num[i] - 1) * (num[i] - 2) / 6;
        ans += num[i] * tot * (tot - 1) / 2;
    }
    printf("%lld\n", ans);
}

signed main() {
#ifdef LOCAL
    file();
#endif
    int T = rd();
    while(T--) solve();
    return 0;
}

CF1462E2 - Close Tuples (hard version)

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ "] on line " << __LINE__ << endl
#define int long long
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

const int N = 2e5 + 5, mod = 1e9 + 7;
int fac[N];

void init() {
    fac[0] = 1;
    for(int i = 1; i < N; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
}

int qpow(int a, int b) {
    int res = 1, base = a;
    while(b) {
        if(b & 1) res = res * base % mod;
        base = base * base % mod; b >>= 1;
    }
    return res;
}

int inv(int x) {
    return qpow(x, mod - 2);
}

int C(int a, int b) {
    assert(a >= 0); assert(b >= 0); assert(b >= a);
    return fac[b] * inv(fac[a] * fac[b - a] % mod) % mod;
}

vector<int> a, num, sum;
void solve() {
    int n = rd(), m = rd(), k = rd();
    a.resize(n + 1); num.resize(n + 1); sum.resize(n + 1);
    std::fill(a.begin(), a.end(), 0);
    std::fill(num.begin(), num.end(), 0);
    std::fill(sum.begin(), sum.end(), 0);
    for(int i = 1; i <= n; i++) a[i] = rd();
    for(int i = 1; i <= n; i++) num[a[i]]++;
    for(int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + num[i];
    }

    int ans = 0;
    for(int i = n; i; i--) {
        int tot = sum[i - 1] - sum[max(1LL, i - k) - 1];
//      d(i - 1); d(max(1LL, i - k));
        for(int j = 1; j <= min(num[i], m); j++) {
    //      d(j); d(num[i]); d(m - j); d(tot);
            if(m - j <= tot) {
                ans += C(j, num[i]) * C(m - j, tot);
                ans %= mod;
            }
        }
    }

    printf("%lld\n", ans);
}

signed main() {
#ifdef LOCAL
    file();
#endif  
    init();
//  cout << C(0, 4) << endl;
    int T = rd();
    while(T--) solve();
    return 0;
}
最后修改：2021 年 01 月 18 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏