Snow Boots

【题目描述】

到冬天了,这意味着下雪了!从农舍到牛棚的路上有$N$块地砖,方便起见编号为$1…N$,第$i$块地砖上积了$f_i$英尺的雪。在Farmer John的农舍的地窖中,总共$B$双靴子,编号为$1…B$。其中某些比另一些结实,某些比另一些轻便。具体地说,第$i$双靴子能够让FJ在至多si英尺深的积雪中行走,能够让FJ每步至多前进$d_i$。

Farmer John从$1$号地砖出发,他必须到达$N$号地砖才能叫醒奶牛们。$1$号地砖在农舍的屋檐下,$N$号地砖在牛棚的屋檐下,所以这两块地砖都没有积雪。帮助Farmer John求出哪些靴子可以帮助他走完这段艰辛的路程。

【输入格式】

第一行包含两个空格分隔的整数$N$和$B$($1≤N,B≤10^5$)。第二行包含$N$个空格分隔的整数;第$i$个整数为$f_i$,即$i$号地砖的积雪深度($0≤f_i≤10^9$)。输入保证$f_1=f_N=0$。

下面$B$行,每行包含两个空格分隔的整数。第$i+2$行的第一个数为$s_i$,表示第$i$双靴子能够承受的最大积雪深度。第$i+2$行的第二个数为$d_i$,表示第$i$双靴子的最大步长。输入保证$0≤s_i≤10^9$以及$1≤d_i≤N−1$。

【输出格式】

输出包含$N$行。第$i$行包含一个整数:如果Farmer John能够穿着第$i$双靴子从$1$号地砖走到$N$号地砖,为$1$,否则为$0$。

【样例输入】

1
2
3
4
5
6
7
8
9
8 7
0 3 8 5 6 9 0 0
0 5
0 6
6 2
8 1
10 1
5 3
150 7

【样例输出】

1
2
3
4
5
6
7
0
1
1
0
1
1
1

【来源】

USACO Feb18 Gold
供题:Dhruv Rohatgi

分析

将所有靴子按能承受的最大深度从小到大排序,针对每双靴子,用两个set分别维护所有深度大于该靴子所能承受最大深度的积雪区间和它的长度,判断最长的区间能否跨过即可。

代码(Accepted)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <cstdio>
#include <algorithm>
#include <set>
const int maxn=100005;
struct tile {
int f,tag;
bool operator < (const tile &rhs) const {
return f<rhs.f;
}
} tiles[maxn];
struct boot {
int s,d,tag;
bool operator < (const boot &rhs) const {
if(s==rhs.s) return d<rhs.d;
return s<rhs.s;
}
} boots[maxn];
struct segment {
int l,r;
bool operator < (const segment &rhs) const {
return l<rhs.l;
}
};
std::set<segment> segments;
std::multiset<int> seglen;
int ans[maxn];
int main() {
freopen("snowboots.in","r",stdin);
freopen("snowboots.out","w",stdout);
int n,b;
scanf("%d%d",&n,&b);
for(int i=0;i<n;++i) {
scanf("%d",&tiles[i].f);
tiles[i].tag=i;
}
std::sort(tiles,tiles+n);
for(int i=0;i<b;++i) {
scanf("%d%d",&boots[i].s,&boots[i].d);
boots[i].tag=i;
}
std::sort(boots,boots+b);
segments.insert((segment){0,n-1});
seglen.insert(n);
int cur=0;
for(int i=0;i<b;++i) {
for(;cur<n&&tiles[cur].f<=boots[i].s;++cur) {
int loc=tiles[cur].tag;
std::set<segment>::iterator seg=segments.upper_bound((segment){loc,loc});
--seg;
int l=seg->l,r=seg->r,len=r-l+1;
segments.erase(seg);
seglen.erase(seglen.find(len));
if(len==1) continue;
else if(l==loc) {
segments.insert((segment){l+1,r});
seglen.insert(len-1);
}
else if(r==loc) {
segments.insert((segment){l,r-1});
seglen.insert(len-1);
}
else if(l<loc&&loc<r) {
segments.insert((segment){l,loc-1});
seglen.insert((loc-1)-l+1);
segments.insert((segment){loc+1,r});
seglen.insert(r-(loc+1)+1);
}
}
std::set<int>::iterator it=seglen.end();
ans[boots[i].tag]=seglen.size()?*(--it)<boots[i].d:true;
}
for(int i=0;i<b;++i) printf("%d\n",ans[i]);
fclose(stdin);
fclose(stdout);
return 0;
}

