Conquer the Polygon

题目描述

You have a convex polygon. The vertices of the polygon are successively numbered from $1$ to $n$. You also have a triangulation of this polygon, given as a list of $n-3$ diagonals.

There will be $2n-3$ undirected edges in the graph: $n-3$ edges in the triangulation and $n$ edges on the side of the polygon.

You can choose to conquer some vertices, and if you choose to conquer a vertex, you will conquer all the edges linked to this vertex.

Write a program to determine the minimum number of vertices you need to choose such that you can conquer all the edges. Note that you are not required to conquer all the vertices.

题意概述

给定一个$n$边形的三角剖分,求它的最小点覆盖。

数据范围:$4 \le n \le 10^5$。

算法分析

考虑一个度数为$2$的点:

  • 如果这个点已被选择,那么与它相邻的两条边都已被覆盖;
  • 否则,为了覆盖与它相邻的边,最优方案是选择与它相邻的两个点。

于是可以将这个点和与它相邻的边删去,又会得到新的度数为$2$的点。可以用类似拓扑排序的方法来维护。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
 
int const N = 100005;
int nume, h[N], in[N], used[N], que[N];
struct Edge {
    int v, nxt;
} e[N << 2];
 
void add_edge(int u, int v) {
    e[++nume] = (Edge) {v, h[u]};
    h[u] = nume;
}
 
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= 2 * n - 3; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
        ++in[u];
        ++in[v];
    }
    int qb = 0, qe = 0;
    for (int i = 1; i <= n; ++i) {
        if (in[i] == 2) {
            que[qe++] = i;
        }
    }
    for (; qb < qe;) {
        int cur = que[qb++];
        if (!used[cur]) {
            for (int i = h[cur]; i; i = e[i].nxt) {
                if (in[e[i].v] > 2) {
                    used[e[i].v] = 1;
                }
            }
        }
        for (int i = h[cur]; i; i = e[i].nxt) {
            --in[cur];
            --in[e[i].v];
            if (in[e[i].v] == 2) {
                que[qe++] = e[i].v;
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += used[i];
    }
    printf("%d\n", ans);
    return 0;
}

Coin Troubles

题目描述

In the Isle of Guernsey there are $n$ different types of coins. For each $i \; (1 \le i \le n)$, coin of type $i$ is worth $a_i$ cents. It is possible that $a_i=a_j$ for some $i$ and $j \; (i \neq j)$.
Bessie has some set of these coins totaling $t$ cents. She tells Jessie $q$ pairs of integers. For each $i \; (1 \le i \le q)$, the pair $b_i, c_i$ tells Jessie that Bessie has a strictly greater number of coins of type $b_i$ than coins of type $c_i$. It is known that all $b_i$ are distinct and all $c_i$ are distinct.
Help Jessie find the number of possible combinations of coins Bessie could have. Two combinations are considered different if there is some $i \; (1 \le i \le n)$, such that the number of coins Bessie has of type $i$ is different in the two combinations. Since the answer can be very large, output it modulo $1000000007$ ($10^9+7$).
If there are no possible combinations of coins totaling $t$ cents that satisfy Bessie’s conditions, output $0$.

题意概述

你有$n$种纸币,第$i$种纸币的价值为$a_i$(可能有多个$a_i$相等)。已知所有纸币的总价值为$t$。给定$q$对整数$b_i, c_i$,表示第$b_i$种纸币的数量严格大于第$c_i$种纸币的数量。所有$b_i$均不相等,所有$c_i$均不相等。求满足这些条件的方案数。
数据范围:$1 \le n \le 300, \; 1 \le t \le 10^5, \; 1 \le a_i \le 10^5$。

算法分析

将每种硬币看成点,每条限制看成有向边,这样就构成了一张有向图。若这张图中存在环,则方案数为$0$。否则,所有边构成的一定是链。对于一条链上的点$v_1, v_2, \ldots, v_m$,我们将$a_{v_2}$变成$a_{v_1}+a_{v_2}$,将$a_{v_3}$变成$a_{v_1}+a_{v_2}+a_{v_3}$,以此类推。这样做的原因是:如果选了第$v_2$件物品一次,就必须也选第$v_1$件物品一次;如果选了第$v_3$件物品一次,就必须也选第$v_1$和第$v_2$件物品一次。这就变成一个完全背包问题了。注意到完全背包问题中的物品是可以不选的,而在这个问题中有些物品是必须选的。例如,第$v_{m-1}$件物品必须至少选一次,第$v_{m-2}$件物品必须至少选两次(因为题目中要求严格大于)。只需在$t$中减去这些必须选的就可以了。

代码

#include <iostream>
using namespace std;
const long long mod = 1000000007ll;
long long n, q, t, ma, a[301], to[301], f[100001];
bool m[301], in[301], vis[301];
void dfs(long long u, long long d, long long s) {
  ma = d, vis[u] = true;
  if (to[u]) dfs(to[u], d + 1, s + a[u]);
  t -= (ma - d) * a[u], a[u] += s;
}
int main()
{
  cin >> n >> q >> t, f[0] = 1;
  for (int i = 1; i <= n; cin >> a[i], ++i);
  for (int i = 1; i <= q; ++i) {
    long long b, c; cin >> b >> c;
    m[b] = m[c] = true, in[c] = true, to[b] = c;
  }
  for (int i = 1; i <= n; ++i)
    if (m[i] && !in[i]) ma = 0, dfs(i, 0, 0);
  if (t < 0) { cout << 0 << endl; return 0; }
  for (int i = 1; i <= n; ++i)
    if (m[i] && !vis[i]) { cout << 0 << endl; return 0; }
  for (int i = 1; i <= n; ++i)
    for (int j = 0; j <= t - a[i]; ++j)
      (f[j + a[i]] += f[j]) %= mod;
  cout << f[t] << endl;
  return 0;
}

Minimal Labels

题目描述

You are given a directed acyclic graph with $n$ vertices and $m$ edges. There are no self-loops or multiple edges between any pair of vertices. Graph can be disconnected.
You should assign labels to all vertices in such a way that:

  • Labels form a valid permutation of length $n$ – an integer sequence such that each integer from $1$ to $n$ appears exactly once in it.
  • If there exists an edge from vertex $v$ to vertex $u$ then $label_v$ should be smaller than $label_u$.
  • Permutation should be lexicographically smallest among all suitable.

Find such sequence of labels to satisfy all the conditions.

题意概述

给定一张$n$个点$m$条边的有向无环图。现要将图中所有点标号。如果点$u$有一条连向点$v$的边,那么点$u$的标号要比点$v$小。求一组字典序最小的标号方案。
数据范围:$2 \le n \le 10^5, \; 1 \le m \le 10^5$。

算法分析

这是一张拓扑图,只需进行一次拓扑排序即可得到一组方案。但由于题目要求字典序最小,因此需要逆向拓扑,并用优先队列维护id最大的节点。证明如下:

对于节点$1$,它的标号等于它在逆向拓扑树上的子树大小,这显然属于字典序最小的方案。对于节点$2$,它的标号等于节点$1$子树并上节点$2$子树的大小,这也属于字典序最小的方案。以此类推,每个节点的标号都属于字典序最小的方案。

由此得证。

代码

#include <iostream>
#include <queue>
using namespace std;
struct edge { int v, nxt; } e[100001];
int n, m, nume, cnt, h[200001], in[200001], id[200001];
priority_queue<int> que;
void add_edge(int u, int v) {
  e[++nume].v = v, e[nume].nxt = h[u], h[u] = nume;
}
int main()
{
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int u, v; cin >> u >> v;
    add_edge(v, u), ++in[u];
  }
  for (int i = 1; i <= n; ++i) if (!in[i]) que.push(i);
  while (!que.empty()) {
    int u = que.top(); que.pop(), id[u] = cnt++;
    for (int i = h[u]; i; i = e[i].nxt) {
      --in[e[i].v]; if (!in[e[i].v]) que.push(e[i].v);
    }
  }
  for (int i = 1; i <= n; ++i) cout << n - id[i] << ' ';
  cout << 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;
}