头像

无A不成C

$Acwing\ University$




离线:1小时前


最近来访(90)
用户头像
zzz_90
用户头像
呆比
用户头像
Misaka_9982
用户头像
zhihaoFu
用户头像
冰菓
用户头像
MIisaka
用户头像
齐天大仙
用户头像
小崔崔
用户头像
zdkk
用户头像
小萌妹
用户头像
Nan97
用户头像
hunzia
用户头像
贪心的小马
用户头像
Pipipapi
用户头像
Fantasyli
用户头像
kaaaaa
用户头像
炽天使
用户头像
直行格子
用户头像
Thu_yc
用户头像
acWing_lbwnb

活动打卡代码 AcWing 1085. 不要62

无A不成C
3小时前

Snipaste_2021-07-26_21-30-57.png

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

using namespace std;

const int N = 12;

int f[N][10];

void init(){
    for(int i = 0; i <= 9; i ++)
        if(i != 4)
            f[1][i] = 1;
    for(int i = 2; i < N; i ++)
        for(int j = 0; j <= 9; j ++){
            if(j == 4) continue;
            for(int k = 0; k <= 9; k ++){
                if(k == 4 || j == 6 && k == 2) continue;
                f[i][j] += f[i - 1][k];
            }
        }
}

int dp(int n){
    vector<int> nums;
    if(!n) return 1;

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

    int res = 0;
    int last = 0;
    for(int i = nums.size() - 1; i >= 0; i --){
        int x= nums[i];
        for(int j = 0; j < x; j ++){
            if(j == 4 || last == 6 && j == 2) continue;
            res += f[i + 1][j];
        }
        if(x == 4 || last == 6 && x == 2) break;
        last = x;
        if(!i) res ++;
    }

    return res;
}
int main(){
    init();
    int l, r;
    while(cin >> l >> r, l || r) 
        cout << dp(r) - dp(l - 1) << endl;

    return 0;
}


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

无A不成C
4小时前

Snipaste_2021-07-26_20-27-05.png

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

using namespace std;

const int N = 11, M = 110;

int P;
// i位数 最高位为j   mod n 为k 的数的个数
int f[N][10][M];

int mod(int x, int y)
{
    return (x % y + y) % y;
}

void init()
{
    memset(f, 0, sizeof f);

    for (int i = 0; i <= 9; i ++ ) f[1][i][i % P] ++ ;

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

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

    vector<int> nums;
    while (n) nums.push_back(n % 10), n /= 10;

    int res = 0;
    int last = 0;
    for (int i = nums.size() - 1; i >= 0; i -- )
    {
        int x = nums[i];
        for (int j = 0; j < x; j ++ )
            res += f[i + 1][j][mod(-last, P)];

        last += x;

        if (!i && last % P == 0) res ++ ;
    }

    return res;
}

int main()
{
    int l, r;
    while (cin >> l >> r >> P)
    {
        init();

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

    return 0;
}



活动打卡代码 AcWing 1083. Windy数

无A不成C
6小时前
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 11;

int f[N][10];

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

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

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

    vector<int> nums;
    while (n) nums.push_back(n % 10), n /= 10;

    int res = 0;
    int last = -2;
    for (int i = nums.size() - 1; i >= 0; i -- )
    {
        int x = nums[i];
        //暂不处理第一位是0的情况
        for (int j = i == nums.size() - 1; j < x; j ++ )
            if (abs(j - last) >= 2)
                res += f[i + 1][j];

        if (abs(x - last) >= 2) last = x;
        else break;

        if (!i) res ++ ;
    }

    // 在这里特殊处理有前导零的数, 即第一位是0的情况
    for (int i = 1; i < nums.size(); i ++ )
        for (int j = 1; j <= 9; j ++ )
            res += f[i][j];

    return res;
}

int main()
{
    /*因为本题中特殊规定了,windy数不能包含前导零。如果把位数较低的数看成是包含前导零,那么首位就不能是1了,但windy数的首位可以是1。*/
    init();

    int l, r;
    cin >> l >> r;
    cout << dp(r) - dp(l - 1) << endl;

    return 0;
}


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

无A不成C
7小时前

Snipaste_2021-07-26_17-02-55.png
Snipaste_2021-07-26_17-03-19.png

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

using namespace std;

const int N = 15;

int f[N][N];

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

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

int dp(int n){
    vector<int> nums;
    if(!n) return 1;
    while(n) nums.push_back(n % 10), n /= 10;

    int res = 0;
    //记录右分支 即上一个数
    int last = 0;
    for(int i = nums.size() - 1; i >= 0; i --){
        int x = nums[i];
        //左分支架
        for(int j = last; j < x; j ++)
            res += f[i + 1][j];

        //该右分支大于上一个数, 提前break    
        if(x < last) break;
        last = x;

        //若走到了最后一个数没被break, 则加上
        if(!i) res ++;
    }

    return res;
}

