头像

song666

114514


访客:11070

离线:17小时前


活动打卡代码 AcWing 294. 计算重复

song666
1天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#define maxn 110
#define maxm 31
#define ll long long

using namespace std;

int n1, n2;
string s1, s2;
ll f[maxn][maxm];

int main()
{
    while (cin >> s2 >> n2 >> s1 >> n1)
    {
        bool flag = true;
        int siz = s1.size();
        for (int i = 0; i < siz; i ++ )
        {
            int p = i, cnt = 0;
            f[i][0] = 0;
            for (int j = 0; j < s2.size(); j ++ )
            {
                cnt = 0;
                while (s1[p] != s2[j])
                {
                    p = (p + 1) % siz;
                    cnt ++ ;
                    if (cnt >= siz) { flag = false; break; }
                }
                if (!flag) break;
                p = (p + 1) % siz;
                f[i][0] += cnt + 1;
            }

            if (!flag) break;
        }

        if (!flag) { puts("0"); continue; }//

        for (int j = 1; j < maxm; j ++ )
            for (int i = 0; i < siz; i ++ ) 
                f[i][j] = f[i][j - 1] + f[(i + f[i][j - 1]) % siz][j - 1];

        ll ans = 0;
        for (int i = 0; i < siz; i ++ )
        {
            int p = i;
            ll t = 0;
            for (int k = maxm - 1; ~k; k -- )
                if (p + f[p % siz][k] <= n1 * siz)
                {
                    p += f[p % siz][k];
                    t += (1 << k);
                }

            ans = max(ans, t);
        }

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

    return 0;
}


活动打卡代码 AcWing 293. 开车旅行

song666
1天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#define maxn 100010
#define maxm 20
#define ll long long
#define pli pair<ll, int>

using namespace std;
const ll inf = 1e12;

int n, m;
int h[maxn];
int ga[maxn], gb[maxn];
int f[maxm][maxn][2];
ll da[maxm][maxn][2], db[maxm][maxn][2];

int getdist(int a, int b) { return abs(h[a] - h[b]); }

void initg()
{
    set< pli > S;
    S.insert({inf, 0}), S.insert({inf + 1, 0});
    S.insert({-inf, 0}), S.insert({-inf - 1, 0});
    for (int i = n; i; i -- )
    {
        pli t = {h[i], i};
        auto it = S.lower_bound(t);
        it ++ ;
        vector< pli > s;
        for (int j = 0; j < 4; j ++ )
        {
            s.push_back(*it);
            it -- ;
        }

        ll d1 = inf, d2 = inf;
        int p1 = 0, p2 = 0;
        for (int k = 3; k >= 0; k -- )
        {
            ll d = abs(h[i] - s[k].first);
            if (d1 > d)
            {
                d2 = d1, d1 = d;
                p2 = p1, p1 = s[k].second;
            }
            else if (d2 > d) d2 = d, p2 = s[k].second;
        }

        ga[i] = p2, gb[i] = p1;
        S.insert(t);
    }
}

void initf()
{
    for (int i = 1; i <= n; i ++ ) f[0][i][0] = ga[i], f[0][i][1] = gb[i];
    for (int i = 1; i < maxm; i ++ )
        for (int j = 1; j <= n; j ++ )
            for (int k = 0; k < 2; k ++ )
            {
                if (i == 1) f[1][j][k] = f[0][f[0][j][k]][1 - k];
                else f[i][j][k] = f[i - 1][f[i - 1][j][k]][k];
            }
}

void initd()
{
    for (int i = 1; i <= n; i ++ ) da[0][i][0] = getdist(i, ga[i]), da[0][i][1] = 0, db[0][i][0] = 0, db[0][i][1] = getdist(i, gb[i]);
    for (int i = 1; i < maxm; i ++ )
        for (int j = 1; j <= n; j ++ )
            for (int k = 0; k < 2; k ++ )
            {
                if (i == 1) da[1][j][k] = da[0][j][k] + da[0][f[0][j][k]][1 - k], db[1][j][k] = db[0][j][k] + db[0][f[0][j][k]][1 - k];
                else da[i][j][k] = da[i - 1][j][k] + da[i - 1][f[i - 1][j][k]][k], db[i][j][k] = db[i - 1][j][k] + db[i - 1][f[i - 1][j][k]][k];
            }
}

void calc(int p, int x, int &la, int &lb)
{
    la = lb = 0;
    for (int i = maxm - 1; i >= 0; i -- )
        if (f[i][p][0] && la + lb + da[i][p][0] + db[i][p][0] <= x)
            la += da[i][p][0], lb += db[i][p][0], p = f[i][p][0];
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);

    initg(), initf(), initd();

    int x0; scanf("%d", &x0);
    double minr = inf;
    int res = 0, maxh = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int la, lb;
        calc(i, x0, la, lb);
        double r = (lb != 0) ? (double)la / lb : inf;
        if (minr > r || (minr == r && maxh < h[i])) minr = r, maxh = h[i], res = i;
    }

    printf("%d\n", res);

    scanf("%d", &m);
    while (m -- )
    {
        int s, x, la, lb;
        scanf("%d%d", &s, &x);
        calc(s, x, la, lb);
        printf("%d %d\n", la, lb);
    }

    return 0;
}



