自学内容网 自学内容网
自学内容网 > 正文

atcoder-374（a-e）

🕗 发布于 2024-10-07 17:12 算法比赛  

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

image-20241006014914769

image-20241006015120513

打印开始，坐标位于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;
}

image-20241006144944034

样例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简直是令人赏心悦目

image-20241006222756860

#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;
// 这样还不会爆int
while(l<r)
{
ll mid=(l+r+1)>>1;
if(check(mid)) l=mid;
else r=mid-1;
}

cout<<r<<endl;

return 0;
}

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

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


原文地址：https://blog.csdn.net/weixin_73683197/article/details/142735729

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024