int main(){
    init();
    int l, r;
    while(cin >> l >> r) cout << dp(r) - dp(l - 1) << endl;
    return 0;
}


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

思路

首先, 转换题意, 根据题意可知一个数X是B进制的话, 则X = $a * B^0 + b * B^1 + c * B^2 + …$

要想符合题意, 它们的系数必须为0或1

则题意转化为, 将X转化为B进制, 求0~X 中满足1的个数为$k$, 其余全部为0的情况个数

所以我们只需依次枚举各个位上的数即可。 其实类比是个树状结构

Snipaste_2021-07-23_20-38-04.png

通用对在区间的满足的数求法:$F([l,r]) = F[r] - F[l - 1]$

对枚举第i个数的情况

1.x == 0

那么第i位只能是0,后面数位上现在都不能确定,只能继续向后看.

2.x == 1

这里第i位可以分成两种情况:

  • 第i位放0,那么后面的数位上可以放k-last个1,res += f[i][k-last];
  • 第i位放1,那么后面数位上的情况不能用组合数计算,因为要保证答案中的数字比原数字要小

3.x > 1

同样第i位分成两种情况

  • 第i位放0,那么后面的数位上可以放k-last个1,res += f[i][k-last];
  • 第i位放1,那么后面的数位上可以放k-last-1个1,res += f[i][k-last-1];
  • 此时计算完了该位取0,1的情况后,需要break,因为每一位不能取除0和1以外的数
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

using namespace std;

const int N = 35;

int 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 n){
    if(!n) return 0;

    vector<int> nums;
    //转换为B进制
    while(n) nums.push_back(n % B), n /= B;

    int res = 0;
    int last = 0;
    for(int i = nums.size() - 1; i >= 0; i --){
        int x = nums[i];
        //如果x不为0
        if(x){
            //先加上该位取0的情况,后面i位随便选k-last个1
            res += f[i][K - last];
            if(x > 1){
                //加上该位取1的情况, 后面i位随便选k-last-1个1
                if(K - last - 1 >= 0) res += f[i][K - last - 1];
                //该位不能取其他数了, 不用继续枚举了, break
                break;
            }
            else{
                //该位必须为1, 后面不能随便选, last ++
                last ++;
                if(last > K) break;
            }
        }
        //最右边的分支
        if(!i && last == K) res ++;
    }

    return res;
}
int main(){
    init();

    int l, r;
    cin >> l >> r >> K >> B;

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

    return 0;
}


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

首先这道题的题意是:给定一棵树,要在一些节点上放置守卫,每个守卫可以看护当前节点以及与此节点连通的节点,在不同节点放置守卫的代价不同,如何选取节点使代价最小,这是个典型的树形DP问题,显然每个节点有放置守卫和不放置守卫两种,但是从计算的过程看,不放置守卫的状态由两种,一种是有其父节点上的守卫看护,一种是由其子节点的守卫看护,因此可将每个节点的看护情况分为三种:

  • 该节点由父节点处放置的守卫看护
  • 该节点由子节点处放置的守护看护
  • 该节点由在该节点放置的守卫看护

状态表示

$f[i,0]$:在点 i 不摆放警卫,且被父结点看到的所有摆放方案的最小花费

$f[i,1]$:在点 i 不摆放警卫,且被子结点看到的所有摆放方案的最小花费

$f[i,2]$:在点 i 摆放警卫的所有方案的最小花费

状态转移

$f[i,0]=∑min(f[j,1],f[j,2])$
$f[i,2]=∑min(f[j,0],f[j,1],f[j,2])$
$f[i,1]=min(f[k,2]+∑_{j≠k}min(f[j,1],f[j,2]))$

计算$f[i,1]$时,先把所有儿子的$min(f[j,1],f[j,2])$的总和 $sum$ 计算出来,当使用第 $k$ 个儿子放警卫时,把第 $k$ 个儿子的$min(f[k,1],f[k,2])$ 减去,便得到了 $∑_{j≠k}min(f[j,1],f[j,2])$

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

using namespace std;

const int N = 1510;

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

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

void dfs(int u)
{
    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(min(f[j][0], f[j][1]), f[j][2]);
        sum += min(f[j][1], f[j][2]);
    }

    f[u][1] = 1e9;
    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[u][1] = min(f[u][1], sum - min(f[j][1], f[j][2]) + f[j][2]);
    }
}

int main()
{
    cin >> n;

    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ )
    {
        int id, cost, cnt;
        cin >> id >> cost >> cnt;
        w[id] = cost;
        while (cnt -- )
        {
            int ver;
            cin >> ver;
            add(id, ver);
            st[ver] = true;
        }
    }

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

    dfs(root);

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

    return 0;
}


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

思路

