首页 > 其他分享 >UNIQUE VISION Programming Contest 2024 Summer (AtCoder Beginner Contest 359) 题解

UNIQUE VISION Programming Contest 2024 Summer (AtCoder Beginner Contest 359) 题解

时间：2024-06-22 22:43:00浏览次数：29  
标签：Summer Contest 题解 LL pos fi rep se define

点我看题

A - Count Takahashi

没啥好说的

点击查看代码 
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

int main()
{
  fileio();

  int n,ans=0;
  string s;
  cin>>n;
  rep(i,n)
  {
    cin>>s;
    if(s[0]=='T') ++ans;
  }
  cout<<ans<<endl;

  termin();
}

B - Couples

从\(1\)到\(n-2\)依次检查第\(i\)个数和第\(i+2\)个数是否相同，相同就把答案加一。

时间复杂度\(O(n)\)。

点击查看代码 
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

int n,a[210];

int main()
{
  fileio();

  cin>>n;
  rep(i,n*2) cin>>a[i];
  int ans=0;
  rep(i,n*2-2) if(a[i]==a[i+2]) ++ans;
  cout<<ans<<endl;

  termin();
}

C - Tile Distance 2​

发现我们的最优策略一定是先走到与终点在同一行(y坐标相同)，这个过程中尽量缩短横向与终点的距离；到达终点所在行后，再直着走过去。证明：瞪眼法。也就是说我们的路线大概长这样：

其中斜着的那一段与x轴夹角为45度，这样走可以在把纵向距离缩到0的同时尽量缩短横向距离。令起点和终点的纵向距离为d。走了d步并把纵向距离缩到0后，我们可能到达的砖块是下面这些：

如果终点已经在这些砖块中，那么答案就是d；否则我们就一开始花d步走到这些砖块中离终点最近的，然后横向直着走过去。

时间复杂度\(O(1)\)。

点击查看代码 
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <LL,LL>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

pii s,t;

bool same(LL x1,LL y1,LL x2,LL y2)
{
  pii aa=mpr(x1,y1),bb=mpr(x2,y2);
  if(aa>bb) swap(aa,bb);
  return (aa==bb)||(aa.se==bb.se&&aa.fi+1==bb.fi&&(aa.fi+aa.se)%2==0);
}

int main()
{
  fileio();

  cin>>s.fi>>s.se>>t.fi>>t.se;
  LL ans=0;
  while(!same(s.fi,s.se,t.fi,t.se))
  {
    if(s>t) swap(s,t);
    if(s.se==t.se)
    {
      if((s.fi+s.se)%2==0) ++s.fi;
      if((t.fi+t.se)%2==1) --t.fi;
      LL dist=(t.fi-s.fi-1)/2+1;
      ans+=dist;
      break;
    }
    LL dirx=(t.fi>s.fi ? 1:(t.fi==s.fi ? 0:-1)),diry=(t.se>s.se ? 1:(t.se==s.se ? 0:-1)),dist=abs(t.se-s.se);
    ans+=dist;
    LL ori=s.fi;
    s.fi+=dirx*dist;
    s.se+=diry*dist;
    if(min(ori,s.fi)<t.fi&&t.fi<max(ori,s.fi)) s.fi=t.fi;
  }
  cout<<ans<<endl;

  termin();
}

D - Avoid K Palindrome

令\(f_{i,j}\)表示处理了前i个位置，从第i个位置往前k个位置的字母组成的bitmask为j的二进制表示的方案数(如果i<k，可以用0填充)。转移时枚举下一位填A(0)还是B(1)，计算出新的j(\(nj=(j<<1)\&((1<<k)-1)|newbit\))，然后看一下nj写成k位二进制数是否回文，如果不是就可以转移。

时间复杂度\(O(2^kn)\)。

点击查看代码 
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

const int MOD=998244353;

int n,k,bad[1100],dp[1100][1100];
string s;

