当前位置： 首页 > article >正文

AtCoder Beginner Contest 391（ABCDE）

article 2025/2/2 19:37:29

A - Lucky Direction

翻译：

        给你一个字符串 D，代表八个方向（北、东、西、南、东北、西北、东南、西南）之一。方向与其代表字符串之间的对应关系如下。

  • 北：   N
  • 东：   E
  • 西：  W
  • 南：  S
  • 东北方 ：NE
  • 西北： NW 
  • 东南： SE 
  • 西南： SW

        打印与 D 表示的方向相反的字符串。

思路：

使用map对应即可

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // 不使用科学计数法
    // cout<<fixed;
    // 中间填保留几位小数，不填默认
    // cout.precision();
    map<string,string> mp;
    mp["N"] = "S";
    mp["S"] = "N";
    mp["E"] = "W";
    mp["W"] = "E";
    mp["NE"] = "SW";
    mp["SW"] = "NE";
    mp["NW"] = "SE";
    mp["SE"] = "NW";
    string s;
    cin>>s;
    cout<<mp[s]<<endl;
}

B - Seek Grid

 翻译：

        给你一个 N×N 网格 S 和一个 M×M 网格 T。从上往下第 i 行和从左往右第 j 列的单元格用 (i,j) 表示。

        S 和 T 中单元格的颜色用 N^{2}个字符 S_{i,j}(1≤i,j≤N）表示和 M^{2}个字符 T_{i,j}（1≤i,j≤M）来表示。在网格 S 中，如果 S_{i,j} 为 '. '，则单元格 (i,j) 为白色；如果 S_{i,j} 为 '#'，则单元格 (i,j) 为黑色。网格 T也相同

        找到S内的T。更准确地说，输出满足以下条件的整数 a 和 b（1≤a,b≤N-M+1）：

  • S_{a+i-1,b+j-1}=T_{i,j}对于i,j来说 i,j (1≤i,j≤M).

思路：

以S中（a，b）为右上角遍历M*M的网格，判断是否相同。

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

void solve(){
  int n,m;
  cin>>n>>m;
  vector<string> S(n),T(m);
  for (int i=0;i<n;i++){
    cin>>S[i];
  }
  for (int i=0;i<m;i++){
    cin>>T[i];
  }
  for (int a=0;a<=n-m;a++){
    for (int b=0;b<=n-m;b++){
      // judge same
      int f = 1;
      for (int i=0;i<m;i++){
        if (!f) break;
        for (int j=0;j<m;j++){
          if (T[i][j]!=S[a+i][b+j]){
            f = 0;
            break;
          }
        }
      }
      if (f){
        cout<<a+1<<" "<<b+1<<endl;
        return;
      }
    }
  }
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // 不使用科学计数法
    // cout<<fixed;
    // 中间填保留几位小数，不填默认
    // cout.precision();
    solve();
}

C - Pigeonhole Query

 翻译：

        有N 只鸽子，编号从1 到N，还有N 个巢，编号从1 到N。最初，鸽子i 在巢i 中，其中
1≤i≤N。

        你将收到Q 个查询，需要按顺序处理。查询有两种类型，每种查询的格式如下：

  • 1 P H：将鸽子P 移动到巢H。
  • 2：输出包含多于一只鸽子的巢的数量。

思路：

        用两个数组（nests，pigeon）分别记录，nests[i]记录巢i中有几只鸽子，pigeon[i]记录鸽子i在哪个巢穴中。

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;


int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // 不使用科学计数法
    // cout<<fixed;
    // 中间填保留几位小数，不填默认
    // cout.precision();
    int n,q,f,p,h,res = 0;
    cin>>n>>q;
    vector<int> nests(n+1,1),pigeon(n+1);
    for (int i=0;i<=n;i++) pigeon[i] = i;
    while (q--){
      cin>>f;
      if (f==1){
        cin>>p>>h;
        // move p
        if (nests[pigeon[p]]-- ==2){
          res -= 1;
        }
        pigeon[p] = h;
        if (nests[pigeon[p]]++ == 1){
          res += 1;
        }
      }else if (f==2){
        cout<<res<<endl;
      }
    }
}

 D - Gravity

