头像

题目多做就行

TYUT




在线 


最近来访(76)
用户头像
qujunyi
用户头像
weak_like_old_time
用户头像
1900-
用户头像
铃兰の顶点
用户头像
阿吉迷得牛炖咖喱略
用户头像
烧魔芋
用户头像
李三思
用户头像
rainchen
用户头像
whlbest
用户头像
zx_explorer
用户头像
ylqhe001
用户头像
吴子涵
用户头像
自律
用户头像
TheGiao
用户头像
2079512280
用户头像
icebreaker
用户头像
0x5A48
用户头像
cxposition
用户头像
NBxiang
用户头像
PDX

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

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

using namespace std;

const int N = 35;

int f[N][10];
/*
思路相差无几, 认真点!
*/
void init()
{
    for (int i = 0; i <= 9; i ++ )
        if (i != 4)
            f[1][i] = 1;

    for (int i = 1; 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)
{
    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 ++ )
        {
            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

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

using namespace std;

const int N = 15, M = 110;

int l, r, P;
int f[N][10][M];//填了i位数字, 最高位是j, 所有位数和mod(sum, P)的余数为k!! 

int mod(int x, int y)
{
    return (x % y + y) % y; //c++中mod会得到负数!! 
}

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 u)
{
    if (!u) return 1;

    int res = 0;
    int last = 0;
    vector<int> nums;
    while (u) nums.push_back(u % 10), u /= 10;

    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;//这里统计的是每位数之和的mod, 所以last记录的是前面的所有位数的和!!! 

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

    return res;
}

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

    return 0;
}


活动打卡代码 AcWing 1083. Windy数

#include <iostream>
#include <vector>

using namespace std;

const int N = 11;

int f[N][N];
/*
思路与前面相差无几!!简单 
*/
void init()
{
    for (int i = 0; i <= 9; i ++ ) f[i][1] = 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[j][i] += f[k][i - 1];
}

int dp(int u)
{
    if (u == 0) return 0;

    vector<int> nums;
    int last = -2;
    int res = 0;

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

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

        //用有前导0的去算没有前导0的!!! 
        for (int j = i == nums.size() - 1; j < x; j ++ )
        {
            if (abs(j - last) >= 2)
                res += f[j][i + 1];
        }

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

        if (!i) res ++;
    }   

    //用有前导0的去算没有前导0的!!! 
    for (int j = 1; j <= nums.size() - 1; j ++ )
            for (int k = 1; k <= 9; k ++ )
                res += f[k][j];

    return res;
}

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

    return 0;   
}


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

#include <iostream>
#include <vector>

using namespace std;

const int N = 15;

int f[N][N];//以i开头的, 有j位数字的非递减数个数!! 

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

    //这样一个个数可以由长度由小到大推出来!! 很快呀!! 
    for (int i = 2; i <= N; i ++ )
        for (int j = 0; j <= 9; j ++ )
            for (int k = j; k <= 9; k ++ )
                f[j][i] += f[k][i - 1];
}

//这里求的是0 - u的个数!!! 
int dp(int u)
{
    if (!u) return 1;//如果是0的话确实0本身就满足要求, 如果不特判的话下面的vector中就没有数字!! 返回结果就是0!!! 

    vector<int> nums;
    int res = 0;
    int last = 0;

    while (u) nums.push_back(u % 10), u /= 10;//倒除法! 

    for (int i = nums.size() - 1; i >= 0; i -- )
    {
        //选last~num[i] - 1 
        for (int j = last; j <= nums[i] - 1; j ++ )
            res += f[j][i + 1];//开头比这个数开头小的情况一定满足条件 !!

        //可以的话选num[i]!!  相当于子问题划分了!!这里思维魔鬼了!!认真想!!! 
        if (nums[i] >= last)
            last = nums[i];
        else break;

        //如果没有break, 证明这个数本身满足要求!!然后加一下完事了!! 
        if (!i) res ++;
    }

    return res;
}

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


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

#include <iostream>
#include <vector>

using namespace std;

const int N = 35;

int l, r, 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];   
}