该题与没有上司的舞会极其类似

  • 没有上司的舞会:每条边上最多选择一个点,求最大权值

  • 战略游戏:每条边上最少选择一条点,求最小权值

状态表示

  • f[u][0]:所有以u为根的子树中选择,并且不选u这个点的方案
  • f[u][1]:所有以u为根的子树中选择,并且选u这个点的方案
  • 属性:Min

状态计算

当前u结点不选,子结点一定选
($s_i$代表$u$的子节点们)

  • $f[u][0] = \sum f[s_i, 1]$
  • $f[u][1] = \sum min(f[s_i, 0], f[s_i, 1])$
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1510;

int e[N], ne[N], h[N], idx;
int f[N][2];
bool st[N];
int n;

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

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

    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        dfs(j);
        f[u][0] += f[j][1];
        f[u][1] += min(f[j][0], f[j][1]);
    }

}

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

        int cnt, id;
        for(int i = 0; i < n; i ++){
            scanf("%d:(%d)", &id, &cnt);
            while(cnt --){
                int ver;
                scanf("%d", &ver);
                add(id, ver);
                st[ver] = true;
            }
        }
        int root = 0;
        while(st[root]) root ++;
        dfs(root);
        printf("%d\n", min(f[root][0], f[root][1]));
    }

    return 0;
}


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

状态表示

  • f[u][j]:表示所有以u为树根的子树中选,选j条边的最大价

状态计算

f[u][j] = max(f[u][j], f[u][j - 1 - k] + f[son][k]+ w[i])

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

using namespace std;

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

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

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

void 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; j -- )
            for (int k = 0; k + 1 <= j; k ++ )
                f[u][j] = max(f[u][j], f[u][j - k - 1] + f[e[i]][k] + w[i]);
    }
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    dfs(1, -1);

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

    return 0;
}



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

思路

能转换的两个数字连一条边, 这里可以连有向边, 因为这样连父节点永远比儿子结点要小, 可以直接从1开始dfs

步骤

  • 把每个数的约数之和用筛法筛出来,复杂度是$O(nlogn)$, 试除法是$O(n \sqrt{n})$
  • 若某个数的约数之和小于本身, 则可以连一条边
  • 再次和第一题树的最长路径一样, res = max(res, d1 + d2)
#include<iostream>
#include<cstring>

using namespace std;

const int N = 100010;

int h[N], e[N], ne[N], idx;
int n;
int sum[N];
int res;

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int dfs(int u){
    int d1 = 0, d2 = 0;
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        int d = dfs(j) + 1;
        if(d > d1) d2 = d1, d1 = d;
        else if(d > d2) d2 = d;
    }

    res = max(res, d1 + d2);

    return d1;
}

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

    cin >> n;

    for(int i = 1; i <= n; i ++)
        for(int j = 2; j <= n / i; j ++){
            sum[i * j] += i;
        }

    for(int i = 2; i <= n; i ++)
        if(sum[i] < i) 
            add(sum[i], i);
    dfs(1);

    cout << res << endl;
}


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

思路

此题目需要每个点的向下最长和向上最长

  1. 当前点向下求最长 与上题一样
  2. 当前点向上求最长:
    分为两种: 向上的向上
    $\quad$ $\quad$$\quad$ $\quad$ 向上的向下: 此处又有两种情况:(1)它的向下最长过当前点 (2)它的向下最长不过当前点

下面放三张图理解向上求最长

Snipaste_2021-07-19_00-13-24.png

Snipaste_2021-07-19_00-21-06.png

Snipaste_2021-07-19_00-18-54.png

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

using namespace std;

const int N = 10010, M = N * 2, INF = 0x3f3f3f3f;

int n;
int h[N], e[M], w[M], ne[M], idx;
//该点向下走的最大值,该点向下走的次大值
//该点向下走的最大值所经过的儿子结点, 该点向上走的最大值
int d1[N], d2[N], p1[N], up[N];
//是否是叶子结点
bool is_leaf[N];

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

//通过儿子结点更新父亲
//和上题一样, 求该点向下走的最大值和次大值
int dfs_d(int u, int father)
{
    d1[u] = d2[u] = -INF;
    for (int i = h[u]; i != -1; 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;
            p1[u] = j;
        }
        else if (d > d2[u]) d2[u] = d;
    }

    if (d1[u] == -INF)
    {
        d1[u] = d2[u] = 0;
        is_leaf[u] = true;
    }

    return d1[u];
}

//注意dfs顺序:通过父节点更新儿子
//求该点向上走的最大值, 分两种情况 1.p1[u] == j 2.p1[u] != j 代码中取max一步操作即可
void dfs_u(int u, int father)
{
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;

        if (p1[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()
{
    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 res = d1[1];
    for (int i = 2; i <= n; i ++ )
        if (is_leaf[i]) res = min(res, up[i]);
        else res = min(res, max(d1[i], up[i]));

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

    return 0;
}