原题：铁路修复计划 原题大意在 A 国有很多城际铁路。这些铁路都连接两个城市（城市从1到n编号），可以双向通行，使得任意两个城市之间都由铁路网联系起来。 不过在一次星球大战之后，所有的铁路都经历了不同程度的损伤以至于无法通行了。由于经费紧缺，A 国政府不愿意再出资造新的铁路。对于原有的城际铁路，根据铁路的实际情况，有以下两种处理办法： 使用国内技术进行修复：主要针对损坏情况不是很严重的铁路。国内公司会对铁路状况进行评估，然后如实开出铁路修复的费用。使用国外技术进行修复：主要针对损坏情况严重的铁路。国外公司也会对铁路情况进行评估，然后按照铁路实际修复费用的k倍来收费（其中k是一个由国外公司决定的实数，不管怎么说，优惠是不可能的，所以 k≥1）。A国政府修复铁路的总预算是 M，目标是要让任意两个城市之间都能通过铁路联系起来。在预算不够且能够完成目标的条件下，显然没必要修复每一条铁路。 国外公司通过不知什么途径了解到了 A 国政府的总预算 M，他们现在要把 k 定下来，并且希望 k 尽可能得大。但 k 又不能太大，不然，如果A国政府发现无法完成任务的话，整个订单都会泡汤。 Input测试数据 ...

原题：丽娃河的狼人传说 原题大意丽娃河可以看成是从 1 到 n的一条数轴。为了美观，路灯只能安装在整数点上，每个整数点只能安装一盏路灯。经专业勘测，有m个区间特别容易发生事故，所以至少要安装一定数量的路灯，请问至少还要安装多少路灯。 Input第一行一个整数 T (1≤T≤300)，表示测试数据组数。 对于每组数据： 第一行三个整数 n,m,k (1≤n≤103,1≤m≤103,1≤k≤n)。 第二行 k 个不同的整数用空格隔开，表示这些位置一开始就有路灯。 接下来 m 行表示约束条件。第 i 行三个整数 li,ri,ti 表示：第 i 个区间 [li,ri]少要安装 ti 盏路灯 (1≤li≤ri≤n,1≤ti≤n)。 Output对于每组数据，输出Casex:y。其中x表示测试数据编号（从1开始），y表示至少要安装的路灯数目。如果无解，y 为 −1。 算法分析按右端点排序，然后对于不满足条件的尽量往右垒就好了。贪心的证明：由于左边的都已经垒满了，所以垒左边的肯定是没意义的。垒中间肯定没有垒右边的号，因为右边的区间不可能长得断开，使得垒在左边收益更大。这样就可以实现 O(n2)。 程 ...

原题：Strange Optimization 原题大意 找到一个α，使得f（1/2+α）最大。 可以看成两点之间距离，中点处最大。 程序代码#include <bits/stdc++.h> using namespace std; typedef long long ll; ll gcd(ll a, ll b){ return b == 0 ? a : gcd(b, a%b); } int main(){ //freopen("input.txt", "r", stdin); ios::sync_with_stdio(false); cin.tie(0); ll n, m; while(cin >> n >> m){ ll t1 = gcd(n, m); ll t2 = 2 * n * m; ll num = gcd(t1, t2); ll p = t1 / num; ll q = t2 / num; cout < ...

原题：Highway 原题大意n个城市要建造(n-1)条路，求最贵的建造方法。 算法分析 两次dfs求出直径，然后lca更新答案 程序代码#include <cstdio> #include <algorithm> #include <vector> #include <cstring> #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; const int maxn=100005; int fir[maxn],no[2*maxn],se[2*maxn],st[2*maxn][20],lo[200005]; ll dep[maxn]; struct nod { int to; ll cost; }; int n,m,d1,d2; vector<nod> g[maxn]; int cnt,sum; void mkST() { for(int i=1;i& ...

原题：Super Resolution 原题大意给一个01串，按照要求放大a*b倍，并且相对位置不变 算法分析比赛时唯一一道水题，模拟即可 程序代码#include <bits/stdc++.h> using namespace std; int n, m, a, b; int m1[11][11]; string s[11]; int main(){ ios::sync_with_stdio(false); cin.tie(0); while(cin >> n >> m >> a >> b){ for(int i = 0; i < n; i++) cin >> s[i]; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ m1[i][j] = s[i][j] - '0'; ...