web analytics

USACO2017FEB Gold 解析报告

测试链接:http://usaco.org/index.php?page=feb17results

第一题:

Spfa的时候应该加上步数.
其实就是一个裸Spfa.
有一种分层图的感觉.

第二题:

一道DP题.
很巧妙.

因为要保证没有交叉线.
所以我们从前往后递推.

首先要预处理.如果可以连上线.+1;
之后每个F[i][j]都可以通过F[i-1][j]或者是F[i][j-1]来进行递推.这样就完美的保证了没有相交.

第三题:

一道很简单的数据结构题

我们很容易发现其实我们动态加点的树状数组来完成统计区间.
单点修改,区间查询.

只是需要排序.这样可以保证正确性

就这样动态加右结点.
数区间有多少个右结点.

当时想到用线段树写.
但是树状数组更好写.

Post a Comment

You must be logged in to post a comment.