解答
A Facer is learning to swim
dp , num[k][v][y] 保存在x（x>=1, x<=M) 时，深度为y（y>=1, y<=N) ,速度为v（v<=21*K, v>=0-N) 时获得最多的金钱。
B Zombies VS Plants
搜索
C Seat taking up is tough
水题， 枚举
D Ancient Vending machine
几何
E Open-air shopping malls
简单几何，二分法
F Posters
漂浮法（不造可行不）， 线段树
G Hamlet‘s gambling
推理
很难的一道提，结合了字符串匹配，概率
H Graph Game
博弈， 有n个点m条边。两个人，a每次从中挑出一条边，最后希望构出一个树出来（联通图）; b阻止a，阻止方法为从中丢掉一条边。最后谁赢？
I Columbus‘s bargain
这个题目简单，图论 + 单S最短路径
- 先把每两个商品看成点i、j， 如果p[i]<=p[j], 有边 i-》j，距离为p[j]-p[i]
- 然后插入savages， 即在i到j插入边， 距离为 r
- 这样一来i到j可能有2条边，懒得去重复了，原因在下方
- graph存在邻接矩阵上，djstra，用个最小堆保存最短距离值和对应点
- 两点之间如果多条边，每个点将得到多个最短距离，小丁堆只取最小的那个，其他忽略
J P2P File Sharing System
代码
#include<iostream>
#include <algorithm>
using namespace std;
#include <map>
typedef pair<int, int> Pair;
#include <vector>
#include <queue>
// #include <priority_queue>
struct cmp{
bool operator()(const Pair &a, const Pair &b){
return a.first>b.first;
}
}cmper;
void djstra(vector<vector<Pair> > &graph, vector<int> &ds){
int n=graph.size();
vector<bool> tag(n, false);
ds[0]=0, tag[0]=true;
priority_queue<Pair, vector<Pair>, cmp> minq;
int t=0;
for(int i=1; i<n; i++){
for(int j=0; j<graph[t].size(); j++){
Pair &p=graph[t][j]; int v=p.second;
if(!tag[v]){
minq.push(Pair(ds[t]+p.first, v));
}
}
while(!minq.empty()){
Pair p=minq.top(); minq.pop();
if(!tag[p.second]){
ds[p.second]=p.first, tag[p.second]=true;
t=p.second; break;
}
}
}
}
int main(){
int casen; cin>>casen;
for(int ci=0; ci<casen; ci++){
int n; cin>>n;
vector<int> p(n+1, -1);
vector<vector<Pair> > graph(n+1, vector<Pair>());
for(int i=1; i<=n; i++){
int a;
cin>>a>>p[i];
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(p[i]<=p[j]) graph[i].push_back(Pair(p[j]-p[i], j));
}
}
int m; cin>>m;
for(int i=0; i<m; i++){
int a, b, q;
cin>>a>>b>>q;
graph[a].push_back(Pair(q, b));
}
// buy with one glass bead and ..
for(int i=1; i<=n; i++){
graph[0].push_back(Pair(p[i]-1, i));
}
vector<int> ds(n+1, -1);
djstra(graph, ds);
for(int i=1; i<=n; i++){
cout<<i<<" "<<ds[i]<<endl;
}
sort(ds.begin()+1, ds.end());
int cnt=0;
for(int i=3; i<=n; i++){
for(int j=1; j<=i-2; j++){
if(binary_search(ds.begin()+j+1, ds.begin()+i, ds[i]-ds[j])) cnt++;
}
}
cout<<cnt<<endl;
}
return 0;
}