//这里求的是0 - u中的满足1为K, 其它全为0的  数的个数
//这里是在转化进制之后做的计算!!! 
int dp(int u)
{
    if (!u) return 0;
    vector<int> nums;
    while (u) nums.push_back(u % B), u /= B;//倒除法求N进制数, 别还给老师了! 

    int res = 0, last = 0;
    for (int i = nums.size() - 1; i >= 0; i -- )
    {
        int x = nums[i];
        if (x)//如果>1的话证明可以有左边 
        {
            res += f[i][K - last];//这一位取0时候的个数 
            if (x > 1) 
            {
                //这一位取一时的个数 
                if (K - last - 1 >= 0) res += f[i][K - last - 1];
                break;//右边没有, 因为右边是填x的情况, 但是题目只要0/1所以直接不计算这个子树了!! 
            }
            else
            {
                last ++;
                if (last > K) break;//一定是">K"再去break, 因为下面还要去特判下最后情况!! 
            }
        }
        //如果填到最后一个位置&&这个位置以及之前已经填了K个1, 证明合法的!!! 
        if (!i && K == last) res ++;//特判下最右下的是不是合法的!! 
    }
    return res;     
}

int main()
{
    cin >> l >> r >> K >> B;
    init();

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

    return 0;
}


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

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1510;

int n;
int h[N], e[N], ne[N], idx;
int w[N];
bool st[N];
int f[N][3];
/*
状态机: 如果递推方程搞不出来, 就多加几个状态或者多加一维!!!
        这样能够很好的将所以情况搞出来!!! 
*/
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];
    for (int i = h[u]; ~i; i = ne[i])
    {
        int son = e[i];
        dfs(son);
        f[u][0] += min(f[son][1], f[son][2]);
        f[u][2] += min(min(f[son][0], f[son][1]), f[son][2]);
    }

    f[u][1] = 0x3f3f3f3f;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int son = e[i];
        //递推方程自己认真思考下!!! 
        f[u][1] = min(f[u][1], f[son][2] + f[u][0] - min(f[son][1], f[son][2]));
    }
}

int main()
{
    cin >> n;

    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ )
    {
        int id, cost, cnt, x;
        cin >> id >> cost >> cnt;
        w[id] = cost;

        while (cnt -- )
        {
            cin >> x;
            add(id, x);
            st[x] = true;   
        }
    }

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

    dfs(root);

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

    return 0;   
}


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

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1510;

int n;
int h[N], e[N], ne[N], idx;
int f[N][2];
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][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 (cin >> n)
    {
        memset(st, 0 , sizeof st);
        memset(f, 0, sizeof f);
        memset(h, -1, sizeof h);
        idx = 0;//注意这个恢复原装很容易漏下的!!!记住了!!! 
        string str;
        int root = 1;
        for (int i = 0; i < n; i ++ )
        {
            cin >> str;
            int l = str.find('('), r = str.find(')');
            int mao = str.find(':');

            int a = stoi(str.substr(0, mao));
            int count = stoi(str.substr(l + 1, r - l - 1));

            for (int j = 0; j < count; j ++ )
            {
                int x;
                cin >> x;
                add(a, x);
                st[x] = true;
            }
        }

        for (int i = 0; i < n; i ++ )
            if (!st[i])
            {
                root = i;
                break;
            }

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



#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

int n, m;
int h[N], e[N], ne[N], idx;
int v[N], w[N];
int f[N][N];
/*
本题 : dfs出子树的信息 + 对子树的信息搞一下分组背包 (同时进行)
*/
void dfs(int u)
{
    for (int i = h[u]; ~i; i = ne[i])//一共有几个子节点就有几个组!! 
    {
        dfs(e[i]);//将子节点的数据计算出来!! 
        for (int j = m - v[u]; j >= 0; j -- )//枚举这个组中怎么选比较好!!!
            for (int k = 1; k <= j; k ++ )//这里的DP不包含根节点的值!! 
                f[u][j] = max(f[u][j], f[e[i]][k] + f[u][j - k]);//这里省略了一维, 省略了从前i个子树中选择!!所以体积从大到小枚举!!! 
    }

    //把根节点加上!! 
    for (int i = m; i >= v[u]; i -- ) f[u][i] = f[u][i - v[u]] + w[u];
    for (int i = 0; i < v[u]; i ++ ) f[u][i] = 0;//放不下根节点就是0!! 
}

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

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);

    int root;
    for (int i = 1; i <= n; i ++ )
    {
        int c;
        cin >> v[i] >> w[i] >> c;
        if (c == -1)
        {
            root = i;
            continue;
        }
        add(c, i);
    }    

    dfs(root);

    cout << f[root][m] << endl;

    return 0;
}


活动打卡代码 AcWing 524. 愤怒的小鸟

#include <iostream>
#include <cmath>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;

