望得分：100+100+100
实际得分：100+100+100
Problem 1 晨跑(running.cpp/c/pas)【题目描述】为了响应学校的号召，模范好学生王队长决定晨跑。不过由于种种原因，每天都早起去跑步不太现实，所以王队长决定每 a 天晨跑一次。换句话说，假如王队长某天早起去跑了步，之后他会休息 a-1 天，然后第 a 天继续去晨跑，并以此类推。王队长的好朋友小钦和小针深受王队长坚持锻炼的鼓舞， 并决定自己也要坚持晨跑。小钦决定每 b 天早起跑步一次，而小针决定每 c 天早起跑步一次。某天早晨，王队长、小钦和小针在早起跑步时相遇了，他们非常激动、相互鼓励，共同完成了一次完美的晨跑。为了表述方便，我们把三位同学相遇的这天记为第 0 天，他们想知道，下一次三人在跑步时相遇是第几天。由于三位同学都不会算，所以希望由你来告诉他们答案。【输入格式】输入文件 running.in输入共一行，包含三个正整数 a,b,c，表示王队长每隔 a 天晨跑一次、小钦每隔 b 天晨跑一次且小针每隔 c 天晨跑一次。【输出格式】输出文件 running.out输出共一行，包含一个正整数 x，表示三位同学下次将在第 x 天相遇。【样例输入】2 3 5【样例输出】30【数据范围】对于 30%的数据 1<=a,b,c<=100对于 50%的数据 1<=a,b,c<=1000对于 100%的数据 1<=a,b,c<=1000000
solution: 很明显，答案就是$\lcm (a,b,c)$，只需要求出来两两之间的$\gcd$，然后套用一下$\lcm$的公式就行了。
我们有：
\begin{aligned}
\lcm (a,b)=\frac{ab}{\gcd(a,b)}\\
\lcm (a,b,c)=\lcm(\lcm(a,b),c)
\end{aligned}
问题得解。
#include using namespace std;typedef long long ll;ll a,b,c;inline ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}inline ll lcm(ll a,ll b){return a*b/gcd(a,b);}inline ll lcm(ll a,ll b,ll c){return lcm(lcm(a,b),c);}int main(){ #ifndef LOCAL freopen("running.in","r",stdin); freopen("running.out","w",stdout); #endif scanf("%lld%lld%lld", printf("%lld\n",lcm(a,b,c)); fclose(stdin); fclose(stdout); return 0;}Problem 2 货物运输(goods.cpp/c/pas)【题目描述】在一片苍茫的大海上，有 n 座岛屿，岛屿与岛屿之间由桥梁连接，所有的岛屿刚好被桥梁连接成一个树形结构，即共 n-1 架桥梁，且从任何一座岛屿出发都能到达其他任何一座岛屿。第 i 座桥梁有一个承重量 wi， 表示该桥梁一次性最多通过重量为 wi 的货物。现在有 m 个货物运输路线，第 i 个路线要从岛屿 xi 出发到达岛屿 yi。为了最大化利益，你需要求出在不超过路线上任何一架桥梁的承重量的基础上，每个路线最多运输重量为多少货物。【输入格式】输入文件 goods.in第一行为两个整数 n，m。接下来 n-1 行，每行三个整数 x,y,w，表示有一座承重量为 w 的桥梁连接岛屿 x 和 y。接下来 m 行，每行两个整数 x,y，表示有一条从岛屿 x 出发到达岛屿 y 的路线，保证 x≠y。【输出格式】输出文件 goods.out输出共 m 行，每行一个整数，第 i 个整数表示第 i 条路线的最大重量。【样例输入】6 51 2 22 3 52 4 22 5 35 6 12 46 21 33 51 6【样例输出】21231【样例解释】岛屿间连接情况如图所示：
2,4 间只有一架桥，该路线最大运输重量为 26,2 间有两架桥，承重分别为 3 和 1，该路线最大运输重量为 1剩余询问不再作解释【数据范围】对于 50%的数据 n,m<=2000对于 100%的数据 n,m<=100000，w<=10^9
solution: NOIp2013 货车运输弱化版。给定一棵树，求一下LCA，在求LCA的时候顺便维护一下路径上的最小值（ST表），然后倍增求树上两点到LCA路径上的最小值即可。
#include#includeusing namespace std;#define MAXN 100010#define INF 999999999struct Edge{int to,next,w;}edge[MAXN*2];int cnt,n,m,head[MAXN],deep[MAXN],fa[MAXN][21],w[MAXN][21];bool vis[MAXN];inline int min(int a,int b){return adeep[y]) swap(x,y); for(int i=20; i>=0; i--) if(deep[fa[y][i]]>=deep[x]) { ans=min(ans, w[y][i]); y=fa[y][i]; } if(x==y) return ans; for(int i=20; i>=0; i--) if(fa[x][i]!=fa[y][i]) { ans=min(ans, min(w[x][i], w[y][i])); x=fa[x][i]; y=fa[y][i]; } ans=min(ans, min(w[x][0], w[y][0])); return ans;}int main(){ #ifndef LOCAL freopen("goods.in","r",stdin); freopen("goods.out","w",stdout); #endif int x,y,z; read(n);read(m); for(int i=1; i<=n-1; i++) { read(x);read(y);read(z); addedge(x,y,z);addedge(y,x,z); } for(int i=1; i<=n; i++) if(!vis[i]) { deep[i]=1; dfs(i); fa[i][0]=i; w[i][0]=INF; } for(int i=1; i<=20; i++) for(int j=1; j<=n; j++) { fa[j][i]=fa[fa[j][i-1]][i-1]; w[j][i]=min(w[j][i-1], w[fa[j][i-1]][i-1]); } for(int i=1; i<=m; i++) { read(x);read(y); printf("%d\n",lca(x,y)); } fclose(stdin); fclose(stdout); return 0;}Problem 3 数三角形(triangle.cpp/c/pas)【题目描述】给定一个 n×m 的网格，请计算三点都在格点上的三角形共有多少个。下图为 4×4 的网格上的一个三角形。
注意 ：三角形的三点不能共线。m n×m 的网格 共有( ( n+1) ) ×( ( m+1) ) 个格点【输入格式】输入文件 triangle.in输入一行，包含两个正整数 m,n。【输出格式】输出文件 triangle.out输出一个正整数，为所求三角形数量。【样例输入】2 2【样例输出】76【数据范围】对于 30%的数据 n,m<=10对于 60%的数据 n,m<=40对于 100%的数据 n,m<=1000
solution: 计算一条线段的斜率，明显的，若三点共线则一定构不成三角形。枚举一条线段的两个端点之差即可计算出斜率。计算出全集，然后减掉不能构成三角形的方案数即可。
#includeusing namespace std;typedef unsigned long long ull;ull m,n;ull ans;ull gcd(ull a,ull b){return !b?a:gcd(b,a%b);}int main(){ #ifndef LOCAL freopen("triangle.in","r",stdin); freopen("triangle.out","w",stdout); #endif scanf("%llu%llu", m++;n++; ans=m*n; ans=ans*(ans-1)/2*(ans-2)/3; for (ull a=0;a<=n;a++) for (ull b=0;b<=m;b++) if (a||b) { ull t=(gcd(a,b)-1)*(n-a)*(m-b); if (!a||!b) ans-=t; else ans-=2*t; } printf("%llu\n",ans); fclose(stdin); fclose(stdout); return 0;}SDWC 2018 day5