gym101666题解
- 2019 年 10 月 5 日
- 筆記
A Amsterdam Distance
题意
求圆环上的两点距离。
分析
显然是沿半径方向走到内圈再走圆弧最短。
代码
#include <bits/stdc++.h> using namespace std; double m,n,r,sx,sy,tx,ty; const double pi=acos(-1.0); int main(){ scanf("%lf%lf%lf%lf%lf%lf%lf",&m,&n,&r,&sx,&sy,&tx,&ty); double ans=fabs(ty-sy)*r/n; double mr=min(sy,ty)*r/n; double ps=fabs(tx-sx); ans+=ps*pi*mr/m; printf("%.14lfn",min(ans,(ty+sy)*r/n)); return 0; }C Collatz Conjecture
题意
n个数，求所有不同区间的gcd值的不同个数。
分析
- 序列的gcd问题经常就是暴力乱搞…不过姿势要对，因为gcd降得很快。
- 考虑暴力，我们从长度为1的区间依次合并，即每次
a[i]=gcd(a[i],a[i+1]);，然后直接对a数组去重，比如6 4 2 2，此时两个长度为3的区间的gcd值都是2，所以直接去重舍弃第二个，因为整个序列从头开始的gcd值一定是不增的，所以直接舍弃掉后面小的是正确的。
代码
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=5e5+50; int n; ll a[N]; ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b); } set<ll> s; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); s.insert(a[i]); } for(int r=n;r>1;r--){ for(int i=1;i<r;i++){ a[i]=gcd(a[i],a[i+1]); s.insert(a[i]); } r=unique(a+1,a+r)-a; } printf("%dn",int(s.size())); return 0; }D Detour
题意
给一个图，对每个节点不能走该节点到终点最短路方向的边，求路径。
分析
从终点跑一遍最短路，相当于多源到终点的最短路，然后删除最短路边(单向边)，再从起点跑一遍最短路。
代码
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+50; const int M=2e6+50; struct Edge{ int u,v; ll w; int next,vis; }e[M*2]; int cnt,head[N]; void init(){ cnt=0; memset(head,-1,sizeof(head)); } void add(int u,int v,ll w){ e[cnt]=Edge{u,v,w,head[u],0}; head[u]=cnt++; e[cnt]=Edge{v,u,w,head[v],0}; head[v]=cnt++; } int s,t,n,m,u,v,p[N]; ll w; int vis[N]; ll dis[N]; const ll INF=1e18; struct node{ int v; ll w; bool operator<(const node& rhs)const{ return w>rhs.w; } }; void dijk(bool del){ for(int i=1;i<=n;i++){ vis[i]=0; dis[i]=INF; p[i]=-1; } dis[s]=0; priority_queue<node> q; q.push(node{s,0}); while(!q.empty()){ node t=q.top(); q.pop(); int u=t.v; if(vis[u]){ continue; } vis[u]=1; for(int i=head[u];i!=-1;i=e[i].next){ int v=e[i].v; ll w=e[i].w; if(del && e[i].vis){ continue; } if(!vis[v] && dis[v]>dis[u]+w){ dis[v]=dis[u]+w; p[v]=u; q.push(node{v,dis[v]}); } } } } int ans[N]; int main(){ //freopen("in.txt","r",stdin); scanf("%d%d",&n,&m); init(); for(int i=1;i<=m;i++){ scanf("%d%d%lld",&u,&v,&w); u++; v++; add(u,v,w); } s=2,t=1; dijk(0); // for(int u=1;u<=n;u++){ // for(int i=head[u];i!=-1;i=e[i].next){ // int v=e[i].v; // if(p[u]==v){ // e[i].vis=1; // } // } // } for(int i=0;i<cnt;i++){ int u=e[i].u; int v=e[i].v; ll w=e[i].w; //printf("%d %d %lld %lldn",u,v,abs(dis[u]-dis[v]),w); if(dis[u]-dis[v]==w){ e[i].vis=1; //printf("%d %dn",u,v); } } s=1,t=2; dijk(1); if(dis[t]==INF){ printf("impossiblen"); }else{ int tot=0; for(int i=t;i!=-1;i=p[i]){ ans[tot++]=i-1; } printf("%d",tot); for(int i=tot-1;i>=0;i--){ printf(" %d",ans[i]); } printf("n"); } return 0; }E Easter Eggs
题意
有b个蓝色点和r个红色点，将n个物品分配到这两种点上，使得红色点上的物品和蓝色点上的物品的最小距离最大。
分析
- 最小距离最大，考虑二分答案，即二分最小距离，转化为使得两种点的任意两点的距离都大于mid。
- 两种点考虑二分图，对点之间距离小于mid的建边，那我们要求的就是该二分图的最大点独立集，即两两之间没有边，也就是距离大于mid。
代码
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1005; int n,b,r; int vis[N],mt[N]; int g[N][N]; ll x[N],y[N],cost[N][N]; bool dfs(int u,int n){ for(int i=1;i<=n;i++){ if(!vis[i] && g[u][i]){ vis[i]=1; if(mt[i]==-1 || dfs(mt[i],n)){ mt[i]=u; return true; } } } return false; } int solve(){ int ans=0; memset(mt,-1,sizeof(mt)); for(int i=1;i<=b;i++){ memset(vis,0,sizeof(vis)); ans+=dfs(i,r); } return ans; } bool check(ll dis){ memset(g,0,sizeof(g)); for(int i=1;i<=b;i++){ for(int j=1;j<=r;j++){ if(cost[i][j]<dis){ g[i][j]=1; } } } int sol=solve(); return b+r-sol>=n; } int main(){ //freopen("in.txt","r",stdin); scanf("%d%d%d",&n,&b,&r); for(int i=1;i<=b+r;i++){ scanf("%lld%lld",&x[i],&y[i]); } for(int i=1;i<=b;i++){ for(int j=1;j<=r;j++){ cost[i][j]=1ll*(x[i]-x[b+j])*(x[i]-x[b+j])+1ll*(y[i]-y[b+j])*(y[i]-y[b+j]); } } ll L=0,R=1e18+50; ll ans=0; while(L<=R){ ll mid=(L+R)/2; if(check(mid)){ L=mid+1; ans=mid; }else{ R=mid-1; } } printf("%.10lfn",sqrt(ans*1.0)); return 0; }F Falling Apart
题意
n个数，两人轮流取，两个人都要最大。
分析
排序。
代码
#include <bits/stdc++.h> using namespace std; const int N=20; int a[N],n; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } sort(a+1,a+1+n); int aa=0,bb=0; int f=0; for(int i=n;i>=1;i--){ if(f){ bb+=a[i]; }else{ aa+=a[i]; } f^=1; } printf("%d %dn",aa,bb); return 0; }I Irrational Division
题意
有一个p*q的黑白相间的格子图，你站在左边往右切，另一个人站在下边往上切，切到的部分黑色加1分，白色减1分，两人都按最优策略尽量让自己分最大，问最大可能的分数差值绝对值。
分析
- 显然分奇偶判断一下。
- 当p为偶数，列无论怎么取都是黑白相同0，所以最优取法是保守取剩下偶数列，这样对方也只能保守取偶数行，最后答案为0。如果取剩下奇数列，那最后的得分是0和-2，虽然答案变大，但是并不是最优的使得两人得分尽量多的策略。
- 当p为奇数，q也为奇数时，第一步保守取偶数列得分0，剩下奇数列，对方显然可以只选一行，得1分，最后结果是0和1，若第一步激进选奇数列得1分，考虑直接取完的情况，所以最后结果是1和0，所以答案为1。
- 当p为奇数，q为偶数时，还需要判断p和q的关系。
- 当p<q时，第一步保守取偶数列得0分，对方最优肯定也是保守取1行，转化为pq均为偶数的情况，答案为0，第一步激进取1列得1分，对方只能保守取偶数行得0分，我们再保守取，最后肯定能剩下一个白色角落给对方，因此最后结果是0和-2，答案为2。
- 当p>q时，第一步保守取偶数列得0分，对方最优肯定取奇数行剩下偶数行，转化为pq均为偶数的情况，答案为0，第一步激进取1列得1分，对方最优取偶数行剩下奇数行，我们只能保守取偶数列，最后肯定剩下一个白色角落给我们，因此最后结果是0和0，答案为0。
代码
#include <bits/stdc++.h> using namespace std; int p,q; int main(){ scanf("%d%d",&p,&q); if(p%2==0 && q%2==0){ printf("0n"); }else if(p%2==0 && q%2==1){ printf("0n"); }else if(p%2==1 && q%2==0){ if(p<q){ printf("2n"); }else{ printf("0n"); } }else if(p%2==1 && q%2==1){ printf("1n"); } return 0; }K King of the Waves
题意
给n个人的对战胜负关系，要求构造一个擂台挑战顺序使得0号赢。
分析
- 从0号开始按照胜负关系递归下去，如果能访问到每个点，那就可以，按dfs序输出即可。
代码
#include <bits/stdc++.h> using namespace std; const int N=1e3+50; char s[N][N]; int w[N][N],vis[N]; int n,cnt; vector<int> ans; void dfs(int u){ cnt++; vis[u]=1; for(int i=0;i<n;i++){ if(vis[i] || w[u][i]!=1){ continue; } dfs(i); } ans.push_back(u); } int main(){ //freopen("in.txt","r",stdin); scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%s",s[i]); for(int j=0;j<n;j++){ if(s[i][j]=='X'){ w[i][j]=-1; }else{ w[i][j]=s[i][j]-'0'; } } } dfs(0); if(cnt==n){ for(int i=0;i<n;i++){ printf("%d%c",ans[i],i==n-1?'n':' '); } }else{ printf("impossiblen"); } return 0; }L Lemonade Trade
题意
初始有1升pink，给n个交易关系，问最后最多能换多少blue。
分析
- 一开始看错题意以为可以随便交易，那就是建图跑。
- 由于只能按顺序交易，那么直接把字符串映射一下然后简单dp即可，注意把乘法改成加log，然后最后判断大于10也不能先计算结果再判断，因为2的1e5次方太大，所以直接用log判断。
代码
#include <bits/stdc++.h> using namespace std; const int N=2e5+50; const double INF=1e18; map<string,int> idx; int n; char a[15],b[15]; double w; double mx[N]; int vis[N]; int main(){ //freopen("in.txt","r",stdin); int tot=0; scanf("%d",&n); idx["pink"]=++tot; vis[tot]=1; for(int i=1;i<N;i++){ mx[i]=-INF; } mx[1]=0.0; for(int i=1;i<=n;i++){ scanf("%s%s%lf",a,b,&w); if(idx.find(a)==idx.end()){ idx[a]=++tot; } if(idx.find(b)==idx.end()){ idx[b]=++tot; } if(vis[idx[b]]){ mx[idx[a]]=max(mx[idx[a]],mx[idx[b]]+log2(w)); vis[idx[a]]=1; } } int t=idx["blue"]; if(vis[t]){ if(mx[t]>log2(10.0)){ printf("10.000000000n"); }else{ printf("%.14lfn",min(10.000000000,pow(2.0,mx[idx["blue"]]))); } }else{ printf("0.0000000000n"); } return 0; }M Manhattan Mornings
题意
给定起点终点，求二维的最长不下降子序列。
分析
- 一维排序，按顺序枚举，然后另一位离散化后在起点终点范围内的点加入线段树中，并查询最大值更新。
- 注意起点终点的四种可能位置。
代码
#include <bits/stdc++.h> using namespace std; const int N=2e5+50; struct Orz{ vector<int> a; void clr(){ a.clear(); } int siz(){ return a.size(); } void add(int x){ a.push_back(x); } void work(){ sort(a.begin(),a.end()); a.erase(unique(a.begin(),a.end()),a.end()); } int idx(int x){ return lower_bound(a.begin(),a.end(),x)-a.begin()+1; } int val(int i){ return a[i-1]; } }orz; struct ST{ #define ls i<<1 #define rs i<<1|1 #define mid (l+r)/2 int mx[N*4]; void pushup(int i){ mx[i]=max(mx[ls],mx[rs]); } void build(int i,int l,int r){ mx[i]=0; if(l==r){ return; } build(ls,l,mid); build(rs,mid+1,r); } void update(int i,int l,int r,int p,int v){ if(l==r && l==p){ mx[i]=max(mx[i],v); return; } if(p<=mid){ update(ls,l,mid,p,v); }else{ update(rs,mid+1,r,p,v); } pushup(i); } int query(int i,int l,int r,int ql,int qr){ if(ql<=l && qr>=r){ return mx[i]; } int ans=0; if(ql<=mid){ ans=max(ans,query(ls,l,mid,ql,qr)); } if(qr>mid){ ans=max(ans,query(rs,mid+1,r,ql,qr)); } return ans; } }ac; struct node{ int x,y,w; }a[N]; bool cmp1(node a,node b){ if(a.y!=b.y){ return a.y<b.y; }else{ return a.x<b.x; } } bool cmp2(node a,node b){ if(a.y!=b.y){ return a.y<b.y; }else{ return a.x>b.x; } } int n,sx,sy,tx,ty,nx[N],ny[N]; int main(){ //freopen("in.txt","r",stdin); scanf("%d",&n); scanf("%d%d%d%d",&sx,&sy,&tx,&ty); orz.clr(); orz.add(sx); orz.add(sy); orz.add(tx); orz.add(ty); for(int i=1;i<=n;i++){ scanf("%d%d",&nx[i],&ny[i]); orz.add(nx[i]); orz.add(ny[i]); } orz.work(); int ns=orz.siz(); sx=orz.idx(sx); sy=orz.idx(sy); tx=orz.idx(tx); ty=orz.idx(ty); if(sy>ty){ swap(sx,tx); swap(sy,ty); } a[0]=node{sx,sy}; a[1]=node{tx,ty}; for(int i=1;i<=n;i++){ nx[i]=orz.idx(nx[i]); ny[i]=orz.idx(ny[i]); a[i+1]=node{nx[i],ny[i]}; } if(sx<tx){ sort(a,a+n+2,cmp1); for(int i=0;i<=n+1;i++){ if(a[i].x>=sx && a[i].x<=tx && a[i].y>=sy && a[i].y<=ty){ int x=a[i].x; int t=ac.query(1,1,ns,1,x); a[i].w=t+1; ac.update(1,1,ns,x,a[i].w); } } printf("%dn",ac.query(1,1,ns,sx,tx)-2); }else{ sort(a,a+n+2,cmp2); for(int i=0;i<=n+1;i++){ if(a[i].x>=tx && a[i].x<=sx && a[i].y>=sy && a[i].y<=ty){ int x=a[i].x; int t=ac.query(1,1,ns,x,ns); a[i].w=t+1; ac.update(1,1,ns,x,a[i].w); } } printf("%dn",ac.query(1,1,ns,tx,sx)-2); } return 0; }