A:To Europe! To Europe!
AC代码：
#include<cstdio>
const int maxn = 1005;
const double inf = 1e9;
struct Vehicle {
int weight, speed;
Vehicle() {}
Vehicle(int w, int s) : weight(w), speed(s) {}
}v[maxn];
int b, l, n, w, s;
/*** min time to pass first i vehicles and vehicle i ends a convoy ***/
double dp[maxn];
int main() {
#ifdef LOCAL
freopen("1.in", "r", stdin);
#endif
while(true) {
scanf("%d%d%d", &b, &l, &n);
if(b == 0) break;
for(int i = 1; i <= n; i++) {
scanf("%d%d", &w, &s);
v[i] = Vehicle(w, s);
}
for(int i = 1; i <= n; i++) {
double mins = inf;
int sum = 0;
dp[i] = inf;
for(int j = i; j > 0; j--) {
if(sum + v[j].weight > b) break;
sum += v[j].weight;
if(v[j].speed < mins) mins = v[j].speed;
double tmp = l * 60.0 / mins + dp[j - 1];
if(tmp < dp[i]) dp[i] = tmp;
}
}
printf("%.1lf\n", dp[n]);
}
return 0;
}
B:Radar Installation
AC代码
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 1005;
const int inf = 0x7fffffff;
struct Seg {
double l, r;
Seg() {}
Seg(double ll, double rr) : l(ll), r(rr) {}
bool operator < (const Seg &s) const {
return r < s.r;
}
}segs[maxn];
int n;
double d;
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
double x, y;
int kase = 0;
while(true) {
kase++;
bool flag = false;
cin >> n >> d;
if(n == 0) break;
for(int i = 0; i < n; i++) {
cin >> x >> y;
if(y > d) flag = true;
double bias = sqrt(d * d - y * y);
segs[i] = Seg(x - bias, x + bias);
}
if(flag) {
cout << "Case " << kase << ": -1" << endl;
continue;
}
sort(segs, segs + n);
int cnt = 1; double pos = segs[0].r;
for(int idx = 1; idx < n; idx++) {
if(pos >= segs[idx].l) continue;
pos = segs[idx].r;
cnt++;
}
cout << "Case " << kase << ": " << cnt << endl;
}
return 0;
}
C:Percolation
总时间限制: 1000ms 内存限制: 32768kB
描述
定义一个N行N列的矩阵，矩阵中的每个元素是个方格，每个方格有两种可能的状态：开通的或关闭的。初始时，所有方格都是关闭的。输入数据的每一步会指定矩阵中某个原来关闭的方格变成开通的。要求编写程序判断当前是否存在从矩阵中最上面一行的任何一个开着的方格走到最下面一行的任何一个开着的方格的路径。如果存在的话，输出当前的步数。比如走到第14步时，矩阵变成上下通透的，那么就输出14。注意：输入数据中只会把矩阵中的一部分方格打开。如果所有步骤都执行完了，矩阵仍然不是上下通透的，那么输出-1。显然，矩阵变成上下通透的一个必要条件是：最上面一行和最下面一行都至少要有一个方格是打开的。
在矩阵中行走时，只能横着走或竖着走，不能斜着走，也不能走出矩阵的边界。
输入
输入的第一行是一个自然数T(1≤T≤10)，代表测试数据的组数。每组测试数据的第一行有两个自然数N和M，其中N（1≤N≤1,000）代表方阵的维度，M（1≤M≤N*N）代表本组测试中打开的方格数目。随后的M行中每行有两个自然数，分别代表所打开的方格的行、列下标。注意：本题中矩阵的下标从1开始，即所有下标的取值都是[1, N]区间中的正整数。
输出
每组测试数据输出一个自然数K，表示打开第K个方格后，矩阵变成上下通透的。如果M个方格都打开后，矩阵仍然不是上下通透的，那么输出-1。
样例输入
1
4 10
2 2
3 1
4 2
4 4
1 2
2 3
2 1
3 2
3 4
3 1
样例输出
8
AC代码
#include<iostream>
using namespace std;
const int maxn = 1005;
int dx[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
struct Node {
int father, minr, maxr;
}nodes[maxn * maxn];
int n, m, ans;
bool mark[maxn][maxn];
int getFather(int x) {
if(nodes[x].father == x) return x;
Node f = nodes[getFather(nodes[x].father)];
nodes[x].minr = f.minr;
nodes[x].maxr = f.maxr;
return nodes[x].father = f.father;
}
inline bool ok(int x, int y) {
return (x > 0 && x <= n && y > 0 && y <= n && mark[x][y]);
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int kase, x, y;
cin >> kase;
while(kase--) {
cin >> n >> m;
ans = -1;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
int idx = i * n + j;
nodes[idx].father = idx;
nodes[idx].minr = nodes[idx].maxr = i;
}
}
for(int i = 1; i <= m; i++) {
cin >> x >> y;
mark[x][y] = true;
if(ans != -1) continue;
int f1 = x * n + y;
for(int j = 0; j < 4; j++) {
int nx = x + dx[j][0], ny = y + dx[j][1];
if(!ok(nx, ny)) continue;
int f2 = getFather(nx * n + ny);
if(f1 == f2) continue;
nodes[f1].father = f2;
nodes[f2].minr = min(nodes[f1].minr, nodes[f2].minr);
nodes[f2].maxr = max(nodes[f1].maxr, nodes[f2].maxr);
f1 = f2;
if(nodes[f2].minr == 1 && nodes[f2].maxr == n) {
ans = i; break;
}
}
}
cout << ans << endl;
}
return 0;
}
D:Palindrome
动态规划，注意dp数组要用short存
AC代码：
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 5005;
int n;
char s[maxn];
short dp[maxn][maxn];
short min(short x, short y) {
return (x<y)?x:y;
}
int main() {
scanf("%d%s", &n, s);
for(int j = 2; j <= n; j++) {
for(int i = n - j; i >= 0; i--) {
if(s[i] == s[i + j - 1])
dp[i][j] = dp[i + 1][j - 2];
else dp[i][j] = min(dp[i][j - 1] + 1, dp[i + 1][j - 1] + 1);
}
}
printf("%d\n", dp[0][n]);
return 0;
}
E:重要逆序对
总时间限制: 1000ms 内存限制: 256000kB
描述
给定N个数的序列a1,a2,...aN，定义一个数对(ai, aj)为“重要逆序对”的充要条件为 i < j 且 ai > 2aj。求给定序列中“重要逆序对”的个数。
输入
本题有多个测试点，每个测试点分为两行：第一行为序列中数字的个数N（1 ≤ N ≤ 200000），第二行为序列a1, a2 ... aN(0 ≤a ≤ 10000000)，由空格分开。N=0表示输入结束。
输出
每个测试点一行，输出一个整数，为给序列中“重要逆序对”的个数。
样例输入
10
0 9 8 7 6 5 4 3 2 1
0
样例输出
16
提示
请注意答案范围，如果使用printf输出long long类型，请用%lld
AC代码
#include<iostream>
using namespace std;
#define LL long long
const int maxn = 2e5 + 5;
int n, a[maxn], b[maxn];
LL ans;
int binarySearch(int l, int r, int val) {
int ret = r + 1;
while(l <= r) {
if(l == r) {
if(a[l] > val) ret = l;
break;
}
int mid = (l + r) >> 1;
if(a[mid] > val) {
ret = mid; r = mid;
}
else l = mid + 1;
}
return ret;
}
void merge(int l, int mid, int r) {
int i = l, j = mid + 1, cnt = 0;
while(cnt < r - l + 1) {
if(i > mid)
b[cnt++] = a[j++];
else if(j > r)
b[cnt++] = a[i++];
else if(a[i] > a[j]) {
ans += mid - binarySearch(i, mid, 2 * a[j]) + 1;
b[cnt++] = a[j++];
}
else
b[cnt++] = a[i++];
}
for(int k = 0; k < cnt; k++)
a[l + k] = b[k];
}
void mergeSort(int l, int r) {
if(l == r) return;
int mid = (l + r) >> 1;
mergeSort(l, mid);
mergeSort(mid + 1, r);
merge(l, mid, r);
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
while(cin >> n && n) {
ans = 0;
for(int i = 0; i < n; i++)
cin >> a[i];
mergeSort(0, n - 1);
cout << ans << endl;
}
return 0;
}
F:Jamie's Contact Groups
AC代码
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
#define PII pair<int, int>
#define pb push_back
#define mp make_pair
const int maxn = 2000;
const int inf = 0x7fffffff;
struct Edge {
int src, dst, val;
Edge() {}
Edge(int s, int d, int v): src(s), dst(d), val(v) {}
};
int n, m, id, l, r, dep[maxn];
char s[20], c;
vector<Edge> edges;
vector<int> eindex[maxn];
vector<int> linklst[maxn];
void addEdge(int s, int d, int v) {
edges.pb(Edge(s, d, v));
edges.pb(Edge(d, s, 0));
int len = edges.size();
eindex[s].pb(len - 2);
eindex[d].pb(len - 1);
}
bool bfs() {
memset(dep, -1, sizeof(dep));
queue<int> q;
q.push(0);
dep[0] = 0;
while(!q.empty()) {
int hd = q.front();
q.pop();
for(int i = 0; i < eindex[hd].size(); i++) {
Edge e = edges[eindex[hd][i]];
if(dep[e.dst] != -1 || e.val == 0)
continue;
q.push(e.dst);
dep[e.dst] = dep[hd] + 1;
if(e.dst == n + m + 1) return true;
}
}
return false;
}
int dfs(int cur, int flow) {
if(cur == n + m + 1) {
return flow;
}
int ret = 0;
for(int i = 0; i < eindex[cur].size(); i++) {
int idx = eindex[cur][i];
Edge e = edges[idx];
if(e.val == 0 || dep[e.dst] != dep[cur] + 1)
continue;
int delta = dfs(e.dst, min(flow, e.val));
if(delta > 0) {
edges[idx].val -= delta;
edges[idx ^ 1].val += delta;
}
ret += delta;
flow -= delta;
if(flow <= 0) break;
}
return ret;
}
int dinic() {
int ret = 0;
while(bfs()) {
ret += dfs(0, inf);
}
return ret;
}
int main() {
#ifdef LOCAL
freopen("1.in", "r", stdin);
#endif
while(true) {
scanf("%d%d", &n, &m);
if(n == 0 && m == 0) break;
edges.clear();
for(int i = 0; i < maxn; i++)
eindex[i].clear();
for(int i = 1; i <= n; i++) {
scanf("%s", s);
addEdge(0, i, 1);
while(true) {
scanf("%d%c", &id, &c);
addEdge(i, n + id + 1, 1);
linklst[i].pb(n + id + 1);
if(c == '\n') break;
}
}
int len1 = edges.size();
for(int i = 1; i <= m; i++) {
addEdge(n + i, n + m + 1, 0);
}
int len2 = edges.size();
l = 0, r = n;
while(l < r) {
int mid = (l + r) >> 1;
for(int i = 0; i < edges.size(); i++) {
if(edges[i].dst < edges[i].src)
edges[i].val = 0;
else if(edges[i].dst == n + m + 1)
edges[i].val = mid;
else edges[i].val = 1;
}
int flow = dinic();
// printf("%d %d\n", mid, flow);
if(flow < n)
l = mid + 1;
else
r = mid;
}
printf("%d\n", l);
}
return 0;
}
G:昂贵的聘礼
AC代码
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
#define PII pair<int, int>
#define pb push_back
#define mp make_pair
const int maxn = 105;
const int inf = 0x7fffffff;
int m, n, p, l, x, t, v, ans = inf;
int level[maxn];
bool flag[maxn];
vector<PII> e[maxn];
struct cmp {
bool operator () (const PII &p1, const PII &p2) {
return p1.second > p2.second;
}
};
int dijkstra(int src, int dst) {
priority_queue<PII, vector<PII>, cmp> q;
q.push(mp(src, 0));
int ret = inf;
while(true) {
while(!q.empty() && flag[q.top().first])
q.pop();
if(q.empty()) break;
int id1 = q.top().first, dis1 = q.top().second;
q.pop();
flag[id1] = true;
if(id1 == dst) {
ret = dis1; break;
}
for(int i = 0; i < e[id1].size(); i++) {
int id2 = e[id1][i].first, dis2 = e[id1][i].second;
if(flag[id2]) continue;
q.push(mp(id2, dis2 + dis1));
}
}
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin >> m >> n;
for(int i = 1; i <= n; i++) {
cin >> p >> l >> x;
e[0].pb(mp(i, p));
level[i] = l;
while(x--) {
cin >> t >> v;
e[t].pb(mp(i, v));
}
}
for(int i = 1; i <= n; i++) {
memset(flag, 0, sizeof(flag));
for(int j = 1; j <= n; j++)
if(level[j] - level[i] > m || level[j] < level[i])
flag[j] = true;
ans = min(ans, dijkstra(0, 1));
}
cout << ans << endl;
return 0;
}
H:最小路径覆盖
总时间限制: 10000ms 单个测试点时间限制: 1000ms 内存限制: 10000kB
描述
给定有向图G=(V,E)。设P 是G 的一个简单路（顶点不相交）的集合。如果V 中每个顶点恰好在P 的一条路上，则称P是G 的一个路径覆盖。P 中路径可以从V 的任何一个顶点开始，长度也是任意的，特别地，可以为0。G 的最小路径覆盖是G 的所含路径条数最少的路径覆盖。
设计一个有效算法求一个有向无环图G 的最小路径覆盖。
输入
第1行有2个正整数m和n。m是G 的边数，n是给定有向无环图G 的顶点数。
接下来的m行，每行有2个正整数i和j，表示一条有向边(i,j)。
输出
1行，只输出最少路径数。
样例输入
9 11
2 3
5 2
3 6
9 8
9 10
5 8
2 9
10 7
6 8
样例输出
5
提示
n<=500,m<=500
注: 裸的最小不相交路径覆盖问题
AC代码：
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 505;
struct Edge {
int src, dst, val;
Edge() {}
Edge(int s, int d, int v) : src(s), dst(d), val(v) {}
};
int n, m;
int depth[maxn * 2];
vector<vector<int> > linklst;
vector<Edge> edges;
void addEdge(int src, int dst) {
edges.push_back(Edge(src, dst, 1));
edges.push_back(Edge(dst, src, 0));
int len = edges.size();
linklst[src].push_back(len - 2);
linklst[dst].push_back(len - 1);
}
bool bfs() {
queue<int> q;
q.push(0);
memset(depth, -1, sizeof(depth));
depth[0] = 0;
while(!q.empty()) {
int hd = q.front();
q.pop();
for(int i = 0; i < linklst[hd].size(); i++) {
int idx = linklst[hd][i];
Edge e = edges[idx];
if(depth[e.dst] != -1 || e.val == 0) continue;
depth[e.dst] = depth[hd] + 1;
if(e.dst == 2 * n + 1) return true;
q.push(e.dst);
}
}
return false;
}
int dfs(int idx) {
if(idx == 2 * n + 1) return 1;
for(int i = 0; i < linklst[idx].size(); i++) {
int eid = linklst[idx][i];
Edge e = edges[eid];
if(e.val == 0 || depth[e.dst] != depth[idx] + 1)
continue;
if(dfs(e.dst) != 0) {
edges[eid].val -= 1;
edges[eid ^ 1].val += 1;
return 1;
}
}
return 0;
}
int dinic() {
int ret = 0;
while(bfs())
ret += dfs(0);
return ret;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> m >> n;
linklst.resize(2 * n + 2);
for(int i = 1; i <= n; i++) {
addEdge(0, i);
addEdge(n + i, 2 * n + 1);
}
int st, ed;
for(int i = 0; i < m; i++) {
cin >> st >> ed;
addEdge(st, ed + n);
}
int maxFlow = dinic();
cout << n - maxFlow << endl;
return 0;
}
