A - Amsterdam Distance
题意：极坐标系，给出两个点，求最短距离
思路：只有两种方式，取min 第一种，先走到0点，再走到终点 第二种，走到同一半径，再走过去
#include <bits/stdc++.h> using namespace std;
#define INF 0x3f3f3f3f const double PI = acos(-1.0); double n, m, r;
double n1, m1, n2, m2; inline double work1()
{
double dis1 = r * n1 / n;
double dis2 = r * n2 / n;
return dis1 + dis2;
} inline double work2()
{
double dis1 = r * (n2 - n1) / n;
double dis2 = fabs(m1 - m2) * r * n1 * PI/ (n * m);
return dis1 + dis2;
} int main()
{
while (scanf("%lf%lf%lf", &m, &n, &r) != EOF)
{
scanf("%lf%lf%lf%lf", &m1, &n1, &m2, &n2);
if (n1 > n2)
{
swap(n1, n2);
swap(m1, m2);
}
double ans = INF * 1.0;
ans = min(ans, work1());
ans = min(ans, work2());
printf("%.10f\n", ans);
}
return ;
}
B - Bearly Made It
留坑。
C - Collatz Conjecture
题意：给出n个数，求有多少个不同的区间gcd
思路：从头扫过去，每次扩展gcd，如果有重复的直接剪掉
因为假设扫到第i个的时候，有x个gcd 那么到第i个，这x个gcd 如果都被保留下来，那么第i个数一定要是这n个数的倍数，那么显然如果存在这样的数，那么当x > 30 的时候 早就爆 1e18 了 所以复杂度应该在 30 * (n) * log(n)
#include<bits/stdc++.h> using namespace std; #define N 500050 typedef long long ll; inline ll gcd(ll a, ll b)
{
return b == ? a : gcd(b, a % b);
} int n;
ll GCD[N];
ll num;
map<ll, int>mp; int main()
{
while(~scanf("%d" ,&n))
{
mp.clear();
int len = ;
for(int i = ; i <= n; ++i)
{
scanf("%lld", &num);
for(int j = ; j < len; ++j)
{
GCD[j] = gcd(GCD[j], num);
}
GCD[len++] = num;
sort(GCD, GCD + len);
int tmp = ;
for(int i = ; i< len; ++i)
{
mp[GCD[i]]++;
if(i == )
{
GCD[tmp++] = GCD[i];
continue;
}
if(GCD[i] == GCD[i - ]) continue;
else GCD[tmp++] = GCD[i];
}
len = tmp;
}
int ans = mp.size();
printf("%d\n",ans);
}
return ;
}
D - Detour
题意：给出n条路，每次选择的路都不选从这条路到0的最短路径上的路，求最后选的最短路径
思路：先从1反向跑最短路，然后删边，再从0正向跑
#include <bits/stdc++.h>
using namespace std; #define N 100010
#define M 1000010
#define ll long long
#define INFLL 0x3f3f3f3f3f3f3f3f struct Edge
{
int to, nx, flag;
ll w;
inline Edge() {}
inline Edge(int to, ll w, int nx, int flag) : to(to), w(w), nx(nx), flag(flag) {}
}edge[M << ]; int head[N], pos; inline void Init()
{
memset(head, -, sizeof head);
pos = ;
} inline void addedge(int u, int v, ll w)
{
edge[++pos] = Edge(v, w, head[u], ); head[u] = pos;
edge[++pos] = Edge(u, w, head[v], ); head[v] = pos;
} int n, m; struct node
{
int to; ll w;
inline node() {}
inline node(int to, ll w) : to(to), w(w) {}
inline bool operator < (const node &r) const
{
return w > r.w;
}
}; ll dist[N];
int pre[N];
bool used[N]; inline void Dijkstra(int st)
{
for (int i = ; i < n; ++i) dist[i] = INFLL, used[i] = false, pre[i] = -;
dist[st] = ;
priority_queue <node> q; q.emplace(st, );
while (!q.empty())
{
int u = q.top().to; q.pop();
used[u] = true;
for (int it = head[u]; ~it; it = edge[it].nx)
{
if (edge[it].flag) continue;
int v = edge[it].to; ll w = edge[it].w;
if (!used[v] && dist[u] + w < dist[v])
{
dist[v] = dist[u] + w;
pre[v] = u;
q.emplace(v, dist[v]);
}
}
}
} int main()
{
while (scanf("%d%d", &n, &m) != EOF)
{
ll w; Init();
for (int i = , u, v; i <= m; ++i)
{
scanf("%d%d%lld", &u, &v, &w);
addedge(u, v, w);
}
Dijkstra();
if (dist[] == INFLL)
{
puts("impossible");
continue;
}
for (int i = ; i < n; ++i)
{
for (int it = head[i]; ~it; it = edge[it].nx)
{
int v = edge[it].to;
if (v == pre[i])
{
edge[it].flag = ;
break;
}
}
}
Dijkstra();
if (dist[] == INFLL)
{
puts("impossible");
continue;
}
vector <int> ans;
int it = ;
while (it != -)
{
ans.push_back(it);
it = pre[it];
}
reverse(ans.begin(), ans.end());
int len = ans.size();
printf("%d ", len);
for (int i = ; i < len; ++i) printf("%d%c", ans[i], " \n"[i == len - ]); }
return ;
}
E - Easter Eggs
留坑。
F - Falling Apart
水。
#include <bits/stdc++.h> using namespace std; int n;
int arr[]; int main()
{
while (scanf("%d", &n) != EOF)
{
for (int i = ; i <= n; ++i) scanf("%d", arr + i);
sort(arr + , arr + + n);
int ans[] = {, };
int flag = ;
for (int i = n; i >= ; --i)
{
ans[flag] += arr[i];
flag ^= ;
}
printf("%d %d\n", max(ans[], ans[]), min(ans[], ans[]));
}
return ;
}
G - Going Dutch
留坑。
H - Hoarse Horses
留坑。
I - Irrational Division
题意：给出n * m 的矩形，单位边长为1，黑白交替，Alice 只能一列一列取(从左往右)，Bob只能一行一行取(从下往上)，取到的分数为黑块-白块，求Alice 和 Bob 的最大分差，两人操作都最优
思路：可以找一下规律，偶数行 答案是0
奇数行 奇数列 答案是1
奇数行 偶数列 行 < 列 答案是2 否则 答案是0
#include <bits/stdc++.h> using namespace std; int n, m; int main()
{
while (scanf("%d%d", &n, &m) != EOF)
{
if ((n & ) == )
{
puts("");
continue;
}
if ((m & ))
{
puts("");
continue;
}
puts(n < m ? "" : "");
}
return ;
}
J - Jumping Choreography
留坑。
K - King of the Waves
题意：给出n个人的胜负关系，打擂台赛，求最后0胜利，给出上场顺序
思路：输出DFS序
#include<bits/stdc++.h> using namespace std; #define N 1010 int n;
int tot = ;
int dep[N];
char mp[N][N];
int ans[N]; inline void DFS(int pos, int cnt)
{
dep[pos] = cnt;
ans[++tot] = pos;
for(int i = ; i <= n; ++i)
{
if(mp[pos][i] == '' && !dep[i])
{
DFS(i, cnt + );
}
}
} int main()
{
while(~scanf("%d", &n))
{
tot = ;
memset(dep, , sizeof dep);
for(int i = ; i <= n; ++i)
{
for(int j = ; j <= n; ++j)
{
scanf(" %c", &mp[i][j]);
}
}
DFS(, );
if(tot != n)
{
puts("impossible");
}
else
{
for(int i = n; i >= ; --i)
{
printf("%d%c", ans[i] - , " \n"[i == ]);
}
}
}
return ;
}
L - Lemonade Trade
题意：给出n个兑换关系，刚开始有1l pink 最后想换到blue 要依次换，可以选择换和不换
思路：O(n) 扫一下，记录在这之前被兑换的颜色饮料最多能被换到多少 然后取max 注意 不能直接乘法，取log 再取e的幂次
#include<bits/stdc++.h> using namespace std; #define N 100010 const int INF = 0x3f3f3f3f;
const double EI = exp(1.0); int cnt;
map<string, int >mp;
double ans[N]; inline void init()
{
mp.clear();
cnt = ;
mp["pink"] = cnt++;
mp["blue"] = cnt++;
ans[] = log(1.0);
ans[] = -INF * 1.0;
} int n;
string a, b;
double w; int main()
{
ios::sync_with_stdio(false);
cin.tie();cout.tie();
while(cin >> n)
{
init();
for(int i = ; i <= n; ++i)
{
cin >> a >> b >> w;
if(mp[a] == )
{
mp[a] = cnt++;
ans[mp[a]] = -INF * 1.0;
}
if(mp[b] == )
{
mp[b] = cnt++;
ans[mp[b]] = -INF * 1.0;
}
int id1 = mp[a], id2 = mp[b];
ans[id1] = max(ans[id1], ans[id2] + log(w));
}
ans[] = pow(EI, ans[]);
ans[] = min(ans[], 10.0);
cout << setiosflags(ios::fixed) << setprecision() << ans[] << endl;
}
return ;
}
M - Manhattan Mornings
题意：给出n个点，起始点和终点，求从起始点到终点的最短路径，最多经过多少点
思路：先排序，固定一个轴，再求最长上升子序列
#include <bits/stdc++.h>
using namespace std; #define N 100010 int n; struct node
{
int x, y;
inline void scan()
{
scanf("%d%d", &x, &y);
}
inline bool operator < (const node &r) const
{
return x < r.x || x == r.x && y < r.y;
}
}point[N], st, ed; int arr[N], brr[N]; inline int DP1(int n)
{
if (n == ) return ;
int i, len, pos;
brr[] = arr[];
len = ;
for (int i = ; i <= n; ++i)
{
if (arr[i] >= brr[len])
{
len = len + ;
brr[len] = arr[i];
}
else
{
int pos = upper_bound(brr + , brr + + len, arr[i]) - brr;
brr[pos] = arr[i];
}
}
return len;
} inline bool cmp (node a, node b)
{
return a.x > b.x || a.x == b.x && a.y < b.y;
} int main()
{
while (scanf("%d", &n) != EOF)
{
st.scan(); ed.scan();
for (int i = ; i <= n; ++i)
point[i].scan();
if (st.x > ed.x) swap(st, ed);
if (st.y < ed.y)
{
sort(point + , point + + n);
int cnt = ;
for (int i = ; i <= n; ++i)
{
if (point[i].x >= st.x && point[i].x <= ed.x && point[i].y >= st.y && point[i].y <= ed.y)
arr[++cnt] = point[i].y;
}
printf("%d\n", DP1(cnt));
}
else
{
sort(point + , point + + n, cmp);
int cnt = ;
for (int i = ; i <= n; ++i)
{
if (point[i].x >= st.x && point[i].x <= ed.x && point[i].y >= ed.y && point[i].y <= st.y)
arr[++cnt] = point[i].y;
}
printf("%d\n", DP1(cnt));
}
}
return ;
}