2019 ICPC NAC补题

题目链接(PDF)：https://cs.baylor.edu/~hamerly/icpc/qualifier_2019/naq2019.pdf

B

收获：若题干没有明确具体形式， 就按照最容易的形式计算，如本题，将每个小矩形按照正方形处理 题解：若当做正方形处理，则只需要看直线y = $\frac{Mx}{N}$ ((0,0)->(N,M)) 是否经过正方形中心点即可。 正方形的左下角的点设为(p,q) 则其中心的点为(p+1/2, q+1/2) 即是否满足q + $\frac{1}{2}$ = $\frac{M}{N}$$\ast$(2p+1) 约分后得 2q+1 = $\frac{m}{n}$(2p + 1) 显然此时 m n互质 则只有两种情况 一. m n都是奇数 显然式子左边的必然是整数(奇数)， 则式子右边也是整数(奇数 所以k也是奇数) 即(2p+1) = kn =》有多少个k符合题意 得 k = $\frac{2p}{n}$ + $\frac{1}{n}$ < $\frac{2N}{n}$ + $\frac{1}{n}$ 且k为整数 所以k<=2$\frac{N}{n}$=2gcd(N,M) 又因为k是奇数所以k有gcd(N,M)个 二. m n中有一个是偶数 n(2q+1) = m(2p + 1) 显然该情况下 式中只有m或n是偶数 其余都是奇数 所以等式不成立 综上所述 return m%2 && n%2 ?gcd(M,N) : 0;

#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; ull n, m; ull gcd(ull a, ull b){ return b==0?a:gcd(b, a%b); } int main(){ scanf("%lld%lld",&n,&m); ull d = gcd(n,m); n /= d, m /= d; if(n%2&&m%2) printf("%lld\n",d); else printf("0\n"); //system("pause"); return 0; }

M

收获：开平方注意原值的正负； 出现除法 要考虑分母为0的情况(因为这个WA了) 题解： 初始化 g-=r, h-=r,看作是在地面上 最小值无可非议，两点间直线最短，题干中也明确提到是刚性绳(大概)，所以不需要考虑松弛拉伸的情况。 最大值有两种求法 法一：对称 orz 任取一根柱子作关于ow的对称点P,连接另一个柱子的顶点形成直线l，l的长度就是最长距离，具体证明我忘了(小学知识orz)

#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; int main(){ int t; cin>>t; while(t--){ double w, g, r, h; cin >> w>>g>>h>>r; //if(g<h) swap(g,h); g -= r, h -= r; double mi = sqrt((g-h)*(g-h)+w*w); double mx = sqrt((g+h)*(g+h)+w*w); printf("%.8lf %.8lf\n",mi,mx); } return 0; }

法二：求导 我当时的做法，设结点距离左柱子的距离为x,则最大值函数为 f(x) = $\sqrt{g^2+w^2}$ + $\sqrt{h^2+(w-x{)}^2}$ ，只需求导等于零求出x即可得到答案(就不求二阶导严格证明了) f’(x) = $\frac{x}{\sqrt{g^2+w^2}}$ + $\frac{x-w}{\sqrt{h^2+(w-x{)}^2}}$ 导数等于0移项化简开平方可得 x = $\frac{gw}{g+h}$(分母不为0！！！) 再将x代入最大值函数即可求出答案

#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; int main(){ int t; cin>>t; while(t--){ double w, g, r, h; cin >> w>>g>>h>>r; if(g<h) swap(g,h); g -= r, h -= r; if(g==0&&h==0) printf("%.8lf %.8lf\n",w,w); else{ double x = g*w/(g+h); // g x h w-x double mi = sqrt((g-h)*(g-h)+w*w); double mx = sqrt(g*g+x*x)+sqrt(h*h+(w-x)*(w-x)); printf("%.8lf %.8lf\n",mi,mx); } } //system("pause"); return 0; }

I

收获：弗洛伊德算法 这篇博客写的挺好的 用二维数组储存节点之间的距离，先将数组初始化((i,i)初始化0，其余初始化为∞) 然后根据输入 将(i,j)的值改为 输入的长度值k 即为任意两点之间的距离(无中转点) 核心算法：将1-n节点分别为中转点 改变两点之间的最短距离

for(int k = 1; k <= n; k++){//枚举中转点 for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(e[i][j] > e[i][k] + e[k][j]){ e[i][j] =s e[i][k] + e[k][j]; } } } }

题解：先用弗洛伊德算法 在完整图中计算出任意两点之间的最短距离 再建立一个只有起点、终点、修车店的图G’，将包含非G’节点的以及不符合题意的路径长度设为∞ 再用一遍弗洛伊德算法算出起始点和终点满足题意的最短距离

#include<bits/stdc++.h> using namespace std; #define INF 1e18 typedef long long ll; int n,m,t,d; int rep[505]; ll table[505][505];//用于储存节点之间的距离 bool judge(int x){//判断是否为新图的节点 即起始点 修车店 return x==1 || x==n || rep[x]; } void floid(){ for(int k = 1; k <= n; k++){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ table[i][j] = min(table[i][j],table[i][k] + table[k][j]); } } } } int main(){ scanf("%d%d%d%d",&n,&m,&t,&d); for(int i = 1; i <= t; i++){ int x; scanf("%d",&x); rep[x] = 1;//修车店的节点序号 } //初始化 for(int i = 1; i <=n; i++){ for(int j = 1; j <= n; j++){ table[i][j] = INF; } } int u, v, l; for(int i = 1; i <= m; i++){ scanf("%d%d%d",&u,&v,&l); table[u][v] = l; table[v][u] = l; } //弗洛伊达算法计算出 任意两点之间的最短距离 floid(); //新图只包含起始点和修车店 即人要么在起点 要么在修车店 for(int i = 1; i <= n; i++){//将所有不满足题意的路径 设为无限大 for(int j = 1; j <= n; j++){ if(i!=j){ if(judge(i)&&judge(j)){//是新图节点 if(table[i][j]>d) table[i][j] = INF;//但是到不了 continue; } } table[i][j] = INF;// i j不全是新图结点 } } //再用一遍弗洛伊达算法 floid(); //cout << table[2][n] << endl; if(table[1][n]==INF) printf("stuck\n"); else printf("%d\n",table[1][n]); //system("pause"); return 0; }

剩下的题 之后再补吧 orz