Complete the Graph

题目描述

ZS the Coder has drawn an undirected graph of $n$ vertices numbered from $0$ to $n-1$ and m edges between them. Each edge of the graph is weighted, each weight is a positive integer.
The next day, ZS the Coder realized that some of the weights were erased! So he wants to reassign positive integer weight to each of the edges which weights were erased, so that the length of the shortest path between vertices $s$ and $t$ in the resulting graph is exactly $L$. Can you help him?

题意概述

给定一张连通无向图,其中所有边的权值均为自然数。要求将所有权值为$0$的边的权值变成任意一个不大于$10^{18}$的正整数,使得从$s$到$t$的最短路径的长度为$L$。
数据范围:$2 \le n \le 1000, \; 1 \le m \le 10000, \; 1 \le L \le 10^9, \; 0 \le s, t \le n-1$。

算法分析

首先将权值为$0$的边的权值变成无穷大,求一次最短路,若$s$和$t$之间的距离$dist \lt L$则无解。
若$dist=L$,则已得到可行解。
若$dist \gt L$,枚举初始权值为$0$的边,将它的权值变成$1$,求一次最短路,若$dist \le L$则说明已有可行解,把这条边的权值增加$L-dist$,即得到可行解。若所有初始权值为$0$的边都已枚举且$dist \gt L$,则说明无解。

代码

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
long long n, m, L, s, t, dist[1001], line[1001][1001];
bool flag, in[1001], sign[1001][1001];
void spfa(int p = -1, int q = -1) {
    queue<int> que;
    while (!que.empty()) que.pop();
    memset(in, false, sizeof(in));
    if (p == -1) {
        memset(dist, 0x1f, sizeof(dist));
        que.push(s), dist[s] = 0, in[s] = true;
    } else {
        if (dist[p] > dist[q]) p ^= q ^= p ^= q;
        que.push(p), in[p] = true;
    }
    while (!que.empty()) {
        long long u = que.front();
        que.pop();
        in[u] = false;
        for (int i = 0; i < n; ++i) {
            if (line[u][i] && dist[i] > dist[u] + line[u][i]) {
                dist[i] = dist[u] + line[u][i];
                if (!in[i]) que.push(i), in[i] = true;
            }
        }
    }
}
int main()
{
    cin >> n >> m >> L >> s >> t;
    for (int i = 1; i <= m; ++i) {
        long long x, y, w;
        cin >> x >> y >> w;
        line[x][y] = line[y][x] = w;
        if (!w) sign[x][y] = sign[y][x] = true;
    }
    spfa();
    if (dist[t] < L) {
        cout << "NO" << endl;
        return 0;
    } else if (dist[t] > L) {
        for (int i = 0; i < n - 1; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (sign[i][j]) {
                    line[i][j] = line[j][i] = 1;
                    sign[i][j] = sign[j][i] = false;
                    spfa(i, j);
                    if (dist[t] <= L) {
                        line[i][j] = line[j][i] = L - dist[t] + 1;
                        flag = true; break;
                    }
                }
            }
            if (flag) break;
        }
    } else flag = true;
    if (!flag) cout << "NO" << endl;
    else {
        cout << "YES" << endl;
        for (int i = 0; i < n - 1; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (line[i][j] || sign[i][j]) {
                    cout << i << ' ' << j << ' ';
                    if (line[i][j]) cout << line[i][j];
                    if (sign[i][j]) cout << (long long) 1e18;
                    cout << endl;
                }
            }
        }
    }
    return 0;
}

Choosing the Commander

题目描述

As you might remember from the previous round, Vova is currently playing a strategic game known as Rage of Empires.
Vova managed to build a large army, but forgot about the main person in the army – the commander. So he tries to hire a commander, and he wants to choose the person who will be respected by warriors.
Each warrior is represented by his personality – an integer number $p_i$. Each commander has two characteristics — his personality $p_j$ and leadership $l_j$ (both are integer numbers). Warrior $i$ respects commander $j$ only if $p_i \oplus p_j \lt l_j$ ($x \oplus y$ is the bitwise excluding OR of $x$ and $y$).
Initially Vova’s army is empty. There are three different types of events that can happen with the army:

  • 1 $p_i$ – one warrior with personality $p_i$ joins Vova’s army;
  • 2 $p_i$ – one warrior with personality $p_i$ leaves Vova’s army;
  • 3 $p_i$ $l_i$ – Vova tries to hire a commander with personality $p_i$ and leadership $l_i$.

For each event of the third type Vova wants to know how many warriors (counting only those who joined the army and haven’t left yet) respect the commander he tries to hire.

题意概述

有一个初始为空的数字集合。有三种操作:①向集合中加入一个数$p$;②从集合中删除一个数$p$;③询问集合中与$p$的异或值小于$l$的数的个数。总共进行了$q$次操作。
数据范围:$1 \le q \le 10^5, \; 1 \le p_i, l_i \le 10^8$。

