头像

Ethanyyc

$\Huge\color{red}{学术}$模式:不发帖,不私聊




离线:7小时前


最近来访(618)
用户头像
清风qwq
用户头像
dushucheng0901
用户头像
凉城少年
用户头像
Ariel0501
用户头像
云衣醉梦
用户头像
南岸以南南岸哀
用户头像
源泉
用户头像
旅行家
用户头像
垫底抽風
用户头像
源泉_2
用户头像
别黑我家哥哥
用户头像
心在远方_
用户头像
呕.
用户头像
英语平均分
用户头像
Philip
用户头像
梦若生
用户头像
Finn2009
用户头像
垫抽底风
用户头像
胡尔摩斯
用户头像
无敌的超人

活动打卡代码 AcWing 1129. 热浪

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2510, M = 6200 * 2 + 10;

int n, m, S, T;
int h[N], e[M], w[M], ne[M], idx;
int d[N], q[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(d, 0x3f, sizeof d);
    d[S] = 0;

    int hh = 0, tt = 1;
    q[0] = S, st[S] = true;

    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (d[j] > d[t] + w[i])
            {
                d[j] = d[t] + w[i];
                if (!st[j])
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
}

int main()
{
    cin >> n >> m >> S >> T;

    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }

    spfa();

    cout << d[T] << endl;

    return 0;
}



活动打卡代码 AcWing 181. 回转游戏

# include <bits/stdc++.h>
using namespace std;

int op[8][7] =
{
    {0, 2, 6, 11, 15, 20, 22},
    {1, 3, 8, 12, 17, 21, 23},
    {10, 9, 8, 7, 6, 5, 4},
    {19, 18, 17, 16, 15, 14, 13},
    {23, 21, 17, 12, 8, 3, 1},
    {22, 20, 15, 11, 6, 2, 0},
    {13, 14, 15, 16, 17, 18, 19},
    {4, 5, 6, 7, 8, 9, 10}
};

int opt[8] = {5, 4, 7, 6, 1, 0, 3, 2};
int ctr[8] = {6, 7, 8, 11, 12, 15, 16, 17};

int q[24];
int pth[100];

int f()
{
    static int s[4];
    memset(s, 0, sizeof s);
    for (int i = 0; i < 8; i ++ )
        s[q[ctr[i]]] ++ ;

    int maxv = 0;

    for (int i = 1; i <= 3; i ++ )
        maxv = max(maxv, s[i]);

    return 8 - maxv;
}

void opr(int x)
{
    int t = q[op[x][0]];
    for (int i = 0; i < 6; i ++ )
        q[op[x][i]] = q[op[x][i + 1]];
    q[op[x][6]] = t;
}

bool dfs(int dep, int mx, int last)
{
    if (dep + f() > mx)
        return 0;

    if (f() == 0)
        return 1;

    for (int i = 0; i < 8; i ++ )
    {
        if (last != opt[i])
        {
            opr(i);
            pth[dep] = i;
            if (dfs(dep + 1, mx, i))
                return 1;
            opr(opt[i]);
        }
    }

    return 0;
}

int main()
{
    while (cin >> q[0], q[0])
    {
        for (int i = 1; i < 24; i ++ )
            cin >> q[i];

        int dep = 0;
        while (!dfs(0, dep, -1)) dep ++ ;

        if (!dep) printf("No moves needed");
        else
        {
            for (int i = 0; i < dep; i ++ ) printf("%c", 'A' + pth[i]);
        }
        printf("\n%d\n", q[6]);
    }

    return 0;
}



活动打卡代码 AcWing 180. 排书

# include <bits/stdc++.h>
using namespace std;

int n;

int q[15];
int w[5][15];

int f()
{
    int cnt = 0;

    for (int i = 0; i + 1 < n; i ++ )
    {
        if (q[i + 1] != q[i] + 1)
            cnt ++ ;
    }

    return (cnt + 2) / 3;
}

bool check()
{
    for (int i = 0; i + 1 < n; i ++ )
    {
        if (q[i + 1] != q[i] + 1)
            return 0;
    }

    return 1;
}

bool dfs(int dep, int mx)
{
    if (dep + f() > mx)
        return 0;

    if (check())
        return 1;

    for (int len = 1; len <= n; len ++ )
    {
        for (int l = 0; l + len - 1 < n; l ++ )
        {
            int r = l + len - 1;

            for (int k = r + 1; k < n; k ++ )
            {
                memcpy(w[dep], q, sizeof q);

                int x, y;

                for (x = r + 1, y = l; x <= k; x ++, y ++ )
                    q[y] = w[dep][x];

                for (x = l; x <= r; x ++, y ++ )
                    q[y] = w[dep][x];

                if (dfs(dep + 1, mx))
                    return 1;

                memcpy (q, w[dep], sizeof q);
            }
        }
    }

    return 0;
}