Directory Traversal

【题目描述】

奶牛Bessie令人惊讶地精通计算机。她在牛棚的电脑里用一组文件夹储存了她所有珍贵的文件,比如:

bessie/

​ folder1/

​ file1

​ folder2/

​ file2

​ folder3/

​ file3

​ file4

只有一个“顶层”的文件夹,叫做bessie。

Bessie可以浏览任何一个她想要访问的文件夹。从一个给定的文件夹,每一个文件都可以通过一个“相对路径”被引用。在一个相对路径中,符号“..”指的是上级目录。如果Bessie在folder2中,她可以按下列路径引用这四个文件:

../file1

file2

../../folder3/file3

../../file4

Bessie想要选择一个文件夹,使得从该文件夹出发,对所有文件的相对路径的长度之和最小。

【输入格式】

第一行包含一个整数$N$($2≤N≤100,000$),为所有文件和文件夹的总数量。为了便于输入,每个对象(文件或文件夹)被赋予一个唯一的1至$N$之间的ID,其中ID 1指的是顶层文件夹。接下来有$N$行。每行的第一项是一个文件或是文件夹的名称。名称仅包含小写字母a-z和数字0-9,长度至多为16个字符。名称之后是一个整数$m$。如果$m$为0,则该对象是一个文件。如果$m>0$,则该对象是一个文件夹,并且该文件夹下共有$m$个文件或文件夹。在$m$之后有$m$个整数,为该文件夹下的对象的ID。

【输出格式】

输出所有文件的相对路径的长度之和的最小值。注意这个值可能超过32位整数的表示范围。

【样例输入】

1
2
3
4
5
6
7
8
9
8
bessie 3 2 6 8
folder1 2 3 4
file1 0
folder2 1 5
file2 0
folder3 1 7
file3 0
file4 0

【样例输出】

1
42

【提示】

这个输入样例描述了上面给出的样例目录结构。

最优解是选择folder1。从这个文件夹出发,相对路径分别为:

file1

folder2/file2

../folder3/file3

../file4

【来源】

USACO Feb18 Gold
供题:Mark Gordon

分析

树形动态规划,二次扫描与换根法。

代码(Accepted)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
typedef long long int ll;
const int maxn=1e5+5;
std::vector<int> tree[maxn];
int fa[maxn];
ll name[maxn],len[maxn],cnt[maxn];
bool leaf[maxn];int leafcnt=0;
void dfs(int u) {
for(int i=0;i<tree[u].size();++i) {
dfs(tree[u][i]);
cnt[u]+=cnt[tree[u][i]]==0?1:cnt[tree[u][i]];
len[u]+=len[tree[u][i]]+(cnt[tree[u][i]]==0?1:cnt[tree[u][i]])*(name[tree[u][i]]+(leaf[tree[u][i]]?0:1));
}
}
ll ans=0,rev[maxn];
void dfs2(int u) {
if(!leaf[u]&&!rev[u]) {
rev[u]=rev[fa[u]]-(name[u]+1)*cnt[u]+3*(leafcnt-cnt[u]);
ans=std::min(ans,rev[u]);
}
for(int i=0;i<tree[u].size();++i) {
dfs2(tree[u][i]);
}
}
int main() {
freopen("dirtraverse.in","r",stdin);
freopen("dirtraverse.out","w",stdout);
int n;
scanf("%d",&n);
char s[maxn];int m;
for(int i=1;i<=n;++i) {
scanf("%s%d",s,&m);
name[i]=strlen(s);
if(m==0) {
leaf[i]=true;
leafcnt++;
}
int son;
while(m--) {
scanf("%d",&son);
tree[i].push_back(son);
fa[son]=i;
}
}
dfs(1);
ans=rev[1]=len[1];
dfs2(1);
printf("%lld\n",ans);
fclose(stdin);
fclose(stdout);
return 0;
}

