# Toyota Programming Contest 2024#7（AtCoder Beginner Contest 362)

Toyota Programming Contest 2024#7（AtCoder Beginner Contest 362）

A - Buy a Pen (atcoder.jp)

void solve()
{ 
   int a,b,c;
   string t;
   cin>>a>>b>>c;
   cin>>t;
   if(t=="Red")cout<<min(b,c)<<endl;
   else if(t=="Green")cout<<min(a,c)<<endl;
   else cout<<min(a,b)<<endl;
}

B - Right Triangle (atcoder.jp)

int calc(pii a,pii b)
{
return (a.x-b.x)*(a.x-b.x)+(b.y-a.y)*(b.y-a.y);
}
void solve()
{
pii ax,bx,cx;
cin>>ax.x>>ax.y>>bx.x>>bx.y>>cx.x>>cx.y;
int a=calc(ax,bx);
int b=calc(bx,cx);
int c=calc(cx,ax);
if(a+b==c||b+c==a||c+a==b)
{
cout<<"Yes"<<endl;
return;
}
cout<<"No"<<endl;
}

C - Sum = 0 (atcoder.jp)

零点定理：只要最小的小于等于0，最大的大于等于0就一定存在一个序列的和是0。

然后我们只要把序列变成最小的，然后再看还差多少才能变成0即可。

void solve()
{
cin>>n;
for(int i=1;i<=n;i++)
   cin>>a[i].x>>a[i].y;
    int x=0,y=0;
    for(int i=1;i<=n;i++)
       x+=a[i].x,y+=a[i].y;
    if(x<=0&&y>=0)
    {
    cout<<"Yes"<<endl;
    vector<int>res;
    res.push_back(0);
    for(int i=1;i<=n;i++)
    res.push_back(a[i].x);
    if(x==0)
    {
    for(int i=1;i<=n;i++)
       cout<<res[i]<<' ';
    cout<<endl;
    return;
    }
    else
    {
    int t=abs(x);
    for(int i=1;i<=n;i++)
    {
    if(t==0)break;
      if((a[i].y-res[i])<t)
      {
      t-=(a[i].y-res[i]);
      res[i]=a[i].y;
      }
      else
      {
      res[i]+=t;
      t=0;
      }
    }
    }
    for(int i=1;i<=n;i++)
       cout<<res[i]<<' ';
    cout<<endl;
    return;
    }
    cout<<"No"<<endl;
}

D - Shortest Path 3 (atcoder.jp)

最短路的板子题

void dijkstra()
{
memset(st,0,sizeof st);
memset(dist,0x3f,sizeof dist);
priority_queue<pii,vector<pii>,greater<pii>>q;
dist[1]=a[1];
q.push({a[1],1});
while(q.size())
{
auto t=q.top();
q.pop();
int ver=t.second,distance=t.first;
if(st[ver])continue;
st[ver]=true;
for(auto v:e[ver])
{
int j=v.first;
    if(dist[j]>distance+v.second+a[v.first])
    {
    dist[j]=distance+v.second+a[v.first];
    q.push({dist[j],j});
    }
}
}
}
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
   cin>>a[i];
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
e[a].push_back({b,c});
e[b].push_back({a,c});
}
    dijkstra();
    for(int i=2;i<=n;i++)
        cout<<dist[i]<<' ';
cout<<endl;
}

E - Count Arithmetic Subsequences (atcoder.jp)

dp:

定义$f(i,j,k)$表示的是子序列中最后一位是$i$长度是$j$公差是$k$的方案数

如果最后一个是$i$的话倒数第二个$v$可能是$\mathrm{1...}i-1$中的任何一个，所以我们可以这样写出转移方程

一种是选：

$f(i,j,k)=f(i,j,k)+f(v,j-1,k)$

另一种是不选第$i$个，方程是：$f(i,j,k)=f(i,j,k)$相当于没有意义

所以方程还是$f(i,j,k)=f(i,j,k)+f(v,j-1,k)$，类似于最长上升子序列

任意两个数都是等差数列，所以初始化$f(i,2,k)=f(i,2,k)+1$

int n;
int a[N];
map<int,map<int,map<int,int>>>f;//防止越界，公差可能是负数
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)
  cin>>a[i];
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j++)
{
int d=a[i]-a[j];
        for(int k=2;k<=n;k++)
        {
        f[i][k][d]=(f[i][k][d]+f[j][k-1][d])%mod;
        }
        f[i][2][d]=(f[i][2][d]+1)%mod;
}
}
vector<int>res(n+1,0);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(auto x:f[i][j])
{
res[j]=(res[j]+x.second)%mod;
}
}
}
cout<<n<<' ';
for(int i=2;i<=n;i++)
   cout<<res[i]<<' ';
}

原文地址：https://blog.csdn.net/qq_33269561/article/details/140407760

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