本文主要是介绍Codeforces Round #290 (Div. 1) A, B, C，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
A：对于每个名字，和上一个人比较一下，可以知道哪些字母应该在哪些字母前面，然后拓扑排序判一下是否有环，要注意判断是否存在字符串等于前一个字符串的前缀，有环就是矛盾，没环就输出拓扑序即可
B：其实只要选一些数字gcd能满足1，就是可以构造无限多的数字（这个跟辗转相除法有关系），然后题目就转换成，选一些数字使得gcd为1的最小代价，那么进行背包即可，dp[i][j]表示选到i个数字，gcd为j的最小代价，由于数字挺大的，但是实际要存的数字不多，用map存即可
C：神奇的网络流，首先题目不会加出2这个素数，所以加出来的素数都是奇数，那必然是一个奇数一个偶数相邻，这样的话，可以构造一个二分图，左边奇数，右边偶数，由于一个奇数要匹配两个偶数，一个偶数匹配两个奇数，所以只要源点连向奇数容量2，偶数连向汇点容量2，然后满足的奇数偶数连一个边容量1，跑一下最大流，判断流量是否为n即可，然后这题还要输出路径，那么就把匹配边找出来，就可以知道奇数偶数分别要匹配哪两个，然后去搜一遍即可
代码：
A：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
using namespace std;int n, flag = 0, du[30];
char str[105][105];
vector<int> g[30];
int out[30], on = 0;void gao() {queue<int> Q;for (int i = 0; i < 26; i++)if (!du[i]) Q.push(i);while (!Q.empty()){int u = Q.front();out[on++] = u;Q.pop();for (int j = 0; j < g[u].size(); j++) {int v = g[u][j];du[v]--;if (du[v] == 0) Q.push(v);}}for (int i = 0; i < 26; i++)if (du[i]) flag = 1;if (flag) printf("Impossible\n");else {for (int i = 0; i < on; i++)printf("%c", out[i] + 'a');printf("\n");}
}int main() {scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%s", str[i]);if (i == 0) continue;int len1 = strlen(str[i - 1]);int len2 = strlen(str[i]);int u1 = 0, u2 = 0;while (u1 != len1 && u2 != len2) {if (str[i - 1][u1] == str[i][u2]) {u1++; u2++;} else {g[str[i - 1][u1] - 'a'].push_back(str[i][u2] - 'a');du[str[i][u2] - 'a']++;break;}}if (u2 == len2 && len1 > len2) flag = 1;}gao();return 0;
}B：
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;const int N = 305;map<int, int> dp[2];
map<int, int>::iterator it;int n, l[N], c[N];int gcd(int a, int b) {if (!b) return a;return gcd(b, a % b);
}int main() {scanf("%d", &n);for (int i = 0; i < n; i++) scanf("%d", &l[i]);for (int i = 0; i < n; i++) scanf("%d", &c[i]);int now = 0, pre = 1;dp[now].clear();dp[now][0] = 0;for (int i = 0; i < n; i++) {swap(now, pre);dp[now].clear();for (it = dp[pre].begin(); it != dp[pre].end(); it++) {int u = it->first, w = it->second;int v = gcd(u, l[i]), vw = w + c[i];if (!dp[now].count(u)) dp[now][u] = w;else dp[now][u] = min(dp[now][u], w);if (!dp[now].count(v)) dp[now][v] = vw;else dp[now][v] = min(dp[now][v], vw);}}if (dp[now].count(1)) printf("%d\n", dp[now][1]);else printf("-1\n");return 0;
}C：
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;const int MAXNODE = 205 * 2;
const int MAXEDGE = 100005;typedef int Type;
const Type INF = 0x3f3f3f3f;const int N = 205;int n, a, odd[N], even[N], oddid[N], evenid[N];
int on, en;
int vis[20005], prime[20005], pn = 0;struct Edge {int u, v;Type cap, flow;Edge() {}Edge(int u, int v, Type cap, Type flow) {this->u = u;this->v = v;this->cap = cap;this->flow = flow;}
};struct Dinic {int n, m, s, t;Edge edges[MAXEDGE];int first[MAXNODE];int next[MAXEDGE];bool vis[MAXNODE];Type d[MAXNODE];int cur[MAXNODE];int match[MAXNODE][2], mn[MAXNODE];int vv[MAXNODE];vector<int> cut;void init(int n) {this->n = n;memset(first, -1, sizeof(first));memset(mn, 0, sizeof(mn));m = 0;}void add_Edge(int u, int v, Type cap) {edges[m] = Edge(u, v, cap, 0);next[m] = first[u];first[u] = m++;edges[m] = Edge(v, u, 0, 0);next[m] = first[v];first[v] = m++;}bool bfs() {memset(vis, false, sizeof(vis));queue<int> Q;Q.push(s);d[s] = 0;vis[s] = true;while (!Q.empty()) {int u = Q.front(); Q.pop();for (int i = first[u]; i != -1; i = next[i]) {Edge& e = edges[i];if (!vis[e.v] && e.cap > e.flow) {vis[e.v] = true;d[e.v] = d[u] + 1;Q.push(e.v);}}}return vis[t];}Type dfs(int u, Type a) {if (u == t || a == 0) return a;Type flow = 0, f;for (int &i = cur[u]; i != -1; i = next[i]) {Edge& e = edges[i];if (d[u] + 1 == d[e.v] && (f = dfs(e.v, min(a, e.cap - e.flow))) > 0) {e.flow += f;edges[i^1].flow -= f;flow += f;a -= f;if (a == 0) break;}}return flow;}Type Maxflow(int s, int t) {this->s = s; this->t = t;Type flow = 0;while (bfs()) {for (int i = 0; i < n; i++)cur[i] = first[i];flow += dfs(s, INF);}return flow;}void solve() {for (int i = 0; i < m; i += 2) {if (edges[i].u == n - 2 || edges[i].v == n - 1) continue;if (edges[i].flow == 0) continue;match[oddid[edges[i].u]][mn[oddid[edges[i].u]]++] = evenid[edges[i].v - on];match[evenid[edges[i].v - on]][mn[evenid[edges[i].v - on]]++] = oddid[edges[i].u];}memset(vv, 0, sizeof(vv));int out[205][205], hn = 0, on[205];memset(on, 0, sizeof(on));for (int i = 1; i <= n - 2; i++) {if (vv[i]) continue;on[hn] = 0;int s = i;while (1) {vv[s] = 1;out[hn][on[hn]++] = s;if (!vv[match[s][0]]) {s = match[s][0];continue;}if (!vv[match[s][1]]) {s = match[s][1];continue;}break;}hn++;}printf("%d\n", hn);for (int i = 0; i < hn; i++) {printf("%d", on[i]);for (int j = 0; j < on[i]; j++)printf(" %d", out[i][j]);printf("\n");}}
} gao;int main() {for (int i = 2; i < 20005; i++) {if (vis[i]) continue;prime[pn++] = i;for (int j = i * i; j < 20005; j += i) {vis[j] = 1;}}scanf("%d", &n);gao.init(n + 2);on = en = 0;for (int i = 1; i <= n; i++) {scanf("%d", &a);if (a % 2) {oddid[on] = i;odd[on++] = a;}else {evenid[en] = i;even[en++] = a;}}for (int i = 0; i < on; i++) gao.add_Edge(n, i, 2);for (int i = 0; i < en; i++) gao.add_Edge(i + on, n + 1, 2);for (int i = 0; i < on; i++)for (int j = 0; j < en; j++) {if (!vis[odd[i] + even[j]])gao.add_Edge(i, on + j, 1);}if (gao.Maxflow(n, n + 1) != n) printf("Impossible\n");else {gao.solve();}return 0;
}这篇关于Codeforces Round #290 (Div. 1) A, B, C的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