int main()
{
  fileio();

  cin>>n>>k>>s;
  rep(i,1<<k)
  {
    string ss="",tt;
    int j=i;
    rep(p,k)
    {
      ss+=(j%2+'0');
      j/=2;
    }
    tt=ss;
    reverse(tt.begin(),tt.end());
    if(ss==tt) bad[i]=1;
  }
  dp[0][0]=1;
  rep(i,n) rep(j,1<<k) if(dp[i][j])
  {
    //cout<<i<<' '<<j<<' '<<dp[i][j]<<endl;
    rep(p,2) if((p==0&&s[i]!='B')||(p==1&&s[i]!='A'))
    {
      int nj=(j<<1)&((1<<k)-1)|p;
      if(i+1<k||!bad[nj]) dp[i+1][nj]=(dp[i+1][nj]+dp[i][j])%MOD;
    }
  }
  int ans=0;
  rep(j,1<<k) ans=(ans+dp[n][j])%MOD;
  cout<<ans<<endl;

  termin();
}

E - Water Tank​

拒绝理性思考，拥抱感性猜测（雾。

第i个容器有水的前一刻，所有容器的状态应该是这样：

也就是第j个容器中水的高度是\(max_{k\in[j,i)}\{H_k\}\)。我们要对每个\(i\in[2,n+1]\)求出\(\sum_{j=1}^{i-1}max_{k\in[j,i)}\{H_k\}\)。用一个单调栈完美解决。

时间复杂度\(O(n)\)。

点击查看代码 
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <LL,LL>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

LL n,a[200010];
stack <pii> q;

pii Front(){return q.empty() ? mpr(-1LL,-1LL):q.top();}

int main()
{
  fileio();

  cin>>n;
  LL ans=0;
  rep(i,n)
  {
    scanf("%lld",a+i);
    while(!q.empty()&&q.top().fi<=a[i])
    {
      pii cur=q.top();q.pop();
      pii nxt=Front();
      ans-=cur.fi*(cur.se-nxt.se);
    }
    pii cur=Front();
    ans+=a[i]*(i-cur.se);
    q.push(mpr(a[i],i));
    printf("%lld ",ans+1);
  }
  cout<<endl;

  termin();
}

F - Tree Degree Optimization

注意到如果所有n个节点的度数都>0且和为\(2n-2\)，那一定存在一棵合法的树。所以只要构造一个满足这个条件的最优的度数序列就可以了。

发现答案不会特别大。比如我们给权值最大的两个点分配度数1，其它点分配度数2，那答案最大就是\(4\cdot权值_{max}\cdot n\)这个级别。我们先按这个方式分配初始权值，然后通过微小的调整把他调成最优构造。其实一开始怎么分配都行

维护两个堆(可以是set)，第一个装所有节点度数+1后会增加的花费以及相应节点的编号；第二个装所有当前分配的度数>1的节点度数-1后会减少的花费以及相应节点的编号。两个堆都按增加/减少的花费为关键字排序。贪心地想，如果第一个堆中的最大元素增加的花费\(\geq\)第二个堆中的最小元素减少的花费，那怎么调整都不能使花费更小，当前的分配方式就是最优解。否则就把第一个堆中的最大元素度数+1，第二个堆中的最小元素度数-1，然后在两个堆中也做出相应的调整。用瞪眼法看出调整的次数不会超过n次。

时间复杂度\(O(nlog_2n)\)。

点击查看代码 
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <LL,LL>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

LL n,a[200010],deg[200010];
set <pii> incs,decs;

LL inc(LL x){return ((deg[x]<<1)|1)*a[x];}
LL dec(LL x){return ((deg[x]<<1)-1)*a[x];}

int main()
{
  fileio();

  cin>>n;
  rep(i,n) scanf("%lld",a+i);
  sort(a,a+n);
  rep(i,n-2) deg[i]=2;
  deg[n-2]=deg[n-1]=1;
  rep(i,n)
  {
    incs.insert(mpr(inc(i),i));
    if(deg[i]>1) decs.insert(mpr(dec(i),i));
  }
  while(!incs.empty()&&!decs.empty())
  {
    pii d=*decs.rbegin(),i=*incs.begin();
    if(d.fi<=i.fi) break;
    decs.erase(d);if(incs.find(mpr(inc(d.se),d.se))!=incs.end()) incs.erase(mpr(inc(d.se),d.se));
    incs.erase(i);if(decs.find(mpr(dec(i.se),i.se))!=decs.end()) decs.erase(mpr(dec(i.se),i.se));
    --deg[d.se];++deg[i.se];
    if(deg[d.se]>1) decs.insert(mpr(dec(d.se),d.se));incs.insert(mpr(inc(d.se),d.se));
    if(deg[i.se]>1) decs.insert(mpr(dec(i.se),i.se));incs.insert(mpr(inc(i.se),i.se));
  }
  LL ans=0;
  rep(i,n) ans+=a[i]*deg[i]*deg[i];
  cout<<ans<<endl;

  termin();
}

