头像

DriftingAE86

坏银




离线:2小时前



如题,样例通过情况为 11/12,n == 50000, m == 54997 时 TLE 了。有没有巨巨知道这是为何???

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

using namespace std;

typedef pair<int, int> PII;

const int N = 150010, M = 2 * N;
int e[M], ne[M], idx, h[N], w[M];
int n, m;

int d[N];
int siz;
PII hp[N];

void init() {
    memset(h, -1, sizeof h);
}

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

void down(int u) {
    int t = u;

    if (2 * u <= siz && hp[2 * u].first < hp[t].first) t = 2 * u;
    if (2 * u + 1 <= siz && hp[2 * u + 1].first < hp[t].first) t = 2 * u + 1;
    if (t != u) {
        swap(hp[t], hp[u]);
        down(t);
    }
}

void up(int u) {
    while (u / 2 && hp[u / 2].first > hp[u].first) {
        swap(hp[u / 2], hp[u]);
        u /= 2;
    }
}

int dijkstra() {
    memset(d, 0x3f, sizeof d);
    d[1] = 0;

    hp[1] = {0, 1};
    siz = 1;
    while (siz) {
        PII t = hp[1];
        hp[1] = hp[siz--];
        down(1);

        int now = t.second, distance = t.first;


        for (int i = h[now]; ~i; i = ne[i]) {
            int next = e[i];

            if (d[next] > d[now] + w[i]) {
                d[next] = d[now] + w[i];

                hp[++siz] = {d[next], next};
                up(siz);
            }
        }
    }

    if (d[n] == 0x3f3f3f3f) return -1;
    else return d[n];
}

int main()
{
    init();
    scanf("%d%d", &n, &m);

    int x, y, z;
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }

    int ans = dijkstra();


    if (ans != -1) printf("%d\n", ans);
    else puts("-1");
}


活动打卡代码 AcWing 1477. 拼写正确

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

using namespace std;

string digits[10] = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};

int main()
{
    string s;
    getline(cin, s);

    for (int i = 0; i < 10; ++i) {
        reverse(digits[i].begin(), digits[i].end());
    }

    int length = s.size();
    int sum = 0;
    for (int i = 0; i < length; ++i) {
        sum += s[i] - '0';
    }

    string result = "";
    if (sum == 0) result = digits[0] + " ";
    while (sum) {
        int digit = sum % 10;
        sum /= 10;
        result += digits[digit] + " ";
    }
    result.erase(result.size() - 1);

    reverse(result.begin(), result.end());
    cout << result;

}


活动打卡代码 AcWing 1473. A + B 格式

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

using namespace std;

int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    int sumN = a + b;
    string s = "";
    int i = 0;
    // cout << sumN << endl;
    bool flag = false;
    if (sumN < 0) flag = true;
    sumN = abs(sumN);
    if (sumN == 0) s = "0";
    while (sumN) {
        char digit = sumN % 10 + '0';
        sumN /= 10;
        s += digit;
        ++i;
        if (i == 3) {
            i = 0;
            s += ',';
        }
    }
    if (s[s.size() - 1] == ',') {
        s.erase(s.size() - 1);
    }
    if (flag) {
        s += '-';
    }
    // cout << s << endl;
    int length = s.size();
    for (int i = length - 1; i >= 0; --i) 
        cout << s[i];
}


活动打卡代码 AcWing 1477. 拼写正确

/*
 * @Author: your name
 * @Date: 2020-11-19 00:24:35
 * @LastEditTime: 2020-11-19 00:35:24
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: /algorithm/PAT/002-1005-Spell It Right.cpp
 */
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

string digits[10] = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};

int main()
{
    string s;
    getline(cin, s);

    for (int i = 0; i < 10; ++i) {
        reverse(digits[i].begin(), digits[i].end());
    }

    int length = s.size();
    int sum = 0;
    for (int i = 0; i < length; ++i) {
        sum += s[i] - '0';
    }

    string result = "";
    if (sum == 0) result = digits[0] + " ";
    while (sum) {
        int digit = sum % 10;
        sum /= 10;
        result += digits[digit] + " ";
    }
    result.erase(result.size() - 1);

    reverse(result.begin(), result.end());
    cout << result;

}


活动打卡代码 AcWing 1217. 垒骰子

/*
 * @Author: your name
 * @Date: 2020-11-10 00:08:12
 * @LastEditTime: 2020-11-12 19:43:46
 * @LastEditors: wangziyang
 * @Description: In User Settings Edit
 * @FilePath: /algorithm/049-垒骰子.cpp
 */
/**
 * *注意理解题面:“两种垒骰子方式相同:当且仅当这两种方式中对应高度的骰子的对应数字的 朝向 都相同。”。这意味着一个合法的骰子可以旋转4次变成4种情况
 * */
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 1000000010, MOD = 1000000000 + 7, K = 6;

int n, m;

int getOp(int x) {
    if (x >= 3) return x - 3;// 注意我们假设骰子的数字是0~5
    else return x + 3;
}