const int N = 18, M = 1 << N;
const double eps = 1e-8;

int T;
int n, m;
PDD q[N];//存每个点 
int f[M];//每个状态用的抛物线最少个数 
int p[N][N];//两个点的抛物线可以穿过哪些点 

int cmp(double x, double y)//浮点数判断大小 
{
    if (fabs(x - y) < eps) return 0;
    else if (x < y) return -1;
    return 1;
}
/*
状态压缩技巧 : 点的编号从0开始比较好, 后面移位的时候正好方便!! 
与前面背包不同 : 背包是大找小!
                 状压是小更大! 
*/

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        cin >> n >> m;
        for (int i = 0; i < n; i ++ ) cin >> q[i].x >> q[i].y;

        memset(p, 0, sizeof p);//多组测试数据, 注意了! 
        for (int i = 0; i < n; i ++ )
        {
            p[i][i] = 1 << i;//题中保证没有重复的点, 所以两点同为本身只能穿过自己!!! 
            for (int j = 0; j < n; j ++ )
            {
                double x1 = q[i].x, y1 = q[i].y;
                double x2 = q[j].x, y2 = q[j].y;
                if (!cmp(x1, x2)) continue;//不符合抛物线要求, 穿过个数为0 
                double a = (y1 / x1 - y2 / x2) / (x1 - x2);
                double b = y1 / x1 - a * x1;

                if (cmp(a, 0) >= 0) continue;//>=0就不能作为抛物线!! 
                int state = 0;
                //预处理所以穿过的抛物线 
                for (int k = 0; k < n; k ++ )
                {
                    double x = q[k].x, y = q[k].y;
                    if (!cmp(a * x * x + b * x, y)) state += 1 << k;
                }
                p[i][j] = state;//穿过的点编号用状态压缩成一个数 
            }
        }

        memset(f, 0x3f, sizeof f);
        f[0] = 0;//没有穿过一个点, 所以需要的抛物线为0 
        for (int i = 0; i + 1 < 1 << n; i ++ )//向后更新, 所以从0开始 
        {
            int x = 0;
            for (int j = 0; j < n; j ++ )
                if ((i >> j & 1) == 0)//挑一个没有被穿过的抛物线给它穿过 
                {
                    x = j;
                    break;//因为一个点最后一定属于一个抛物线, 先后没关系! 
                }

            //可以被转移的状态跟新计算一下!! 
            for (int j = 0; j < n; j ++ )
                f[i | p[x][j]] = min(f[i | p[x][j]], f[i] + 1);
        }

        cout << f[(1 << n) - 1] << endl;
    }

    return 0;
}



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

using namespace std;

typedef long long LL;

const int N = 55, M = 35, INF = 1e9;

int n;
int w[N];
LL f[N][N][M];

void add(LL a[], LL b[])
{
    static LL c[M];
    memset(c, 0, sizeof c);
    for (int i = 0, t = 0; i < M; i ++ )
    {
        t += a[i] + b[i];
        c[i] = t % 10;
        t /= 10;
    }
    memcpy(a, c, sizeof c);
}

void mul(LL a[], LL b)
{
    static LL c[M];
    memset(c, 0, sizeof c);
    LL t = 0;
    for (int i = 0; i < M; i ++ )
    {
        t += a[i] * b;
        c[i] = t % 10;
        t /= 10;
    }
    memcpy(a, c, sizeof c);
}

int cmp(LL a[], LL b[])
{
    for (int i = M - 1; i >= 0; i -- )
        if (a[i] > b[i]) return 1;
        else if (a[i] < b[i]) return -1;
    return 0;
}

void print(LL a[])
{
    int k = M - 1;
    while (k && !a[k]) k -- ;
    while (k >= 0) cout << a[k -- ];
    cout << endl;
}

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

    LL temp[M];
    for (int len = 3; len <= n; len ++ )
        for (int l = 1; l + len - 1 <= n; l ++ )
        {
            int r = l + len - 1;
            f[l][r][M - 1] = 1;
            for (int k = l + 1; k < r; k ++ )
            {
                memset(temp, 0, sizeof temp);
                temp[0] = w[l];
                mul(temp, w[k]);
                mul(temp, w[r]);
                add(temp, f[l][k]);
                add(temp, f[k][r]);
                if (cmp(f[l][r], temp) > 0)
                    memcpy(f[l][r], temp, sizeof temp);
            }
        }

    print(f[1][n]);

    return 0;
}