int main()
{
    int T;
    cin >> T;

    while (T -- )
    {
        cin >> n;

        for (int i = 0; i < n; i ++ )
            cin >> q[i];

        int dep = 0;

        while (dep < 5 && !dfs(0, dep))
            dep ++ ;

        if (dep >= 5)
            puts("5 or more");
        else
            cout << dep << endl;
    }

    return 0;
}


活动打卡代码 AcWing 171. 送礼物

# include <bits/stdc++.h>
using namespace std;

int n, m, k;
int g[50];
int w[1 << 24];

int cnt = 0;
int ans;

void dfs (int u, int s)
{
    if (u == k)
    {
        w[cnt ++ ] = s;

        return ; 
    }

    if ((long long)s + g[u] <= m)
        dfs (u + 1, s + g[u]);

    dfs (u + 1, s);
}

void dfs2 (int u, int s)
{
    if (u == n)
    {
        int l = 0, r = cnt - 1;

        while (l < r)
        {
            int mid = l + r + 1 >> 1;

            if (w[mid] + (long long)s <= m)
                l = mid;
            else
                r = mid - 1;
        }

        if (w[l] + (long long)s <= m)
            ans = max(ans, w[l] + s);

        return ;
    }

    if ((long long)s + g[u] <= m)
        dfs2(u + 1, s + g[u]);

    dfs2 (u + 1, s);
}


int main()
{
    cin >> m >> n;

    for (int i = 0; i < n; i ++ )
        cin >> g[i];

    sort (g, g + n);
    reverse (g, g + n);

    k = n / 2;
    dfs(0, 0);

    sort(w, w + cnt);

    int t = 1;

    for (int i = 1; i < cnt; i ++ )
    {
        if (w[i] != w[i - 1])
            w[t ++ ] = w[i];
    }

    cnt = t;

    dfs2(k, 0);

    cout << ans;

    return 0;
}


活动打卡代码 AcWing 170. 加成序列

# include <bits/stdc++.h>
using namespace std;

int n;

int pth[105];

bool dfs(int u, int k)
{
    if (u == k)
        return pth[u - 1] == n;

    bool vis[105] = {0};

    for (int i = u - 1; i >= 0; i -- )
    {
        for (int j = i; j >= 0; j -- )
        {
            int s = pth[i] + pth[j];

            if (s > n || s <= pth[u - 1] || vis[s])
                continue;

            vis[s] = 1;

            pth[u] = s;

            if (dfs(u + 1, k))
                return 1;
        }
    }

    return 0;
}

int main()
{
    pth[0] = 1;

    while (cin >> n, n)
    {
        int k = 1;

        while (!dfs(1, k))
            k ++ ;

        for (int i = 0; i < k; i ++ )
            cout << pth[i] << " ";

        cout << endl;
    }

    return 0;
} 


活动打卡代码 AcWing 168. 生日蛋糕

# include <bits/stdc++.h>
using namespace std;

int n, m;

int minv[25];
int mins[25];

int R[25], H[25];

int ans = 1e9;

void dfs (int u, int v, int s)
{
    if (v + minv[u] > n)
        return;

    if (s + mins[u] >= ans)
        return;

    if (s + 2 * (n - v) / R[u + 1] >= ans)
        return;

    if (!u)
    {
        if (v == n)
            ans = s;

        return;
    }

    for (int r = min(R[u + 1] - 1, (int)sqrt(n - v)); r >= u; r -- )
    {
        for (int h = min(H[u + 1] - 1, (n - v) / r / r); h >= u; h -- )
        {
            int t = 0;

            if (u == m)
                t = r * r;

            R[u] = r;
            H[u] = h;

            dfs(u - 1, v + r * r * h, s + 2 * r * h + t);
        }
    }
}

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= m; i ++ )
    {
        minv[i] = minv[i - 1] + i * i * i;
        mins[i] = mins[i - 1] + 2 * i * i;
    }


    R[m + 1] = H[m + 1] = 1e9;

    dfs (m, 0, 0);

    if (ans == 1e9)
        ans = 0;

    cout << ans;

    return 0;
}



活动打卡代码 AcWing 167. 木棒

# include <bits/stdc++.h>
using namespace std;

int n;

int w[70];
int sum;
int l;

bool st[70];

bool dfs(int u, int cur, int s)
{
    if (u * l == sum)
        return 1;

    if (cur == l)
        return dfs(u + 1, 0, 0);

    for (int i = s; i < n; i ++ )
    {
        if (st[i] || cur + w[i] > l)
            continue;

        st[i] = 1;
        if (dfs(u, cur + w[i], i + 1))
            return 1;

        st[i] = 0;

        if (!cur || cur + w[i] == l)
            return 0;

        int j = i;
        while (j < n && w[j] == w[i]) j ++ ;
        i = j - 1;
    }

    return 0;
}

