头像

Kue

烟台大学




离线:18小时前


活动打卡代码 AcWing 1593. 整数分解

Kue
18小时前

核心:完全背包问题,m 是价值总和, n是体积 0~192, j是选取k个以内

dp方案的反向求解

dp分析思路非常重要

拓展训练:背包问题具体方案

https://www.acwing.com/problem/content/12/

#include <cstring>
#include <iostream>
#include <math.h>
using namespace std;

const int N = 410;
int f[21][N][N];
int n, k, p;
int main()
{
    cin >> n >> k >> p;
    memset(f, -0x3f, sizeof f);
    int m;
    f[0][0][0] = 0;
    for(m = 1; ; m++)
    {
        int v = pow(m, p);
        if (v > n) break;
        for(int i = 0; i <= n; i++)
        {
            for(int j = 0; j <= k; j++)
            {
                f[m][i][j] = f[m - 1][i][j];
                if (i >= v && j) // 一定要大于+等于
                {
                    f[m][i][j] = max(f[m][i - v][j - 1] + m, f[m][i][j]);
                }
            }
        }
    }
    m--;
    if(f[m][n][k] < 0) puts("Impossible");
    else
    {
        printf("%d = ", n);
        bool f1 = true;
        while (m)
        {
            int v = pow(m, p);
            while (f[m][n - v][k - 1] + m >= f[m - 1][n][k])
            {
                if (f1) f1 = false;
                else printf(" + ");
                printf("%d^%d", m, p);
                n -= v;
                k --;
            }
            m--;
        }

    }
}



Kue
2天前