G - Sum of Tree Distance

这题长的一脸启发式合并的样子。我们随便找一个点作为根开始dfs，并对每个节点维护一个set，其中的元素是一些三元组\(\{颜色，子树中这个颜色的节点个数，子树中所有这个颜色的节点的深度之和\}\)。其中"颜色"包括了这个子树中出现过的所有颜色。 在搜完当前节点所有子树后，我们来在搞出这个节点对应set的同时计算所有经过这个节点的路径产生的贡献。维护set则用启发式合并，也就是在儿子节点中选择最大的一个set作为"母set"，然后把其它儿子的set中的元素加入进去，加入完的set作为当前节点的set。这样总加入次数是\(O(nlog_2n)\)的。具体实现：令当前节点为pos，set最大的儿子为u，然后swap(s[pos],s[u])(set的swap是O(1)的)。这样空间复杂度也是\(O(nlog_2n)\)。具体的加入方式就是如果要加入的元素的颜色没有在母set中出现过，就直接插入且不需计算贡献；否则把这个元素和母set中对应颜色的元素合并，然后计算一下这俩元素所代表的对应颜色的节点们互相之间的路径总长，这个用记录的深度之和以及当前节点的深度可以算出来。

时间复杂度\(O(nlog_2n)\)。

点击查看代码 
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <LL,LL>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

LL n,a[200010],dep[200010],ans=0;
vector <LL> g[200010];
set <pair <LL,pii> > st[200010];//{color,{count,sum of depths}}

void dfs(LL pos,LL par,LL d)
{
  dep[pos]=d;
  rep(i,g[pos].size())
  {
    LL u=g[pos][i];
    if(u==par) continue;
    dfs(u,pos,d+1);
  }
}

void dfs2(LL pos,LL par)
{
  st[pos].insert(mpr(a[pos],mpr(1,dep[pos])));
  vector <LL> v={pos};
  rep(i,g[pos].size()) if(g[pos][i]!=par)
  {
    dfs2(g[pos][i],pos);
    v.pb(g[pos][i]);
  }
  sort(v.begin(),v.end(),[&](LL x,LL y){return st[x].size()>st[y].size();});
  swap(st[pos],st[v[0]]);
  rep(i,v.size()) if(v[i]!=pos)
  {
    LL u=v[i];
    for(auto it:st[u])
    {
      LL col=it.fi,cnt=it.se.fi,sum=it.se.se;
      auto it2=st[pos].lower_bound(mpr(col,mpr(0,0)));
      if(it2!=st[pos].end()&&it2->fi==col)
      {
        LL cnt2=it2->se.fi,sum2=it2->se.se;
        ans+=cnt*(sum2-dep[pos]*cnt2)+cnt2*(sum-dep[pos]*cnt);
        st[pos].erase(it2);
        st[pos].insert(mpr(col,mpr(cnt+cnt2,sum+sum2)));
      }
      else st[pos].insert(it);
    }
  }
}

int main()
{
  fileio();

  cin>>n;
  LL x,y;
  repn(i,n-1)
  {
    scanf("%lld%lld",&x,&y);
    g[x].pb(y);
    g[y].pb(x);
  }
  repn(i,n) scanf("%lld",&a[i]);
  dfs(1,0,0);
  dfs2(1,0);
  cout<<ans<<endl;

  termin();
}

标签：Summer,Contest,题解,LL,pos,fi,rep,se,define
From： https://www.cnblogs.com/legendstane/p/18262822/atcoder-beginner-contest-abc-359-solution

