头像

Q.c

江西师范大学附属中学




离线:16小时前



Q.c
16小时前
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;

int n, idx = 0;
int a[N], m[N], b[N];
int t[N];

int main()
{
    scanf("%d", &n);
    memset(m, 0x3f, sizeof m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        m[a[i]] = i;
    }
    for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
    for (int i = 1; i <= n; ++i) {
        if (!idx || m[b[i]] > t[idx]) {
            if (m[b[i]] == 0x3f3f3f3f) continue;
            t[++idx] = m[b[i]];
            continue;
        }
        int l = 1, r = idx, mid;
        while (l < r) {
            mid = l + r >> 1;
            if (t[mid] < m[b[i]]) l = mid + 1;
            else r = mid;
        }
        t[l] = m[b[i]];
    }
    printf("%d\n", idx);
}



Q.c
17小时前

建议倍增

常数极小

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int N = 1010;
const double eps = 1e-5;

int n, k;
double a[N], b[N];
double c[N];

bool check(double x)
{
    double res = 0;
    for (int i = 1; i <= n; ++i) c[i] = a[i] - x * b[i];
    sort(c + 1, c + 1 + n);
    for (int i = k + 1; i <= n; ++i) res += c[i];
    return res >= 0;
}

int main()
{
    while (scanf("%d%d", &n, &k), n || k) {
        for (int i = 1; i <= n; ++i) scanf("%lf", &a[i]);
        for (int i = 1; i <= n; ++i) scanf("%lf", &b[i]);
        double l = 0, p = 1;
        while (check(l + p)) l += p, p *= 2;
        while (fabs(p) > eps) {
            if (check(l + p)) l += p;
            p /= 2;
        }
        printf("%.0lf\n", l * 100);
    }
    return 0;
}


活动打卡代码 AcWing 3493. 最大的和

Q.c
2天前
#include <cstdio>

using namespace std;

int n, k;
int a[100010];
long long s[100010];

long long max(long long a, long long b) { return a > b ? a : b; }

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    int x;
    long long t = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &x);
        if (x) t += a[i], a[i] = 0;
    }
    for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + a[i];
    long long ans = 0;
    for (int i = k, j = 0; i <= n; ++i, ++j) ans = max(s[i] - s[j] + t, ans);
    printf("%lld\n", ans);
    return 0;
}


活动打卡代码 AcWing 232. 守卫者的挑战

Q.c
4天前
#include <cstdio>

using namespace std;

const int N = 210;

int n, l, k;
double p[N];
double f[N][N][N << 1];

inline int min(int a, int b) { return a < b ? a : b; }

int main()
{
    scanf("%d%d%d", &n, &l, &k);
    for (int i = 0; i < n; ++i) scanf("%lf", &p[i]), p[i] /= 100;

    int x;
    f[0][0][min(n << 1, n + k)] = 1;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &x);
        for (int j = 0; j <= i; ++j)
            for (int size = 0; size <= (n << 1); ++size)
                if (size + x >= 0)
                    f[i + 1][j + 1][min(size + x, n << 1)] += f[i][j][size] * p[i], f[i + 1][j][size] += f[i][j][size] * (1 - p[i]);
    }

    double ans = 0;

    for (int i = l; i <= n; ++i)
        for (int j = n; j < N << 1; ++j)
            ans += f[n][i][j];

    printf("%.6lf\n", ans);

    return 0;
}


活动打卡代码 AcWing 231. 天码

Q.c
4天前
#include <cstdio>
#include <cstring>

using namespace std;

#define ll long long
const int N = 1e4 + 10;

int n;
int a[N], mu[N];
int idx, v[N], prime[N];
ll cnt[N], C[N];

void get_mu(int n);

int main()
{
    get_mu(N - 1);
    for (int i = 1; i < N; ++i) C[i] = 1ll * i * (i - 1) * (i - 2) * (i - 3) / 24;
    while (~scanf("%d", &n)) {
        memset(cnt, 0, sizeof cnt);
        int m = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%d", &a[i]);
            m = m > a[i] ? m : a[i];
            for (int j = 1; j * j <= a[i]; ++j) {
                if (a[i] % j) continue;
                ++cnt[j];
                if (j * j != a[i]) ++cnt[a[i] / j];
            }
        }
        ll ans = 0;
        for (int i = 1; i <= m; ++i)
            ans += 1ll * mu[i] * C[cnt[i]];

        printf("%lld\n", ans);
    }
    return 0;
}
void get_mu(int n)
{
    mu[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!v[i]) {
            v[i] = i;
            prime[++idx] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= idx && prime[j] * i <= n; ++j) {
            v[i * prime[j]] = prime[j];
            if (v[i] ^ prime[j])
                mu[i * prime[j]] = -1 * mu[i];
            else break;
        }
    }
}