Sexy primes are pairs of primes of the form (p, p+6), so-named since “sex” is the Latin word for “six”. (Quoted from http://mathworld.wolfram.com/SexyPrimes.html)

Now given an integer, you are supposed to tell if it is a sexy prime.

Input Specification:
Each input file contains one test case. Each case gives a positive integer N (≤10).

Output Specification:
For each case, print in a line Yes if N is a sexy prime, then print in the next line the other sexy prime paired with N (if the answer is not unique, output the smaller number). Or if N is not a sexy prime, print No instead, then print in the next line the smallest sexy prime which is larger than N.

Sample Input 1:
47
Sample Output 1:
Yes
41
Sample Input 2:
21
Sample Output 2:
No
23

#include <cstring>
#include <iostream>

using namespace std;
const int N = 110;
bool res = true;

bool is_prime(int x)
{
    for(int i = 2; i <= x / i; i++)
    {
        if (x % i == 0) return false;
    }
    return true;
}
int check(int m)
{   
    if (is_prime(m))
    {
        bool f1 = is_prime(m - 6);
        bool f2= is_prime(m + 6);
        if (f1) return m - 6;
        else if (f2) return m + 6;
        else{
            m++;
            res = false;
            while(true)
            {
                bool f1 = is_prime(m);
                bool f2 = is_prime(m - 6);
                bool f3 = is_prime(m + 6);
                if (f1 && f2) return m;
                else if (f1 && f2) return m;
                m++;
            }
        }
    }else{
        m++;
        res = false;
        while(true)
        {
            bool f1 = is_prime(m);
            bool f2 = is_prime(m - 6);
            bool f3 = is_prime(m + 6);
            if (f1 && f2) return m;
            else if (f1 && f2) return m;
            m++;
        }
    }
}

int main()
{
    int m;
    cin >> m;
    int k = check(m);
    if (res) puts("Yes");
    else puts("No");
    printf("%d", k);
}



Kue
2天前

英语词汇 - 数学篇

digit n. 数字
例句: “Forever number” is a positive integer A with K digits
例句: google招聘
a URL consisting of the first 10-digit prime found in consecutive digits of the natural constant e

consecutive adj. 连续的
例句: The manufacturing economy contracted for the sixth consecutive month.
integer n. 整数

meanings n. 含义

sexy adj 性感的
例句: Sexy primes are pairs of primes of the form (p, p+6)

PP奶核心句
fatter panda can have more milk
each panda can only compare with its neighbor(s)
It is only when another bowl of milk is at least 100 ml more than its own that a panda can sense the difference




Kue
2天前

核心:判定买的地是连续的,需要用前缀和算法,由于数据量较大,需要剪枝

#include <iostream>
#include <cstring>

using namespace std;
const int N = 10010;
int p[N];

int main()
{
    int m, sum;
    cin >> m >> sum;
    for(int i = 1; i <= m; i++) 
    {
        cin >> p[i];
        p[i] = p[i] + p[i - 1];
    }
    int cnt = 0;
    for(int i = 0; i < m; i++)
    {
        for(int j = i + 1; j <= m; j++)
        {
            //printf("%d %d %d\n", p[j] - p[i], p[j], p[i]);
            if (p[j] - p[i] <= sum) cnt++;
            else break;
        }
    }
    printf("%d", cnt);
}



Kue
2天前

核心:从左往右遍历,找递增序列,从右往左遍历,找递增序列,输出两者最大值

本质:熊猫重的喝的奶要比别人至少多100ml

搜狗截图20201129192538.png

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10010;
int p[N], l[N], r[N];

int main()
{
    int m, num = 2, sum = 0;
    cin >> m;
    for(int i = 0; i < m; i++) cin >> p[i];
    l[0] = num;
    for(int i = 1; i < m; i++)
    {
        if (p[i] > p[i - 1]) l[i] = l[i - 1] + 1;
        else if (p[i] == p[i - 1]) l[i] = l[i - 1];
        else l[i] = 2;
    }
    num = 2;
    r[m - 1] = num;
    for (int i = m - 2; i >= 0; i--)
    {
        if (p[i] > p[i + 1]) r[i] = r[i + 1] + 1;
        else if (p[i] == p[i + 1]) r[i] = r[i + 1];
        else r[i] = 2;
    }

    for(int i = 0; i < m; i++)
    {
        sum += max(l[i], r[i]);
    }
    printf("%d", sum * 100);
}


活动打卡代码 AcWing 1539. 等重路径

Kue
3天前

核心:dfs来搜索每一条可能的路径,最后权值相同,将路径copy

拓展:vector[HTML_REMOVED]> ans; 通过ans来将vector内部排序,特别好用

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 110, M = 2 * N;
int e[M], ne[M], h[N], w[M], cnt;
int s;
vector<int> res;
vector<vector<int>> ans;
void add(int a, int b, int c, int d)
{
    e[cnt] = b, ne[cnt] = h[a], w[a] = c, w[b] = d, h[a] = cnt++;
}

void dfs(int u, int x)
{
    bool f = true;
    res.push_back(w[u]);
    if (x > s)
    {
        res.pop_back();
        return;
    }
    for(int i = h[u]; ~i; i = ne[i])
    {
        int v = e[i];
       // res.push_back(w[v]);
        dfs(v, x + w[v]);
       // res.pop_back();
        f = false;
    }
    if (f)
    {
        if (x == s)
        {
            ans.push_back(res);
        }
    }
    res.pop_back();

}
int main()
{
    int m, n, x, y, z;
    cin >> m >> n >> s;
    vector<int> vc(m);
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i++) cin >> vc[i];
    for(int i = 0; i < n; i++)
    {
        cin >> x >> y;
        while (y--)
        {
            cin >> z;
            add(x, z, vc[x], vc[z]);
        }
    }
    dfs(0, vc[0]);
    sort(ans.begin(), ans.end(), greater<vector<int>>());
    for(auto t : ans)
    {
        printf("%d", t[0]);
        for(int i = 1; i < t.size(); i++)
        {
            printf(" %d", t[i]);
        }
        puts("");
    }
}


活动打卡代码 AcWing 1576. 再次树遍历

Kue
5天前

核心:就是看出规律,将push分成两个层次,push前是push,左儿子,push前是pop,右儿子

#include <iostream>
#include <cstring>
#include <stack>
#include <queue>
using namespace std;
const int N = 40;
int l[N], r[N];
bool f1 = true;
void post(int s)
{
    if (l[s] != -1) post(l[s]);
    if (r[s] != -1) post (r[s]);

    if (f1) f1 = false;
    else printf(" ");
    printf("%d", s);
}
int main()
{
    int m;
    cin >> m;
    string str;
    memset(l, -1, sizeof l);
    memset(r, -1, sizeof r);
    bool flag = true;
    int root = 0, s, type = 1;
    stack<int> stk;
    for(int i = 1; i <= 2 * m; i++)
    {
        cin >> str;
        //cout << str;
        if (str == "Push")
        {
            int x;
            cin >> x;


            if (flag) {
                s = x;
                flag = false;
            }else{
                if (type)
                {
                    l[root] = x;
                }else
                {
                    r[root] = x;
                }
            }
            // type放在后面
            // 防止先执行后,type一直是1
            type = 1;
            root = x;
            stk.push(x);


        }else if (str == "Pop"){
            type = 0;
            root = stk.top();
            stk.pop();
        }
    }

    post(s);
}