相关文章

  • abc359_G Sum of Tree Distance 题解
    题目链接：Atcoder或者洛谷先考虑暴力，显然是枚举整棵树的路径，这个枚举复杂度显示是\(O(n^2)\)，还不考虑计算\(f(i,j)\)，考虑使用点分治优化枚举复杂度：\(O(n\log{n})\)。接下来考虑如何计算每条路径的\(f(i,j)\)，注意到\(f(i,j)\)：当且仅当\(a[i]=a[j]\)时，答案加上\(dis(i,j......
  • AtCoder Beginner Contest 359 解题报告
    AtCoderBeginnerContest359吐槽：A-F还算正常，G题你tm给我放了个出过的板子（ABC340G）是几个意思啊？？？ASimulate.#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineendl'\n'#definePBemplace_back#definePPBpop_back#defineMPmake_pai......
  • P1971 [NOI2011] 兔兔与蛋蛋游戏 题解
    Description这些天，兔兔和蛋蛋喜欢上了一种新的棋类游戏。这个游戏是在一个\(n\)行\(m\)列的棋盘上进行的。游戏开始之前，棋盘上有一个格子是空的，其它的格子中都放置了一枚棋子，棋子或者是黑色，或者是白色。每一局游戏总是兔兔先操作，之后双方轮流操作，具体操作为：兔兔每次操作......
  • P10538 [APIO2024] 星际列车 题解
    题意：有\(n\)个行星，编号为\(0\simn-1\)。有\(m\)辆星际列车，第\(i\)辆列车在时刻\(a_i\)从行星\(x_i\)出发，在时刻\(b_i\)到达行星\(y_i\)，代价为\(c_i\)。换乘条件为上一辆车的终点和下一辆车的起点相同，且上一辆车到达时刻\(\le\)下一辆车出发时刻。你需要吃......
  • qoj8542 Add One 2 题解
    题目链接点击打开链接题目解法我们先考虑什么样的序列\(x_1,...,x_n\)是可以被得到的对于\(x_i>x_{i+1}\)的位置，我们需要至少对前缀\([1,i]\)做\(x_i-x_{i+1}\)次操作；对于\(x_{i-1}<x_{i}\)的位置，我们需要至少对后缀\([i,n]\)做\(x_i-x_{i-1}\)次操作我们需要......
  • [集训队互测 2023] 树哈希 题解报告
    [集训队互测2023]树哈希题解报告/bx/bx/bxzky！！！题意给定常数\(q\)，定义一棵以\(1\)为根的有根树\(T\)的\(s(T)\)为\(T\)中本质不同的子树数量，定义其权值为\(q^{s(T)}\)。给定\(n\)，对于\(i=1,\dots,n\)求所有大小为\(i\)的有标号有根树的权值之和对\(P\)......
  • CF1978E Computing Machine 题解
    好写程度：\(E>D>C\)。好想程度：\(C>D=E\)。总结：C是全场最难。我们考虑把两个操作对全体的\(a_i,b_i\)都做一遍，会发现我们只会做这两遍，不会再有嵌套的了，因为都做过一遍后\(\{a\}\)中0的数量只会减少，而且即使再做一遍也无法给\(\{b\}\)改成不一样的了，比较显然。下文中令......
  • [题解]AT_abc267_f [ABC267F] Exactly K Steps
    大家好，我是毒瘤，喜欢用玄学算法过题。发现题解区没有这个做法，于是来发一篇。思路不难发现如果一个点对\((u,v)\)的距离为\(d\)，那么在这棵树以\(u\)为根时，\(v\)的深度为\(d\)。于是考虑换根DP。首先思考如何计算答案。显然我们可以将查询离线下来，然后当换根到以\(u\)......
  • BD202301·公园题解
    BD202301·公园题解考虑将整个移动过程分为两个部分：小度和度度熊汇合之前小度和度度熊汇合之后第一部分可以直接用Dijkstra算法直接搞定，第二部分可以考虑反向思考，从N点出发做一次Dijkstra，最后枚举每个汇合点即可得到答案。时间复杂度\(\Theta(nlogn)\)代码如下：#include......
  • [题解]AT_abc264_e [ABC264E] Blackout 2
    思路一道很经典的题，运用了一种叫「时光倒流」的技巧。「时光倒流」本质上就是将所有删边（或删点）的操作，通过倒序循环求值的方式转化为加边（或加点）。「时光倒流」具体实现通常伴随着并查集出现，维护一个连通块的某种性质。首先，我们需要将所有从始至终没有删过的边加入并查集。在这......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99