算法分析

根据集合中数的二进制建立Trie树,记录下每个节点子树的大小。对于每次询问,从高到低枚举$p, l$二进制的第$k$位,用$p_k, l_k$表示。设当前走到的节点为$t$,下一位为$s$则走到节点$t_s$。若$l_k=1$,则节点$t_{p_k}$所表示的数一定小于$l$;若$l_k=0$,则节点$t_{1-p_k}$所表示的数一定大于$l$。

代码

#include <iostream>
using namespace std;
int q, o, p, l;
struct trie_tree {
    int tot = 1;
    struct node_type {
        int sum, child[2];
    } a[2000001];
    void insert(int t) {
        int r = 1; ++a[r].sum;
        for (int i = 26; i >= 0; --i) {
            if (!a[r].child[(t >> i) & 1]) a[r].child[(t >> i) & 1] = ++tot;
            r = a[r].child[(t >> i) & 1], ++a[r].sum;
        }
    }
    void remove(int t) {
        int r = 1; --a[r].sum;
        for (int i = 26; i >= 0; --i) {
            r = a[r].child[(t >> i) & 1], --a[r].sum;
        }
    }
    int find(int p, int l) {
        int r = 1, ret = 0;
        for (int i = 26; i >= 0; --i) {
            int s = (p >> i) & 1, t = (l >> i) & 1;
            if (t && a[r].child[s]) ret += a[a[r].child[s]].sum;
            if (t && a[r].child[!s]) r = a[r].child[!s];
            else if (!t && a[r].child[s]) r = a[r].child[s];
            else break;
        }
        return ret;
    }
} tree;
int main()
{
    cin >> q;
    while (q--) {
        cin >> o;
        switch (o) {
            case 1: {
                cin >> p, tree.insert(p);
                break;
            }
            case 2: {
                cin >> p, tree.remove(p);
                break;
            }
            default: {
                cin >> p >> l;
                cout << tree.find(p, l) << endl;
            }
        }
    }
    return 0;
}

Fox and Dinner

题目描述

Fox Ciel is participating in a party in Prime Kingdom. There are $n$ foxes there (include Fox Ciel). The $i$-th fox is $a_i$ years old.
They will have dinner around some round tables. You want to distribute foxes such that:

  • each fox is sitting at some table,
  • each table has at least 3 foxes sitting around it,
  • the sum of ages of any two adjacent foxes around each table should be a prime number.

If $k$ foxes $f_1, f_2, \ldots, f_k$ are sitting around table in clockwise order, then for $1 \le i \le k-1$: $f_i$ and $f_{i+1}$ are adjacent, and $f_1$ and $f_k$ are also adjacent.
If it is possible to distribute the foxes in the desired manner, find out a way to do that.

题意概述

给定$n$个数$a_i$,你需要将它们分成若干个圈,使得每个圈中至少有$3$个数,且任意两个相邻的数的和为质数。
数据范围:$3 \le n \le 200, \; 2 \le a_i \le 10000$。

算法分析

因为每个数都大于$1$,所以任意两个相邻的数必定是一奇一偶。对于任意一个奇数$a_i$和任意一个偶数$a_j$,如果$a_i+a_j$是质数,那么就由$a_i$向$a_j$连一条流量为$1$的边。由于每个数都必须与另外两个数相连,因此可以由一个假设的源点向每个奇数的点连一条流量为$2$的边,由每个偶数的点向一个假设的汇点连一条流量为$2$的边。找出这张图的最大流,如果源点连出的边和连向汇点的边全部满流则说明有解。最后遍历找出所有环即可。

代码

