第一题，数学问题

题目大意

有物品要放在箱子里，一个箱子可以用隔板隔成若干个隔间，一个箱子放2个隔板就可以隔成3个隔间，3个隔板可以隔成4个隔间，以此类推，但一个箱子的隔间数不能超过k个，且每个隔间最多放v个物品。现给出物品个数a、隔板个数b以及k和v，求至少需要多少个箱子才能放下所有物品。a、b、k、v均是正整数。

思路

不难得知至少需要need = ceil(a / v)个隔间，问题就转化成至少要多少个箱子才能得到need个隔间，可以反向思考，有s个箱子和b个隔板最多能得到多少个隔间，由于一个箱子最多有k个隔间，因此最多可以有s * k个隔间，但这需要s * (k-1)个隔板，如果隔板个数b少于这个值，也无法得到这么多隔间，考虑到这种情况下（b < s * (k-1))，每少一个隔板就少获得一个隔间，所以这时得到的隔间个数是s * k - (s * (k-1) - b) = s + b个，综上可以得出在有s个箱子和b个隔板的情况下能得到s + min(b, s * (k-1))个隔间，不妨先假设min的取值是b，那么s = need - b，如果此时s * (k-1)确实大于等于b，那么b确实是min函数的取值，所以这个s是正确的，否则min的取值应当是s * (k-1)，那么有s * k >= need，此时s的取值为ceil(need / k)。注意本题要循环处理多个用例。

代码（只列出核心函数）

int solve(int a, int b, int k, int v) {
    int need = (a + v - 1) / v, s = need - b;
    if (s * (k-1) >= b) return s;
    else return (need + k - 1) / k;
}

第二题，图论问题

题目大意

给出一个带权无向图，没有自环和重边，给出两个节点s和t，求从s到达t的路径中的所有边里，边权最大的边的权至少有多大。保证s与t连通。
用例以n（节点个数）、m（边数）、s、t，然后m行u、v、w（权的大小）给出，比如：
5 6 1 5
1 5 100
1 2 10
2 5 5
1 3 3
3 4 2
4 5 1
选择从1->3->4->5的路径，经过3条w分别为3、2、1的边，因此答案为3。如果选择1->5或1->2->5则最大边权分别为100和10，都比3大。

思路

类似kruskal算法，先按权的大小升序排序，然后每次依次增加一条边，看s与t是否已经连通，如果此时变得连通，返回此边的权。为什么正确呢？因为在加入这条边之前所有权值小于它的边都已加入图中，但仍未使s与t连通，说明答案不可能比其权值w1小，而加入它以后s与t已经连通，那么必定能找到一条从s到t的路径，且路径上的边最大权值不大于w1（因为权值比w1大的边此时还没加入图中），因此w1就是答案。为了快速地判定s与t的连通性，使用并查集。

代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100005, M = 200005;

struct Edge {
    int u, v, w;
    bool operator< (Edge const& e) const { return w < e.w;}
} es[M];
int n, m, s, t, par[N], rk[N];

//并查集
int find(int x) { return x == par[x] ? x : (par[x] = find(par[x]));}
bool same(int x, int y) { return find(x) == find(y);}
void unite(int x, int y) {
    if ((x = find(x)) == (y = find(y))) return;
    if (rk[x] < rk[y]) {
        par[x] = y;
    } else {
        par[y] = x;
        if (rk[x] == rk[y]) rk[x]++;
    }
}

int solve() {
    sort(es, es + m);//按权值排序，Edge类已重载operator<
    for (int i = 0; i < n; i++) par[i] = i;//初始化并查集
    for (int i = 0; i < m; i++) {
        unite(es[i].u, es[i].v);//将这条边加入
        if (same(s, t)) return es[i].w;//如果此时s与t连通返回此边的边权。
    }
    return -1;
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    s--, t--;//题目给的点编号是1~n，个人习惯从0开始编号，所以自减1，下同。
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &es[i].u, &es[i].v, &es[i].w);
        es[i].u--, es[i].v--;
    }
    printf("%d\n", solve());
}