Potato的个人训练 The 2017 Benelux Algorithm Programming Contest

蔚落 2021-12-03 12:55 167阅读 0赞

# Potato的个人训练 The 2017 Benelux Algorithm Programming Contest #

来源：codeforces Gym101666

## [A - Amsterdam Distance][] ##

###### 题意：给出一个圆类似的坐标上的两个点，求两个点之间的最短距离。 ######

###### 思路：实际上通过推表达式我们可以知道，策略只有两种，直接走到圆心或者先走到靠内的半径再走一个弧长。 ######

###### 代码： ######

#include<bits/stdc++.h> using namespace std; const long double PI = acos(-1.0); const double eps = 1e-6; const int INF = 0x3f3f3f3f; long double M,N,R; long double ax,ay,bx,by; int main() { cin >> M>>N>>R>>ax>>ay>>bx>>by; long double r = R/N; long double ans1 = r * (fabs(ay - by)) + acos(-1) * r * min(ay, by) * fabs(ax - bx) / M; long double ans2 = r*fabs(ay+by); printf("%.14Lf\n",min(ans1,ans2)); }

## [C - Collatz Conjecture][] ##

###### 题意：给出一个长度为n的数组，求所有子区间的gcd，要求输出gcd的个数 ######

思路：对于一个区间\\(\[i,j\]\\)我们考虑固定右区间端点\\(j\\) ，我们记录以J为右端点的所有gcd的值，当我们考虑右端点为j+1的所有区间时，我们只需要考虑a\[j\]对于前一个区间的影响即可。

代码：

#include<bits/stdc++.h> using namespace std; const int maxn = 5e5+5; typedef long long ll; ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);} ll n; ll a[maxn],pre[maxn]; set<ll> ans; int main() { ios::sync_with_stdio(false); cin>>n; int cnt = 0; for(int i = 1;i <= n;i++) cin>>a[i]; for(int i = 1;i <= n;i++) { int len = cnt; for(int j = 0;j < len;j++) { ll t = gcd(pre[j],a[i]); pre[j] = t; } pre[cnt++] = a[i]; sort(pre,pre+cnt); cnt = unique(pre,pre+cnt) - pre; for(int k = 0;k < cnt;k++) ans.insert(pre[k]); } cout<<ans.size(); return 0; }

## [D - Detour][] ##

题意：有n个点，编号为0到1，每个点有一个指示告知往哪个点走为0到1的一条最短路，现在要求找到一条从0到1的路径满足每次走都不遵循这个指示。

思路：从1做一次dij记录路径，这样就可以知道具体的告示，再从0做dfs记录路径看是否能到达1即可。

代码：

#include<bits/stdc++.h> using namespace std; const int maxn = 1e5+5; const int maxm = 1e6+5; const int INF = 5e5+5; struct Edge{ int u,v,w,next; Edge() {} Edge(int u,int v,int w,int next): u(u),v(v),w(w),next(next) {} }; int n,m; int head[maxn],d[maxn],path[maxn],ans[maxn],cnt = 0; bool vis[maxn],mark[maxn],ok = false; Edge G[maxm]; inline void AddEdge(int u,int v,int w) { G[++cnt] = Edge(u,v,w,head[u]); head[u] = cnt; } inline void dijkstra() { priority_queue<pair<int,int> > Q; for(int i = 0;i < n;i++) { d[i] = INF; vis[i] = false; } d[1] = 0; Q.push(make_pair(0,1)); while(!Q.empty()) { pair<int,int> f = Q.top();Q.pop(); int u = f.second; vis[u] = true; for(int i = head[u];i;i = G[i].next) { Edge e = G[i]; if(vis[e.v]) continue; if(d[e.v] > d[u] + e.w) { d[e.v] = d[u] + e.w; Q.push(make_pair(-d[e.v],e.v)); path[e.v] = u; } } } } void dfs(int u) { if(u == 1) { ok = true; return; } for(int i = head[u];i;i = G[i].next) { Edge e = G[i]; if(path[u] == e.v || mark[e.v]) continue; ans[u] = e.v; mark[e.v] = true; dfs(e.v); if(ok) return; } } int main() { scanf("%d%d",&n,&m); for(int i = 0;i < m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); AddEdge(u,v,w); AddEdge(v,u,w); } dijkstra(); memset(ans,-1,sizeof(ans)); dfs(0); if(ok) { vector<int> res; for(int i = 0;i != -1;i = ans[i]) res.push_back(i); printf("%d ",res.size()); for(int i = 0;i < res.size();i++) printf("%d ",res[i]); } else printf("impossible\n"); return 0; }

## [F - Falling Apart][] ##

###### 题意：A和B玩一个游戏，每个人轮流从N个数中选，每个人都想拿到最大，求最后两人的收获 ######

思路：贪心

#include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); int n,a[16]; cin>>n; for(int i = 0;i < n;i++) cin>>a[i]; sort(a,a+n); int ans1 = 0,ans2 = 0; bool flag = 1; for(int i = n-1;i >= 0;i--) { if(flag) ans1+=a[i],flag = false; else ans2 += a[i],flag = true; } cout<<ans1<<" " << ans2; return 0; }

## [G - Going Dutch][] ##

题意：有m个人和n笔账单，要求最少通过几次转账才能还清。

思路：我们知道n个人最多可以通过n次转账来完成一次还清，而如果这n个人的盈亏总和为0，那么就可以减少一次操作，因此我们应该尽可能地去将这n个人分成多的盈亏总和为0的组。我们用\\(f(t)\\) 来表示当前状态\\(t\\) 的总盈亏，用\\(dp\[t\]\\) 来表示此状态的最大0分组个数，通过记忆化搜索更新值即可。

