题目描述

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.

算法分析

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

代码

#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);
++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;
}

题目描述

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$.

代码

#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;
}


题目描述

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.

代码

#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;
}
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 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.

代码

#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;
}