首页 > 其他分享 >Hitachi Vantara Programming Contest 2024(AtCoder Beginner Contest 368)题解A~D

Hitachi Vantara Programming Contest 2024(AtCoder Beginner Contest 368)题解A~D

时间:2024-08-25 22:04:30浏览次数:9  
标签:AtCoder 题意 Contest int 题解 ++ ret read 节点

A - Cut

  • 题意:
    将数组的后k个字符移到前面
  • 思路:
    1. 可以用rotate()函数让数组中的元素滚动旋转
      rotate(v.begin(), v.begin() + n - k, v.end());
      
    2. 直接输出后k个元素,再输出前n-k个元素
      for(int i=n-k;i<n;i++) write(v[i]);
      for(int i=0;i<n-k;i++) write(v[i]);
      

B - Decrease 2 max elements

  • 题意:
    每次令数组中最大的两个数-1,求多少次操作后只剩下一个数
  • 思路:
    注意到 2≤N≤1001<=A[i]<=100
    两眼一闭就是写,直接就上priority_queue,不带半点智慧和思考,题干怎么说就怎么写,怎么简单怎么来
    void solve()
    {
      priority_queue<int> q;
      int n = read();
      for(int i=0;i<n;i++) q.push(read());
    
      int cnt = 0;
      while(q.size()>1){
          int t1 = q.top();
          q.pop();
          int t2 = 1;
          if(q.size()) t2 = q.top();
          q.pop();
          if(t1 - 1) q.push(t1-1);
          if(t2 - 1) q.push(t2-1);
          cnt++;
      }
      cout<<cnt<<endl;
    }
    
    
    
    

C - Triple Attack

  • 题意:
    从前往后遍历数组A, 每次操作 T+=1, T%3!=0 的时候 A[i]-=1, T%3==0 的时候 A[i]-=3;
  • 思路:
    每轮 T += 3, A[i] -= 5 , 所以当 T%3==0 的时候直接将 A[i] 减到5以下,再逐次操作
    code:
      int n = read();
      vector<int> v;
      for(int i = 0; i < n; i++) v.push_back(read());
    
      int t = 1;
      for(int i=0; i < n; i++){
          while(v[i]>0){
              if(t%3==0 && v[i]>0) v[i]-=3,t++;
              else if(t%3!=0 && v[i]>0) v[i]-=1,t++;
              if(t%3==0 && t>=3 && v[i]>=5) t+=v[i]/5*3,v[i]%=5;
          }
      }
    
      cout<<t-1<<endl;
    

D - Minimum Steiner Tree

  • 题意:
    给一个树,再给一些关键节点,求如果要保留这些关键节点则至少应该保留哪些节点
  • 思路:
    显然给出的关键节点必须保留,考虑到是树可以用dfs,而因为关键节点必须保留所以可以任意选一个关键节点当作根
    从根往深处搜索,如果该节点为关键节点则该节点必然需要保留,标记此节点;
    如果该节点往下的任一 一节点为关键节点,该节点同样不可或缺,标记节点;
    可以根据dfs的返回值知道该节点往下的分支是否包含关键节点。
    int n, k;
    vector<vector<int>> e;
    unordered_map<int,int> mp,st,vis;
    int dfs(int x){
        int ret = 0;
        vis[x] = 1;  //记忆化搜索,搜过的就不再搜了
        for(auto it:e[x]){
            if(!vis[it]){
                ret |= dfs(it); //按位与,如果返回值有1则ret为1
            }
        }
        if(mp[x]) ret = 1;
        if(ret) st[x] = 1;
        return ret;
    }
    void solve()
    {
        n = read(), k = read();
        e.resize(n+1);
        for(int i=1;i<n;i++){
            int u = read(), v = read();
            e[u].push_back(v);
            e[v].push_back(u);
        }
        int ed = 0;
        for(int i=0;i<k;i++){
            ed = read();
            mp[ed] = 1; //记录该节点为关键节点
        }
    
        dfs(ed);
        int ans = 0;
        for(auto it:st){
            if(it.se) ans++;
        }
        cout<<ans<<endl;
    }
    

标签:AtCoder,题意,Contest,int,题解,++,ret,read,节点
From: https://www.cnblogs.com/klri/p/18379611

