Apple Tree

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

using namespace std;

const int N = 100010;

int t[N];
int l[N], r[N], deep = 1;
int n, m;
int h[N], e[N * 2], ne[N * 2], idx = 1;
int sum[N];

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

void dfs(int u) {
    l[u] = deep;

    for (int i = h[u]; i != -1; i = ne[i]) {

        int j = e[i];

        if (l[j])
            continue;
        deep ++ ;
        dfs(j);
    }

    r[u] = deep;
}

int lowbit(int x) {
    return x & -x;
}

void add_tree(int x, int k) {
    for ( ; x <= n; x += lowbit(x))

        t[x] += k;
}

int ask(int x) {
    int res = 0;

    for ( ; x; x -= lowbit(x))

        res += t[x];
    return res;
}

int main() {
    memset(h, -1, sizeof h);
    memset(sum, 1, sizeof sum);
    scanf("%d", &n);

    for (int i = 1; i < n; i ++ ) {

        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }

    dfs(1);

    for (int i = 1; i <= n; i ++ )

        add_tree(i, 1);
    scanf("%d", &m);

    while (m -- ) {
        char op[2];
        int x;
        scanf("%s%d", op, &x);

        if (op[0] == 'C') {
            if (sum[x] == 0)
                add_tree(l[x], 1);
            else
                add_tree(l[x], -1);
            sum[x] = !sum[x];
        } else
            printf("%d\n", ask(r[x]) - ask(l[x] - 1));
    }

    return 0;
}

最短路

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

using namespace std;

const int N = 110;

#define INF 0x3f3f3f3f

int dist[N];
bool st[N];
int n, m;
int g[N][N];

int dijkstra() {
    memset(st, false, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 1; i < n; i ++ ) {

        int t = -1;

        for (int j = 1; j <= n; j ++ )

            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        st[t] = true;

        for (int j = 1; j <= n; j ++ )

            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }

    return dist[n];
}

int main() {
    while (~scanf("%d%d", &n, &m)) {
        if (n == 0 && m == 0)
            break;
        memset(g, 0x3f, sizeof g);

        while (m -- ) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            g[a][b] = g[b][a] = min(g[a][b], c);
        }

        printf("%d\n", dijkstra());
    }

    return 0;
}

不要62

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

using namespace std;

const int N = 1e6 + 10;

int s[N];
int l, r;

int judge(int x) {
    while (x) {
        int y = x;

        if (y % 10 == 4 || y % 100 == 62)
            return 0;
        x /= 10;
    }

    return 1;
}

int main() {
    s[1] = 1;

    for (int i = 2; i <= N; i ++ )

        s[i] = s[i - 1] + judge(i);

    while (~scanf("%d%d", &l, &r)) {
        if (l == 0 && r == 0)
            break;
        printf("%d\n", s[r] - s[l - 1]);
    }

    return 0;
}

数位dp

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

using namespace std;

const int N = 10;

int f[N][N]; // f[i][j] 表示最高位是j的i位数中，满足条件的数的数量
int digit[N];
int l, r;

int sum(int n) {
    int len = 0, res = 0;

    while (n) {
        digit[++ len] = n % 10;
        n /= 10;
    }

    digit[len + 1] = 0;

    for (int i = len; i >= 1; i -- ) {

        for (int j = 0; j < digit[i]; j ++ )

            if (j != 4 && !(j == 2 && digit[i + 1] == 6))
                res += f[i][j];

        if (digit[i] == 4 || (digit[i] == 2 && digit[i + 1] == 6))
            break;
    }

    return res;
}

int main() {
    f[0][0] = 1;

    for (int i = 1; i <= 7; i ++ )

        for (int j = 0; j <= 9; j ++ )

            for (int k = 0; k <= 9; k ++ )

                if (j != 4 && !(j == 6 && k == 2))
                    f[i][j] += f[i - 1][k];

    while (~scanf("%d%d", &l, &r)) {
        if (l == 0 && r == 0)
            break;
        printf("%d\n", sum(r + 1) - sum(l));
    }

    return 0;
}

Milking Time

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

using namespace std;

const int N = 1010;

int f[N]; // f[i]表示以第i个时间段结尾的最大产量
int n, m, R;