活动打卡代码 AcWing 1476. 数叶子结点

Kue
6天前

核心在于dfs,透传一个层级数

#include <cstring>
#include <iostream>

using namespace std;

const int N = 110;
int e[N], ne[N], h[N], cnt;
int max_dep;
int dep[N];
void add(int a, int b)
{
    e[cnt] = b, ne[cnt] = h[a], h[a] = cnt++;
}

void dfs(int u, int d)
{
    if (h[u] == -1)
    {
        dep[d]++;
        max_dep = max(max_dep, d);
        return;
    }
    for(int i = h[u]; ~i; i = ne[i])
    {
        dfs(e[i], d + 1);
    }
}
int main()
{
    int m, n;
    cin >> m >> n;
    memset(h, -1, sizeof h);
    while (n--)
    {
        int x, c, y;
        cin >> x >> c;
        while (c--)
        {
            cin >> y;
            add(x, y);
        }

    }
    dfs(1, 0);
    printf("%d", dep[0]);
    for(int i = 1; i <= max_dep; i++) printf(" %d", dep[i]);
}


活动打卡代码 AcWing 1172. 祖孙询问

Kue
9天前

核心:lca的运用,直接跳上一层是不行的

方法2 倍增法 预处理(nlogn) + 查询(logn)
⭐关键是理解二进制拼凑 在这里是怎么体现的
即在 f[x][0]!=f[y][0] 的约束下 我们能跳的最多的步数跳完后 x,y就达到了LCA的下面一层
假定我们知道 x,y出发点为第1层
LCA下一层为第12层
那么最多能跳的步数t = 12-1 = 11 = (1011)2 = 最多能跳2^3 + 2^2 + 2^0 步
所以我们就通过从大到小枚举k使得我们刚好跳11步而不能跳超过12步
但实际上我们并不知道要跳11步,所以我们可以通过f[x][0]!=f[x][0]的约束来实现
即f[x][总共>=12步] = f[y][总共>=12步] 那就不跳(不拼凑2^k)
f[x][总共<12步] != f[y][总共<12步] 那就跳(拼凑2^k)

预处理出每个点向上走2^k步的节点的父亲是谁
f[i][j] 从i开始向上走2^j步所能走到的节点 0<=j<=logn
1
/ \
2 3
/ \
4 5
/ \
6 7
f[6][0] = 4
f[6][1] = 2
f[6][2] = 空集

作者:仅存老实人

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 40010, M = 2 * N;
int e[M], ne[M], h[N], cnt;
int f[N][16], depth[N];

void add(int a, int b)
{
    e[cnt] = b, ne[cnt] = h[a], h[a] = cnt++;
}
void bfs(int s)
{
    queue<int> q;
    q.push(s);
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[s] = 1;
    while (q.size())
    {
        int u = q.front();
        q.pop();
        for(int i = h[u]; ~i; i = ne[i])
        {
            int v = e[i];

            if (depth[v] > depth[u] + 1) // 防止反向边
            {
                q.push(v);
                depth[v] = depth[u] + 1;
                f[v][0] = u;
                for(int j = 1; j <= 15; j++)
                {
                    f[v][j] = f[f[v][j - 1]][j - 1];
                }
            }

        }
    }
}

int lca(int a, int b)
{
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 15; k >= 0; k -- )
        if (depth[f[a][k]] >= depth[b])
            a = f[a][k];
    if (a == b) return a;
    for (int k = 15; k >= 0; k -- )
        if (f[a][k] != f[b][k])
        {
            a = f[a][k];
            b = f[b][k];
        }
    return f[a][0];
}
// 这种做法不可行,会超时,不懂为啥
// 应该是有一层是自己跳自己,所以得从15层一直向上
/*int lca(int a, int b)
{
    if (depth[a] < depth[b]) swap(a, b);

    while (depth[a] > depth[b])
    {
        a = f[a][0];
    }
    while (a != b)
    {
        a = f[a][0];
        b = f[b][0];
    }
    return a;
}*/
int main()
{
    int m, n, root = 0;
    cin >> m;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        if (b == -1) root = a;
        else add(a, b), add(b, a);
    }
    bfs(root);

    cin >> n;
    while (n --)
    {
        int a, b;
        cin >> a >> b;
        int res = lca(a, b);
        if (res == a) puts("1");
        else if (res == b) puts("2");
        else puts("0");
    }
}

核心,有的步数需要一下子跳一个15层,有数据4000层

核心:设置层级,除了第一次,每一次都是向上两层的级别

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 40010, M = 2 * N;
int e[M], ne[M], h[N], cnt;
int f[N][16], depth[N];