void mult(int c[][K], int a[][K], int b[][K]) {
    int temp[K][K];
    memset(temp, 0, sizeof temp); // 必须对局部数组进行初始化,否则你根本不知道数组的初始值是多少。

    for (int i = 0; i < K; ++i) {
        for (int j = 0; j < K; ++j) {
            for (int t = 0; t < K; ++t) {
                temp[i][j] = (temp[i][j] + (LL)a[i][t] * b[t][j]) % MOD;
            }
        }
    }

    memcpy(c, temp, sizeof temp);
}

int main()
{
    scanf("%d%d", &n, &m);

    int a[K][K];
    for (int i = 0; i < 6; ++i) {
        for (int j = 0; j < 6; ++j) {
            a[i][j] = 4;
        }
    }

    int x, y;
    while(m--) {
        scanf("%d%d", &x, &y); // 注意我们假设骰子的数字是0~5
        x--;
        y--;
        a[x][getOp(y)] = 0;
        a[y][getOp(x)] = 0;
    }


    int fn[K][K] = { //完全可以使用 1*6 矩阵,之所以使用 6*6 是因为这样可以少自定义一个矩阵1*6 与 矩阵6*6的乘法函数
        {4, 4, 4, 4, 4, 4} // 初始化 f[0][0~5]。当只有一个骰子的时候,每种数字朝上的情况都是4种
    };
    n--; // 因为快速幂一共需要循环 n - 1 次
    while (n) {
        if (n & 1 == 1) {
            mult(fn, fn, a);
        }
        n >>= 1;
        mult(a, a, a);
    }

    int ans = 0;
    for (int i = 0; i < K; ++i) {
        ans = (ans + fn[0][i]) % MOD;
    }
    printf("%d\n", ans);
}



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

using namespace std;

typedef long long LL;

const int N = 3;
int n, m;

void mult(int c[], int a[], int b[][N]) {
    int temp[N] = {0};

    //* 用C++实现1*N矩阵 ✖️ N*N矩阵(鸡肋)
    for(int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            temp[i] = (temp[i] + (LL)a[j] * b[j][i]) % m;
        }
    }
    memcpy(c, temp, sizeof temp); //! 这里第三个参数绝对不能写c,这是C++初学者特别容易犯的一个错误
}

void mult(int c[][N], int a[][N], int b[][N]) {
    int temp[N][N] = {0};

    //* 用C++实现N*N矩阵 ✖️ N*N矩阵 (需要使用三重for循环)
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            for (int k = 0; k < N; ++k) {
                temp[i][j] = (temp[i][j] + (LL)a[i][k] * b[k][j]) % m;
            }
        }
    }

    memcpy(c, temp, sizeof temp); //! 注意这里第三个参数绝对不可以是c!
}

int main()
{
    scanf("%d%d", &n, &m);
    int f1[N] = {1, 1, 1};
    int a[N][N] = {
        {0, 1, 0},
        {1, 1, 1},
        {0, 0, 1}
    };

    n--; // 这是因为:Fn = F1 * a^(n-1)
    //* 快速幂的模板
    while (n) {
        if(n & 1 == 1) {
            mult(f1, f1, a);
        }
        n >>= 1;
        mult(a, a, a);
    }

    printf("%d\n", f1[2]);
}


活动打卡代码 AcWing 826. 单链表

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <sstream>

using namespace std;

const int N = 100010, M = 2 * N;
int e[N], ne[N], idx, head;

void init() {
    idx = 0;
    head = -1;
    memset(ne, -1, sizeof ne);
}

void add_to_head(int a) {
    e[idx] = a;
    ne[idx] = head;
    head = idx++;
}

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

void removeIt(int a) {
    ne[a] = ne[ne[a]];
}

int main()
{
    init();
    int m;
    scanf("%d", &m);

    string line;
    int k, x;
    char op;
    getline(cin, line);
    while(m--) {
        getline(cin, line);
        stringstream scin(line);
        scin >> op;

        if (op == 'H') {
            scin >> x;
            add_to_head(x);
        } else if (op == 'D') {
            scin >> k;
            if (k == 0) {
                head = ne[head];
                continue;
            }
            removeIt(k - 1);
        } else {
            scin >> k >> x;
            add(k - 1, x);
        }
    }

    for (int i = head; ~i; i = ne[i]) {
        printf("%d ", e[i]);
    }
}


活动打卡代码 AcWing 1078. 旅游规划

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

using namespace std;

const int N = 200010, M = N * 2;
int h[N], ne[M], idx, e[M];
int n;
int d1[N], d2[N]; // d1[i],d2[i] 表示以 i 为根节点,向下遍历的最大路径值 和 次大路径值
int up[N]; // up[i]:在一个树中,从i号节点向上遍历的路径长度最大值。应当等于:从父节点u出发且不经过i的最大路径值
int p1[N]; // p[i] 表示与节点i连接的所有子树中,最大的子树的根节点序号。
int maxd;

void init() {
    idx = 0;
    memset(h, -1, sizeof h);
}

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

