头像

int_main




离线:4天前


最近来访(3)
用户头像
枫灵FengLing
用户头像
yxc
用户头像
苍茫得胖帅

活动打卡代码 AcWing 1083. Windy数

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

using namespace std;

const int N = 15;
int f[N][10];

void init()
{
    for (int i = 0; i < 10; i ++) f[1][i] = 1;
    //越界会把其他地方答案弄乱

    for (int i = 2; i < N; i ++) 
        for (int j = 0; j < 10; j ++)
            for (int k = 0; k < 10; k ++)
                if (abs(j - k) >= 2)
                    f[i][j] += f[i - 1][k];
}

int dp(int n)
{
    if (!n) return 0;
    //由于a也是范围内

    vector<int> nums;

    int ans = 0, last = -2;

    while(n) nums.push_back(n % 10), n /= 10;

    for (int i = nums.size() - 1; i >= 0; i --)
    {
        int x = nums[i];

        for (int j = i == nums.size() - 1; j < x; j ++)
            if (abs(last - j) >= 2)
                ans += f[i + 1][j];
        //第一个数不能填0
        //这样的话对于那些位数低的数,就没有计算

        if (abs(x - last) < 2) break;

        last = x;

        if (!i) ans ++;
    }

    for (int i = 1; i < nums.size(); i ++)
        for (int j = 1; j < 10; j ++)
            ans += f[i][j];
    //补上


    return ans;

}

int main()
{
    init();

    int l, r;
    cin >> l >> r;

    cout << dp(r) - dp(l - 1);
}


活动打卡代码 AcWing 1082. 数字游戏

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

using namespace std;

const int N = 15;
int f[N][N];//有i个位置,第一位是j的不降序列数

void init()
{
    for (int i = 0; i < 10; i ++) f[1][i] = 1;

    for (int i = 2; i < N; i ++)
        for (int j = 0; j < 10; j ++)
            for (int k = j; k <= 9; k ++)
                f[i][j] += f[i - 1][k];
}

int dp(int x)
{
    if (!x) return 1;

    vector<int> nums;

    while (x) nums.push_back(x % 10), x /= 10;

    int last = 0, ans = 0;

    for (int i = nums.size() - 1; i >= 0; i --)
    {
        int x = nums[i];

        for (int j = last; j < x; j ++)
            ans += f[i + 1][j];
        //当前从last到x - 1的选法
        //方案数已经预处理了
        //前导0也算

        if (x < last)
            break;
        //不能往下选了,退出

        last = x;
        //记一下前缀的信息

        if (!i) ans ++;
        //最后一个选了要+1
    }

    return ans;
}

int main()
{
    int a, b;


    init();

    while (cin >> a >> b)
        cout << dp(b) - dp(a - 1) << endl; 
}



核心思想代码注释写得很清楚

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

using namespace std;

const int N = 35;

int x, y, k, b;

int f[N][N];

void init()
{
    for (int i = 0; i < N; i ++)
        for (int j = 0; j <= i; j ++)
            if (!j) f[i][j] = 1;
            else f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
}

int dp(int y)
{
    if (!y) return 0;

    int ans = 0, last = 0;

    vector<int> nums;

    while (y) nums.push_back(y % b), y /= b;

    for (int i = nums.size() - 1; i >= 0; i --)
    {
        int x = nums[i];
        if (x)
        {
            ans += f[i][k - last];
            //当前位大于0
            //那么选择0,以后随便选
            if (x > 1)
            {
                if (k - last - 1 >= 0) ans += f[i][k - last - 1];
                break;
                //如果当前位大于1,那么以后的可以随便选,选完就break
            }
            else 
            {
                last ++;
                if (last > k) break;
                //如果当前位==1
                //那么把可用的1减少,往下看
            }
        }

        if (!i && k == last) ans ++;
        //如果最后一位等于0
        //选0,答案+1
    }

    return ans;
}

int main()
{
    cin >> x >> y >> k >> b;

    init();


    cout << dp(y) - dp(x - 1);
}


活动打卡代码 AcWing 1081. 度的数量

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

using namespace std;

const int N = 35;

int x, y, k, b;

int f[N][N];

void init()
{
    for (int i = 0; i < N; i ++)
        for (int j = 0; j <= i; j ++)
            if (!j) f[i][j] = 1;
            else f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
}