song666
1天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#define maxn 15
#define maxm 2100

using namespace std;

int n, m;
bool state[maxm];
long long f[maxn][maxm];

bool Dream()
{
    memset(f, 0, sizeof f);
    memset(state, 0, sizeof state);
    scanf("%d%d", &n, &m);
    if (!n) return 0;

    for (int i = 0; i < 1 << m; i ++ )
    {
        bool flag = true;
        int cnt = 0;
        for (int j = 0; j < m; j ++ )
            if (i >> j & 1)
            {
                if (cnt & 1) { flag = false; break; }
                cnt = 0;
            }
            else cnt ++ ;
        if (cnt & 1) flag = false;

        state[i] = flag;
    }

    f[0][0] = 1;
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j < 1 << m; j ++ )
            for (int k = 0; k < 1 << m; k ++ )
            {
                if ((j & k) || !state[j | k]) continue;
                f[i][j] += f[i - 1][k];
            }

    printf("%lld\n", f[n][0]);

    return 1;
}

int main()
{
    while (Dream());
    return 0;
}


活动打卡代码 AcWing 288. 休息时间

song666
1天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#define maxn 3840

using namespace std;

int n, B;
int w[maxn];
int f[2][maxn][2];

int main()
{
    scanf("%d%d", &n, &B);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    memset(f, -0x3f, sizeof f);
    f[1][0][0] = f[1][1][1] = 0;
    for (int i = 2; i <= n; i ++ )
        for (int j = 0; j <= B; j ++ )
        {
            f[i & 1][j][0] = max(f[i - 1 & 1][j][0], f[i - 1 & 1][j][1]);
            if (j) f[i & 1][j][1] = max(f[i - 1 & 1][j - 1][0], f[i - 1 & 1][j - 1][1] + w[i]);
        }

    int res = f[n & 1][B][0];

    memset(f, -0x3f, sizeof f);
    f[1][1][1] = w[1];
    f[1][0][0] = 0;
    for (int i = 2; i <= n; i ++ )
        for (int j = 0; j <= B; j ++ )
        {
            f[i & 1][j][0] = max(f[i - 1 & 1][j][0], f[i - 1 & 1][j][1]);
            if (j) f[i & 1][j][1] = max(f[i - 1 & 1][j - 1][0], f[i - 1 & 1][j - 1][1] + w[i]);
        }

    res = max(res, f[n & 1][B][1]);

    printf("%d\n", res);

    return 0;
}


活动打卡代码 AcWing 290. 坏掉的机器人

song666
1天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#define maxn 1010

using namespace std;

int n, m, x, y;
double f[maxn][maxn], a[maxn][maxn];