#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
struct edge {
    int v, f, nxt;
} e[50001];
int n, nume = 1, top, src, sink, a[202], h[202], g[202], dist[202], que[202];
bool vis[202];
vector<int> ans[201];
void add_edge(int u, int v, int f) {
    e[++nume].v = v, e[nume].f = f, e[nume].nxt = h[u], h[u] = nume;
    e[++nume].v = u, e[nume].f = 0, e[nume].nxt = h[v], h[v] = nume;
}
void bfs() {
    memset(dist, 0, sizeof(dist));
    que[1] = src, dist[src] = 1;
    int s = 0, t = 1;
    while (s < t) {
        int u = que[++s];
        for (int i = h[u]; i; i = e[i].nxt) {
            if (e[i].f && !dist[e[i].v]) {
                que[++t] = e[i].v, dist[e[i].v] = dist[u] + 1;
            }
        }
    }
}
int dfs(int u, int delta) {
    if (u == sink) return delta;
    int ret = 0;
    for (int i = g[u]; i; i = e[i].nxt) {
        if (e[i].f && dist[e[i].v] == dist[u] + 1) {
            int dd = dfs(e[i].v, min(e[i].f, delta));
            e[i].f -= dd, e[i ^ 1].f += dd;
            if (e[i].f) g[u] = i;
            delta -= dd, ret += dd;
        }
    }
    return ret;
}
int max_flow() {
    int ret = 0;
    while (1) {
        bfs();
        if (!dist[sink]) return ret;
        for (int i = 0; i <= n + 1; ++i) g[i] = h[i];
        ret += dfs(src, 1e9);
    }
}
bool is_prime(int t) {
    int k = (int) sqrt(t);
    for (int i = 2; i <= k; ++i) if (!(t % i)) return false;
    return true;
}
void find(int u, int t) {
    vis[u] = true, ans[t].push_back(u);
    for (int i = h[u]; i; i = e[i].nxt) {
        if (e[i].v && e[i].v != n + 1 && e[i].f == !(a[u] & 1) && !vis[e[i].v]) find(e[i].v, t);
    }
}
int main()
{
    cin >> n;
    src = 0, sink = n + 1;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        if (a[i] & 1) add_edge(src, i, 2);
        else add_edge(i, sink, 2);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (a[i] & 1 && !(a[j] & 1) && is_prime(a[i] + a[j])) add_edge(i, j, 1);
        }
    }
    max_flow();
    for (int i = h[0]; i; i = e[i].nxt) {
        if (e[i].f) {
            cout << "Impossible" << endl;
            return 0;
        }
    }
    for (int i = h[n + 1]; i; i = e[i].nxt) {
        if (e[i].f < 2) {
            cout << "Impossible" << endl;
            return 0;
        }
    }
    for (int i = 1; i <= n; ++i) if (!vis[i]) top++, find(i, top);
    cout << top << endl;
    for (int i = 1; i <= top; ++i) {
        cout << ans[i].size() << ' ';
        for (vector<int>::iterator iter = ans[i].begin(); iter != ans[i].end(); ++iter) {
            cout << *iter << ' ';
        }
        cout << endl;
    }
    return 0;
}

Karen and Cards

题目描述

Karen just got home from the supermarket, and is getting ready to go to sleep.
After taking a shower and changing into her pajamas, she looked at her shelf and saw an album. Curious, she opened it and saw a trading card collection.
She recalled that she used to play with those cards as a child, and, although she is now grown-up, she still wonders a few things about it.
Each card has three characteristics: strength, defense and speed. The values of all characteristics of all cards are positive integers. The maximum possible strength any card can have is $p$, the maximum possible defense is $q$ and the maximum possible speed is $r$.
There are $n$ cards in her collection. The $i$-th card has a strength $a_i$, defense $b_i$ and speed $c_i$, respectively.
A card beats another card if at least two of its characteristics are strictly greater than the corresponding characteristics of the other card.
She now wonders how many different cards can beat all the cards in her collection. Two cards are considered different if at least one of their characteristics have different values.

题意概述

给定$n$张牌,每张牌有三个属性$a_i, b_i, c_i$。一张牌能压制另一张牌$\Leftrightarrow$前者的至少两个属性严格大于后者的对应属性。已知三个属性的上限分别为$p, q, r$,问有多少种不同的牌能压制给定的$n$张牌。
数据范围:$1 \le n, p, q, r \le 5 \times 10^5, \; 1 \le a_i \le p, \; 1 \le b_i \le q, \; 1 \le c_i \le r$。

算法分析

可以先枚举从$1$到$p$枚举$a$属性,分别算出可行的牌数,累加得到答案。
现在考虑$b, c$属性。设正在枚举$a=k$的情况。我们以$b$为$x$轴、$c$为$y$轴建立平面直角坐标系。对于$a_i \ge k$的牌,必须满足$b_i \lt x \land c_i \lt y$;对于$a_i \lt k$的牌,必须满足$b_i \lt x \lor c_i \lt y$。
A Plane
如图,红色区域表示$a_i \ge k$的牌可取的点,蓝色、绿色区域表示$a_i \lt k$的牌不可取的点。显然,用红色区域的点数减去红色和蓝色、绿色区域交集的点数,就是$a=k$时可行的牌数。
红色区域的大小取决于$a_i \ge k$的牌中$b_i, c_i$的最大值。蓝色、绿色区域的大小取决于$a_i \lt k$的牌中$b_i, c_i$的值;这可以用线段树来维护。理论时间复杂度为$O(n\log n)$。

代码