void add(int a, int b)
{
    e[cnt] = b, ne[cnt] = h[a], h[a] = cnt++;
}
void bfs(int s)
{
    queue<int> q;
    q.push(s);
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[s] = 1;
    while (q.size())
    {
        int u = q.front();
        q.pop();
        for(int i = h[u]; ~i; i = ne[i])
        {
            int v = e[i];

            if (depth[v] > depth[u] + 1) // 防止反向边
            {
                q.push(v);
                depth[v] = depth[u] + 1;
                f[v][0] = u;
                for(int j = 1; j <= 15; j++)
                {
                    f[v][j] = f[f[v][j - 1]][j - 1];
                }
            }

        }
    }
}

/*int lca(int a, int b)
{
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 15; k >= 0; k -- )
        if (depth[f[a][k]] >= depth[b])
            a = f[a][k];
    if (a == b) return a;
    for (int k = 15; k >= 0; k -- )
        if (f[a][k] != f[b][k])
        {
            a = f[a][k];
            b = f[b][k];
        }
    return f[a][0];
}*/
// 这种做法不可行,会超时,不懂为啥
// 应该是有一层是自己跳自己,所以得从15层一直向上
int lca(int a, int b)
{
    int cnt = 0;
    if (depth[a] < depth[b]) swap(a, b);

    while (depth[a] > depth[b])
    {
        a = f[a][0];
        cnt++;
        // 这里找深度的问题, 应该是有1000+的深度
        if (cnt >1000)
        {
            printf("===%d %d\n", a, f[a][0]);
            for (int k = 15; k >= 0; k -- )
            {
                if (depth[f[a][k]] >= depth[b])
                {
                    printf("----%d %d\n", a, f[a][k]);
                    a = f[a][k];

                }
            }

            break;
        }
    }
    cnt = 0;
    while (a != b)
    {
        a = f[a][0];
        b = f[b][0];
        cnt++;
        if (cnt > 10) break;
    }
    return a;
}
int main()
{
    int m, n, root = 0;
    cin >> m;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        if (b == -1) root = a;
        else add(a, b), add(b, a);
    }
    bfs(root);

    cin >> n;
    while (n --)
    {
        int a, b;
        cin >> a >> b;
        int res = lca(a, b);
        if (res == a) puts("1");
        else if (res == b) puts("2");
        else puts("0");
    }
}


活动打卡代码 AcWing 456. 车站分级

Kue
10天前

核心的思路:还是在于差分,有点需要思考

#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 2010, M = 1000010; // 为啥一百万条边
int e[M], ne[M], h[N], w[M], cnt;
int deg[N], d[N];
bool st[N];
vector<int> vc;
int m, n;
void add(int a, int b, int c)
{
    e[cnt] = b, w[cnt] = c, ne[cnt] = h[a], h[a] = cnt++;
    deg[b]++;
}
void topo_sort()
{
    queue<int> q;
    for(int i = 1; i <= m + n; i++)
    {
        if (deg[i] == 0) q.push(i);
    }
    while (q.size())
    {
        int u = q.front();
        q.pop();
        vc.push_back(u);
        for(int i = h[u]; ~i; i = ne[i])
        {
            int v = e[i];
            deg[v]--;
            if (deg[v] == 0) q.push(v);
        }
    }
}
int main()
{
    cin >> m >> n;
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n; i++)
    {
        int idx;
        cin >> idx;
        int beg = n, end = 1;
        memset(st, false, sizeof st);
        while (idx--)
        {
            int stop;
            cin >> stop;
            beg = min(beg, stop);
            end = max(end, stop);
            st[stop] = true;
        }
        int ver = m + i; // 虚拟点
        // 错误做法, k (1, m)之间
        for(int k = beg; k <= end; k++)
        {
            if (!st[k]) add(k, ver, 0);
            else add(ver, k, 1);
        }
    }
    topo_sort();
    for(int i = 1; i <= m; i++) d[i] = 1; // 为啥要全部初始化为1??, 因为不知道从哪个节点开始
    //d[vc[0]] = 1; // 这种会少算,可能有多个度为0节点
    for(int i = 0; i < vc.size(); i++)
    {
        int v = vc[i];
        for(int j = h[v]; ~j; j = ne[j])
        {
            int x = e[j];
            d[x] = max(d[x], d[v] + w[j]);
        }
    }
    int res = 0;
    for(int i = 1; i <= m; i++)
    {
        res = max(res, d[i]);
    }
    printf("%d", res);
}