9.20 考试
（某窦老师的题）表示以后不想看到这名字，肽毒瘤
T1
题意:
我们可以把供游艇航行的航道看作一条单行道，航道上 (N+1) 艘游艇自西 向东依次编号为 (0..N)，小 Z 所在的游艇在最西边编号为 0，而编号为 (N) 的游艇 还要再往东航行一段才是小蛮腰。由于晚上航行视野不佳，排在后面的船不允 许超越前面的船，而当前面的船航行速度太慢时，后面的船只能以相同的速度 紧跟着，此时两船之间的距离可以忽略。 已知第 i 艘游艇船身长为 (L[i])，船头与小蛮腰距离为 (X[i])，最大航行速 度为 (V[i])。小 Z 好奇，他到底要等多久，才能乘着游艇经过小蛮腰脚下呢??
反思： 考场上先是想了贪心（显然是不对的），，又推了DP，
$f_i=max(X_i/V_i, f_{i+1}+L_{i+1}/V_{i+1}) $
最后的时候发现好像也是不对的，没有考虑过线后其实也在堵着。。。然后就凉了；
倒是(yych),很涩会，机房唯一一个切此题的人%%%%%
正解是实数域上二分：
可以看出答案是具有单调性的， 所以我们可以二分一个时间，判断它成不成立。
设(dis =tim*V_i) (lin_i) 为(tim)时间后第(i)个船离小蛮腰还有多久
则就有dp ： (lin[i]=max(lin[i]-dis, l[i+1]+lin[i+1]));
((lin[i])初值赋的(X[i]))
然后只需判断是不是所有的穿都能越过小蛮腰啊~~
PS:(c++11)用“%lf“会屎的很惨
/***********丝毫不慌********/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 100005
using namespace std;
double l[N], x[N], v[N];
double f[N], lin[N];
int n, t;
bool check(double tim)
{
for(int i = 0; i <= n; i ++) lin[i] = x[i];
lin[n] = lin[n] - tim*v[n];
for(int i = n-1; i >= 0; i--)
{
double dis = tim*v[i];
lin[i] = max(lin[i] - dis, l[i+1] + lin[i+1]);
if(lin[i] > 0) return false;
}
return true;
}
void solve1()
{
double L = 0.0, R = 1e8;
while((R - L) > 1e-3)
{
double mid = (R+L)/2.0;
if(check(mid)) R = mid;
else L = mid;
}
printf("%.4f
", L);
}
signed main()
{
freopen("cruise.in","r",stdin);
freopen("cruise.out","w",stdout);
scanf("%d",&t);
while(t --)
{
scanf("%d",&n);
for(int i = 0; i <=n; i ++ )
scanf("%lf",&l[i]);
for(int i = 0; i <= n;i ++)
scanf("%lf",&x[i]);
for(int i = 0; i <= n; i++)
scanf("%lf",&v[i]);
solve1();
}
return 0;
}
T2
题意：
小 Z 事先准备了一份地图，地图上给出了 N 个小 Z 心仪的城市，依次编号 1…N，以及 M 条连接两个城市的路，编号 1…M。小 Z 打算把 M 条路都走一遍且 仅一遍，但他发现这样的路线可能是不存在的。于是他打算，当他走到一个城 市后发现从这个城市出发的道路他都已经走过了，他便会坐飞机到另一个城市， 然后继续他的旅行。 现在小 Z 想知道，在最好的路线计划下，他至少要坐多少趟飞机 。。
【输入格式】 第一行为测试数据组数 T（1≤T≤10）。 每组测试数据的第一行为城市数 N 及道路数 M。 接下来 M 行，每行两个整数 x 和 y，表示一条连接城市 x 和城市 y 的双向 道路。
【输出格式】 对于每组测试数据，输出第一行包含一个整数 K，表示小 Z 至少要坐多少 趟飞机。 接下来 K+1 行，第 i 行输出小 Z 的第 i 段行程。若第 i 段行程经过 x 条道 路，则先输出 x，然后输出 x 个整数，分别表示路线经过的道路的编号。若是 正向通过第 i 条道路，则输出 i，否则输出-i。 若有多组方案，输出任意一组。
（这不显然是一笔画问题吗。。。然而我并没有做过欧拉回路的题，不会，果断放弃）
性质：
- 一个欧拉回路里， 所有点度数均为偶数；
- 一个联通块内，度数为奇数的点的个数为偶数
思想：
把一个联通块内度数为奇数的点连起来（虚边），然后它就可以一笔画了；
那么换个角度想，连了多少条虚边，不就是坐了多少趟飞机吗；emm....
(然而毒瘤出题人还让你输出路径)
1.存边时把路径的权值赋成 id 或 -id
2.每遍历一条边就把它放到当前旅程vector里记录下来；
/***********丝毫不慌********/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 100010
using namespace std;
int read()
{
int x = 0, f = 1; char ch = getchar();
while(!isdigit(ch)) f = (ch =='-') ? -1 : 1, ch = getchar();
while(isdigit(ch)) x = (x<<3)+(x<<1)+(ch^48), ch = getchar();
return x * f;
}
int t, n, m, tot;
vector<int>v[N];
int nxt[N<<2], cnt = 1, to[N<<2], head[N], val[N<<2], vis[N], vis_e[N<<2], deg[N];
void add(int x, int y, int z)
{
to[++cnt] = y;
vis_e[cnt] = 0;
val[cnt] = z;
nxt[cnt] = head[x];
head[x] = cnt;
}
void dfs(int x) {
vis[x] = 1;
for(int i = head[x]; i; i = nxt[i])
{
if(vis_e[i] == 1) continue;
vis_e[i] = vis_e[i^1] =1;
dfs(to[i]);
if(val[i]) v[tot].push_back(-val[i]);
else tot++;
}
}
signed main()
{
freopen("travelling.in","r",stdin);
freopen("travelling.out","w",stdout);
t = read();
while(t --)
{
cnt = 1, tot = 0;
for(int i = 1; i <= n; i ++)
vis[i] = head[i] = deg[i] = 0;
n = read(); m = read();
for(int i = 1; i <= m; i++)
{
int x = read(), y = read();
add(x, y, i); add(y, x, -i);
deg[x] ++; deg[y] ++;
}
int last = 0;
for(int i = 1; i <= n; i ++) {//连虚边
if(deg[i]&1) {
if(last) add(i, last, 0), add(last, i, 0), last = 0;
else last = i;
}
}
for(int i = 1; i <= n; i ++) {
if(!vis[i]&&(deg[i]&1)) {
tot ++, dfs(i), tot --;
}
}
for(int i = 1; i <= n; i ++) {
if(!vis[i]&°[i]) {
tot ++, dfs(i);
}
}
// for(int i = 1; i <= m; ++ i )
printf("%d
",tot - 1);
for(int i = 1; i <= tot; i++)
{
int l = v[i].size();
printf("%d ",l);
for(int j = 0; j < l; j++)
printf("%d ",v[i][j]);
printf("
");
v[i].clear();
}
}
return 0;
}
T3
题意：
【题目描述】小 Z 的爸爸是一位通信工程师，他所在的通信公司最近接到了一个新的通 信工程建设任务，他们需要在 C 城建设一批新的基站。 C 城的城市规划做得非常好，整个城市被规整地划分为 8 行 8 列共 64 个街 区，现在已知新基站需要建设在哪些街区，用字符“#”表示，而不需要建设基 站的街区用“.”表示.. 爸爸告诉小 Z 说，建设基站最耗时的是基站两两之间互相通信的调试，每 建设一个新的基站，需要确保其与其他已经建好的基站之间能互相通信，若两 个基站的坐标分别为((x1,y1))和((x2,y2))，则调试所需时间大概为 (max(|x1- x2|,|y1-y2|))，而一个基站的总调试时间为与其他已经建好的基站的调试时间 中的最大值。现在爸爸想考考小 Z，看小 Z 能否计算出如何设计建设基站的顺 序，使得总的调试时间尽量少
【输入格式】 输入一个 8 行 8 列的矩阵，全部由“#”和“.”组成。
【输出格式】 输出一个整数，表示花费的最少时间。
【样例输入一】
........
........
...#....
.#......
.......#
........
........
........
【样例输出一】 8
思路：
数据10以内显然是可以暴力的，(n！)的那种(10！) 才3628800， 显然是可以过的；；
正解：（非正解）
先盗图（自己懒得画啦）
看上面这个图
（已经解释得很清楚）先放中间比先放四周优；
然后就考虑怎么先放中间 正解给的是一个不像dp的dp 然后我用的爆搜
（调了一个下午）；
大概思路就是：每次找到剩下的点构成的最大的矩阵（就是保证矩阵的上下左右边界都有点，之外没有），枚举最后放哪一行哪一列就行，往下搜就行，一直搜到只剩一个点；
一个比较麻烦的地方就是：回溯的时候比较难回溯，要把所有的点都记录下来；
然后ctrl+c， Ctrl+v 就行
（PS：不要觉得搜索过程很相近就无脑复制， 有些细微地方是很要命的， 要不也不会调一下午）；
/***********丝毫不慌***********/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
#define IT set<int>::iterator
#define RI register int
using namespace std;
int cnt, vis[100];
struct node
{
int x, y;
int val[100];
}e[100];
int ans = 1e9;
int zh_dou = 233333;
set <int >t[20];
void solve(RI v)
{
if(v == 1)
{
// cout<<ans<<endl;
zh_dou = min(ans, zh_dou);
return;
}
// cout<<ans<<endl;
RI tmp[100], top=0,maxx = -233333, maxy = -23333,minx = 233333, miny = 233333,flag,a1,a2,id,i;
IT it;
for(i = 1; i <= cnt; i ++)
{
if(vis[i]) continue;
maxx = max(maxx, e[i].x);
maxy = max(maxy, e[i].y);
minx = min(minx, e[i].x);
miny = min(miny, e[i].y);
}
flag = (maxx-minx) > (maxy - miny);
if((maxx-minx) == (maxy - miny)) flag = 2;
// cout<<maxx<<" "<<minx<<" "<<maxy<<" "<<miny<<endl;
if(flag == 1|| flag ==2)
{
/*********************/
a1 = t[maxx].size(),a2 = (maxx - minx) * t[maxx].size();
ans += a2;
for(it = t[maxx].begin(); it!=t[maxx].end(); it ++)
{
id = *it;
vis[id] = 1;
tmp[++top] = id;
t[e[id].y+8].erase(id);
}
solve(v-a1);
ans -= a2;
for(i = 1; i <= top; i++)
{
id = tmp[i];
t[e[id].y+8].insert(id);
vis[id] = 0;
}
/****************/
top = 0;
// cout<<maxx<<" "<<minx<<" "<<maxy<<" "<<miny<<endl;
a1 = t[minx].size();
a2 = (maxx - minx) * t[minx].size();
ans += a2;
for(it = t[minx].begin(); it!=t[minx].end(); it ++)
{
id = *it;
vis[id] = 1;
tmp[++top] = id;
t[e[id].y+8].erase(id);
}
solve(v-a1);
ans -= a2;
for(i = 1; i <= top; i++)
{
id = tmp[i];
t[e[id].y+8].insert(id);
vis[id] = 0;
}
/***************************/
}
if(flag == 0 || flag == 2)
{
/*********************/
a1 = t[maxy+8].size();
a2 = (maxy - miny) * t[maxy+8].size();
ans += a2;
for(it = t[maxy+8].begin(); it!=t[maxy+8].end(); it ++)
{
id = *it;
vis[id] = 1;
tmp[++top] = id;
t[e[id].x].erase(id);
}
solve(v-a1);
ans -= a2;
for(i = 1; i <= top; i++)
{
id = tmp[i];
t[e[id].x].insert(id);
vis[id] = 0;
}
/****************/
top = 0;
a1 = t[miny+8].size();
a2 = (maxy - miny) * t[miny+8].size();//*****//
ans += a2;
for(it = t[miny+8].begin(); it!=t[miny+8].end(); it ++)
{
id = *it;
vis[id] = 1;
tmp[++top] = id;
t[e[id].x].erase(id);
}
solve(v-a1);
ans -= a2;
for(i = 1; i <= top; i++)
{
id = tmp[i];
t[e[id].x].insert(id);
vis[id] = 0;
}
/***************************/
}
}
inline void solve2()
{
ans = 0;
RI n = cnt,i;
for(i = 1; i <= cnt; i ++)
{
t[e[i].x].insert(i);
t[e[i].y+8].insert(i);
}
solve(n);
printf("%d",zh_dou);
}
signed main()
{
freopen("station.in","r",stdin);
freopen("station.out","w",stdout);
char s[10];
for(RI i = 1,j; i <= 8; i ++)
{
scanf("%s",s+1);
for(j = 1; j <= 8; j++)
if(s[j] == '#')
{
e[++cnt].x = i;
e[cnt].y = j;
}
}
solve2();
return 0;
}
(color{red}{end})