atcoder-374（a-e）

atcoder-374

A

#include<bits/stdc++.h>using namespace std;signed main()
{string s;cin>>s;string str=s.substr(s.size()-3);if(str =="san") puts("Yes");else puts("No");return 0;
}

B

#include<bits/stdc++.h>using namespace std;signed main()
{string s,t;cin>>s>>t;int slen=s.size();int tlen=t.size();if(slen>tlen){swap(s,t);swap(slen,tlen);}int flag=1;if(s==t) puts("0");else{for(int i=0;i<s.size();i++){if(s[i]!=t[i]){cout<<i+1<<endl;flag=0;return 0;}}if(flag&&tlen!=slen){cout<<slen+1<<endl;}}return 0;
}

C

#include<bits/stdc++.h>using namespace std;signed main()
{int n;cin>>n;vector<int> k(n);int ans=0;for(int i=0;i<n;i++){cin>>k[i];ans+=k[i];}sort(k.begin(),k.end());int mid=0;for(int i=0;i<n;i++){mid+=k[i];if(mid>=ans/2){break;}}cout<<mid<<endl;return 0;
}

找到离中间值最近的组合

n最大也就20，搜索算法即可

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=25;
ll k[N];
int v[N];
int n;
ll ans=0;
ll res=1e18;void dfs(int u,ll cnt)
{if(cnt<=res&&cnt>=ans/2ll){res=cnt;}for(int i=1;i<n;i++){if(!v[i]){v[i]=1;dfs(i,cnt+k[i]);v[i]=0;}}
}signed main()
{cin>>n;for(int i=0;i<n;i++){cin>>k[i];ans+=k[i];}
//   cout<<ans<<endl;dfs(0,0ll);cout<<res<<endl;return 0;
}

为什么正着做不行

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=25;
ll k[N];
int v[N];
int n;
ll ans=0;
ll res=0;void dfs(int u,ll cnt)
{if(cnt<=ans/2ll&&res<=cnt){res=cnt;}for(int i=u;i<n;i++){if(!v[i]){v[i]=1;dfs(i,cnt+k[i]);v[i]=0;}}
}signed main()
{cin>>n;for(int i=0;i<n;i++){cin>>k[i];ans+=k[i];}
//   cout<<ans<<endl;dfs(0,0);cout<<ans-res<<endl;return 0;
}

简洁的写法

因为N最大为20，2的20次方也就1e6的复杂度，那直接暴力枚举就可以求解

但是用二进制表示选或者不选，怎么去做判断呢

#include<bits/stdc++.h>using namespace std;signed main()
{int n;cin>>n;vector<int> a(n+1);for(int i=1;i<=n;i++) cin>>a[i];int ans=0;for(int i=0;i< (1<<n+1);i++){int s = i;for(int j=0;j<32;j++){if(i>>j&1) ans+=a[i];}if(ans) }return 0;
}

正解

jianly的状态求和有点像前缀和

#include<bits/stdc++.h>using namespace std;signed main()
{int n;cin>>n;vector<int> k(n+1);for(int i=1;i<=n;i++) cin>>k[i];int tot = accumulate(k.begin()+1,k.end(),0);
//   cout<<tot<<endl;vector<int> sum(1<<n);int ans=1e9;for(int i=0; i<(1<<n); i++){if(i>0){int u = __builtin_ctz(i);sum[i]=k[u]+sum[i^(1<<u)];}ans = min(ans,max(sum[i],tot-sum[i]));}cout<<ans<<endl;return 0;
}

D

那两条线近就先走哪两段

就是最短路

其实是最小生成树

#include<bits/stdc++.h>using namespace std;signed main()
{ios::sync_with_stdio(false);cin.tie(0);int n,s,t;cin>>n>>s>>t;vector<int> a(n+1),b(n+1),c(n+1),d(n+1);vector<bool> v(n+1);for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i]>>d[i];double res=1e9;auto dfs = [&](auto &self,int x,int y,double ans=0.0,int cnt=0){if(cnt==n){res=min(ans,res);return ;}for(int i=1;i<=n;i++){if(v[i]) continue;double dis0=hypot(a[i]-x,b[i]-y);double dis1=hypot(c[i]-x,b[i]-y);double dis =hypot(a[i]-c[i],b[i]-d[i]);cout<<dis<<endl;v[i]=1;self(self,a[i],b[i],ans+dis,cnt+1);self(self,c[i],d[i],ans+dis,cnt+1);v[i]=0;}};dfs(dfs,0,0);return 0;
}