#include<bits/stdc++.h> using namespace std; const int maxm = 21; int s[maxm],n,m; int f[1<<maxm],dp[1<<maxm]; int dfs(int t) { if(~dp[t]) return dp[t]; if(f[t] == 0) { for(int i = 0;i < m;i++) { if(t&(1<<i)) return dp[t] = dfs(t-(1<<i))+1; } } else { for(int i = 0;i < m;i++) { if(t&(1<<i)) dp[t] = max(dp[t],dfs(t-(1<<i))); } } return dp[t]; } int main() { ios::sync_with_stdio(false); cin>>m>>n; for(int i = 0;i < n;i++) { int a,b,p; cin>>a>>b>>p; s[a]+=p; s[b]-=p; } for(int i = 0;i < (1<<m);i++) { dp[i] = -1; f[i] = 0; } for(int i = 0;i < (1<<m);i++) { for(int j = 0;j < m;j++) { if(i & (1<<j)) f[i] += s[j]; } } dp[0] = 0; cout<<m-dfs((1<<m)-1)<<endl; return 0; }

## [K - King of the Waves][] ##

###### 题意：有n个人，每个人各自能战胜某些人，让这n个人以一定的次序上擂台比赛，现在要求编号为0的人能够赢到最后，若能，则询问这n个人上擂台的次序，否则输出impossible. ######

思路：只需要从一个人到他能战胜的人连边，然后从0开始dfs看是否能够遍历所有点即可。

#include <bits/stdc++.h> using namespace std; int n; int a[1010][1010]; int used[1010]; int ans[1010]; char str[1010]; bool f; int t; void dfs(int u) { if(t==n-1) { f=1; return ; } for(int i=0; i<n; i++) if(a[u][i] && !used[i]) { used[i]=1; ans[t++]=i; dfs(i); } } int main() { scanf("%d",&n); f=0,t=0; memset(used,0,sizeof used); for(int i=0; i<n; i++) { scanf("%s",str); for(int j=0; j<n; j++) { if(str[j]=='X') a[i][j]=0; else if(str[j]=='1') a[i][j]=1; else a[i][j]=0; } } used[0]=1; dfs(0); if(f){ for(int i=t-1; i>=0; i--) printf("%d ",ans[i]); printf("0"); } else printf("impossible"); return 0; }

## [L - Lemonade Trade][] ##

###### 题意：给你一个Pink的饮料，要求获得最大的blue饮料，各种颜色的饮料之间的交换比率按次序给出，只能按次序兑换。 ######

思路：用map记录更新最佳的兑换比即可

#include<bits/stdc++.h> using namespace std; map<string,double> mp; int main() { ios::sync_with_stdio(false); mp["pink"] = 0.0; string s1,s2;double rate; int n; cin>>n; for(int i = 0;i < n;i++) { cin>>s1>>s2>>rate; if(!mp.count(s2)) continue; if(!mp.count(s1)) mp[s1] = mp[s2]+log10(rate); else mp[s1] = max(mp[s1],mp[s2] + log10(rate)); } double ans = mp["blue"]; if(ans > 1.0) printf("10.0\n"); else if(ans == 0) printf("0.0\n"); else printf("%.15lf\n",pow(10,ans)); return 0; }

## [M - Manhattan Mornings][] ##

题意：再平面直角坐标上给出起点和终点，和一些得分点，要求从起点到终点只允许走最近的曼哈顿路径，要求怎么走可以得到最多的分。

思路：将各个得分点先按x再按y排序，本质上就是去求一个lis

#include<bits/stdc++.h> using namespace std; const int maxn = 1e5+5; struct Point{ int x,y; Point() {} Point(int x,int y): x(x),y(y) {} }; Point G[maxn]; int L[maxn],n; int cnt = 0; int lis() { L[0] = G[0].y; int len = 1; for(int i = 1;i < cnt;i++) { if(L[len - 1] <= G[i].y) L[len++] = G[i].y; else *upper_bound(L,L+len,G[i].y) = G[i].y; } return len; } bool cmp1(Point a,Point b) { if(a.x == b.x) return a.y < b.y; else return a.x < b.x; } bool cmp2(Point a,Point b) { if(a.x == b.x) return a.y < b.y; else return a.x > b.x; } int main() { ios::sync_with_stdio(false); int x1,y1,x2,y2; cin>>n>>x1>>y1>>x2>>y2; if(x1 > x2) { swap(x1,x2);swap(y1,y2); } int xl = min(x1,x2),xr = max(x1,x2),yd = min(y1,y2),yu = max(y1,y2); for(int i = 0;i < n;i++) { int x,y; cin>>x>>y; if(xl<=x&&x<=xr&&yd<=y&&y<=yu) G[cnt++] = Point(x,y); } if(!cnt) {printf("0\n");return 0;} if(y1 < y2) sort(G,G+cnt,cmp1); else sort(G,G+cnt,cmp2); printf("%d\n",lis()); return 0; }

转载于:https://www.cnblogs.com/pot-a-to/p/11202069.html

[A - Amsterdam Distance]: https://vjudge.net/problem/Gym-101666A
[C - Collatz Conjecture]: https://vjudge.net/problem/Gym-101666C
[D - Detour]: https://vjudge.net/problem/Gym-101666D
[F - Falling Apart]: https://vjudge.net/problem/Gym-101666F
[G - Going Dutch]: https://vjudge.net/problem/Gym-101666G
[K - King of the Waves]: https://vjudge.net/problem/Gym-101666K
[L - Lemonade Trade]: https://vjudge.net/problem/Gym-101666L
[M - Manhattan Mornings]: https://vjudge.net/problem/Gym-101666M