T1 珠江夜游
题目描述:
小 Z 放假后难得来一趟广州游玩,当然要吃遍广州各路美食小吃然后再
到珠江新城看看远近闻名的小蛮腰啦!可当小 Z 一路吃吃吃以后,天渐渐黑了,
珠江边上的建筑全亮起了灯,好看得不要不要的,于是小 Z 决定搭乘游艇从西
边的广州港沿着珠江夜游到小蛮腰脚下。小 Z 的游艇一路向东,可小 Z 却感觉
船动得出奇的慢,一问船家才知道,原来今天珠江上堵船了。
我们可以把供游艇航行的航道看作一条单行道,航道上 N+1 艘游艇自西
向东依次编号为 0..N,小 Z 所在的游艇在最西边编号为 0,而编号为 N 的游艇
还要再往东航行一段才是小蛮腰。由于晚上航行视野不佳,排在后面的船不允
许超越前面的船,而当前面的船航行速度太慢时,后面的船只能以相同的速度
紧跟着,此时两船之间的距离可以忽略。
已知第 i 艘游艇船身长为 L[i],船头与小蛮腰距离为 X[i],最大航行速
度为 V[i]。小 Z 好奇,他到底要等多久,才能乘着游艇经过小蛮腰脚下呢?
输入格式:
第一行为测试数据组数 T,表示接下来有 T 组数据。
每组测试数据第一行为一个正整数 N,表示排在小 Z 前面的游艇数量。
接下来 3 行,每行包含 N+1 个数字,每行的第 i 个数字分别为 L[i],
X[i]和 V[i],含义见题面描述。
输出格式:
每组测试数据输出一行,包含一个实数,表示小 Z 要等待的时间,至少
保留三位小数。
设你的输出答案和标准答案分别为 a 和 b,若 fabs(a-b)/max(1,b)<1e-3,
则认为你的输出答案是正确的。
样例输出:
2
1
2 2
7 1
2 1
2
1 2 2
10 7 1
6 2 1
样例输出:
3.500
5.000
思路:
二分,最终答案time,然后二分check的时候开一个数组,存一下当前的船最终能到达的离
目标的位置,那么头一个船的位置就是二分到的时间乘上他的速度.
后边的船还要考虑一下前边的船是不是挡着他.
如果前边的船能当着他那就是.
两种情况.
一种就是当前的船的速度比前边的船快的时候.
前边的船的最终距离加上前边那个船的船长.
第二种就是当前的船比前边的船慢的时候.
和一开始离小蛮腰的距离减去它能行驶的最大距离取一个max.
因为他是前边挡着的,当然要取一个max.
然后得到的距离是不是在一个精度误差(1e-3)之内.
code
#include <bits/stdc++.h> #define N 100010 #define ll long long using namespace std; double l[N], v[N], x[N], a[N]; int n; ll read() { ll s = 0, f = 0; char ch = getchar(); while (!isdigit(ch)) f |= (ch == '-'), ch = getchar(); while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar(); return f ? -s : s; } bool check(double tim) { for (int i = 0; i <= n; i++) a[i] = x[i]; a[n] = a[n] - tim * v[n]; for (int i = n - 1; i >= 0; i--) { double ddd = tim * v[i]; a[i] = max(a[i] - ddd, a[i + 1] + l[i + 1]); if (a[i] > 1e-3) return false; } return true; } int main() { // freopen("cruise.in", "r", stdin); // freopen("cruise.out", "w", stdout); int T = read(); while (T--) { n = read(); for (int i = 0; i <= n; i++) l[i] = read(); for (int i = 0; i <= n; i++) x[i] = read(); for (int i = 0; i <= n; i++) v[i] = read(); double l = 0, r = 1000000000; while (r - l > 1e-5) { double mid = (r + l) / 2.0; if (check(mid)) r = mid; else l = mid; } printf("%.5lf\n", r); } }
T2 旅行计划
解题思路:
每个连通块显然是独立的。对于一个连通块(除了单个点的),如果奇度数点个数 为 k,那么至少需要 max(k/2,1)条路径。
这是因为在一个无向图中,将两个度数为奇数的 点连起来,就可以消去两个奇数点。
所以如果一个无向图要有欧拉回路(全部点的度数全 为偶数),只要加 k/2 条边就可以了。
于是乎,我们只要将一个连通块变成欧拉图,搜一 遍得到路径,再将我们人为添加的边删掉,剩下的就是这个连通块的"笔画"了。
这里为什么一定变成欧拉回路而不是欧拉通路,其实这里欧拉回路和欧拉通路都是 可以的,得到的答案是一样的。
主要是算法实现上的问题,如果变成欧拉通路,就一定得 从剩下的两个奇数点出发,终止。
至于为什么这里加 k/2 条边后扫出的结果删掉多加的边 就是答案,并且这个答案=max(k/2,1)呢?
这是因为一个图中,我们从奇数点开始走,停止 的也一定是在奇数点,
那么再一遍遍不重复地从图中走出一条条类似前面地路径(奇数点 开始,奇数点结束)然后我们将这些路径地终点连接下一条路径的起点(多加的边),
这样又 因为每一条路径的起止点都为奇数点,一条边删去两个奇数点。
所以最终把他们连成欧拉 回路所需的边的数量就是 k/2。
code:
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <queue> #include <stack> #include <vector> #define int long long #define MAXN 500000 #define INF 1e9 + 7 using namespace std; struct node { int u, v, w, next, vis; } edge[MAXN]; int head[MAXN], num, vis[MAXN], n, m, ans, cnt[MAXN]; vector<int> b[MAXN]; inline int read() { int s = 0, f = 0; char ch = getchar(); while (!isdigit(ch)) f |= (ch == '-'), ch = getchar(); while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar(); return f ? -s : s; } inline void build(int u, int v, int w) { num++; edge[num].u = u, edge[num].v = v; edge[num].w = w, edge[num].vis = 0; edge[num].next = head[u], head[u] = num; } void dfs(int u) { vis[u] = 1; for (int i = head[u]; i; i = edge[i].next) { int v = edge[i].v; if (edge[i].vis) continue; edge[i].vis = 1; if (i % 2 != 0) edge[i + 1].vis = 1; else edge[i - 1].vis = 1; dfs(v); if (edge[i].w != INF) b[ans].push_back(-edge[i].w); else ans++; } } signed main() { // freopen("travelling.in", "r", stdin); // freopen("travelling.out", "w", stdout); int t = read(); while (t--) { num = ans = 0; n = read(), m = read(), ans = 0; for (int i = 1; i <= m; i++) { int u = read(), v = read(); build(u, v, i); build(v, u, -i); cnt[u]++; cnt[v]++; } int now = 0; for (int i = 1; i <= n; i++) if (cnt[i] % 2 != 0) if (now) { build(now, i, INF); build(i, now, INF); now = 0; } else now = i; for (int i = 1; i <= n; i++) if (!vis[i] && cnt[i] % 2 != 0) { ans++; dfs(i); ans--; } for (int i = 1; i <= n; i++) if (!vis[i] && cnt[i]) { ans++; dfs(i); } cout << ans - 1; puts(""); for(int i = 1; i <= ans; i++) { int len = b[i].size(); cout << len << ' '; for(int j = 0; j < len; j++) cout << b[i][j] << ' '; puts(""); b[i].clear(); } for (int i = 1; i <= n; i++) vis[i] = cnt[i] = head[i] = 0; } return 0; }
T3
解题思路:
用f[i][j][k][l]来表示当前矩阵左上角为i,j 右下角为k,l的矩阵的最优解.
可以先从最小的一行来看,我们不会分着去取,以为那样的贡献会非常大,然后矩阵上也一样.
我们一定是取一个矩阵,然后不断地加一行或者一列,然后我们枚举四边加一行或一列需要的
贡献,然后取一个最小值,然后加上去,这样dfs.
code
#include<cstdio> #include<iostream> #include<cstdlib> #include<ctime> #include<queue> #include<vector> #include<cstring> using namespace std; typedef long long ll; const int N = 10; int f[N][N][N][N]; char s[N][N]; ll read() { int s = 0, f = 0; char ch = getchar(); while (!isdigit(ch)) f |= (ch == '-'), ch = getchar(); while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar(); return f ? -s : s; } int calc(int x1, int x2, int y1, int y2, int xx1, int xx2, int yy1, int yy2) { int mnx = 1e9, mxx = 0, mny = 1e9, mxy = 0; for (int i = xx1; i <= xx2; ++i) for (int j = yy1; j <= yy2; ++j) if (s[i][j] == '#') { mnx = min(mnx,i); mxx = max(mxx,i); mny = min(mny,j); mxy = max(mxy,j); } if(mxx == 0) return 0; int ans = 0; for (int i = x1; i <= x2; ++i) for (int j = y1; j <= y2; ++j) if (s[i][j] == '#') ans += max(abs(i - mnx),max(abs(i - mxx),max(abs(j - mny),abs(j-mxy)))); return ans; } int dfs(int x1, int y1, int x2, int y2) { if (x1 > x2 || y1 > y2) return 0; if (f[x1][y1][x2][y2] != -1) return f[x1][y1][x2][y2]; int ret = dfs(x1 + 1,y1,x2,y2) + calc(x1,x1,y1,y2,x1,x2,y1,y2); ret = min(ret,dfs(x1,y1 + 1,x2,y2) + calc(x1,x2,y1,y1,x1,x2,y1,y2)); ret = min(ret,dfs(x1,y1,x2 - 1,y2) + calc(x2,x2,y1,y2,x1,x2,y1,y2)); ret = min(ret,dfs(x1,y1,x2,y2 - 1) + calc(x1,x2,y2,y2,x1,x2,y1,y2)); return f[x1][y1][x2][y2] = ret; } int main() { // freopen("station.in","r",stdin); // freopen("station.out","w",stdout); for(int i = 1; i <= 8; ++i) scanf("%s",s[i] + 1); memset(f,-1,sizeof(f)); cout << dfs(1,1,8,8); return 0; }