现在需要解决的是，如何输出样例那么长的小数，以及当两条线段重合时的距离需要重新计算

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=10,M=2*N;
int pa[N];
int n;
double s,t;struct xian{int a,b;int c,d;double dis=0;
}xs[N];struct node{int a,b;double dis;bool operator<(const node &M)const{return dis<M.dis;}
}ns[M];double dist(double x,double y,double xx,double yy){return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));
}int find(int x){if(x!=pa[x]) pa[x]=find(pa[x]);return pa[x];
}signed main()
{cin>>n>>s>>t;double ans=0;for(int i=1;i<=n;i++){cin>>xs[i].a>>xs[i].b>>xs[i].c>>xs[i].d;xs[i].dis=dist(xs[i].a,xs[i].b,xs[i].c,xs[i].d);ans+=xs[i].dis/t;// cout<<xs[i].a<<' '<<xs[i].b<<' '<<xs[i].c<<' '<<xs[i].d<<' '<<xs[i].dis<<endl;}
//   cout<<ans<<endl;int cnt=1;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){auto &u=xs[i],&v=xs[j];double dis=1e9;dis=min(dist(u.a,u.b,v.a,v.b),dis);dis=min(dist(u.a,u.b,v.c,v.d),dis);dis=min(dist(u.c,u.d,v.a,v.b),dis);dis=min(dist(u.c,u.d,v.c,v.d),dis);ns[cnt++]={i,j,dis};}}sort(ns+1,ns+cnt+1);for(int i=1;i<=n;i++) pa[i]=i;for(int i=1;i<=cnt;i++){int a=ns[i].a;int b=ns[i].b;double dis=ns[i].dis;a=find(a),b=find(b);if(a!=b){// cout<<a<<' '<<b<<' '<<dis<<endl;    pa[a]=b;ans+=dis/s;}}printf("%lf",ans);return 0;
}

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=10,M=2*N;
int pa[N];
int n;
double s,t;struct xian{int a,b;int c,d;double dis=0;
}xs[N];struct node{int a,b;double dis;bool operator<(const node &M)const{return dis<M.dis;}
}ns[M];double dist(double x,double y,double xx,double yy){return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));
}int find(int x){if(x!=pa[x]) pa[x]=find(pa[x]);return pa[x];
}signed main()
{cin>>n>>s>>t;double ans=0;for(int i=1;i<=n;i++){cin>>xs[i].a>>xs[i].b>>xs[i].c>>xs[i].d;xs[i].dis=dist(xs[i].a,xs[i].b,xs[i].c,xs[i].d);ans+=xs[i].dis/t;// cout<<xs[i].a<<' '<<xs[i].b<<' '<<xs[i].c<<' '<<xs[i].d<<' '<<xs[i].dis<<endl;}
//   cout<<ans<<endl;int cnt=1;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){auto &u=xs[i],&v=xs[j];double dis=1e9;dis=min(dist(u.a,u.b,v.a,v.b),dis);dis=min(dist(u.a,u.b,v.c,v.d),dis);dis=min(dist(u.c,u.d,v.a,v.b),dis);dis=min(dist(u.c,u.d,v.c,v.d),dis);ns[cnt++]={i,j,dis};}}sort(ns+1,ns+cnt+1);for(int i=1;i<=n;i++) pa[i]=i;for(int i=1;i<=cnt;i++){int a=ns[i].a;int b=ns[i].b;double dis=ns[i].dis;a=find(a),b=find(b);if(a!=b){// cout<<a<<' '<<b<<' '<<dis<<endl;    pa[a]=b;ans+=dis/s;}}printf("%lf",ans);return 0;
}

打印开始，坐标位于0，0.。。。。。。。。

佩服，我是理解错了，如果用最小生成树，那么还得建其实坐标到所有边的两个端点的边

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=10,M=2*N;
int pa[N];
int n;
double s,t;struct xian{int a,b;int c,d;double dis=0;
}xs[N];struct node{int a,b;double dis;bool operator<(const node &M)const{return dis<M.dis;}
}ns[M];double dist(double x,double y,double xx,double yy){return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));
}int find(int x){if(x!=pa[x]) pa[x]=find(pa[x]);return pa[x];
}signed main()
{cin>>n>>s>>t;double ans=0;for(int i=1;i<=n;i++){cin>>xs[i].a>>xs[i].b>>xs[i].c>>xs[i].d;xs[i].dis=dist(xs[i].a,xs[i].b,xs[i].c,xs[i].d);ans+=xs[i].dis/t;// cout<<xs[i].a<<' '<<xs[i].b<<' '<<xs[i].c<<' '<<xs[i].d<<' '<<xs[i].dis<<endl;}
//   cout<<ans<<endl;int cnt=1;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){auto &u=xs[i],&v=xs[j];double dis=1e9;dis=min(dist(u.a,u.b,v.a,v.b),dis);dis=min(dist(u.a,u.b,v.c,v.d),dis);dis=min(dist(u.c,u.d,v.a,v.b),dis);dis=min(dist(u.c,u.d,v.c,v.d),dis);ns[cnt++]={i,j,dis};}}for(int i=1;i<=n;i++){auto &u = xs[i];double dis=1e9;dis=min(dis,dist(u.a,u.b,0,0));dis=min(dis,dist(u.c,u.d,0,0));ns[cnt++]={0,i,dis};}sort(ns+1,ns+cnt+1);for(int i=1;i<=n;i++) pa[i]=i;for(int i=1;i<=cnt;i++){int a=ns[i].a;int b=ns[i].b;double dis=ns[i].dis;a=find(a),b=find(b);if(a!=b){// cout<<a<<' '<<b<<' '<<dis<<endl;    pa[a]=b;ans+=dis/s;}}printf("%lf",ans);return 0;
}

样例2，还是不行，因为对于0到其他的点，不可能再从0出发，那样会浪费时间

还是老老实实的搜索吧

#include<bits/stdc++.h>using namespace std;signed main()
{int n,s,t;cin>>n>>s>>t;vector<int> a(n+1),b(n+1),c(n+1),d(n+1);vector<bool> v(n+1);for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i]>>d[i];double res=1e9;auto dfs = [&](auto &self,int x,int y,double ans=0.0,int cnt=0){if(cnt==n){res=min(ans,res);return ;}for(int i=1;i<=n;i++){if(v[i]) continue;double dis0=hypot(a[i]-x,b[i]-y);double dis1=hypot(c[i]-x,b[i]-y);double dis =hypot(a[i]-c[i],b[i]-d[i]);cout<<dis<<endl;v[i]=1;self(self,a[i],b[i],ans+dis,cnt+1);self(self,c[i],d[i],ans+dis,cnt+1);v[i]=0;}};dfs(dfs,0,0);return 0;
}

