比赛链接：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;
}
对Floyd的思考
值得指出的是，弗洛伊德算法兼具动态规划、矩阵乘法的性质。一类经典问题是 “长度为 $K$ 的路径计数”（“走 $K$ 步的最短路计数”、“经过 $K$ 条边的最短路计数”），就可以使用弗洛伊德算法配合快速幂在 $O(n^3lgK)$ 内解决。