void gauss()
{
    for (int i = 1; i <= m; i ++ )
    {
        double r = a[i][i];
        a[i][i] /= r, a[i][i + 1] /= r;
        if (i < m) a[i][m + 1] /= r;
        double t = a[i + 1][i];
        int c[3] = {i, i + 1, m + 1};
        for (int j = 0; j < 3; j ++ ) a[i + 1][c[j]] -= t * a[i][c[j]]; 
    }

    for (int i = m; i; i -- )
    {
        a[i - 1][m + 1] -= a[i - 1][i] * a[i][m + 1];
        a[i - 1][i] = 0;
    }
}

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

    if (m == 1) printf("%.4lf\n", 2.0 * (n - x));
    else
    {
        for (int i = n - 1; i >= x; i -- )
        {
            a[1][1] = 2.0 / 3, a[1][2] = -1.0 / 3, a[1][m + 1] = f[i + 1][1] / 3 + 1;
            a[m][m] = 2.0 / 3, a[m][m - 1] = -1.0 / 3, a[m][m + 1] = f[i + 1][m] / 3 + 1;
            for (int j = 2; j < m; j ++ )
                a[j][j - 1] = -1.0 / 4, a[j][j] = 3.0 / 4, a[j][j + 1] = -1.0 / 4, a[j][m + 1] = f[i + 1][j] / 4 + 1;

            gauss();

            for (int j = 1; j <= m; j ++ ) f[i][j] = a[j][m + 1];
        }

        printf("%.4lf\n", f[x][y]);
    }

    return 0;
}


活动打卡代码 AcWing 280. 陪审团

song666
2天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#define maxn 210
#define maxm 25
#define maxv 810

using namespace std;

int n, m, C;
int p[maxn], d[maxn];
bool st[maxn];
int f[maxn][maxm][maxv];

bool valid(int x) { return x >= 0 && x <= 800; }

bool Jury()
{
    C ++ ;
    memset(f, -0x3f, sizeof f);
    memset(st, 0, sizeof st);
    f[0][0][400] = 0;
    scanf("%d%d", &n, &m);
    if (!n) return false;

    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d%d", &p[i], &d[i]);
        for (int j = 0; j <= m; j ++ )
            for (int k = 0; k <= 800; k ++ )
            {
                f[i][j][k] = f[i - 1][j][k];
                if (j && valid(k - (p[i] - d[i]))) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k - (p[i] - d[i])] + p[i] + d[i]);
            }
    }

    int maxp = -0x3f3f3f3f, ans = -1;
    for (int i = 0; i <= 400; i ++ )
    {
        if (f[n][m][400 + i] >= 0) maxp = f[n][m][400 + i], ans = 400 + i;
        if (f[n][m][400 - i] >= 0 && f[n][m][400 - i] > maxp) maxp = f[n][m][400 - i], ans = 400 - i;
        if (maxp >= 0) break;
    }

    int sump = 0, sumd = 0, jury = m;
    for (int i = n; i; i -- )
        if (f[i][jury][ans] == f[i - 1][jury - 1][ans - (p[i] - d[i])] + p[i] + d[i])
            jury --, st[i] = true, ans -= (p[i] - d[i]), sump += p[i], sumd += d[i];

    printf("Jury #%d\n", C);
    printf("Best jury has value %d for prosecution and value %d for defence:\n", sump, sumd);
    for (int i = 1; i <= n; i ++ ) if (st[i]) printf(" %d", i);
    puts("\n");

    return true;
}

int main()
{
    while (Jury());
    return 0;
}


活动打卡代码 AcWing 276. I-区域

song666
2天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#define maxn 20
#define maxm 230

using namespace std;

int n, m, K;
int w[maxn][maxn];
struct State{ int i, j, l, r, x, y; }g[maxn][maxm][maxn][maxn][2][2];
int f[maxn][maxm][maxn][maxn][2][2];