int dp(int y)
{
    if (!y) return 0;

    int ans = 0, last = 0;

    vector<int> nums;

    while (y) nums.push_back(y % b), y /= b;

    for (int i = nums.size() - 1; i >= 0; i --)
    {
        int x = nums[i];
        if (x)
        {
            ans += f[i][k - last];
            //当前位大于0
            //那么选择0,以后随便选
            if (x > 1)
            {
                if (k - last - 1 >= 0) ans += f[i][k - last - 1];
                break;
                //如果当前位大于1,那么以后的可以随便选,选完就break
            }
            else 
            {
                last ++;
                if (last > k) break;
                //如果当前位==1
                //那么把可用的1减少,往下看
            }
        }

        if (!i && k == last) ans ++;
        //如果最后一位等于0
        //选0,答案+1
    }

    return ans;
}

int main()
{
    cin >> x >> y >> k >> b;

    init();


    cout << dp(y) - dp(x - 1);
}


活动打卡代码 AcWing 1077. 皇宫看守

int_main
10天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1510, INF = 0x3f3f3f3f;

int h[N], e[N], ne[N], idx;
bool st[N];
int f[N][3], w[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u)
{
    f[u][1] = INF;
    f[u][2] = w[u];

    int sum = 0;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];

        dfs(j);

        f[u][0] += min(f[j][1], f[j][2]);
        f[u][2] += min(f[j][1], min(f[j][2], f[j][0]));
    }


    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        f[u][1] = min(f[u][1], f[u][0] - min(f[j][1], f[j][2]) + f[j][2]);
        //这里必须+f[j][2]
        //如果只加w[j],那么就跳过了那些之前的累积代价
    }

}

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

    memset(h, -1, sizeof h);

    for (int i = 0; i < n; i ++)
    {
        int a, v, b, m;
        cin >> a >> v >> m;
        w[a] = v;
        for (int j = 0; j < m; j ++)
        {
            cin >> b;
            add(a, b);
            st[b] = true;
        }
    }

    int root = 1;
    while (st[root]) root ++;

    dfs(root);

    cout << min(f[root][1], f[root][2]) << endl;
}

自己思路 最后点没过 待解决

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

using namespace std;

const int N = 1510, M = N, INF = 0x3f3f3f3f;

typedef long long LL;

LL f[N][2][2];
int h[N], e[M], ne[M], w[N], idx;
bool st[N], not_leaf[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u)
{
    f[u][1][0] = f[u][1][1] = w[u];
    f[u][0][1] = INF;
    int sum = 0;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];

        dfs(j);

        f[u][1][0] += min(f[j][0][1], f[j][0][0]);
        f[u][1][1] += min(f[j][1][0], f[j][1][1]);
        f[u][0][0] += f[j][0][1];
        sum += min(min(f[j][1][0], f[j][0][1]), f[j][1][1]);
    }

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];

        f[u][0][1] = min(f[u][0][1], 
        sum - min(min(f[j][1][0], f[j][0][1]), f[j][1][1])
        + min(f[j][1][0], f[j][1][1]));
    }

}

int main()
{
    memset(h, -1, sizeof h);

    int n;
    cin >> n;

    for (int i = 0; i < n; i ++)
    {
        int a, v, m;
        cin >> a >> v >> m;
        w[a] = v;
        for (int j = 0; j < m; j ++)
        {
            int b;
            cin >> b;
            add(a, b);
            st[b] = true;
            not_leaf[a] = true;
        }
    }

    int root = 1;
    while (st[root]) root ++;

    dfs(root);

    cout << min(min(f[root][1][0], f[root][1][1]), f[root][0][1]);
}


活动打卡代码 AcWing 323. 战略游戏

int_main
10天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1510, M = 2 * N;
int f[N][2];
int h[N], e[M], ne[M], idx;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u, int father)
{
    f[u][1] = 1;
    f[u][0] = 0;

    for (int i = h[u]; ~i; i = ne[i])
    {
        if (e[i] == father) continue;

        dfs(e[i], u);

        f[u][0] += f[e[i]][1];
        f[u][1] += min(f[e[i]][0], f[e[i]][1]);
        //求总的数量,因此+=
    }

}