活动打卡代码 AcWing 230. 排列计数

Q.c
6天前
#include <cstdio>

using namespace std;

const int N = 1e6 + 10;
const int mod = 1e9 + 7;

int T;
int n, m;
int jc[N], jcinv[N], d[N];

int qpow(int base, int k);

int main()
{
    jc[0] = jcinv[0] = 1;
    for (int i = 1; i < N; ++i) {
        jc[i] = 1ll * jc[i - 1] * i % mod;
        jcinv[i] = qpow(jc[i], mod - 2);
    }
    d[0] = 1, d[1] = 0;
    for (int i = 2; i < N; ++i)
        d[i] = 1ll * (d[i - 2] + d[i - 1]) % mod * (i - 1) % mod;

    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        printf("%d\n", 1ll * jc[n] * jcinv[m] % mod * jcinv[n - m] % mod * d[n - m] % mod);
    }

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


活动打卡代码 AcWing 229. 新NIM游戏

Q.c
6天前
#include <cstdio>
#include <algorithm>

using namespace std;

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

int n;
int a[1010];
int f[60];
long long ans;

int insert(int);

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    sort(a + 1, a + 1 + n, cmp());
    for (int i = 1; i <= n; ++i) {
        ans += insert(a[i]);
    }
    printf("%lld\n", ans);

    return 0;
}
int insert(int x)
{
    int tmp = x;
    for (int i = 30; i >= 0; --i)
        if ((x >> i) & 1) {
            if (f[i]) x ^= f[i];
            else {
                f[i] = x;
                return 0;
            }
        }
    return tmp;
}


活动打卡代码 AcWing 228. 异或

Q.c
6天前
#include <vector>
#include <cstdio>
#include <cstring>

using namespace std;

#define ll long long

struct PII
{
    int to; ll w;
};

int n, m;
vector<PII> v[50010];
vector<ll> a;
ll f[64];
bool vis[50010];
ll dis[50010];

void dfs(int now);

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int st, ed; ll w;
        scanf("%d%d%lld", &st, &ed, &w);
        v[st].push_back({ed, w});
        v[ed].push_back({st, w});
    }
    memset(vis, 0, sizeof vis);
    dis[1] = 0;
    dfs(1);
    memset(f, 0, sizeof f);
    for (int i = 1; i <= a.size(); ++i)
        for (int j = 60; j >= 0; --j)
            if ((a[i] >> j) & 1) {
                if (!f[j]) {
                    f[j] = a[i];
                    break;
                }
                a[i] ^= f[j];
            }
    ll ans = dis[n];
    for (int i = 60; i >= 0; --i) {
        if (!((ans >> i) & 1)) ans ^= f[i];
    }
    printf("%lld\n", ans);
    return 0;
}
void dfs(int now)
{
    vis[now] = 1;
    for (unsigned int i = 0; i < v[now].size(); ++i) {
        int to = v[now][i].to; ll w = v[now][i].w;
        if (vis[to]) a.push_back(dis[now] ^ dis[to] ^ w);
        else {
            dis[to] = dis[now] ^ w;
            dfs(to);
        }
    }
}


活动打卡代码 AcWing 227. 小部件厂

Q.c
6天前
#include <map>
#include <string>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 310;

map<string, int> mp;
int n, m;
int f[N][N];