#include <cstdio>
#include <algorithm>
using namespace std;
struct card {
    long long a, b, c;
} c[500002];
bool operator < (card a, card b) {
    return a.a < b.a;
}
long long n, p, q, r, pnt = 1, ans, s[500002], t[500002];
struct segment_tree {
    struct node_type {
        long long l, r, val, max, sum, tag;
        node_type *child[2];
    } *root;
    void build_tree(node_type *root) {
        if (root->l == root->r) return;
        long long mid = root->l + root->r >> 1;
        node_type *p, *q;
        p = new node_type;
        p->l = root->l, p->r = mid, p->val = p->max = p->sum = p->tag = 0;
        q = new node_type;
        q->l = mid + 1, q->r = root->r, q->val = q->max = q->sum = q->tag = 0;
        build_tree(p), build_tree(q);
        root->child[0] = p, root->child[1] = q;
    }
    void push_up(node_type *root) {
        if (root->l != root->r) {
            root->sum = root->child[0]->sum + root->child[1]->sum;
            root->max = max(root->child[0]->max, root->child[1]->max);
        }
    }
    void push_down(node_type *root) {
        if (root->tag && root->l != root->r) {
            root->child[0]->tag = root->child[0]->max = root->child[1]->tag = root->child[1]->max = root->tag;
            root->child[0]->sum = (root->child[1]->l - root->child[0]->l) * root->tag;
            root->child[1]->sum = (root->child[1]->r - root->child[0]->r) * root->tag;
        }
        root->tag = 0;
    }
    void insert_line(node_type *root, long long l, long long r, long long t) {
        if (l == root->l && r == root->r) {
            root->tag = root->max = t;
            root->sum = (r - l + 1) * t;
            return;
        }
        push_down(root);
        if (r < root->child[1]->l) insert_line(root->child[0], l, r, t);
        else if (l > root->child[0]->r) insert_line(root->child[1], l, r, t);
        else {
            insert_line(root->child[0], l, root->child[0]->r, t);
            insert_line(root->child[1], root->child[1]->l, r, t);
        }
        push_up(root);
    }
    long long get(node_type *root, long long t) {
        if (root->l == root->r) return root->l;
        push_down(root);
        if (root->child[1]->max < t) return get(root->child[0], t);
        else return get(root->child[1], t);
    }
    long long get_sum(node_type *root, int l, int r) {
        if (l == root->l && r == root->r) return root->sum;
        push_down(root);
        if (r < root->child[1]->l) return get_sum(root->child[0], l, r);
        else if (l > root->child[0]->r) return get_sum(root->child[1], l, r);
        else return get_sum(root->child[0], l, root->child[0]->r) + get_sum(root->child[1], root->child[1]->l, r);
    }
} tree;
int main()
{
    scanf("%lld%lld%lld%lld", &n, &p, &q, &r);
    tree.root = new segment_tree::node_type;
    tree.root->l = 0, tree.root->r = q, tree.root->val = tree.root->max = tree.root->sum = tree.root->tag = 0;
    tree.build_tree(tree.root);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld%lld%lld", &c[i].a, &c[i].b, &c[i].c);
    }
    sort(c + 1, c + n + 1);
    s[n] = c[n].b, t[n] = c[n].c;
    for (int i = n - 1; i; --i) {
        s[i] = max(s[i + 1], c[i].b);
        t[i] = max(t[i + 1], c[i].c);
    }
    tree.insert_line(tree.root, 0, 0, q + 1);
    long long tmp;
    for (int i = 1, j = 1; i <= p; ++i) {
        for (; j <= n && c[j].a < i; ++j) {
            tmp = tree.get(tree.root, c[j].c);
            if (tmp >= c[j].b) continue;
            tree.insert_line(tree.root, tmp + 1, c[j].b, c[j].c);
        }
        tmp = max(s[j], tree.get(tree.root, t[j] + 1));
        ans += (tmp - s[j]) * r + (q - tmp) * (r - t[j]);
        if (tmp > s[j]) ans -= tree.get_sum(tree.root, s[j] + 1, tmp);
    }
    printf("%lld\n", ans);
    return 0;
}

Limits in C

Limits on Integer Constants

Constant Meaning Value
CHAR_BIT Number of bits in the smallest variable that is not a bit field. 8
SCHAR_MIN Minimum value for a variable of type signed char. –128
SCHAR_MAX Maximum value for a variable of type signed char. 127
UCHAR_MAX Maximum value for a variable of type unsigned char. 255 (0xff)
CHAR_MIN Minimum value for a variable of type char. –128; 0 if /J option used
CHAR_MAX Maximum value for a variable of type char. 127; 255 if /J option used
MB_LEN_MAX Maximum number of bytes in a multicharacter constant. 5
SHRT_MIN Minimum value for a variable of type short. –32768
SHRT_MAX Maximum value for a variable of type short. 32767
USHRT_MAX Maximum value for a variable of type unsigned short. 65535 (0xffff)
INT_MIN Minimum value for a variable of type int. –2147483648
INT_MAX Maximum value for a variable of type int. 2147483647
UINT_MAX Maximum value for a variable of type unsigned int. 4294967295 (0xffffffff)
LONG_MIN Minimum value for a variable of type long. –2147483648
LONG_MAX Maximum value for a variable of type long. 2147483647
ULONG_MAX Maximum value for a variable of type unsigned long. 4294967295 (0xffffffff)
_I64_MIN Minimum value for a variable of type __int64 -9223372036854775808
_I64_MAX Maximum value for a variable of type __int64 9223372036854775807
_UI64_MAX Maximum value for a variable of type unsigned __int64 18446744073709551615 (0xffffffffffffffff)

