10.2司机出的考试太太太太毒瘤了...用组里某嘤嘤怪的话说：
“看起来人畜无害，出题比谁都变态。”
由于博主太过蒟(懒)蒻(惰)，所以题解就没有啦！
今天猫的题还是很友善的...
T1 题上说每次必须融合一个马猴值为1的龙珠，因此可以设A=a/b，B=1。
那么第一种融合即为a/b+1=(a+b)/b
第二种融合即为1/(b/a+1)=a/(a+b)
发现两种融合即为分子/(分子+分母)或(分子+分母)/分母
因此题目可以简化为：对于二元组(a,b)，每次操作可以使二元组中的一个数加上另一个数，求到达最
终状态(c,d)的最少操作数。
发现整个过程的逆过程类似于求gcd。
#include//STL通用算法#include //STL位集容器#include #include #include #include #include #include #include #include //STL双端队列容器#include //STL线性列表容器#include
T2 一道纯思路题。
把三枚棋子之间的两段距离看做此状态的两个参数。
由于在某一状态下，其能转移到的状态最少2种，最多3种：
1.a<--->b<------->c 在此状态下，b可以向左或向右跳，a可以向右跳；
2.a<------->b<--->c 在此状态下，b可以向左或向右跳，c可以向左跳；
3.a<----->b<----->c 在此状态下，b可以向左或向右跳。
发现无论是哪种状态，中间的旗子都能向两边跳，而两侧的棋子却不一定能向中间跳。
若把每个状态都抽象成一个点，那么以上规律可总结为：
在一棵树上，每个节点都有2个儿子，却不一定有父亲。(根节点)
因此此题转化成了树上求两点间路径+统计多余步数分配方案数。
由于最大步数仅有100步，因此可以直接从起始状态与终止状态分别向上暴跳k步，找到最深的公共节点
即为LCA。(若无符合条件的节点则无解)
那么如何统计多余步数的分配方案数呢？
发现无论如何消耗步数，其方式无非2种：向路径外走或走回路径。可用dp实现。
#include//STL通用算法#include //STL位集容器#include #include #include #include #include #include #include #include //STL双端队列容器#include //STL线性列表容器#include
T3 又一道思路题...
然而前15个数据点分5部分分别暴力可拿60分2333
标算是分治最短路。
发现每个城市最多5个派送点，一次性横跨城市最多3个，这就是说，在n个派送点中去除最多15个连
续的派送点会使左右两侧的派送点不连通。换句话说，左右两边的派送点想要互相到达，必须经过中
间这15个派送点。可以依据这个性质进行分治。
对于k个城市内的每一个配送点进行一次分治，查出每个询问的l与r到分治点的最短路，取最优即可。
由于博主已经被第二题虐的死去活来，故仅把std放上来供大佬们参考。
#include#include #include #include #include using namespace std;const int MaxN = 50010;const int MaxM = 200010;int n, m, k, p, q;int belong[MaxM * 10], place_num;int sum[MaxM], c[MaxM];long long dis[MaxM * 10];long long ans[MaxM];int vis[MaxM * 10];struct edge { int to, w; edge *next;} *last[MaxM], e[MaxM << 1], *edge_cnt = e;struct query { int s, t, i;} ask[MaxM], t[MaxM];void add_edge(int u, int v, int w) { *++ edge_cnt = (edge) {v, w, last[u]}, last[u] = edge_cnt;}#include struct data { int v; bool operator < (const data& a) const { return dis[v] > dis[a.v]; }} ;priority_queue que;void spfa(int l, int r, int s) { for (int i = sum[l - 1] + 1; i <= sum[r]; ++ i) dis[i] = 1ll << 60; for (vis[s] = 1, dis[s] = 0, que.push((data) { s}); que.size(); vis[que.top().v] = 0, que.pop()) { for (edge *iter = last[que.top().v]; iter; iter = iter -> next) { if (l <= belong[iter -> to] && belong[iter -> to] <= r && (dis[iter -> to] > dis[que.top().v] + iter -> w ? dis[iter -> to] = dis[que.top().v] + iter -> w, 1 : 0)) { if (!vis[iter -> to]) { vis[iter -> to] = 1; que.push((data) { iter -> to }); } } } }}void divide(int l, int r, int ql, int qr) { if (ql > qr) return ; if (r - l + 1 <= k + 5) { for (int i = ql; i <= qr; ++ i) { spfa(l, r, ask[i].s); ans[ask[i].i] > dis[ask[i].t] ? ans[ask[i].i] = dis[ask[i].t] : 0; } return ; } int ll = r + l - k >> 1, rr = ll + k + 1; int qll = ql, q1, q2; for (int i = ql; i <= qr; ++ i) t[i] = ask[i]; for (int i = ql; i <= qr; ++ i) { if (belong[t[i].s] <= ll && belong[t[i].t] <= ll) ask[qll ++] = t[i]; } q1 = qll - 1; for (int i = ql; i <= qr; ++ i) { if (belong[t[i].s] >= rr && belong[t[i].t] >= rr) ask[qll ++] = t[i]; } q2 = qll - 1; for (int i = ql; i <= qr; ++ i) { if (!(belong[t[i].s] <= ll && belong[t[i].t] <= ll || belong[t[i].s] >= rr && belong[t[i].t] >= rr)) ask[qll ++] = t[i]; } for (int i = sum[ll] + 1; i <= sum[rr - 1]; ++ i) { spfa(l, r, i); for (int j = ql; j <= qr; ++ j) { ans[ask[j].i] > dis[ask[j].s] + dis[ask[j].t] ? ans[ask[j].i] = dis[ask[j].s] + dis[ask[j].t] : 0; } } divide(l, ll, ql, q1); divide(rr, r, q1 + 1, q2);}int main() {// freopen("transport.in", "r", stdin);// freopen("transport.out", "w", stdout); scanf("%d%d%d%d%d", &n, &m, &k, &p, &q); for (int i = 1; i <= n; ++ i) { scanf("%d", c + i); for (int j = 1; j <= c[i]; ++ j) belong[++ place_num] = i; sum[i] = sum[i - 1] + c[i]; } memset(ans, 63, sizeof ans); for (int i = 1; i <= m; ++ i) { int u, v, w; scanf("%d%d%d", &u, &v, &w); add_edge(u, v, w); add_edge(v, u, w); } for (int i = 1; i <= q; ++ i) { int s, t; scanf("%d%d", &s, &t); ask[i] = (query) { s, t, i }; } divide(1, n, 1, q); for (int i = 1; i <= q; ++ i) { if (ans[i] > 1000000000) puts("-1"); else printf("%lld\n", ans[i]); } return 0;}