int main()
{
    scanf("%d%d%d", &n, &m, &K);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &w[i][j]), w[i][j] += w[i][j - 1];

    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= n * m; j ++ )
            for (int l = 1; l <= m; l ++ )
                for (int r = l; r <= m; r ++ )
                {
                    if (j < (r - l + 1)) continue;

                    //左、右扩张 
                    {
                        auto &vf = f[i][j][l][r][1][0];
                        auto &vg = g[i][j][l][r][1][0];
                        for (int p = l; p <= r; p ++ )
                            for (int q = p; q <= r; q ++ )
                            {
                                int val = f[i - 1][j - (r - l + 1)][p][q][1][0];
                                if (vf < val) vf = val, vg = {i - 1, j - (r - l + 1), p, q, 1, 0};
                            }
                        vf += w[i][r] - w[i][l - 1];
                    }

                    //左扩张、右收缩 
                    {
                        auto &vf = f[i][j][l][r][1][1];
                        auto &vg = g[i][j][l][r][1][1];
                        for (int p = l; p <= r; p ++ )
                            for (int q = r; q <= m; q ++ )
                                for (int y = 0; y < 2; y ++ )
                                {
                                    int val = f[i - 1][j - (r - l + 1)][p][q][1][y];
                                    if (vf < val) vf = val, vg = {i - 1, j - (r - l + 1), p, q, 1, y};//
                                }
                        vf += w[i][r] - w[i][l - 1];
                    }

                    //左收缩,右扩张 
                    {
                        auto &vf = f[i][j][l][r][0][0];
                        auto &vg = g[i][j][l][r][0][0];
                        for (int p = 1; p <= l; p ++ )
                            for (int q = l; q <= r; q ++ )
                                for (int x = 0; x < 2; x ++ )
                                {
                                    int val = f[i - 1][j - (r - l + 1)][p][q][x][0];
                                    if (vf < val) vf = val, vg = {i - 1, j - (r - l + 1), p, q, x, 0};
                                }
                        vf += w[i][r] - w[i][l - 1];
                    }

                    //左、右收缩 
                    {
                        auto &vf = f[i][j][l][r][0][1];
                        auto &vg = g[i][j][l][r][0][1];
                        for (int p = 1; p <= l; p ++ )
                            for (int q = r; q <= m; q ++ )
                                for (int x = 0; x < 2; x ++ )
                                    for (int y = 0; y < 2; y ++ )
                                    {
                                        int val = f[i - 1][j - (r - l + 1)][p][q][x][y];
                                        if (vf < val) vf = val, vg = {i - 1, j - (r - l + 1), p, q, x, y};
                                    }
                        vf += w[i][r] - w[i][l - 1];
                    }
                }

    int res = 0;
    State final;
    for (int i = 1; i <= n; i ++ )
        for (int l = 1; l <= m; l ++ )
            for (int r = 1; r <= m; r ++ )
                for (int x = 0; x < 2; x ++ )
                    for (int y = 0; y < 2; y ++ )
                        if (res < f[i][K][l][r][x][y]) res = f[i][K][l][r][x][y], final = {i, K, l, r, x, y};

    printf("Oil : %d\n", res);
    while (final.j)
    {
        for (int i = final.l; i <= final.r; i ++ ) printf("%d %d\n", final.i, i);
        final = g[final.i][final.j][final.l][final.r][final.x][final.y];
    }

    return 0;
}


活动打卡代码 AcWing 277. 饼干

song666
2天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#define maxn 35
#define maxm 5010

using namespace std;

int n, m;
pair<int, int> g[maxn];
int sum[maxn], f[maxn][maxm];
int ans[maxn];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &g[i].first), g[i].second = i;
    sort(g + 1, g + n + 1);
    reverse(g + 1, g + n + 1);
    for (int i = 1; i <= n; i ++ ) sum[i] = sum[i - 1] + g[i].first;

    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            if (j < i) continue;
            f[i][j] = f[i][j - i];
            for (int k = 1; k <= i; k ++ ) f[i][j] = min(f[i][j], f[i - k][j - k] + (sum[i] - sum[i - k]) * (i - k));
        }

    printf("%d\n", f[n][m]);

    int i = n, j = m, delta = 0;
    while (i)
    {
        if (f[i][j] == f[i][j - i]) j -= i, delta ++ ;
        else
        {
            for (int k = 1; k <= i; k ++ )
                if (f[i][j] == f[i - k][j - k] + (sum[i] - sum[i - k]) * (i - k))
                {
                    for (int t = i - k + 1; t <= i; t ++ ) ans[g[t].second] = delta + 1;
                    i -= k, j -= k;
                    break;
                }
        }
    }

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

    return 0;
}