相关文章

  • 题解:AT_joisc2017_f 鉄道旅行 (Railway Trip)
    题意鉄道旅行(RailwayTrip)分析非常神仙的倍增做法。我们设\(l_{i,j}\)表示从\(i\)点出发,停靠\(2^j\)站后能抵达的最左位置。同理设\(r_{i,j}\)表示从\(i\)点出发,停靠\(2^j\)站后能抵达的最右位置。考虑如何更新这两个状态。因为可以走回头路,所以简单的\(l......
  • 题解:SP3109 STRLCP - Longest Common Prefix
    三倍经验:UVA11996JewelMagicP4036[JSOI2008]火星人题意维护一个字符串\(S\),支持以下操作:\(Q\i\j\):输出\(\operatorname{LCP}(S[i\dotsl],S[j\dotsl])\)\(R\i\char\):用\(char\)替换\(S\)的第\(i\)个字符\(I\i\char\):在\(S\)的第\(i\)......
  • 题解:CF590E Birthday
    题目分析题意给定\(n\)个字符串,要求从中选出若干个组成一个集合,且集合中每个字符串都互不包含。求集合最大包含几个字符串。分析本题弱化版:[ABC354G]SelectStrings就是求一个最长反链,并求构造方案。求构造方案还是比较有意思的。建议先做P4298[CTSC2008]祭祀。一......
  • 题解:P5217 贫穷
    题意维护一个字符串,支持以下操作:\(\texttt{Ixc}\),在第\(x\)个字母后面插入一个\(c\)。\(\texttt{Dx}\),删除第\(x\)个字母。\(\texttt{Rxy}\),反转当前文本中的区间\([x,y]\)。\(\texttt{Px}\),输出初始文本中第\(x\)个字母在当前文本中的位置。特别地,若不存在,......
  • 题解:UVA11996 Jewel Magic
    题意给你一个01串,要求完成以下操作:单点插入。单点删除。区间翻转。查询两点开始的LCP。分析先看查询操作,如何得到LCP的长度?我们可以考虑二分长度\(l\),然后用哈希检验区间\([p1,p1+l-1]\)是否等于区间\([p2,p2+l-1]\)。平衡树维护哈希即可。发现......
  • 题解:AT_abc354_g [ABC354G] Select Strings
    题目分析题意给定\(n\)个字符串,要求从中选出若干个组成一个集合,且集合中每个字符串都互不包含。求集合中字符串的权值的和的最大值。分析首先很容易想到用KMP判两个串是否存在包含关系。考虑建图,将不能同时存在于一个集合中的串的节点相连。然后发现只需求出这个图的最......
  • 题解:P7952 [✗✓OI R1] 天动万象
    提供一种和第一篇题解不同的理解思路。题目分析看到操作\(1\):拿dfs序水水就行了。看到操作\(2\):???特殊情况我们考虑一下特殊情况下操作\(2\)怎么处理。假如这棵树是一条链。设从根到叶节点权值如下:(随便赋的)节点编号123456权值123456如果我们......
  • 题解:CF1995C Squaring
    题意给定序列\(a\),每次操作可以使\(a_i\getsa_i^2\),求使\(a\)不降的最少操作次数。分析因为\(1^k=1\),所以无解的情况只有\(\exist\a_i=1\)且\(\exist\j\in[1,i),a_j>1\)。在有解的情况下,假设对\(a_{i-1}\)操作\({k_{i-1}}\)次,对\(a_i\)操作\({k_i}\)次。......
  • 题解:UVA1479 Graph and Queries
    分析先看删边操作。由于并不保证是森林,所以我们没有好的方法来在线维护删边相关的操作。所以,我们可以套路地把询问离线,然后倒着操作。删边变成加边。需要注意的是权值的修改,记录时要把当前权值和修改的权值反过来。然后我们发现这个操作很经典,维护方式和[HNOI2012]永无乡......
  • 题解:P7475 「C.E.L.U-02」简易输入法
    题意给定词典\(\text{U}\),每次询问读入一个字符串\(s\),以及一个整数\(x\)对于这个字符串有以下几种情形:设\(s_i\in\text{U}\)且\(s\)为\(s_i\)的前缀的个数为\(a\)。当\(a\gex\)时,请输出按照以输出次数从大到小为第一关键字,以字典序为第二关键字排序后的第\(x......