Limits on Floating-Point Constants

Constant Meaning Value
FLT_DIG DBL_DIG LDBL_DIG Number of digits, q, such that a floating-point number with q decimal digits can be rounded into a floating-point representation and back without loss of precision. 6 15 15
FLT_EPSILON DBL_EPSILON LDBL_EPSILON Smallest positive number x, such that x + 1.0 is not equal to 1.0. 1.192092896e–07F 2.2204460492503131e–016 2.2204460492503131e–016
FLT_GUARD 0
FLT_MANT_DIG DBL_MANT_DIG LDBL_MANT_DIG Number of digits in the radix specified by FLT_RADIX in the floating-point significand. The radix is 2; hence these values specify bits. 24 53 53
FLT_MAX DBL_MAX LDBL_MAX Maximum representable floating-point number. 3.402823466e+38F 1.7976931348623158e+308 1.7976931348623158e+308
FLT_MAX_10_EXP DBL_MAX_10_EXP LDBL_MAX_10_EXP Maximum integer such that 10 raised to that number is a representable floating-point number. 38 308 308
FLT_MAX_EXP DBL_MAX_EXP LDBL_MAX_EXP Maximum integer such that FLT_RADIX raised to that number is a representable floating- point number. 128 1024 1024
FLT_MIN DBL_MIN LDBL_MIN Minimum positive value. 1.175494351e–38F 2.2250738585072014e–308 2.2250738585072014e–308
FLT_MIN_10_EXP DBL_MIN_10_EXP LDBL_MIN_10_EXP Minimum negative integer such that 10 raised to that number is a representable floating- point number. –37

–307

–307

FLT_MIN_EXP DBL_MIN_EXP LDBL_MIN_EXP Minimum negative integer such that FLT_RADIX raised to that number is a representable floating-point number. –125

–1021

–1021

FLT_NORMALIZE 0
FLT_RADIX _DBL_RADIX _LDBL_RADIX Radix of exponent representation. 2 2 2
FLT_ROUNDS _DBL_ROUNDS _LDBL_ROUNDS Rounding mode for floating-point addition. 1 (near) 1 (near) 1 (near)

Karen and Supermarket

题目描述

On the way home, Karen decided to stop by the supermarket to buy some groceries.
She needs to buy a lot of goods, but since she is a student her budget is still quite limited. In fact, she can only spend up to $b$ dollars.
The supermarket sells $n$ goods. The $i$-th good can be bought for $c_i$ dollars. Of course, each good can only be bought once.
Lately, the supermarket has been trying to increase its business. Karen, being a loyal customer, was given $n$ coupons. If Karen purchases the $i$-th good, she can use the $i$-th coupon to decrease its price by $d_i$. Of course, a coupon cannot be used without buying the corresponding good.
There is, however, a constraint with the coupons. For all $i \ge 2$, in order to use the $i$-th coupon, Karen must also use the $x_i$-th coupon (which may mean using even more coupons to satisfy the requirement for that coupon).
Karen wants to know the following. What is the maximum number of goods she can buy, without exceeding her budget $b$?

题意概述

有$n$件商品,第$i$件商品的价格为$c_i$。同时,第$i$件商品有一张可以将价格降低$d_i$的优惠券,使用这张优惠券的前提是第$x_i$件商品的优惠券也被使用(使用优惠券后必须买对应的商品;第一件商品的优惠券没有使用前提)。问在总价格不超过$b$的情况下最多能购买多少商品。
数据范围:$1 \le n \le 5000, \; 1 \le b \le 10^9, \; 1 \le d_i \lt c_i \le 10^9, \; 1 \le x_i \lt i$。

算法分析

很明显这是一棵树。
令$s_i$表示第$i$件商品已处理过的子树大小,$f_{i, j, 1/0}$表示从第$i$件商品以及它的子树中购买$j$件商品且第$i$件商品使用/不使用优惠券时的最少价格。初始时
$$s_i=1, \; f_{i, 0, 0}=0, \; f_{i, 1, 0}=c_i, \; f_{i, 1, 1}=c_i-d_i$$
转移方程如下
$$
\begin{align}
f_{i, j + k, 0}&=\min(f_{i, j, 0} + f_{u, k, 0}) \\
f_{i, j + k, 1}&=\min(f_{i, j, 1} + \min(f_{u, k, 0}, f_{u, k, 1}))
\end{align}
$$
转移时需要满足$u$是$i$的儿子,且$0 \le j \le s_i, \; 0 \le k \le s_u$。

