D1T1 玩具谜题
分析
直接模拟即可
代码如下
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
char s[100003][11];
int a[100003];
int main(){
int i, j, n, m, t = 1, w;
scanf("%d%d", &n, &m);
for(i = 1; i <= n; i++){
scanf("%d%s", &a[i], s[i]);
}
for(i = 1; i <= m; i++){
scanf("%d%d", &j, &w);
if(!(j ^ a[t])) t = (t - w + n - 1) % n + 1;
else t = (t + w - 1) % n + 1;
}
printf("%s", s[t]);
return 0;
}
D2T2 天天爱跑步
分析
一条链总是由上去和下来两部分组成。
这题我们分两种情况思考。
第一种：上去的时候被观察到
第二种：下来的时候被观察到
我们先来看第一种情况，不难发现，一个点 t 被某一个观察员 i 观察到需满足
dept=depi+wi，这样一来我们统计每个观察员 i 能观察到多少从下面上来的人只需要看 i 的子树中有多少 depj=depi+wi 的即可。（被统计的前提当然是那条链经过 i）
下面来看第二种情况。大概长这样。
首先我们为了方便统计，一般都是统计子树中的值。
那么我们怎么看 观察员 i 能统计到多少下来的人呢？
推一推柿子，可以看到 len−(depy−depi)=wi⇒len−depy=wi−depi，这样我们只要统计 i 的子树中有多少 len−depy=wi−depi的值就可以了。
于是我们的思路就出来了。
下面思考一下怎么统计。
第一种做法是用桶型线段树。对每个深度维护一颗线段树，最后对每个观察员 i 统计 i 能观察到多少人。
第二种做法是用 dfs， dfs 的过程中维护一个桶，每次路过端点时 tong[dep[x]]+1，路过 lca 时 tong[dep[x]]−1，这样我们就能一遍 dfs 完成统计。这种做法关键在于从每个点 dfs 相当于是遍历子树，也就是在进行统计的过程，回溯回来，说明统计已经结束了。
给出的代码是用桶型线段树的（比较好打hhh
代码如下
#include <bits/stdc++.h>
#define lson l, m, lch[rt]
#define rson m + 1, r, rch[rt]
#define N 300005
using namespace std;
struct node{
int a, b, n;
}d[N * 2];
int h[N], cnt, ret, tot;
int fa[N], son[N], dfn[N], siz[N], dep[N], top[N], re[N], w[N];
int x[N], y[N], lca[N], len[N], ans[N];
int root[N * 10], lch[N * 30], rch[N * 30], sum[N * 30];
void cr(int a, int b){
d[++cnt].a = a; d[cnt].b = b; d[cnt].n = h[a]; h[a] = cnt;
}
void dfs1(int a){
int i, b;
siz[a] = 1;
for(i = h[a]; i; i = d[i].n){
b = d[i].b;
if(b == fa[a]) continue;
fa[b] = a;
dep[b] = dep[a] + 1;
dfs1(b);
siz[a] += siz[b];
if(siz[b] > siz[son[a]]) son[a] = b;
}
}
void dfs2(int a, int f){
int i, b;
top[a] = f;
dfn[a] = ++tot; re[tot] = a;
if(son[a]) dfs2(son[a], f);
for(i = h[a]; i; i = d[i].n){
b = d[i].b;
if(b != son[a] && b != fa[a]) dfs2(b, b);
}
}
int get(int a, int b){
int f1 = top[a], f2 = top[b];
while(f1 != f2){
if(dep[f1] < dep[f2]) swap(f1, f2), swap(a, b);
a = fa[f1], f1 = top[a];
}
if(dep[b] < dep[a]) return b;
return a;
}
void update(int l, int r, int &rt, int p, int c){
if(!p) return;
if(!rt) rt = ++ret;
sum[rt] += c;
if(l == r) return;
int m = l + r >> 1;
if(p <= m) update(lson, p, c);
else update(rson, p, c);
}
int query(int l, int r, int rt, int a, int b){
if(!rt) return 0;
if(l >= a && r <= b) return sum[rt];
int m = l + r >> 1, ans = 0;
if(a <= m) ans += query(lson, a, b);
if(b > m) ans += query(rson, a, b);
return ans;
}
int main(){
int i, j, n, m, a, b;
scanf("%d%d", &n, &m);
for(i = 1; i < n; i++){
scanf("%d%d", &a, &b);
cr(a, b);
cr(b, a);
}
dfs1(1);
dfs2(1, 1);
for(i = 1; i <= n; i++) scanf("%d", &w[i]);
for(i = 1; i <= m; i++){
scanf("%d%d", &x[i], &y[i]);
lca[i] = get(x[i], y[i]);
len[i] = dep[x[i]] + dep[y[i]] - 2 * dep[lca[i]];
update(1, n, root[dep[x[i]]], dfn[x[i]], 1);
update(1, n, root[dep[x[i]]], dfn[fa[lca[i]]], -1);
}
//printf("---------\n");
//for(i = 1; i <= m; i++) printf("%d ", lca[i]);
for(i = 1; i <= n; i++) ans[i] += query(1, n, root[dep[i] + w[i]], dfn[i], dfn[i] + siz[i] - 1);
//for(i = 1; i <= m; i++) printf("%d ", len[i]);
//printf("\n");
memset(sum, 0, sizeof(sum));
memset(root, 0, sizeof(root));
memset(lch, 0, sizeof(lch));
memset(rch, 0, sizeof(rch));
for(i = 1; i <= m; i++){
update(1, n, root[len[i] - dep[y[i]] + N], dfn[y[i]], 1);
update(1, n, root[len[i] - dep[y[i]] + N], dfn[lca[i]], -1);
}
for(i = 1; i <= n; i++) ans[i] += query(1, n, root[w[i] - dep[i] + N], dfn[i], dfn[i] + siz[i] - 1);
for(i = 1; i <= n; i++) printf("%d ", ans[i]);
return 0;
}
D1T3 换教室
分析
这题作为 noip 第一次出的期望题，可能重点不在于 dp，而在于考察选手对期望的理解吧。
首先 floyd 预处理出任意两点间的最小路程，需注意的是 mp[i][i]=0
然后记 f[i][j][0/1] 表示到了第 i 节课，总共换了 j 节，第 i 节换不换的最小期望。分别对 f[i][j][0] 和 f[i][j][1] 进行转移，转移对第 i−1 节课是否换课进行讨论即可。
代码如下
#include <bits/stdc++.h>
#define N 2005
#define maxn 90000000
#define inf 2147483647
using namespace std;
int c[N], d[N], mp[305][305];
double k[N], f[N][N][2], ans = inf;
int main(){
int i, j, t, n, m, v, e, a, b;
for(i = 1; i <= 300; i++){
for(j = 1; j <= 300; j++){
mp[i][j] = 30000000;
}
}
scanf("%d%d%d%d", &n, &m, &v, &e);
for(i = 1; i <= n; i++) scanf("%d", &c[i]);
for(i = 1; i <= n; i++) scanf("%d", &d[i]);
for(i = 1; i <= n; i++) scanf("%lf", &k[i]);
for(i = 1; i <= e; i++){
scanf("%d%d%d", &a, &b, &t);
if(mp[a][b] > t) mp[a][b] = mp[b][a] = t;
}
for(i = 1; i <= v; i++) mp[i][i] = 0;
for(t = 1; t <= v; t++){
for(i = 1; i <= v; i++){
for(j = 1; j <= v; j++){
mp[i][j] = min(mp[i][j], mp[i][t] + mp[t][j]);
}
}
}
for(i = 0; i <= 2000; i++)
for(j = 0; j <= 2000; j++) f[i][j][0] = f[i][j][1] = maxn;
f[1][0][0] = f[1][1][1] = 0;
for(i = 2; i <= n; i++){
f[i][0][0] = f[i - 1][0][0] + mp[c[i - 1]][c[i]];
for(j = 1; j <= m; j++){
f[i][j][0] = min(f[i - 1][j][0] + mp[c[i - 1]][c[i]], f[i - 1][j][1] + k[i - 1] * mp[d[i - 1]][c[i]] + (1 - k[i - 1]) * mp[c[i - 1]][c[i]]);
f[i][j][1] = min(f[i - 1][j - 1][0] + k[i] * mp[c[i - 1]][d[i]] + (1 - k[i]) * mp[c[i - 1]][c[i]], f[i - 1][j - 1][1] + k[i] * k[i - 1] * mp[d[i - 1]][d[i]] + k[i] * (1 - k[i - 1]) * mp[c[i - 1]][d[i]] + (1 - k[i]) * k[i - 1] * mp[d[i - 1]][c[i]] + (1 - k[i]) * (1 - k[i - 1]) * mp[c[i - 1]][c[i]]);
}
}
for(i = 0; i <= m; i++) ans = min(ans, min(f[n][i][0], f[n][i][1]));
printf("%.2lf", ans);
return 0;
}
D2T1 组合数问题
分析
注意到 k 是对每个询问的。于是我们想到预处理。直接预处理出 c[i][j] 是否是
k 的倍数，然后用二维前缀和即可 O(1) 回答询问。
代码如下
#include <bits/stdc++.h>
#define N 2005
using namespace std;
int c[N][N], s[N][N];
int main(){
int i, j, n, m, t, k;
scanf("%d%d", &t, &k);
for(i = 0; i <= 2000; i++){
c[i][0] = 1;
for(j = 1; j <= i; j++){
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % k;
if(!c[i][j]) s[i][j] = 1;
//printf("%d %d %d\n", i, j, s[i][j]);
}
if(i > 1)
for(j = 1; j <= 2000; j++){
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
}
while(t--){
scanf("%d%d", &n, &m);
if(m > n) m = n;
printf("%d\n", s[n][m]);
}
return 0;
}
D2T2 蚯蚓
分析
做这题最暴力的想法是用优先队列（或者不用），每次把最长的切成两段，然后把所有蚯蚓取出来加 q。
然后不难注意到，不切的蚯蚓之间的相对长度是不变的，每次都加 q 很不好。我们只需要将切出来的两段减 q 就好了。然后再用优先队列可以达到 80pts。
讲讲正解。
维护三个有序数组。
首先将蚯蚓从大到小排序，每次切出来的两条新蚯蚓分别放入另外两个数组。不难发现，这样出来的三个数组都是从大到小有序的。我们每次只需要从 3 个数组的队首比较取出最大值咔咔掉即可。
复杂度是线性的。
代码如下
#include <bits/stdc++.h>
#define N 7000005
#define LL long long
#define inf 2147483647
using namespace std;
LL a[N], b[N], c[N];
int p1, q1, p2, q2, p3, q3;
LL z = 1, maxn;
int cmp(int x, int y){
return x > y;
}
int main(){
int i, j, n, m, q, u, v, t;
int p;
scanf("%d%d%d%d%d%d", &n, &m, &q, &u, &v, &t);
for(i = 1; i <= n; i++) scanf("%lld", &a[i]);
sort(a + 1, a + i, cmp);
p1 = p2 = p3 = 1, q1 = n;
for(i = 1; i <= m; i++){
maxn = -inf;
if(p1 <= q1 && maxn < a[p1]) p = 1, maxn = a[p1];
if(p2 <= q2 && maxn < b[p2]) p = 2, maxn = b[p2];
if(p3 <= q3 && maxn < c[p3]) p = 3, maxn = c[p3];
maxn += (i - 1) * q;
if(i % t == 0) printf("%lld ", maxn);
b[++q2] = maxn * u / v - i * q;
c[++q3] = maxn - maxn * u / v - i * q;
if(p == 1) p1++;
if(p == 2) p2++;
if(p == 3) p3++;
//printf("%d %d %d\n", p1, p2, p3);
}
//printf("====%d %d\n====%d %d\n====%d %d\n", p1, q1, p2, q2, p3, q3);
printf("\n");
for(i = 1; ; i++){
if(p1 > q1 && p2 > q2 && p3 > q3) break;
maxn = -inf;
if(p1 <= q1 && maxn < a[p1]) p = 1, maxn = a[p1];
if(p2 <= q2 && maxn < b[p2]) p = 2, maxn = b[p2];
if(p3 <= q3 && maxn < c[p3]) p = 3, maxn = c[p3];
if(i % t == 0) printf("%lld ", maxn + m * q);
if(p == 1) p1++;
if(p == 2) p2++;
if(p == 3) p3++;
}
return 0;
}
D2T3 愤怒的小鸟
分析
首先我们可以不管给出的 m，因为我们用 n 只小鸟肯定可以打完，不存在无解的情况，出题人给出来是为了某些同学写搜索剪枝用的。
然后我们回到题目。注意到 n 很小，考虑状压。
一条抛物线肯定由两只小猪连成，我们可以用 g[i][j] 表示 i,j 这两只小猪连成的抛物线能打到的小猪集合。我们用 f[s] 表示打到的小猪集合为 s 时用的最少抛物线。枚举 i,j，那么转移方程为：
f[s]=min(f[s^ (s& g[i][j])]+1)，就是先取 s 和 g[i][j] 的交集，然后咔咔掉。这样子复杂度时 O(n2∗2n)的，能不能更优呢？当然可以。
我们每条抛物线之间时没有先后顺序的，那么我们就可以让最后一只猪作为抛物线的一个点，然后枚举另一只猪作为另一个点，这样复杂度就是 O(n∗2n)的。
代码如下
//f[s] = min(f[s ^ g[i][j]] + 1)
#include <bits/stdc++.h>
#define eps 1e-6
using namespace std;
int f[1 << 20], g[20][20], re[1 << 20];
double a, b, x[20], y[20];
double get(double x1, double y1, double x2, double y2){
return (y1 - y2 * x1 / x2) / (x1 * x1 - x1 * x2);
}
int main(){
int i, j, k, n, m, T, s;
for(i = 0; i < 20; i++) re[1 << i] = i;
//printf("%d", re[4]);
scanf("%d", &T);
while(T--){
memset(f, 1, sizeof(f));
memset(g, 0, sizeof(g));
scanf("%d%d", &n, &m);
for(i = 0; i < n; i++) scanf("%lf%lf", &x[i], &y[i]);
for(i = 0; i < n; i++){
for(j = i + 1; j < n; j++){
if(fabs(x[i] - x[j]) < eps) continue;
a = get(x[i], y[i], x[j], y[j]);
if(a > -eps) continue;
b = (y[i] - a * x[i] * x[i]) / x[i];
for(k = 0; k < n; k++){
if(fabs(y[k] - a * x[k] * x[k] - b * x[k]) < eps) g[i][j] |= (1 << k);
}
//printf("%d %d %d\n", i, j, g[i][j]);
}
}
f[0] = 0;
for(s = 1; s < (1 << n); s++){
j = re[s&-s];
f[s] = min(f[s], f[s ^ (1 << j)] + 1);
for(i = j + 1; i < n; i++){
if(1 << i & s) f[s] = min(f[s], f[s ^ (s & g[j][i])] + 1);
}
}
printf("%d\n", f[(1 << n) - 1]);
}
return 0;
}
京公网安备 11010502036488号