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; }