void gauss(void);
int exgcd(int a, int b, int &x, int &y);
int main()
{
    mp["MON"] = 1, mp["TUE"] = 2, mp["WED"] = 3, mp["THU"] = 4, mp["FRI"] = 5, mp["SAT"] = 6, mp["SUN"] = 7;
    while (scanf("%d%d", &n, &m), n || m) {
        memset(f, 0, sizeof f);

        for (int i = 1; i <= m; ++i) {
            int x; string a, b;
            scanf("%d", &x);
            cin >> a >> b;
            f[i][n + 1] = (mp[b] - mp[a] + 1) % 7;
            for (int j = 1; j <= x; ++j) {
                int tmp;
                scanf("%d", &tmp);
                (++f[i][tmp]) %= 7;
            }
        }
        gauss();
    }

    return 0;
}
int exgcd(int a, int b, int &x, int &y)
{
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y);
    int z = x; x = y; y = z - y * (a / b);
    return d;
}
void gauss(void)
{
    int r, c;
    for (r = 1, c = 1; c <= n; ++c) {
        int t = r;
        for (int i = r + 1; i <= m; ++i)
            if (f[i][c] && (!f[t][c] || f[i][c] > f[t][c])) t = i;
        if (!f[t][c]) continue;
        for (int i = 1; i <= n + 1; ++i) swap(f[r][i], f[t][i]);
        for (int i = 1; i <= m; ++i) {
            if (i == r || !f[i][c]) continue;
            int tmp = f[i][c];
            for (int k = 1; k <= n + 1; ++k)
                f[i][k] = (f[i][k] * f[r][c] - f[r][k] * tmp) % 7;
        }
        ++r;
    }
    for (int i = r + 1; i <= m; ++i)
        if (f[i][n + 1] % 7) {
            puts("Inconsistent data.");
            return;
        }
    if (r < n) {
        puts("Multiple solutions.");
        return;
    }
    for (int i = 1; i <= n; ++i) {
        int x, y;
        int d = exgcd(f[i][i], 7, x, y);
        if (f[i][n + 1] % d) {
            puts("Inconsistent data.");
            return;
        }
        else if (i < n) printf("%d ", ((x * f[i][n + 1] / d - 3) % 7 + 7) % 7 + 3);
        else printf("%d\n", ((x * f[i][n + 1] / d - 3) % 7 + 7) % 7 + 3);
    }
}


活动打卡代码 AcWing 226. 233矩阵

Q.c
10天前
#include <vector>
#include <cstdio>

using namespace std;

#define ll long long
const int mod = 1e7 + 7;

inline int Add(ll a, int b) { a += b; return a >= mod ? a - mod : a; }

struct Matrix
{
#define Ma Matrix
    int r, c;
    vector<vector<int>> unit;

    Ma() {}
    Ma(int r, int c) : r(r), c(c)
    {
        unit.resize(r);
        for (int i = 0; i < r; ++i) unit[i].resize(c);
    }
    Ma(int r, int c, int num) : r(r), c(c)
    {
        unit.resize(r);
        for (int i = 0; i < r; ++i) {
            unit[i].resize(c);
            for (int j = 0; j < c; ++j) unit[i][j] = i == j ? num : 0;
        }
    }

    Ma operator*(const Ma &b) const
    {
        Ma New(r, b.c);
        for (int i = 0; i < r; ++i)
            for (int k = 0; k < c; ++k) {
                int tmp = unit[i][k];
                for (int j = 0; j < b.c; ++j) New.unit[i][j] = Add(New.unit[i][j], 1ll * tmp * b.unit[k][j] % mod);
            }
        return New;
    }
    Ma operator^(int k)
    {
        Ma base = *this; Ma res(r, r, 1);
        while (k) {
            if (k & 1) res = res * base;
            base = base * base;
            k >>= 1;
        }
        return res;
    }
#undef Ma
};

int n, m, len;
Matrix ans, base;

inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
void MakeMa(void);
void MulMa(void);
void Print(Matrix a);

int main()
{
    while (~scanf("%d%d", &n, &m)) {
        ++n, ++m;
        ans = Matrix(1, n + 1);
        base = Matrix(n + 1, n + 1, 1);

        MakeMa();
        MulMa();

        printf("%d\n", ans.unit[0][n - 1]);
    }

    return 0;
}
void MakeMa(void)
{
    ans.unit[0][0] = 23, ans.unit[0][n] = 3;
    for (int i = 1; i < n; ++i) scanf("%d", &ans.unit[0][i]);
    base.unit[n][n] = 1;
    for (int i = 0; i < n; ++i) base.unit[n][i] = 1;
    for (int i = 0; i < n; ++i) base.unit[0][i] = 10;
    for (int j = 1; j < n; ++j)
        for (int i = 1; i <= j; ++i) base.unit[i][j] = 1;
}
void MulMa(void)
{
    int k = m - 1;
    ans = ans * (base ^ k);
}
void Print(Matrix a)
{
    for (int i = 0; i < a.r; ++i)
        for (int j = 0; j < a.c; ++j) printf("%d%c", a.unit[i][j], j == a.c - 1 ? '\n' : ' ');
    return;
}