Codeforces Round #270
题目链接
A：我是筛了下素数。事实上偶数仅仅要输出4和x - 4，奇数输出9和x - 9就可以
B：贪心的策略，把时间排序后。取每k个的位置
C：贪心。每次遇到一个人尽量让他用字典序小的，假设不行就大的，假设还是不行就是矛盾了
D：先推断原来矩阵的对角线。和是否是对称矩阵，求出最小生成树后。dfs n次求出每两点之间的距离。然后你和原来的矩阵相比就能够了
代码：
A：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;typedef long long ll;
const ll N = 1000005;
int n, vis[N];void get() {for (ll i = 2; i < N; i++) {if (vis[i]) continue;for (ll j = i * i; j < N; j += i)vis[j] = 1;}
}int main() {get();scanf("%d", &n);for (int i = 2; i < n; i++) {if (vis[i] && vis[n - i]) {printf("%d %d\n", i, n - i);break;}}return 0;
}B：
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;const int N = 2005;
int n, m, a[N];int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) scanf("%d", &a[i]);sort(a + 1, a + n + 1);int ans = 0;for (int i = n; i >= 1; i -= m)ans += (a[i] - 1) * 2;printf("%d\n", ans);return 0;
}C：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;#define MP(a,b) make_pair(a,b)
const int N = 100005;
typedef pair<int, int> pii;char a[N][55], b[N][55];int n;
pii p[N];
char sb[55];int main() {scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%s%s", a[i], b[i]);if (strcmp(a[i], b[i]) > 0) {strcpy(sb, a[i]);strcpy(a[i], b[i]);strcpy(b[i], sb);}}int tmp;for (int i = 0; i < n; i++) {scanf("%d", &tmp);p[i] = MP(i, tmp - 1);}sort(p, p + n);char pre[55];int flag = 0;memset(pre, 0, sizeof(pre));for (int i = 0; i < n; i++) {int id = p[i].second;if (strcmp(a[id], pre) > 0) {strcpy(pre, a[id]);} else if (strcmp(b[id], pre) > 0) {strcpy(pre, b[id]);} else {flag = 1;break;}}if (flag) printf("NO\n");else printf("YES\n");return 0;
}D：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;typedef long long ll;
const int N = 2005;
int n, parent[N];
ll d[N][N], ans[N][N];int find(int x) {return x == parent[x] ? x : parent[x] = find(parent[x]);
}vector<int> g[N];struct Edge {int u, v, d;Edge() {}Edge(int u, int v, int d) {this->u = u;this->v = v;this->d = d;}
} e[N * N];int en = 0;bool cmp(Edge a, Edge b) {return a.d < b.d;
}void dfs(int st, int u, int f, ll sum) {ans[st][u] = sum;for (int i = 0; i < g[u].size(); i++) {int v = g[u][i];if (f == v) continue;dfs(st, v, u, sum + d[u][v]);}
}bool judge() {for (int i = 1; i <= n; i++) {parent[i] = i;for (int j = 1; j <= n; j++) {if (i == j && d[i][j]) return false;if (i != j && !d[i][j]) return false;if (d[i][j] != d[j][i]) return false;}}for (int i = 1; i <= n; i++)for (int j = i + 1; j <= n; j++) {e[en++] = Edge(i, j, d[i][j]);}sort(e, e + en, cmp);for (int i = 0; i < en; i++) {int u = find(e[i].u);int v = find(e[i].v);if (u != v) {g[e[i].u].push_back(e[i].v);g[e[i].v].push_back(e[i].u);parent[u] = v;}}for (int i = 1; i <= n; i++) {dfs(i, i, 0, 0);}for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)if (ans[i][j] != d[i][j]) return false;return true;
}int main() {scanf("%d", &n);for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)scanf("%lld", &d[i][j]);if (judge()) printf("YES\n");else printf("NO\n");return 0;
}
