题目链接： codeforces 2018EC final D
题意：
有两堆棋子，第一个人有n堆，第二个人有m堆，每人每次能拿一堆，第一个人先拿，问第一个人是否能赢
解题思路：
..........比大小， n <= m能赢，否则输
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5+5; int main(){ int t; cin >> t; while(t--){ int n, m, a, b; cin >> n >> m; for(int i = 1; i <= n; i++){ cin >> a; } for(int i = 1; i <= m; i++){ cin >> b; } if(n <= m){ cout << "Yes" << endl; } else{ cout << "No" << endl; } } return 0; }题目链接：codeforces EC 2018final F
题意：
在三维坐标系中，给定一个球心和半径，然后给两个点，问在不穿过球的情况下，S 点 到T点的最短距离
解题思路：
先判断ST这条线段是否穿过球，如果没穿过（没穿过的情况有一种是点到直线的距离小于半径，但是由于ST是线段，所以并没有穿过圆），那么就是点S到点T的距离，否则按如下方法进行求解
由于是三维平面，所以需要转换为二维平面，可以确定，S，T两点加上圆心可以确定一个的平面，然后两个点做圆的切线，再求圆弧长度
#include<bits/stdc++.h> using namespace std; typedef long long ll; const double pi = acos(-1); struct point{ double x, y, z; }; double dist(point a, point b){ return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) + (a.z-b.z)*(a.z-b.z); } double angle(double x, double y, double z){ // 余弦定理计算角度 return acos((x + y - z) / (2 * sqrt(x) * sqrt(y))); } int main(){ int t; cin >> t; while(t--){ point o, s, t; double r; cin >> o.x >> o.y >> o.z >> r; cin >> s.x >> s.y >> s.z >> t.x >> t.y >> t.z; double dis_os = dist(o, s); double dis_ot = dist(o, t); double dis_st = dist(s, t); if(dis_st == 0){ // ST两点重合 printf("0.00000000\n"); continue; } double ost = angle(dis_os, dis_st, dis_ot);// 角ost的大小 double ots = angle(dis_ot, dis_st, dis_os);// 角ost的大小 double h = sqrt(dis_os) * sin(ost); // 圆心点到直线距离 if(h >= r || (ost >= pi/2 || ots >= pi/2)){ printf("%.15lf\n", sqrt(dis_st)); continue; } double sot = angle(dis_os, dis_ot, dis_st); double ans = sqrt(dis_os-r*r)+sqrt(dis_ot-r*r); // 两条切线长度 ans += (sot-acos(r/sqrt(dis_os))-acos(r/sqrt(dis_ot)))*r; // 圆弧长度 printf("%.15lf\n",ans ); } return 0; }
题目链接：codeforces 2018EC final L
题意：
某国分为东西部，东部城市到东部城市之间的铁路花费为1，西部到西部城市的铁路花费为1，至少有一条公共线路将东西部联通，公共铁路的花费为1 ，问某一城市到其他城市的最小花费总和为多少。输入n代表n个城市，输入m代表m条公共线路，输入n个数，0代表此城市为西部城市，1代表此城市为东部城市，然后输入m行，每行两个数，代表公共线路联通的两个城市。
解题思路：
从某一城市出发到其他城市的最小花费至少为 n - 1。具体情况分为4中，如下图所示：
使用数组模拟后进行讨论就好
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5+5; int a[maxn], b[maxn]; int main(){ int n, m, res = 0, res0 = 0, res1 = 0; cin >> n >> m; for(int i = 1; i <= n; i++){ cin >> a[i]; res += a[i]; // res 最终为东部城市的个数 b[i] = 0; // b[i]记录此城市与相对部分城市有多少条公共线路中 } for(int i = 1; i <= m; i++){ int u, v; cin >> u >> v; if(a[u] != a[v]){ // 如果一个在东部一个在西部，那么记录 b[u]++; b[v]++; } } for(int i = 1; i <= n; i++){ if(b[i] == 0){ // 此城市不在公共线路上 if(a[i] == 0){ res0++; // 西部城市不在公共线路上的数量 } else{ res1++; // 东部城市不在公共线路上的数量 } } } for(int i = 1; i <= n; i++){ int ans = n - 1; // 初始为 n-1 if(b[i] == 0){// 不在公共线路上，加上2倍的没有公共线路的城市和对立部分剩下的城市 if(a[i] == 0){ ans += res1 * 2 + (res - res1); } else{ ans += res0 * 2 + (n - res - res0); } } else{ //如果此城市在公共线路上，那么最多有2花费，只需加上对立的部分的没有和此城市直接相连的城市数量 if(a[i] == 0){ ans += (res - b[i]); } else{ ans += (n - res - b[i]); } } if(i == 1){ cout << ans; } else{ cout << " " << ans; } } return 0; }