代码

#include <iostream>
#include <cstring>
using namespace std;
struct edge {
    int v, nxt;
} e[5001];
long long n, b, tot, h[5001], c[5001], d[5001], x, s[5001], f[5001][5001][2];
void add_edge(int u, int v) {
    e[++tot].v = v;
    e[tot].nxt = h[u];
    h[u] = tot;
}
void dfs(int t) {
    for (int k = h[t]; k; k = e[k].nxt) {
        dfs(e[k].v);
        for (int i = s[t]; i >= 0; --i) {
            for (int j = 0; j <= s[e[k].v]; ++j) {
                f[t][i + j][0] = min(f[t][i + j][0], f[t][i][0] + f[e[k].v][j][0]);
                f[t][i + j][1] = min(f[t][i + j][1], f[t][i][1] + min(f[e[k].v][j][0], f[e[k].v][j][1]));
            }
        }
        s[t] += s[e[k].v];
    }
}
int main()
{
    cin >> n >> b;
    memset(f, 0x7f, sizeof(f));
    for (int i = 1; i <= n; ++i) {
        cin >> c[i] >> d[i];
        s[i] = 1;
        f[i][0][0] = 0;
        f[i][1][0] = c[i];
        f[i][1][1] = c[i] - d[i];
        if (i - 1) {
            cin >> x;
            add_edge(x, i);
        }
    }
    dfs(1);
    for (int i = n; i >= 0; --i) {
        if (min(f[1][i][0], f[1][i][1]) <= b) {
            cout << i << endl;
            break;
        }
    }
    return 0;
}

Karen and Test

题目描述

Karen has just arrived at school, and she has a math test today!
The test is about basic addition and subtraction. Unfortunately, the teachers were too busy writing tasks for Codeforces rounds, and had no time to make an actual test. So, they just put one question in the test that is worth all the points.
There are $n$ integers written on a row. Karen must alternately add and subtract each pair of adjacent integers, and write down the sums or differences on the next row. She must repeat this process on the values on the next row, and so on, until only one integer remains. The first operation should be addition.
Note that, if she ended the previous row by adding the integers, she should start the next row by subtracting, and vice versa.
The teachers will simply look at the last integer, and then if it is correct, Karen gets a perfect score, otherwise, she gets a zero for the test.
Karen has studied well for this test, but she is scared that she might make a mistake somewhere and it will cause her final answer to be wrong. If the process is followed, what number can she expect to be written on the last row?
Since this number can be quite large, output only the non-negative remainder after dividing it by $10^9+7$.

题意概述

有$n$个正整数$a_i$写在一行。依次对相邻两个数交错进行加减运算,并把结果写在下一行,重复这一过程直到只剩下一个数。第一次进行的是加法运算,求最后得到的数。
数据范围:$1 \le n \le 2 \times 10^5, \; 1 \le a_i \le 10^9$。

算法分析

先列举$n \le 12$的情况:
$$
\begin{align}
n=1,\;&ans=a_1 \\
n=2,\;&ans=a_1+a_2 \\
n=3,\;&ans=a_1+2a_2-a_3 \\
n=4,\;&ans=a_1-a_2+a_3-a_4 \\
n=5,\;&ans=a_1+2a_3+a_5 \\
n=6,\;&ans=a_1+a_2+2a_3+2a_4+a_5+a_6 \\
n=7,\;&ans=a_1+2a_2+a_3+4a_4-a_5+2a_6-a_7 \\
n=8,\;&ans=a_1-a_2+3a_3-3a_4+3a_5-3a_6+a_7-a_8 \\
n=9,\;&ans=a_1+4a_3+6a_5+4a_7+a_9 \\
n=10,\;&ans=a_1+a_2+4a_3+4a_4+6a_5+6a_6+4a_7+4a_8+a_9+a_{10} \\
n=11,\;&ans=a_1+2a_2+3a_3+8a_4+2a_5+12a_6-2a_7+8a_8-3a_9+2a_{10}-a_{11} \\
n=12,\;&ans=a_1-a_2+5a_3-5a_4+10a_5-10a_6+10a_7-10a_8+5a_9-5a_{10}+a_{11}-a_{12}
\end{align}
$$
可以发现,对于模$4$余$1$的$n$,其答案中第$i \; (i \bmod 2=1)$项的系数为${2n/4 \choose i/2}$;对于模$4$余$2$的$n$也有类似的结论。而对于模$4$余$0$或余$3$的$n$,都可以由$(n-2)$的答案推导出来。
接下来就是计算组合数的问题。易知${n \choose 0}=1, {n \choose i} \times {n-i \over i+1}={n \choose i+1}$。由于涉及到模意义下的除法,因此还需要计算逆元。

