AtCoder Beginner Contest 243比赛总结

比赛链接：AtCoder Beginner Contest 243 - AtCoder

写在前面

又是一直鸽了总结，好久没写，以后争取当天打完就写，最近是被这疫情搞心态了。
这回ABCD还是挺简单的，D题我甚至是用py去玩了玩，但是果不其然T了，E有点操作，后面慢慢想确实是这么回事

A - Shampoo（签到）

题意

给定一个数 $V$，将按照 $-A,-B,-C,-A,-B,-C...$ 的方式递减。问哪一个数先不够减？

思路

可以取模看余数，也可以循环去减
其实就是对(A+B+C)进行取模，然后判断剩下的去跟A,A+B,比较，不要像我傻乎乎的去一个个减就好

代码

V, A, B, C = map(int, input().split())
V %= A + B + C
print('F' if V < A else 'M' if V < A + B else 'T')

B - Hit and Blow（签到）

题意

给出两个数列，问有多少个对位相等，有多少个对位不相等.

思路

for一遍就好，我用的是map存

代码

简单不表，嘻嘻

C - Collision 2（模拟/STL）

题意

一个二维的坐标系，有若干点还有L或R的方向，问你是否会有相对的点？

思路

这个题有个坑就是，你不能简单的看y相同的时候是不是有相反的，比如LR，虽然方向相反，但是他们是<--和-->，所以不可以，可以用vector存，对于每一个y就按照x大小sort一遍，然后就按照思维去扫一遍即可

代码

https://paste.org.cn/636GQIImQm

D - Moves on Binary Tree（模拟/字符串+bitset）

题意

给你一个完全二叉树，一开始在结点$x$，然后有$n$次操作，包括ULR分别代表往上（父亲结点）、往左（左儿子）、往右（右儿子），其中能超过1e18但是最后的结果是在1e18以内，所以模拟是不太可能的。

思路

这个题我一开始用的python...我低估了python的用时...

其实也是模拟，不过大于1e18的时候你会发现会爆，那么怎么办？其实很简单，只需要记录乘2的次数，比如我现在已经8e17了，再来一次L或R就超过1e18了（虽然还不会爆，但是不止乘一次2），那我就用cnt来记录有多少次乘二。

那我乘二还是乘二加一呢？这个题目保证了最后答案在1e18里面，所以不用管“零头”

想到用bitset去模拟，但是题目数据实在是太大了——$2^{10^{100}}$，就算是bitset模拟的话也得要$10^{100}$位，先不说t不t...这开这么大也是个问题把

这里有个派大星的字符串+bitset代码，十分巧妙！

代码

1）我的代码
代码：https://paste.org.cn/dnL1SxHXuk
2）派大星的代码

#include <bits/stdc++.h>
using i64 = int64_t; // <+>
int main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);
  int N;
  i64 X;
  std::string S;
  std::cin >> N >> X >> S;
  std::string ans(std::bitset<64>(X).to_string());//这样操作可以转换成二进制字符串
  for (char ch : S) {
    if (ch == 'U') {
      ans.pop_back();//除以二相当于右移一位，相当于右边那位不管是0还是1都没有了，直接pop_back()
    } else {
      ans.push_back("01"[ch == 'R']);//这个表述方法就是对于字符串s="01",s[0]='0',s[1]='1'，如果后面表达式[ch=='R']是正确的，那么就是s[1],错误的就是s[0]
    }
  }
  std::cout << std::bitset<128>(ans).to_ullong() << '\n';//最后转化成ull——unsigned long long
  return 0 ^ 0;
}
//作者：Patricky

E - Edge Deletion（Floyd）

题意

给出n个点,m条边，问你有多少条满足条件的边可以删去，最后还是保证是连通图。
条件是：删除这条边之后，对于每两个点的之间的最短距离没有改变

思路

这个题挺妙的hhh
结论就是我们先跑floyd，然后有如下判断:
1）思考一：
对于一个i,j，如果不存在k满足dis[i][j]=dis[i][k]+dis[k][j]，这样的一条边是不需要保留的，因为我们能从i走到k再走到j，可以删掉
2）思考二：
因为边权全部为正整数,那么如果一条边的两个顶点的最短路不经过这条边，那么这条边就可以删去.

代码

1）思考一
https://paste.org.cn/fqc415dK73
2）思考二

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n ,m ;
    cin>>n>>m;
    vector<vector<ll>>dis(n,vector<ll>(n,1e18));
    vector<tuple<int,int,int>>v;
    for(int i = 0; i < m ;i ++){
        int a , b , c;
        cin>>a>>b>>c;
        a--;b--;
        dis[a][b] = dis[b][a] = c;
        v.emplace_back(make_tuple(a,b,c));
    }
    for(int k = 0 ;k < n;k++){
        for(int i = 0; i < n ; i++){
            for(int j = 0; j < n ; j ++){
                dis[i][j] = min(dis[i][j] , dis[i][k] + dis[k][j]);
            }
        }
    }
    int ans = 0;
    for(auto [a,b,c] : v){//对于一开始的边{a,b,c}
        for(int i = 0 ;i < n ; i++){//枚举中间点
            if(dis[a][i] + dis[i][b] <= c){//如果有其他边比c还小，那么这个这条{a,b,c}是可以删的
                ans++;
                break;
            }
        }
    }
    cout<<ans<<'\n';

    return 0;
}