int main()
{
    int n;

    while (scanf("%d", &n) == 1)
    {
        memset(h, -1, sizeof h);
        idx = 0;

        for (int i = 0; i < n; i ++)
        {
            int m, a;
            scanf("%d:(%d)", &a, &m);
            for (int j = 0; j < m; j ++)
            {
                int b;
                scanf("%d", &b);
                add(a, b), add(b, a);
            }
        }

        dfs(1, -1);

        cout << min(f[1][0], f[1][1]) << endl;
    }

}


活动打卡代码 AcWing 1074. 二叉苹果树

int_main
10天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, M = 2 * N;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
int f[N][N];

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

int dfs(int u, int father)
{
    for (int i = h[u]; ~i; i = ne[i])
    {

        if (e[i] == father) continue;
        dfs(e[i], u);

        for (int j = m; j > 0; j --)
            for (int k = 0; k < j; k ++)
                f[u][j] = max(f[u][j], f[e[i]][k] + f[u][j - k - 1] + w[i]);

    }
}

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

    memset(h, -1, sizeof h);

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

    dfs(1, -1);

    cout << f[1][m] << endl;
}


活动打卡代码 AcWing 1075. 数字转换

int_main
11天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 50010, M = 2 * N;

int h[N], ne[M], e[M], idx;
int sum[N];
bool st[N];
int ans;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u)
{
    st[u] = true;
    int d1 = 0, d2 = 0;

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (st[j]) continue;

        int d = dfs(j) + 1;
        if (d > d1) d2 = d1, d1 = d;
        else if (d > d2) d2 = d;
    }

    ans = max(ans, d1 + d2);

    return d1;
}

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

    memset(h, -1, sizeof h);

    for (int i = 1; i <= n; i ++)
        for (int j = 2; j <= n / i; j ++)
            sum[i * j] += i;
        //本题一个数被本身整除不算
        //所以j从2开始

    for (int i = 2; i <= n; i ++)
        if (sum[i] < i) add(sum[i], i);
    //可以只建有向图

    for (int i = 1; i <= n; i ++)
        if (!st[i]) dfs(i);

    //dfs(1);
    //1跟所有树连通,只dfs(1)即可
    //如果是有向图,那么不dfs(1)的话找不到答案

    cout << ans;

}


活动打卡代码 AcWing 1073. 树的中心

int_main
11天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010, M = 2 * N, INF = 1e9;
int h[N], e[M], ne[M], w[M], idx;
int d1[N], d2[N];
int p[N], up[N];

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

int dfs_d(int u, int father)
{
    //d1[u] = d2[u] = -INF;
    //如果有负边

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;

        int d = dfs_d(j, u) + w[i];

        if (d > d1[u])
        {
            d2[u] = d1[u];
            d1[u] = d;
            p[u] = j;
        }
        else if (d > d2[u]) 
            d2[u] = d;
    }

    //if (d1[u] == -INF) d1[u] = 0, d2[u] = 0, is_leaf[u] = 1;
    //如果有负边

    return d1[u];
}

void dfs_u(int u, int father)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;

        if (p[u] == j) up[j] = max(up[u], d2[u]) + w[i];
        else up[j] = max(up[u], d1[u]) + w[i];

        dfs_u(j, u);
    }
}

int main()
{
    int n = 0;
    cin >> n;

    memset(h, -1, sizeof h);

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


    dfs_d(1, -1);
    dfs_u(1, -1);

    int ans = INF;

    for (int i = 1; i <= n; i ++)
        ans = min(ans, max(up[i], d1[i]));

    cout << ans << endl;
}


活动打卡代码 AcWing 1072. 树的最长路径

int_main
12天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010, M = 2 * N;
int e[M], ne[M], w[M], h[N], idx; 
int ans;

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

int dfs(int u, int father)
{
    int d1 = 0, d2 = 0;

    for (int i = h[u]; ~i; i = ne[i])
    {
        if (e[i] == father) continue;
        int temp = dfs(e[i], u) + w[i];

        if (temp > d1) d2 = d1, d1 = temp;
        else if (temp > d2) d2 = temp;
    }

    ans = max(ans, d1 + d2);

    return d1;
}

int main()
{
    int n = 0;
    cin >> n;

    memset(h, -1, sizeof h);

    for (int i = 0; i < n - 1; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    //注意读题,n - 1条边

    dfs(1, -2);
    //根节点随便传一个不存在的父亲

    cout << ans;
}