代码

#include <iostream>
#define MOD 1000000007
using namespace std;
long long n, t, r[3], ans, c[200001], a[200001];
void extend_gcd(long long a, long long b, long long &x, long long &y) {
    if (!b) {
        x = 1, y = 0;
        return;
    }
    extend_gcd(b, a % b, y, x);
    y -= a / b * x;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    t = (n - 1) / 4 << 1;
    c[0] = 1;
    for (int i = 0; i < t; ++i) {
        long long x, y;
        extend_gcd(i + 1, MOD, x, y);
        c[i + 1] = c[i] * (t - i) % MOD * x % MOD;
        if (c[i + 1] < 0) c[i + 1] += MOD;
    }
    for (int i = 0; i <= t; ++i) {
        r[0] += c[i] * a[(i << 1) + 1] % MOD;
        if (!(n & 1)) r[0] += c[i] * a[(i << 1) + 2] % MOD;
    }
    r[0] %= MOD;
    if ((n - 1) % 4 < 2) cout << r[0] << endl;
    else {
        for (int i = 0; i <= t; ++i) {
            r[1] += c[i] * a[(i << 1) + 2] % MOD;
            if (!(n & 1)) r[1] -= c[i] * a[(i << 1) + 3] % MOD;
        }
        r[1] %= MOD;
        for (int i = 0; i <= t; ++i) {
            r[2] += c[i] * a[(i << 1) + 3] % MOD;
            if (!(n & 1)) r[2] += c[i] * a[(i << 1) + 4] % MOD;
        }
        r[2] %= MOD;
        if (n & 1) ans = (r[0] + (r[1] << 1) - r[2]) % MOD;
        else ans = (r[0] - (r[1] << 1) - r[2]) % MOD;
        if (ans < 0) ans += MOD;
        cout << ans << endl;
    }
    return 0;
}

Karen and Game

题目描述

On the way to school, Karen became fixated on the puzzle game on her phone!
The game is played as follows. In each level, you have a grid with $n$ rows and $m$ columns. Each cell originally contains the number $0$.
One move consists of choosing one row or column, and adding $1$ to all of the cells in that row or column.
To win the level, after all the moves, the number in the cell at the $i$-th row and $j$-th column should be equal to $g_{i, j}$.
Karen is stuck on one level, and wants to know a way to beat this level using the minimum number of moves. Please, help her with this task!

题意概述

给定一个初始全为$0$的矩阵$s$和一个目标矩阵$g$,两矩阵大小均为$n \times m$。每次操作可以将矩阵$s$中某一行或某一列的数全部加一。求一个能将$s$变成$g$且操作数最少的操作序列。
数据范围:$1 \le n, m \le 100, \; 0 \le g_{i, j} \le 500$。

算法分析

可以倒过来思考:每次操作将$g$中某一行或某一列的数全部减一,要求得到所有数均为$0$的矩阵。显然,操作序列满足交换律。因此,只要找到所有数都非$0$的一行或一列,就可以立刻对这一行或一列进行操作。由于要求操作数最少,所以先枚举较短的一条边,再枚举较长的一条边。

代码

#include <iostream>
using namespace std;
int n, m, p, q, top, f, a[101][101], ans[100001], mode[100001];
bool check(int t, int mode) {
    if (!mode) {
        for (int i = 1; i <= m; ++i) if (!a[t][i]) return false;
        for (int i = 1; i <= m; ++i) --a[t][i];
        return true;
    } else {
        for (int i = 1; i <= n; ++i) if (!a[i][t]) return false;
        for (int i = 1; i <= n; ++i) --a[i][t];
        return true;
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
        }
    }
    p = n, q = m;
    if (p > q) {
        p ^= q ^= p ^= q;
        f = 1;
    }
    for (int i = 1; i <= p; ++i) while (check(i, f)) {
        ans[++top] = i;
        mode[top] = f;
    }
    for (int i = 1; i <= q; ++i) while (check(i, !f)) {
        ans[++top] = i;
        mode[top] = !f;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i][j]) {
                cout << -1 << endl;
                return 0;
            }
        }
    }
    cout << top << endl;
    for (int i = 1; i <= top; ++i) {
        if (!mode[i]) cout << "row ";
        else cout << "col ";
        cout << ans[i] << endl;
    }
    return 0;
}

Fox and Jumping

题目描述

Fox Ciel is playing a game. In this game there is an infinite long tape with cells indexed by integers (positive, negative and zero). At the beginning she is standing at the cell $0$.
There are also $n$ cards, each card has $2$ attributes: length $l_i$ and cost $c_i$. If she pays $c_i$ dollars then she can apply $i$-th card. After applying $i$-th card she becomes able to make jumps of length $l_i$, i.e. from cell $x$ to cell $(x-l_i)$ or cell $(x+l_i)$.
She wants to be able to jump to any cell on the tape (possibly, visiting some intermediate cells). For achieving this goal, she wants to buy some cards, paying as little money as possible.
If this is possible, calculate the minimal cost.

