第一题快速幂
#include "cstdio" int n, m, k, x; long long a = 10, rt = 1; int main() { freopen("circle.in", "r", &_iob[0]); freopen("circle.out", "w", &_iob[1]); scanf("%d%d%d%d", &n, &m, &k, &x); while(k) (k & 1) ? (rt *= a) %= n : 1, k >>= 1, (a *= a) %= n; printf("%I64d\n", ( (m % n) * rt + x ) % n); }第二题树状数组优化逆序对
#include "cctype" #include "cstdio" #include "algorithm" inline short readIn(int& x) { static char ch; while( !isdigit(ch = getchar()) && (ch ^ -1)); if(ch == -1) return 0; for(x = -48 + ch; isdigit(ch = getchar()); x = x * 10 + ch - 48); return 1; } #define MAXN 100005 #define lowbit(x) (x & (-x)) typedef class Data { public: int v, id; inline short operator < (const Data &rhs) const { return v < rhs.v; } } YSY_LWD; int n, ans, c[MAXN], t[MAXN]; YSY_LWD a[MAXN], b[MAXN]; inline void Add(int x) { for(register int i = x; i <= n; i += lowbit(i)) ++t[i]; } inline int Query(int x) { int rt = 0; for(register int i = x; i; i -= lowbit(i)) rt += t[i]; return rt; } int main() { freopen("match.in", "r", &_iob[0]); freopen("match.out", "w", &_iob[1]); readIn(n); for(register int i = 1; i <= n; ++i) readIn(a[i].v), a[i].id = i; for(register int i = 1; i <= n; ++i) readIn(b[i].v), b[i].id = i; std::sort(a + 1, a + 1 + n); std::sort(b + 1, b + 1 + n); for(register int i = 1; i <= n; c[a[i].id] = b[i++].id); for(register int i = n; i; --i) ans += Query(c[i]), Add(c[i]), ans %= 99999997; printf("%d\n", ans); }第三题， 才是一道不水题。
题目描述 Description
A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
输入描述 Input Description
第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道路。 接下来 m 行每行 3 个整数 x、y、z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意：x 不等于 y，两座城市之间可能有多条道路。 接下来一行有一个整数 q，表示有 q 辆货车需要运货。 接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意：x 不等于 y。
输出描述 Output Description
输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出-1。
样例输入 Sample Input
4 3 1 2 4 2 3 3 3 1 1 3 1 3 1 4 1 3
样例输出 Sample Output
3 -1 3
数据范围及提示 Data Size & Hint
对于 30%的数据，0 < n < 1,000，0 < m < 10,000，0 < q < 1,000； 对于 60%的数据，0 < n < 1,000，0 < m < 50,000，0 < q < 1,000； 对于 100%的数据，0 < n < 10,000，0 < m < 50,000，0 < q < 30,000，0 ≤ z ≤ 100,000。 题意实际是询问森林中两个点的路径上的最小边权，连通性用并查集判一下
可以用树上倍增在logn的复杂度解决一棵树内的一次询问
首先， 此处是一个贪心策略， 最优解一定是在原图的最大生成森林上， 因为不在最大生成森林上的路径一定是更劣的。 预处理Lca， 然后用Rmq处理d(i, j)表示第i个点到其距离为2^j的祖先上的最小权值， 然后用倍增的思想俩个点往上跳一跳， 之后更新答案。
说白了是一类型的模板题
#include "cctype" #include "cstdio" #include "cstring" #include "algorithm" #define min(a, b) ((a) < (b) ? (a) : (b)) inline short readIn(int& x) { static char ch; while( !isdigit(ch = getchar()) && (ch ^ -1)); if(ch == -1) return 0; for(x = -48 + ch; isdigit(ch = getchar()); x = x * 10 + ch - 48); return 1; } #define MAXN 100005 #define MAXM 500005 struct edge { int to, w, pre; edge() { } edge(int to, int w, int pre) : to(to), w(w), pre(pre) { } } g[MAXM << 1]; struct E { int u, v, w; E() { } E(int u, int v, int w) : u(u), v(v), w(w) { } inline short operator < (const E& rhs) const { return w > rhs.w; } } e[MAXM]; #define adde(u, v, w); { g[++ne] = edge(v, w, head[u]); head[u] = ne; } short vis[MAXN]; int ne, x, y, n, m, u, v, w, Q, p, q, lca, tot, logn, logt, head[MAXN], fa[MAXN], anc[MAXN][18], d[MAXN][18], dep[MAXN]; inline int find(int x) { while(x ^ fa[x]) x = fa[x] = fa[fa[x]]; return x; } void dfs(int u) { vis[u] = 1; int v; for(register int i = head[u]; i; i = g[i].pre) { v = g[i].to; if(vis[v] )continue; anc[v][0] = u; d[v][0] = g[i].w; dep[v] = dep[u] + 1; dfs(v); } } inline int Lca(int u, int v) { static int t; if(dep[u] < dep[v]) u ^= v ^= u ^= v; t = dep[u] - dep[v]; for(int p = 0; p <= logn; ++p) if((1 << p) & t) u = anc[u][p]; if(v == u) return u; for(int p = logn; anc[u][0] ^ anc[v][0]; --p) if(anc[u][p] ^ anc[v][p]) u = anc[u][p], v = anc[v][p]; return anc[u][0]; } inline int query(int u, int lca) { static int minn, t; minn = 0x3f3f3f3f; t = dep[u] - dep[lca]; for(int p = 0; p <= logn; ++p) if(t & (1 << p)) minn = min(minn, d[u][p]), u = anc[u][p]; return minn; } int main() { freopen("truck.in", "r", &_iob[0]); freopen("truck.out", "w", &_iob[1]); register int i; for(readIn(n), readIn(m), i = 1; i <= m; ++i) readIn(e[i].u), readIn(e[i].v), readIn(e[i].w); for(i = 2; i <= n; ++i) logn = !(i & (i - 1)) ? logt + 1 : logt, logt = logn; std::sort(e + 1, e + 1 + m); for(i = 1; i <= n; ++i) fa[i] = i; for(i = 1; i <= m; ++i) { u = e[i].u, v = e[i].v; p = find(e[i].u), q = find(e[i].v); if(p ^ q) { fa[p] = q; adde(u, v, e[i].w); adde(v, u, e[i].w); ++tot; if(tot == n - 1) break; } } memset(d, 0x3f, sizeof(d)); for(i = 1; i <= n; ++i) if( !vis[i] ) dfs(i); for(register int p = 1; p <= logn; ++p) for(i = 2; i <= n; ++i) anc[i][p] = anc[anc[i][p - 1]][p - 1], d[i][p] = min(d[i][p - 1], d[anc[i][p - 1]][p - 1]); for(readIn(Q); Q; --Q) { readIn(x); readIn(y); if(find(x) ^ find(y)) { puts("-1"); continue; } lca = Lca(x, y); printf("%d\n", min(query(x, lca), query(y, lca))); } }