void dfs_down(int s, int fa) {
    d1[s] += 1;
    d2[s] += 1;

    for (int i = h[s]; ~i; i = ne[i]) {
        int j = e[i];
        if (j != fa) {

            dfs_down(j, s);
            int distance = d1[j] + 1;
            if (distance > d1[s]) {
                d2[s] = d1[s], d1[s] = distance;
                p1[s] = j; // 记录以当前节点为根节点的、最大子树的根节点为哪一个
            } else {
                d2[s] = max(d2[s], distance);
            }

        }
    }

    maxd = max(maxd, d1[s] + d2[s]);

}

void dfs_up(int s, int fa) {
    for (int i = h[s]; ~i; i = ne[i]) {
        int j = e[i];
        if (j != fa) { // 因为邻接表存储的特点,防止节点s的子节点j在dfs时又遍历回j的父节点s,这样就产生回路,死循环了。

            up[j] = up[s] + 1;
            if (d1[s] + 1 > up[j] && p1[s] != j) {
                up[j] = d1[s] + 1;
            }
            if (p1[s] == j) {
                up[j] = max(up[j], d2[s] + 1);
            }

            // if (p1[s] == j) up[j] = max(up[j], d2[s] + 1);
            // else up[j] = max(up[j], d1[s] + 1);

            dfs_up(j, s);
        }

    }
}

int main()
{
    init();
    scanf("%d", &n);
    int u, v;
    for (int i = 0; i < n - 1; ++i) {
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }

    // 这里第一次调用时,第一个参数0的含义表示我们假设0号点为整个树的根节点。
    dfs_down(0, -1); // 第一遍DFS求得f[i]表示树中,树根为i的子树的最大路径值

    dfs_up(0, -1);

    // printf("%d\n", maxd);

    for (int i = 0; i < n; ++i) {
        int d[3] = {d1[i], d2[i], up[i]};
        sort(d, d + 3);
        if (d[1] + d[2] == maxd)
            printf("%d\n", i);
    }


}


活动打卡代码 AcWing 1070. 括号配对

DriftingAE86
1个月前
/**
 * 这题不能用队列来做。反例:"[(][)]"
 * */
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 110, INF = 0x7fffffff; // INF 表示 int 数据的最大值
int f[N][N];

bool comparedChar(char a, char b) {
    if (a == '[' && b == ']') return true;
    if (a == '(' && b == ')') return true;
    return false;
}

string s;

int main()
{
    cin >> s;

    int n = s.length() - 1;
    for (int len = 1; len <= s.length(); ++len) {
        for (int i = 0; i + len - 1 <= n; ++i) {
            int j = i + len - 1;
            f[i][j] = INF; // f[i][j]默认值是0,需要改成 INF,因为我们使用了min() 函数
            if (comparedChar(s[i], s[j])) {
                f[i][j] = f[i + 1][j - 1];
            }
            f[i][j] = min(f[i][j - 1] + 1, f[i][j]);
            f[i][j] = min(f[i][j], f[i + 1][j] + 1);

            for (int k = i; k < j; ++k) {
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
            }
        }
    }

    printf("%d\n", f[0][n]);
}


活动打卡代码 AcWing 1226. 包子凑数

DriftingAE86
1个月前
/**
 * *裴楚定理:整数a、b的最大公约数若不是 1,则有无数多个不能被a、b凑出来的数字;若是 1,则不能被a、b凑出来的数字个数是 (a-1)(b-1)-1
 * *设count(a,b)表示a、b不能凑出来的数字的数量。那么,一定有 count(a, b, c) <= count(a, b) 。
 * *需要快速求最大公约数,既需要使用 欧几里得求最大公约数的模板。
 * *这道题有一个“玄学”的地方:经验上,1~100不能被凑凑出来的数字最大值应该在 10000 附近
 * *我们把要凑的数字当作背包容量,把每个数字当作背包问题中的每个物品的体积。
 * *因此,我们只需要检查1~10000之间有多少个数字不能被凑出来,这就变成了完全背包问题。
 * *f(i, j) 表示考虑到第 i 个物品时,能不能凑出数字j
 * *滚动数组进行优化
 * */
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 10010;
int a[110]; // 这里每个笼中包子的数量,就相当于背包问题中每个物品的体积
bool f[N];
int n;

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

int main()
{
    scanf("%d", &n);

    int d = 0; // 表示 n 个数字的最大公约数。d 初始值为 0,因为 0 与任何数字的最大公约数都是那个数字本身。
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        d = gys(d, a[i]);
    }
    if (d != 1) { // 根据裴楚定理,n 个数字最大公约数不是 1 时,有无数多个 不能被凑出来的数字
        puts("INF");
    } else {
        f[0] = true; // 初始情况是合法的,一定要记得考虑

        for (int i = 1; i <= n; ++i) {
            for (int j = a[i]; j <= N; ++j) {
                // f[j] = f[j];
                f[j] = f[j] | f[j - a[i]];
            }
        }

        /*
            统计0~10000之间有多少个数字不能被凑出来
        */
        int cnt = 0;
        for (int i = 0; i < N; ++i) {
            if (!f[i]) cnt++;
        }

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

    }
}