题意概述

有$n$张卡片,每张卡片都有两个属性$l_i, c_i$。你需要从中选择一些卡片,使得在满足用已选卡片的$l_i$任意加减可以得到所有整数的情况下,已选卡片的$c_i$之和最小。求出这个最小值。
数据范围:$1 \le n \le 300, \; 1 \le l_i \le 10^9, \; 1 \le c_i \le 10^5$。

算法分析

可以发现,如果所有已选卡片的$l_i$的最大公约数为$1$,则满足要求。
用$f_k$表示已选卡片的$l_i$的最大公约数为$k$时$c_i$之和的最小值。有如下转移方程:
$$f_{(k, l_i)}=\min(f_k+c_i)$$
如果最后$f_1$不存在,则说明无解。
由于$k$可能会很大,但个数不会很多,可以使用map来节省空间。

代码

#include <iostream>
#include <map>
using namespace std;
int n, l[301], c[301];
map<int, int> f;
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> l[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> c[i];
    }
    f[0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (map<int, int>::iterator iter = f.begin(); iter != f.end(); ++iter) {
            int t = gcd(iter->first, l[i]);
            if (!f.count(t)) f[t] = iter->second + c[i];
            else f[t] = min(f[t], iter->second + c[i]);
        }
    }
    if (!f[1]) cout << -1 << endl;
    else cout << f[1] << endl;
    return 0;
}

Fox and Names

题目描述

Fox Ciel is going to publish a paper on FOCS (Foxes Operated Computer Systems, pronounce: “Fox”). She heard a rumor: the authors list on the paper is always sorted in the lexicographical order.
After checking some examples, she found out that sometimes it wasn’t true. On some papers authors’ names weren’t sorted in lexicographical order in normal sense. But it was always true that after some modification of the order of letters in alphabet, the order of authors becomes lexicographical!
She wants to know, if there exists an order of letters in Latin alphabet such that the names on the paper she is submitting are following in the lexicographical order. If so, you should find out any such order.
Lexicographical order is defined in following way. When we compare $s$ and $t$, first we find the leftmost position with differing characters: $s_i \neq t_i$. If there is no such position (i.e. $s$ is a prefix of $t$ or vice versa) the shortest string is less. Otherwise, we compare characters $s_i$ and $t_i$ according to their order in alphabet.

题意概述

给定$n$个字符串$name_1, name_2, name_3, \ldots, name_n$,要求你给出一张字母表,使得这些字符串是按照你所给出字母表的字典序从小到大排序的。
数据范围:$1 \le n \le 100, \; 1 \le |name_i| \le 100$。

算法分析

很明显,对于任意两个字符串$name_i, name_j \; (i \lt j)$来说,设其第一个不同字母的位置为$p$,则有$index_{name_{i, p}} \lt index_{name_{j, p}}$,其中$index_i$表示字母$i$在字母表中的位置。可以发现,这构成了一张拓扑图,进行一次拓扑排序就能解决问题。
注意到其中有些字符串是另一些字符串的前缀。如果$name_i$是$name_j$的前缀($name_i \neq name_j$),且$i \gt j$,则直接输出Impossible。

代码

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct author {
    int id;
    string name;
} a[101];
bool cmp(author a, author b) {
    return a.name < b.name;
}
int n, in[26];
bool graph[26][26];
queue<int> que;
string ans;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].name;
        a[i].id = i;
    }
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i < n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            int p = 0, len1 = a[i].name.length(), len2 = a[j].name.length();
            while (p < len1 && p < len2 && a[i].name[p] == a[j].name[p]) ++p;
            if (p == len1 && p < len2 && a[i].id > a[j].id) {
                cout << "Impossible" << endl;
                return 0;
            }
            if (p < len1) {
                if (a[i].id < a[j].id) graph[a[i].name[p] - 'a'][a[j].name[p] - 'a'] = true;
                else graph[a[j].name[p] - 'a'][a[i].name[p] - 'a'] = true;
            }
        }
    }
    for (int i = 0; i < 26; ++i) {
        for (int j = 0; j < 26; ++j) {
            if (graph[i][j]) ++in[j];
        }
    }
    for (int i = 0; i < 26; ++i) {
        if (!in[i]) que.push(i);
    }
    while (!que.empty()) {
        int t = que.front();
        que.pop();
        for (int i = 0; i < 26; ++i) {
            if (graph[t][i]) {
                --in[i];
                if (!in[i]) que.push(i);
            }
        }
        ans += t + 'a';
    }
    if (ans.length() < 26) {
        cout << "Impossible" << endl;
    } else {
        cout << ans << endl;
    }
    return 0;
}