时间有点晚, 第二天早上补的...... 比赛的时候只做出来前两道题......手动忽略了C题某条件, WA不止......D题差10分钟写完. 积累了一点有关eps的经验. 题解: 5/7.
A. Oleg and shares
n个数ai, 每次可以选一个减少k, 问最少多少次操作后, 所有数可以变得相等. (1≤n≤10^5, 1≤k,ai≤10^9)
a1 - t1 k = a2 - t2 k <=> a2 - a1 = (t2 - t1)k
令最小的ai为m, 当且仅当对所有j, (aj - m) mod k = 0时有解, 答案为 Σ(aj-m)/k.
typedef long long ll;
ll a[(int)1e5];
int main()
{
ios::sync_with_stdio(false);
int n;
ll k, mn = 1e9 + 1;
cin >> n >> k;
rep (i, 0, n) {
cin >> a[i];
mn = min(a[i], mn);
}
ll ans = 0;
rep (i, 0, n) {
if ((a[i] - mn) % k) {
cout << "-1" << endl;
return 0;
}
ans += (a[i] - mn) / k;
}
cout << ans << endl;
return 0;
}B. Igor and his way to work
n行m列的地图, 可以上, 下, 左, 右走, 有些位置不可通行, 初始方向任意. 问方向改变次数不超过2, 起点是否可以到达终点. (1≤n,m≤1000)
BFS. 状态为 (行, 列, 当前方向, 方向改变次数).
const int N = 1e3, dx[] = {1, -1, 0, 0}, dy[] = {0, 0, -1, 1};
typedef pair<int, int> Pair;
bool f[N][N][4][3];
char s[N][N+1];
struct State {
int x, y, d, c;
};
queue<State> Q;
inline void ext(const State& s)
{
bool& g = f[s.x][s.y][s.d][s.c];
if (!g) {
g = true;
Q.push(s);
}
}
int main()
{
int n, m;
Pair S, T;
scanf("%d%d", &n, &m);
rep (i, 0, n) {
scanf("%s", s[i]);
rep (j, 0, m) {
if (s[i][j] == 'S')
S = Pair(i, j);
else if (s[i][j] == 'T')
T = Pair(i, j);
}
}
rep (i, 0, 4)
ext((State){S.first, S.second, i, 0});
while (!Q.empty()) {
State u = Q.front();
if (u.x == T.first && u.y == T.second) {
puts("YES");
return 0;
}
Q.pop();
if (u.c <= 1) {
rep (i, 0, 4)
ext((State){u.x, u.y, i, u.c + 1});
}
State v = (State){u.x + dx[u.d], u.y + dy[u.d], u.d, u.c};
if (v.x >= 0 && v.x < n && v.y >= 0 && v.y < m && s[v.x][v.y] != '*')
ext(v);
}
puts("NO");
return 0;
}C. Mice problem
二维平面上n只老鼠做匀速直线运动. 给出它们的初始位置坐标, 沿x轴, y轴的分速度, 问它们何时第一次同时严格位于某矩形内, 或报告无解. (1≤n≤10^5, 0≤坐标≤10^5, |分速度|≤10^5)
解一解方程求交集就好了, 然而......
题面中说strictly inside.
这个有点古怪. 想了想, 我把它手动忽略了...... (不明白自己为什么这么做)
然后WA.
可以把矩形的边界 (x1, x2) 当成 [x1+eps, x2-eps] 处理, 注意eps不能设得太大. 也可以手写分数类.
我保留了 (l, r), 判断是否有 r-l > eps. eps应小于10^-10.
const double eps = 5e-11, inf = 1e70;
bool cal(double r, double v, double x1, double x2, double& t1, double& t2)
{
x1 -= r;
x2 -= r;
if (fabs(v) < eps) {
if (x2 > eps && x1 < -eps) {
t1 = 0;
t2 = inf;
return true;
} else {
return false;
}
} else if (v > 0) {
t1 = max(0., x1/v);
t2 = x2/v;
} else {
t1 = max(0., x2/v);
t2 = x1/v;
}
return t2 - t1 > eps;
}
inline bool intersection(double a, double b, double c, double d, double& e, double& f)
{
e = max(a, c);
f = min(b, d);
return f - e > eps;
}
const int N = 1e5;
double s[N], t[N];
int main()
{
int n, x1, x2, y1, y2;
scanf("%d%d%d%d%d", &n, &x1, &y1, &x2, &y2);
rep (i, 0, n) {
double t1, t2, t3, t4;
int rx, ry, vx, vy;
scanf("%d%d%d%d", &rx, &ry, &vx, &vy);
if (!(cal(rx, vx, x1, x2, t1, t2)
&& cal(ry, vy, y1, y2, t3, t4)
&& intersection(t1, t2, t3, t4, s[i], t[i]))) {
puts("-1");
return 0;
}
}
rep (i, 1, n)
if (!intersection(s[0], t[0], s[i], t[i], s[0], t[0])) {
puts("-1");
return 0;
}
printf("%.8f\n", s[0]);
return 0;
}D. Presents in Bankopolis
直线上依次有n个点. m条带权的单向道路. 要求选出一条恰经过k个不同点的路径, 并且, 如果走u->v, 那么(min(u,v), max(u,v))上不能有已经过的点. 求路径的最小总长度, 或报告无解. (1≤n,k≤80, 0≤m≤2000)
画一画图, 发现下一步的选择是一个区间, 所以状态可以这样表示: f[x][y][z][w], [x,y]是可选区间, 当前在z, 经过了w条边; 然后, 进行DP.
见过类似的题, 我刚理解题意, 它就被马老师秒掉了......
好像复杂度比较高......大胆猜测合法状态是稀疏的, 跑一个记忆化搜索, 然后就可以AC了.
实现的时候犯了个错误......dp数组中, inf是一个合法的量, 我却同时用它判断状态是否计算过.
Editorial提出了一个优化: [x,y] -> [z+1,y], 无须知道x; [x,y] -> [x,z-1], 无须知道y. 所以, 把状态压缩成三维: f[x][y][w], 直接规定下一步朝哪转移. 现在的位置是y. 当y>x, 下一步可以走[x,y-1]; 当y<x, 下一步可以走[y+1,x].
const int N = 80, inf = (1<<30)-1;
int k, f[N][N][N][N];
bool vis[N][N][N][N];
struct Edge {
int v, w;
};
vector<Edge> adj[N];
int dp(int x, int y, int z, int w)
{
int& now = f[x][y][z][w];
bool& visited = vis[x][y][z][w];
if (visited) return now;
visited = true;
if (w == k-1) return now = 0;
now = inf;
if (x > y) return now;
rep (i, 0, adj[z].size()) {
int t = adj[z][i].v;
if (t >= x && t <= y) {
if (t < z)
now = min(now, dp(x, z-1, t, w+1) + adj[z][i].w);
else
now = min(now, dp(z+1, y, t, w+1) + adj[z][i].w);
}
}
return now;
}
int main()
{
int n, m;
scanf("%d%d%d", &n, &k, &m);
rep (i, 0, m) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
--u;
--v;
if (u != v)
adj[u].push_back((Edge){v, w});
}
int ans = inf;
rep (i, 0, n)
ans = min(ans, dp(0, n-1, i, 0));
printf("%d\n", ans == inf ? -1 : ans);
return 0;
}E. Problem of offices
n个点的有根树. a,b,c,d是叶子结点, 且两两之间的最短路经过根结点. 问是否存在一种欧拉序S, 头尾相接并合并后, S(a..b)上叶子的数目等于S(b..a)上叶子的数目, S(c..d)上叶子的数目等于S(d..c)上叶子的数目. (5≤n≤5000)
设叶子的总数为m. 当m为奇数时无解, 以下假设m为偶数.
如果只有一对点a,b, 很好办. 这样看待: 
问题转化为0-1背包.
但是有两对点. 怎样保证两个条件能同时满足呢?
看了题解, 需要一点构造.
可以约定这样走: a->c->b->d->a. 根据题设, a,b,c,d在根的不同子树中.
考虑a->c->b. 我们在c所在的子树中转了一圈. ban掉b,c所在子树, 做0-1背包.
同样地, c->b->d. ban掉a,b所在子树, 做0-1背包.
如果a->c->b存在一条经过(m/2-1-c所在子树的叶子数目)个叶子的欧拉环游路径, 并且c->b->d存在一条经过(m/2-1-b所在子树的叶子数目)个叶子的欧拉环游路径, 那么有解, 否则无解.
正确性yy一下......?
const int N = 5000;
bitset<N/2> ab, cd;
vector<int> adj[N+1];
int fa[N+1], sz[N+1];
bool ban[N+1];
int dfs(int u)
{
if (!adj[u].size()) {
sz[u] = 1;
} else {
rep (i, 0, adj[u].size())
sz[u] += dfs(adj[u][i]);
}
return sz[u];
}
int up(int v)
{
int u = v;
while (fa[u] != 1)
u = fa[u];
ban[u] = true;
return u;
}
void cal(bitset<N/2>& b, int v)
{
int u = fa[v];
while (u != 1) {
rep (i, 0, adj[u].size()) {
int w = adj[u][i];
if (w != v)
b |= b << sz[w];
}
v = u;
u = fa[u];
}
}
int main()
{
int n, a, b, c, d;
scanf("%d%d%d%d%d", &n, &a, &b, &c, &d);
rep (i, 2, n+1) {
scanf("%d", fa+i);
adj[fa[i]].push_back(i);
}
int m = dfs(1);
if (m & 1) {
puts("NO");
return 0;
}
up(a);
up(d);
int bb = up(b), cc = up(c);
if (m/2-1 < sz[cc] || m/2-1 < sz[bb]) {
puts("NO");
return 0;
}
ab[0] = 1;
rep (i, 0, adj[1].size()) {
int v = adj[1][i];
if (!ban[v])
ab |= ab << sz[v];
}
cd = ab;
cal(ab, a);
cal(ab, b);
if (!ab[m/2-1-sz[cc]]) {
puts("NO");
return 0;
}
cal(cd, c);
cal(cd, d);
if (!cd[m/2-1-sz[bb]]) {
puts("NO");
return 0;
}
puts("YES");
return 0;
}