正解

学会用sublime简直是令人赏心悦目

#include<bits/stdc++.h>using namespace std;signed main()
{int n;double s,t;cin>>n>>s>>t;vector<int> a(n+1),b(n+1),c(n+1),d(n+1);vector<bool> v(n+1);for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i]>>d[i];double res=1e9;auto dfs = [&](auto &self,int x,int y,double ans=0.0,int cnt=0){if(cnt==n){res=min(ans,res);return ;}for(int i=1;i<=n;i++){if(v[i]) continue;double dis0=hypot(a[i]-x,b[i]-y);double dis1=hypot(c[i]-x,d[i]-y);double dis =hypot(a[i]-c[i],b[i]-d[i]);// cout<<dis<<' '<<i<<endl;v[i]=1;self(self,a[i],b[i],ans+dis/t+dis1/s,cnt+1);self(self,c[i],d[i],ans+dis/t+dis0/s,cnt+1);v[i]=0;}};dfs(dfs,0,0);cout<<fixed<<setprecision(20)<<res<<endl;return 0;
}

E

赛时连看都没有机会看

简单读了题目之后，是求最大值

关于生产力的定义是，每道工序在哪一天可以加工的最少产品

不知道怎么个搜法

因为如果像上一题一样有不同的线段，这一题则是有不同的商品，但是每个商品可以选择的个数不定受限制于总预算X

#include<bits/stdc++.h>using namespace std;signed main()
{return 0;
}

jiangly用到了二分答案的做法，关于上面的问题，因为能处理的数量不超过100

所以直接枚举数量到100，计算所产生的总成本，如果成本不超过二分的那个值，那么就可以计算出最小生产力

讲解得还不错的视频

#include<bits/stdc++.h>using namespace std;
typedef long long ll;signed main()
{ios::sync_with_stdio(false);cin.tie(0);int n;ll x;cin>>n>>x;vector<int> a(n+1),p(n+1),b(n+1),q(n+1);// for(int i=1;i<=n;i++) cin>>a[i]>>p[i]>>b[i]>>q[i];for(int i=1;i<=n;i++){cin>>a[i]>>p[i]>>b[i]>>q[i];if(a[i]*q[i]<b[i]*p[i]){swap(a[i],b[i]);swap(q[i],p[i]);}}auto check = [&](int mid){ll ans = 0;for(int i=1;i<=n;i++){ll res = 1e18;for(int j=0;j<=100;j++){ll need = mid-b[i]*j;// mid-=b[i]*j;// 不能直接改变目标生产力// 因为要找到需要最合适的性价比低的物品的数量ll v=j*q[i];if(mid>0){v+=(1ll)*(need+a[i]-1)/a[i]*p[i];}res=min(res,v);}ans+=res;}return ans<=x;};ll l=0,r=1e9;// 这样还不会爆intwhile(l<r){ll mid=(l+r+1)>>1;if(check(mid)) l=mid;else r=mid-1;}cout<<r<<endl;return 0;
}

是有一点背包的感觉，还没有看官方题解

官方题解也是枚举+二分答案