翻译：

        有一个 10^{9} 行 W 列的网格。左起第 x 列和下起第 y 行的单元格用 (x,y) 表示。

        共有 N 个图块。每个区块是 1×1 的正方形，第 i 个区块（1≤i≤N）在 0 时刻位于单元格(X_{i},Y_{i})。

        在 t=1,2,...,10^{100} 时，区块按照以下规则移动：

  • 如果整个底行都布满了图块，则移除底行的所有图块。
  • 对于剩余的每个区块，按照从下到上的顺序，执行以下操作：
    • 如果该图块位于最下面一行，或者它下面的单元格中有一个图块，则不做任何操作。
    • 否则，将该图块向下移动一格。

给您 Q 个查询。对于第 j 个查询 (1≤j≤Q)，请回答区块 A j 在时间 T_{j}+0.5.
 

思路： 

        预处理答案。

        哪些块一定会消失？会构成底行都为图块的块。那么先就求会消掉的层数，即每列的最少块数。

        那么最后会处于同一行的什么时候消失呢？这个由最终同行的最高点决定。

        不消失的块则一直存在。

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

void solve(){
  ll n,w;
  cin>>n>>w;    
  // block_down_time[i]：第i块在哪个时间点消失
  vector<ll> block_down_time(n+1,-1);
  // down_block[i]：第i列中包含的块（块所处高度，第几块）
  vector<vector<pair<ll,ll>>> down_block(w+1);
  for (ll x,y,i=1;i<=n;i++){
    cin>>x>>y;
    down_block[x].emplace_back(y,i);
  }
  // 有几行可被移除
  ll can_removes = INT_MAX;
  for (ll i=1;i<=w;i++){
    sort(down_block[i].begin(),down_block[i].end());
    can_removes = min(can_removes,(ll)down_block[i].size());
  }

  // 遍历消失的行，得到最终相同行的消失时间
  for (ll i=1;i<=can_removes;i++){
    ll need_time = 0;
    for (ll j=1;j<=w;j++){
      need_time = max(need_time,down_block[j][i-1].first);
    }
    for (ll j=1;j<=w;j++){
      block_down_time[down_block[j][i-1].second] = need_time;
    }
  }

  // query
  ll q,t,a;cin>>q;
  while (q--){
    cin>>t>>a;
    // 不会消失 或 还没到消失的点
    if (block_down_time[a]==-1 || block_down_time[a]>t){
      cout<<"Yes"<<endl;
    }else{
      cout<<"No"<<endl;
    }
  }
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // 不使用科学计数法
    // cout<<fixed;
    // 中间填保留几位小数，不填默认
    // cout.precision();
    solve();
}

E - Hierarchical Majority Vote