struct node {
    int l, r, w;
    bool operator < (const node &t) const {
        if (l != t.l)
            return l < t.l;
        else if (r != t.r)
            return r < t.r;
    }
} a[N];

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

    for (int i = 1; i <= m; i ++ )

        scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].w);
    sort(a + 1, a + 1 + m);

    for (int i = 1; i <= m; i ++ ) {

        f[i] = a[i].w;

        for (int j = 1; j < i; j ++ )

            if (a[j].r + R <= a[i].l)
                f[i] = max(f[i], f[j] + a[i].w);
    }

    int res = 0;

    for (int i = 1; i <= m; i ++ )

        res = max(res, f[i]);
    printf("%d\n", res);
    return 0;
}

确定比赛名次

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <functional>

using namespace std;

const int N = 510;

int n, m;
int h[N], e[N], ne[N], idx;
int in[N];
int ans[N], pos;

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

void topsort() {
    priority_queue<int, vector<int>, greater<int>> teap;

    for (int i = 1; i <= n; i ++ )

        if (!in[i])
            teap.push(i);

    while (teap.size()) {
        int t = teap.top();
        teap.pop();
        ans[pos ++ ] = t;

        for (int i = h[t]; i != -1; i = ne[i]) {

            int j = e[i];

            if (-- in[j] == 0)
                teap.push(j);
        }
    }
}

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

        while (m -- ) {
            int a, b;
            scanf("%d%d", &a, &b);
            add(a, b);
            in[b] ++ ;
        }

        topsort();

        for (int i = 0; i < pos; i ++ )

            if (i != pos - 1)
                printf("%d ", ans[i]);
            else
                printf("%d\n", ans[i]);
    }

    return 0;
}

A计划

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

using namespace std;

const int N = 20;

char mp[2][N][N];
int n, m, time;
bool flag;
bool st[2][N][N];

int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};

struct node {
    int x, y, z;
    int step;
};

bool check(int x, int y, int z) {
    if (x < 0 || y < 0 || x >= n || y >= m)
        return false;

    if (st[z][x][y])
        return false;

    if (mp[z][x][y] == '*')
        return false;

    if (mp[z][x][y] == '#' && mp[!z][x][y] == '*')
        return false;

    if (mp[z][x][y] == '#' && mp[!z][x][y] == '#')
        return false;
    return true;
}

void bfs() {
    node One, next;
    queue<node> q;
    One.x = One.y = One.z = One.step = 0;
    q.push(One);
    st[0][0][0] = true;

    while (q.size()) {
        auto t = q.front();
        q.pop();

        if (t.step > time)
            return;

        if (mp[t.z][t.x][t.y] == 'P') {
            flag = true;
            return;
        }

        for (int i = 0; i < 4; i ++ ) {

            next.x = t.x + dx[i], next.y = t.y + dy[i];
            next.z = t.z;

            if (check(next.x, next.y, next.z)) {
                if (mp[next.z][next.x][next.y] == '#')
                    next.z = !next.z;
                st[next.z][next.x][next.y] = true;
                next.step = t.step + 1;
                q.push(next);
            }
        }
    }
}

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

    while (T -- ) {
        memset(st, false, sizeof st);
        scanf("%d%d%d", &n, &m, &time);

        for (int i = 0; i < 2; i ++ )

            for (int j = 0; j < n; j ++ )

                for (int k = 0; k < m; k ++ )

                    cin >> mp[i][j][k];
        flag = false;
        bfs();

        if (!flag)
            puts("NO");
        else
            puts("YES");
    }

    return 0;
}

开门人和关门人

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

using namespace std;

struct node {
    string id, come, go;
};

vector<node> v;
node x;

bool cmp1(node A, node B) {
    return A.come < B.come;
}

bool cmp2(node A, node B) {
    return A.go > B.go;
}

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

    while (T -- ) {
        v.clear();
        int m;
        scanf("%d", &m);

        while (m -- ) {
            cin >> x.id >> x.come >> x.go;
            v.push_back(x);
        }

        sort(v.begin(), v.end(), cmp1);
        cout << v[0].id << ' ';
        sort(v.begin(), v.end(), cmp2);
        cout << v[0].id << endl;
    }

    return 0;
}