Taming the Herd

【题目描述】

一大清早,Farmer John就被木材破裂的声音吵醒了。是这些奶牛们干的,她们又逃出牛棚了!Farmer John已经厌烦了奶牛在清晨出逃,他觉得受够了:是时候采取强硬措施了。他在牛棚的墙上钉了一个计数器,追踪从上次出逃开始经过的天数。所以如果某一天早上发生了出逃事件,这一天的计数器就为$0$;如果最近的出逃是$3$天前,计数器读数就为$3$。Farmer John一丝不苟地记录了每一天计数器的读数。

年末到了,Farmer John准备做一些统计。他说,你们这些奶牛会付出代价的!然而他的某些记录看上去不太对劲……

Farmer John想要知道从他开始记录以来发生过多少次出逃。但是,他怀疑这些奶牛篡改了它的记录,现在他所确定的只有他是从发生出逃的某一天开始记录的。请帮助他求出,对于每个从他开始记录以来可能发生的出逃次数,他被篡改了的记录条数的最小值。

【输入格式】

输入的第一行包含一个整数$N$($1≤N≤100$),表示从Farmer John开始对奶牛出逃计数器进行计数以来已经经过的天数。第二行包含$N$个空格分隔的整数。第i个整数是一个非负整数$a_i$(不超过$100$),表示在第$i$天计数器的数字是$a_i$,除非奶牛篡改了这一天的记录条目。

【输出格式】

输出包含$N$个整数,每行一个。第$i$个整数为所有发生$i$次出逃的事件序列中,与该事件序列不一致的记录条目条数的最小值。

【样例输入】

1
2
6
1 1 2 0 0 1

【样例输出】

1
2
3
4
5
6
4
2
1
2
3
4

【提示】

如果只发生1次出逃,则正确的记录应该为0 1 2 3 4 5,有4处与给定的记录不同。

如果发生2次出逃,则正确的记录可能为0 1 2 3 0 1,有2处与给定的记录不同。在这个例子中,出逃发生在第一天和第五天。

如果发生3次出逃,则正确的记录可能为0 1 2 0 0 1,仅有1处与给定的记录不符。在这个例子中,出逃发生在第一天、第四天和第五天。

以此类推。

【来源】

USACO Feb18 Gold
供题:Brian Dean,Dhruv Rohatgi

分析

简单的动态规划,定义$f[i][j][k]$为第$i$天发生$j$次出逃与记录不符的条目数量最小值,设计状态转移方程即可。

代码(Accepted)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <cstdio>
#include <climits>
#include <cstring>
#include <algorithm>
const int maxn=105;
const int INF=INT_MAX/2;
int n,a[maxn],f[maxn][maxn][maxn];
int main() {
freopen("taming.in","r",stdin);
freopen("taming.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=0;i<=n;++i) {
for(int j=0;j<=n;++j) {
for(int k=0;k<n;++k) {
f[i][j][k]=INF;
}
}
}
f[1][1][0]=(a[1]!=0);
for(int i=1;i<n;++i) {
for(int j=0;j<=n;++j) {
for(int k=0;k<n;++k) {
f[i+1][j][k+1]=std::min(f[i+1][j][k+1],f[i][j][k]+(a[i+1]!=k+1));
f[i+1][j+1][0]=std::min(f[i+1][j+1][0],f[i][j][k]+(a[i+1]!=0));
}
}
}
for(int i=1;i<=n;++i) {
int ans=INF;
for(int j=0;j<n;++j) {
ans=std::min(ans,f[n][i][j]);
}
printf("%d\n",ans);
}
fclose(stdin);
fclose(stdout);
return 0;
}