活动打卡代码 AcWing 344. 观光之旅

song666
3天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#define maxn 110

using namespace std;

int n, m;
int w[maxn][maxn];
int d[maxn][maxn], pos[maxn][maxn];

void getpath(int x, int y, vector<int> &ans)
{
    if (!pos[x][y]) return;
    getpath(x, pos[x][y], ans);
    ans.push_back(pos[x][y]);
    getpath(pos[x][y], y, ans);
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(w, 0x3f, sizeof w);
    for (int i = 1; i <= n; i ++ ) w[i][i] = 0;//
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        w[a][b] = w[b][a] = min(w[a][b], c);
    }
    memcpy(d, w, sizeof w);

    int ans = 0x3f3f3f3f;
    vector<int> res;
    for (int k = 1; k <= n; k ++ )
    {
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                if (i != j && i != k && j != k)
                {
                    if ((long long)w[i][k] + w[k][j] + d[i][j] < ans)//
                    {
                        ans = w[i][k] + w[k][j] + d[i][j];//
                        res.clear();
                        res.push_back(i);
                        getpath(i, j, res);
                        res.push_back(j);
                        res.push_back(k);
                    }
                }
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                if (i != j && j != k && i != k)
                    if (d[i][j] > d[i][k] + d[k][j])
                    {
                        d[i][j] = d[i][k] + d[k][j];
                        pos[i][j] = k;
                    }
    }

    if (ans == 0x3f3f3f3f) puts("No solution.");
    else for (auto x : res) printf("%d ", x);

    return 0;
}


活动打卡代码 AcWing 391. 聚会

song666
3天前

卡常啊

#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#include <cstdio>
#include <cstring>
#include <cmath>
#define maxn 500010

using namespace std;

int n, q, T;
int pos, tmp;
int h[maxn], e[maxn * 2], ne[maxn * 2], idx;
int f[maxn][21], dep[maxn];

inline void swap(int &x, int &y) { int t = x; x = y; y = t; }
inline void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; }
inline void dfs(int u, int fa)
{
    for (register int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        f[j][0] = u;
        dep[j] = dep[u] + 1;
        for (register int t = 1; t <= T; t ++ ) f[j][t] = f[f[j][t - 1]][t - 1];

        dfs(j, u);
    }
}

inline int lca(int x, int y)
{
    if (dep[x] < dep[y]) swap(x, y);
    for (register int t = T; ~t; t -- )
        if (dep[f[x][t]] >= dep[y])
            x = f[x][t];

    if (x == y) return x;//352的教训

    for (register int t = T; ~t; t -- )
        if (f[x][t] != f[y][t])
            x = f[x][t], y = f[y][t];

    return f[x][0];
}

inline int getdist(int x, int y) { return dep[x] + dep[y] - 2 * dep[lca(x, y)]; }
inline int getans(int x, int y, int z)
{
    int ans = getdist(x, y);
    tmp = lca(x, y);
    ans += getdist(tmp, z);
    return ans;
}

int main()
{
    scanf("%d%d", &n, &q);
    memset(h, -1, sizeof h);
    T = (int)(log(n) / log(2));
    for (register int i = 1; i < n; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    dep[1] = 1;
    dfs(1, -1);

    while (q -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        int cost = 1e9;
        if (getans(a, b, c) < cost) cost = getans(a, b, c), pos = tmp;
        if (getans(a, c, b) < cost) cost = getans(a, c, b), pos = tmp;
        if (getans(b, c, a) < cost) cost = getans(b, c, a), pos = tmp;

        printf("%d %d\n", pos, cost);
    }

    return 0;
}