翻译：

        对于长为3^{n}的二进制字符串B=B_{1}B_{2}...B_{3^{n}}我们定义一个如下操作得到一个长为3^{n-1}的二进制字符串C=C_{1}C_{2}...C_{3^{n-1}}：

  •         将B的元素分为三组并得到每个组中的主要值。也就是对于i=1,2,...,3^{n-1},让C_{i}为B_{3i-2},B_{3i-1},B_{3i}中出现最频繁的值。

        你被给予 对于长为3^{N}的二进制字符串A=A_{1}A_{2}...A_{3^{N}}。. 设 A ′ =A_{1}′ 是对 A 进行 N 次上述操作后得到的长度为 1 的字符串。

        确定A中最少要改变多少元素使得A_{1}^{'}的值改变。

思路：

      以010011101为例

        010 011 101        第2层

            0   1    1        第1层

                1            第0层

       定义dfs( i, j )为第i层的第j块改变为A_{1}^{'}反转值（下面都叫最终值），所要用的元素数量。

       如果当前 j 块下的3个块中有2个k1, k2与最终值不同，则min( dfs(i+1 , k1), dfs( i+1, k2))

       如果当前 j 块下的3个块中有3个k1, k2,k3与最终值不同,则

        min( dfs(i+1 , k1)+dfs( i+1, k2), dfs(i+1 , k2)+dfs( i+1, k3), dfs(i+1 , k3)+dfs( i+1, k1))

        终止条件为i>=n返回1表示当前块要改。

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

void solve(){
  int n;
  string s;
  cin>>n;
  cin>>s;
  //colors[i][j]：第i层的第j块的颜色
  vector<vector<int>> colors(n+1);

  // 得到每层每块改变前的颜色
  for (char c:s) colors[n].push_back(c-'0');
  for (int i=n-1;i>=0;i--){
    for (int j=0;j<pow(3,i);j++){
      int cnt1 = 0,cnt0 = 0;
      for (int z=3*j;z<3*j+3;z++){
        if (colors[i+1][z]==1) cnt1++;
        else cnt0++;
      }
      colors[i].push_back(cnt1>cnt0 ? 1 : 0);
    }
  }

  // need：最终值
  int need = colors[0][0]^1;
  // memo[i][j]：第i层第j块中最少要改变的块数
  vector<vector<int>> memo(n+1);
  // 初始化memo
  for (int i=0;i<=n;i++) memo[i].resize(pow(3,i),-1);

  auto dfs = [&](auto&& dfs,int i,int j)->int{
    if (i>=n) return 1;

    int& res = memo[i][j];
    if (res!=-1) return res;
    res = INT_MAX;
    
    // cnt_need：有几个与最终值不同的
    int cnt_need = 0,base = 3*j;
    for (int k=base;k<base+3;k++){
      if (colors[i+1][k]!=need) cnt_need++;
    } 
    if (cnt_need==2){
      for (int k=base;k<base+3;k++){
        if (colors[i+1][k]!=need) res = min(res,dfs(dfs,i+1,k));
      }
    }else if (cnt_need==3){
      for (int k1=base;k1<base+3;k1++){
        for (int k2 = k1+1;k2<base+3;k2++){
          if (colors[i+1][k1]!=need && colors[i+1][k2]!=need){
            res = min(res,dfs(dfs,i+1,k1)+dfs(dfs,i+1,k2));
          }
        }
      }
    }
    return res;
  };
  cout<<dfs(dfs,0,0)<<endl;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // 不使用科学计数法
    // cout<<fixed;
    // 中间填保留几位小数，不填默认
    // cout.precision();
    solve();
}

有建议可以评论，我会积极改进qwq。

codeforces比赛时间十点左右的场基本不会当天写了，atcoder有的话基本会写。


http://www.kler.cn/a/528842.html

相关文章：

  • pytorch生成对抗网络
  • Two Divisors （ Educational Codeforces Round 89 (Rated for Div. 2) ）
  • ASP.NET Core 中间件
  • unity学习24：场景scene相关生成，加载，卸载，加载进度，异步加载场景等
  • C# 环境：深入探讨与优化
  • DeepSeek-R1论文研读：通过强化学习激励LLM中的推理能力
  • Alibaba开发规范_编程规约之命名风格
  • 22.Word：小张-经费联审核结算单❗【16】
  • C_C++输入输出（下）
  • gesp(C++六级)（9）洛谷：P10721：[GESP202406 六级] 计算得分
  • UE学习日志#18 C++笔记#4 基础复习4 指派初始化器和指针
  • 手写防抖函数、手写节流函数
  • 【Rust自学】18.1. 能用到模式（匹配）的地方
  • Python在线编辑器
  • Python 环境隔离和实现方法
  • 【LeetCode 刷题】二叉树-公共祖先
  • TensorFlow简单的线性回归任务
  • OpenAI推出o3-mini推理模型，首次免费开放，性能超越o1，AIME测试准确率高达87.3%
  • 牛客题目分享：JZ64 求1+2+3+...+n（用static成员和构造函数的方法）（C++）
  • 记6（人工神经网络
  • 数据结构：优先级队列—堆
  • C++ strcpy和strcat讲解
  • NeetCode刷题第19天(2025.1.31)
  • 二、CSS笔记
  • 掌握API和控制点(从Java到JNI接口)_35 JNI开发与NDK 03
  • Hot100之子串