【2016】 CSP - S 题解
T2
时间复杂度要求我们不能直接模拟运动员走过树上的所有边,
所以我们要想办法整体处理,枚举每个观察员,看哪些结点会为观察员作出贡献。
$dist[u] - dist[x] = w_x$,变式得,$dist[x] + w_x = dist[u]$,
另一边是,$dist[u]-2*dist[lca]=w[x]-dist[x]$,由于 $dist[u]$ 和 $dist[u]-2\*dist[lca]$
都是定值,既然要打包处理,一个很常见的想法是差分约束$+$树形桶。
最后用差分约束计算完,然后答案数组累计有多少个点满足。
值得一提的是,我们并没有作前缀和,因为只有 $dist[x] + w[x]$ 等的情况是满足的。
值得注意的是,因为上行下行的桶中的数可能重复累计,所以计入答案只看变化量。
#include <bits/stdc++.h>
using namespace std;
const int N = 300010, M = N * 2, L = 19; // 2^L > N
typedef pair<int, int> PII;
int n, m; // 结点数, 玩家数;
int h[N], e[M], ne[M], idx; // 邻接表存边
int depth[N], fa[N][L]; // 往上跳 2^0 ~ 2^19 步后的父亲节点
int ans[N]; // 答案数组
int Time[N]; // 出现观察员的时间
int da[M], db[M];
bool st[N]; // Dfs 时避免重复搜索
queue<int> q; // Bfs 队列
vector<PII> botel[N]; // 在同一条链上
vector<PII> dotel[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void bfs(int root) // Lca 预处理
{
memset(depth, 0x3f, sizeof depth); // 预处理
depth[0] = 0, depth[root] = 1; // 根结点的深度为1
q.push(root); // 从根节点开始遍历
while (q.size()) // 队列不空
{
int t = q.front(); // 取出队头
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i]; // 取与 t 相连接的节点
if (depth[j] > depth[t] + 1) // 当前点过深, 也就是没有更新过
{
depth[j] = depth[t] + 1; // 更新
q.push(j); // 加入队头
fa[j][0] = t; // 父节点为 t
for (int k = 1; k <= L - 1; k ++ ) // 预处理 fa[j] 往上走 2^{1 ~ 18} 步的父节点
{
fa[j][k] = fa[fa[j][k - 1]][k - 1];
// 因为BFS的 最短路性质, 所以一定是正确的
}
}
}
}
}
int lca(int a, int b) // 求最近公共祖先, 复杂度 O(log n)
{
if (depth[a] < depth[b]) swap(a, b); // 选深的
for (int k = L - 1; k >= 0; k -- ) // 往上跳, 二进制拆分思想
if (depth[fa[a][k]] >= depth[b])
{
a = fa[a][k];
}
if (a == b) return a;
for (int k = L - 1; k >= 0; k -- ) // 同时往上跳
if (fa[a][k] != fa[b][k])
{
a = fa[a][k];
b = fa[b][k];
}
return fa[a][0];
}
void update(int s, int t) // 玩家轨迹
{
int p = lca(s, t), f = fa[p][0]; // 找出 父节点 和 父节点的祖先
// 树上差分
botel[s].push_back({depth[s], 1}); // 要走的
botel[f].push_back({depth[s], -1}); // 不走的
int Lenth = depth[s] - 2 * depth[p] + n; // 此外,在使用第二个桶时,下标是w[x]-depth[x]会成为负数,所以使用第二个桶时,下标统一+SIZE,向右平移一段区间,防止下溢。
dotel[t].push_back({Lenth, 1}); // 要走的
dotel[p].push_back({Lenth, -1}); // 不走的
}
void dfs(int u) // 统计答案
{
// 统计 Va, Vb 在树形桶中有没有相等的元素。
int Va = Time[u] + depth[u], Vb = Time[u] - depth[u] + n; // 转换操作
// 此外,在使用第二个桶时,下标是w[x]-depth[x]会成为负数,所以使用第二个桶时,下标统一+SIZE,向右平移一段区间,防止下溢。
int res1 = da[Va], res2 = db[Vb];
st[u] = true;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j]) dfs(j);
}
for (int i = 0; i < botel[u].size() || i < dotel[u].size(); i ++ )
{
if (i < botel[u].size()) da[botel[u][i].first] += botel[u][i].second;
if (i < dotel[u].size()) db[dotel[u][i].first] += dotel[u][i].second;
}
ans[u] = (da[Va] - res1) + (db[Vb] - res2);
}
int main()
{
memset(h, -1, sizeof h); // 预处理
scanf("%d %d", &n, &m);
for (int i = 1; i < n; i ++ )
{
int u, v;
scanf("%d %d", &u, &v);
add(u, v), add(v, u); // 加双向边
}
for (int i = 1; i <= n; i ++ ) scanf("%d", &Time[i]);
int root = 1; // 根在一号节点
bfs(root);
for (int i = 1; i <= m; i ++ ) // 读入玩家
{
int s, t;
scanf("%d %d", &s, &t);
update(s, t);
}
dfs(1);
for (int i = 1; i <= n; i ++ ) printf("%d ", ans[i]);
return 0;
}
T3
$E(x) = P(x)w(x)$
由于去过一个教室后就要返回,所以状态只依赖于上一层,可以$DP$。
/*
状态表示:考虑前i个课程更换j次且第i个课程选择换/不换的最小期望行走距离
状态计算:min
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 2010, M = 310;
const double INF = 1e9;
int n, m, V, E;
int a[N], b[N], d[M][M];
double p[N], f[N][N][2];
int main()
{
scanf("%d%d%d%d", &n, &m, &V, &E);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++ ) scanf("%d", &b[i]);
for (int i = 1; i <= n; i ++ ) scanf("%lf", &p[i]);
memset(d, 0x3f, sizeof d);
for (int i = 1; i <= V; i ++ ) d[i][i] = d[0][i] = 0;
for (int i = 1; i <= E; i ++ )
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
d[u][v] = d[v][u] = min(d[u][v], w);
}
// 经过前k个的节点,i到j的最短路径(动态规划)
/* 每一趟二重循环,实际上都是在考察,
能不能经由k点,把i到j的距离缩短?*/
for (int k = 1; k <= V; k ++ )
for (int i = 1; i <= V; i ++ ) for (int j = 1; j <= V; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
for (int i = 0; i <= n; i ++ ) for (int j = 0; j <= m; j ++ )
for (int k = 0; k < 2; k ++ ) f[i][j][k] = INF;
f[1][0][0] = f[1][1][1] = 0;
for (int i = 2; i <= n; i ++ )
for (int j = 0; j <= m; j ++ )
{
f[i][j][0] = min(f[i-1][j][0]+d[a[i-1]][a[i]],
f[i-1][j][1]+p[i-1]*d[b[i-1]][a[i]]+(1-p[i-1])*d[a[i-1]][a[i]]);
if (j)
{
f[i][j][1] = min(f[i-1][j-1][0]+p[i]*d[a[i-1]][b[i]]+(1-p[i])*d[a[i-1]][a[i]],
f[i-1][j-1][1]+p[i]*p[i-1]*d[b[i-1]][b[i]]
+(1-p[i])*p[i-1]*d[b[i-1]][a[i]]
+p[i]*(1-p[i-1])*d[a[i-1]][b[i]]
+(1-p[i])*(1-p[i-1])*d[a[i-1]][a[i]]);
}
}
double res = INF;
for (int j = 0; j <= m; j ++ ) res = min(res, min(f[n][j][0], f[n][j][1]));
printf("%.2lf", res);
return 0;
}
T4
我们发现组合数可以预处理,如果预处理过程中有组合数是 $k$ 的倍数我们就统计,
下面的查询范围是一个区间,不难想到处理上述所统计的数的前缀和。
#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
int t, k;
int n, m;
int cmd[N][N];
int sum[N][N];
int main()
{
scanf("%d %d", &t, &k);
for (int i = 0; i <= 2000; i ++ ) cmd[i][0] = 1;
for (int i = 0; i <= 2000; i ++ )
for (int j = 1; j <= i; j ++ )
{
cmd[i][j] = (cmd[i - 1][j] + cmd[i - 1][j - 1]) % k;
if (!cmd[i][j]) sum[i][j] = 1;
}
for (int i = 1; i <= 2000; i ++ )
for (int j = 1; j <= 2000; j ++ )
{
sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}
while (t -- )
{
scanf("%d %d", &n, &m);
printf("%d\n", sum[n][m]);
}
return 0;
}
T5
我们切开蚯蚓位置的 $p$ 是固定的,所以我们可以想到去维护被切开蚯蚓的单调性,
那么先对原序列排序,用队列储存,将被切开蚯蚓的两个部分分别拿一个队列储存,
就维护了单调性,这是用队列实现不插入大于队内其它元素的优先队列的方法。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL; //一定要开long long 中间有过程量是爆int的
const LL N = 100010, M = 7000010;
LL n, m, q, u, v, t;
LL q1[N], q2[M], q3[M];
LL delta;
LL hh1, hh2, hh3, tt1, tt2 = -1, tt3 = -1;
LL get_max() //求三个队列中队首元素的最大值
{
LL x = -1e9;
if(hh1 <= tt1) x = max(x, q1[hh1]);
if(hh2 <= tt2) x = max(x, q2[hh2]);
if(hh3 <= tt3) x = max(x, q3[hh3]);
if(hh1 <= tt1 && x == q1[hh1]) hh1 ++;
else if(hh2 <= tt2 && x == q2[hh2]) hh2 ++;
else hh3 ++;
return x;
}
bool cmp(LL a, LL b) {
return a > b;
}
int main()
{
scanf("%d%d%d%d%d%d", &n, &m, &q, &u, &v, &t);
for(int i = 0; i < n; i ++) scanf("%lld", &q1[i]);
sort(q1, q1 + n, cmp); //对所有蚯蚓从大到小排序
tt1 = n - 1;
for(int i = 1; i <= m; i ++)
{
LL x = get_max();
x += delta;
if(i % t == 0) printf("%lld ", x);
LL left = x * 1 * u / v;
LL right = x - left;
delta += q;
left -= delta, right -= delta;
q2[ ++ tt2] = left, q3[ ++ tt3] = right;
}
puts("");
for(int i = 1; i <= n + m; i ++) {
LL x = get_max();
if(i % t == 0) printf("%lld ", x + delta);
}
puts("");
return 0;
}
T6
一般抛物线方程:$y = ax^2+bx+c$
题目中的抛物线有两个特点:
1. 过原点,$c = 0$
2. 开口向下,$a < 0$
由于有两个未知数,因此两点即可确定一条抛物线。
所以最多有$n^2$个不同的抛物线,接下来求出所有抛物线,及其能覆盖的所有点的点集。
它符合最优子结构形,可以用 $DP$ 求解。
/*
f[i] 当前点集覆盖状态为 i 时的最小抛物线数
属性:min
*/
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 18, M = 1 << N;
const double eps = 1e-8;
typedef pair<double, double> PDD;
int T, n, m;
PDD q[N];
int path[N][N];
int f[M];
int cmp(double x, double y)
{
if (fabs(x - y) < eps) return 0;
if (x > y) return 1;
return -1;
}
int main()
{
scanf("%d", &T);
while (T -- )
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) scanf("%lf%lf", &q[i].x, &q[i].y);
memset(path, 0, sizeof path);
for (int i = 0; i < n; i ++ )
{
path[i][i] = 1 << i;
for (int j = 0; j < n; j ++ )
{
double x1 = q[i].x, y1 = q[i].y;
double x2 = q[j].x, y2 = q[j].y;
if (!cmp(x1, x2)) continue; // x坐标相同,无法生成
/*解析式公式*/
double a = (y1 / x1 - y2 / x2) / (x1 - x2);
double b = y1 / x1 - a * x1;
if (cmp(a, 0) >= 0) continue;
int state = 0;
for (int k = 0; k < n; k ++ ) // 枚举它经过的所有点
{
double x = q[k].x, y = q[k].y;
if (!cmp(a * x * x + b * x, y)) state += 1 << k;
}
path[i][j] = state; // i, j 的所有经过的点数
}
}
memset(f, 0x3f, sizeof f);
f[0] = 0;
for (int i = 0; i + 1 < 1 << n; i ++ )
{
int x = 0;
for (int j = 0; j < n; j ++ )
{
if (!(i >> j & 1))
{
x = j;
break;
/*为什么只需要找到第一个未被消灭的小猪即可,
你想一下, 虽然它此时未被消灭,
但是它最后肯定会被某一条抛物线消灭掉,
我们相当于是枚举这个小猪被哪几条抛物线消灭掉,
当然这样能找到最优解即答案了.
*/
}
}
for (int j = 0; j < n; j ++ )
f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1);
// 如果有之后可以等效替代的更小方案就替代,没有就加上这一个方案
}
printf("%d\n", f[(1 << n) - 1]);
}
}