Floyd
POJ 2253 Frogger（Floyd）
Posted on
|
In
ACM
利用Floyd的更新策略，只不过把要更新的值类型从最短路变成最大跨度。输出用%lf WA死我了，改用%f或cout就好了。
POJ 1062 昂贵的聘礼
Posted on
|
In
ACM
每个物品是一个节点，当前dis是直接用钱换的价值，从被申请交换的物品向申请交换的物品方向建边，边权是交换后还需要的优惠价。至于等级的限制，因为最后一定要和酋长交换，否则答案就是酋长给出的原价，所以将所有包含酋长的等级长为m的区间都枚举出来，求所有点到酋长的最短路，spfa就直接把所有点push一遍到queue中就行。
POJ 1860 Currency Exchange（SPFA）
Posted on
|
In
ACM
判断是否存在
负环/正环的最短路/最长路问题，把每种货币当作节点，兑换货币就是图上的有向边，使用SPFA查找是否会让起点进入一个正环就行了
POJ 2996 Help Me with the Game
Posted on
|
In
ACM
又是大模拟，注意黑白的迭代顺序不大一样，和poj2993相反的题目（2993不做了😂，单纯就是在各种操作字符串）
POJ 1068 Parencodings
Posted on
|
In
ACM
给定括号串的两种编码，第一种是显示每个右括号左边有多少个左括号，第二种显示每个右括号与其匹配的左括号间有多少个右括号（包括自己），给出第一种编码，求第二种编码
可以直接模拟，算出原括号串然后去数出第二种编码，也可以定位与右括号匹配的左括号在哪个右括号分割出的区间内，即给出的第一种编码两个数之间是两个相邻右括号之间的左括号数，找的时候就从左边相邻的右括号开始枚举，每次加一个右括号数
num_right同时加上中间相应的左括号数num_left直到num_left > num_right为止