int main()
{
    while (cin >> n, n)
    {
        memset(st, 0, sizeof st);

        sum = 0;

        for (int i = 0; i < n; i ++ )
        {
            cin >> w[i];

            sum += w[i];
        }

        sort(w, w + n);
        reverse(w, w + n);

        l = 1;
        while (1)
        {
            if (sum % l == 0 && dfs(0, 0, 0))
            {
                cout << l << endl;
                break;
            }

            l ++ ;
        }
    }

    return 0;
}



活动打卡代码 AcWing 166. 数独

# include <bits/stdc++.h>
using namespace std;

int ones[1 << 9];

int mp[1 << 9];

int row[9], col[9];

int cell[3][3];

char str[100];

void init()
{
    for (int i = 0; i < 9; i ++ )
        row[i] = col[i] = (1 << 9) - 1;

    for (int i = 0; i < 3; i ++ )
    {
        for (int j = 0; j < 3; j ++ )
            cell[i][j] = (1 << 9) - 1;
    }
}

void draw(int x, int y, int t, bool is_set)
{
    if (is_set)
        str[x * 9 + y] = '1' + t;
    else
        str[x * 9 + y] = '.';

    int v = 1 << t;

    if (!is_set)
        v = -v;

    row[x] -= v;
    col[y] -= v;

    cell[x / 3][y / 3] -= v;
}

int lowbit(int x)
{
    return x & -x;
}

int get(int x, int y)
{
    return row[x] & col[y] & cell[x / 3][y / 3];
}

bool dfs(int cnt)
{
    if (!cnt)
        return 1;

    int minv = 10;

    int x, y;

    for (int i = 0; i < 9; i ++ )
    {
        for (int j = 0; j < 9; j ++ )
        {
            if (str[i * 9 + j] == '.')
            {
                int st = get(i, j);

                if (ones[st] < minv)
                {
                    minv = ones[st];
                    x = i, y = j;
                }
            }
        }
    }

    int st = get(x, y);

    for (int i = st; i; i -= lowbit(i))
    {
        int t = mp[lowbit(i)];

        draw(x, y, t, 1);

        if (dfs(cnt - 1)) 
            return 1;

        draw(x, y, t, 0);
    }

    return 0;
}

int main()
{
    for (int i = 0; i < 9; i ++ )
        mp[1 << i] = i;

    for (int i = 0; i < 1 << 9; i ++ )
    {
        for (int j = 0; j < 9; j ++ )
            ones[i] += i >> j & 1;
    }

    while (cin >> str, str[0] != 'e')
    {
        init();

        int cnt = 0;

        for (int i = 0, k = 0; i < 9; i ++ )
        {
            for (int j = 0; j < 9; j ++, k ++ )
            {
                if (str[k] != '.')
                {
                    int t = str[k] - '1';
                    draw(i, j, t, true);
                }
                else
                    cnt ++ ;
            }
        }

        dfs(cnt);

        puts(str);
    }

    return 0;
}



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

# include <bits/stdc++.h>
using namespace std;

int n, m;

int w[20];

int sum[20];

int ans = 20;

void dfs (int u, int k)
{
    if (k >= ans)
        return;

    if (u == n)
    {
        ans = k;

        return;
    }

    for (int i = 0; i < k; i ++ )
    {
        if (sum[i] + w[u] <= m)
        {
            sum[i] += w[u];

            dfs (u + 1, k);

            sum[i] -= w[u];
        }
    }

    sum[k] = w[u];

    dfs (u + 1, k + 1);

    sum[k] = 0;
}

int main()
{
    cin >> n >> m;

    for (int i = 0; i < n; i ++ )
        cin >> w[i];

    sort (w, w + n);

    reverse (w, w + n);

    dfs (0, 0);

    cout << ans;

    return 0;
}


活动打卡代码 AcWing 1118. 分成互质组

Ethanyyc
12天前
#include <bits/stdc++.h>
using namespace std;

int n;
int p[10];
int group[10][10];
bool st[10];
int ans = 10;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

bool check(int group[], int gc, int i)
{
    for (int j = 0; j < gc; j ++ )
    {
        if (gcd(p[group[j]], p[i]) > 1)
            return 0;
    }
    return 1;
}

void dfs(int g, int gc, int tc, int start)
{
    if (g >= ans)
        return;

    if (tc == n)
        ans = g;

    bool flag = 1;

    for (int i = start; i < n; i ++ )
    {
        if (!st[i] && check(group[g], gc, i))
        {
            st[i] = 1;
            group[g][gc] = i;
            dfs(g, gc + 1, tc + 1, i + 1);
            st[i] = 0;

            flag = 0;
        }
    }

    if (flag)
        dfs(g + 1, 0, tc, 0);
}

int main()
{
    cin >> n;

    for (int i = 0; i < n; i ++ )
        cin >> p[i];

    dfs(1, 0, 0, 0);

    cout << ans;
    return 0;
}