比赛传送门:AtCoder Beginner Contest 243 - AtCoder
因为AB题比较简单,所以就不记录了。
C - Collision 2
题意请看原题。
思路
因为只有同一高度,方向相对的会且一定会碰撞,所以我们将每个高度设一个vector,然后将点分别存入对应的vector,再对同一层的所有点按照x的大小排序,如果先出现了然后遍历,如果先出现R,再出现L,那么一定会碰撞。
因为高度范围较大,我们可以将map和vector嵌套,当然你用数组来离散化也可以,我这是为了方便所以用map。
代码
/*Copyright (C) Eriktse 2022*/ #include <iostream> #include <cstdio> #include <stack> #include <queue> #include <cmath> #include <cstring> #include <string> #include <vector> #include <map> #include <algorithm> #include <bitset> #include <utility> #define fi first #define se second #define gc getchar #define pr printf #define sc scanf #define pb push_back #define int long long //用%lld输出long long类型数据 using namespace std; inline int readInt() { int s = 0,w = 1;char c = gc(); while(c < '0' || c > '9'){if(c == '-')w = -1;c = gc();} while('0' <= c && c <= '9'){s = s * 10 + c - '0',c = gc();} return s * w; } /*--------全局变量--------*/ const int maxn = 2e5 + 10; struct Node { int x, y, f; bool operator < (const Node &m)const { return x < m.x; } }; int N; Node a[maxn]; map<int, vector<Node> > mp; /*--------自定义函数-------*/ signed main() { N = readInt(); for(int i = 1;i <= N; ++ i)a[i].x = readInt(), a[i].y = readInt(); char s[maxn];cin >> s + 1; for(int i = 1; s[i] != '\0'; ++ i)a[i].f = (s[i] == 'L') ? 1 : 0; for(int i = 1;i <= N; ++ i)mp[a[i].y].pb(a[i]); for(auto v : mp) { sort(v.se.begin(), v.se.end()); bool l = 0, r = 0; for(auto i : v.se) { if(i.f == 0)r = 1; if(i.f == 1 && r == 1) { pr("Yes\n"); return 0; } } } pr("No\n"); return 0; }
D - Moves on Binary Tree
这题是一个高精度 + 栈优化的题目。
思路
因为数字很大,所以用高精度,我这里开500大小就够了,具体多大大家可以自己斟酌。
为什么需要栈优化?因为不用就会T。
不难发现,LU相当于没走,LRUU也相当于没走,也就是说每一个U可以和前一个L | R抵消掉,那么就可以利用栈的思想,将大部分的LRU抵消,那么移动次数就会少很多。
具体看代码。
代码
/*Copyright (C) Eriktse 2022*/ #include <iostream> #include <cstdio> #include <stack> #include <queue> #include <cmath> #include <cstring> #include <string> #include <vector> #include <map> #include <algorithm> #include <bitset> #include <utility> #define fi first #define se second #define gc getchar #define pr printf #define sc scanf #define pb push_back #define int long long //用%lld输出long long类型数据 using namespace std; inline int readInt() { int s = 0,w = 1;char c = gc(); while(c < '0' || c > '9'){if(c == '-')w = -1;c = gc();} while('0' <= c && c <= '9'){s = s * 10 + c - '0',c = gc();} return s * w; } /*--------全局变量--------*/ const int maxn = 1e6 + 10; int a[550]; char stk[maxn]; int top = 0; /*--------自定义函数-------*/ inline void add(int a[],int x) { a[1] += x; for(int i = 1;i <= 510; ++ i) { if(a[i] > 9) { a[i + 1] += a[i] / 10; a[i] %= 10; }else break; } } inline void multi(int a[],int x) { for(int i = 1;i <= 510; ++ i)a[i] *= x; for(int i = 1;i <= 510; ++ i) if(a[i] > 9) { a[i + 1] += a[i] / 10; a[i] %= 10; } } inline void divide(int a[],int x) { for(int i = 510; i >= 1; -- i) { a[i - 1] += 10 * (a[i] % x); a[i] /= x; } } inline void out(int a[]) { bool f = 0; for(int i = 510;i >= 1; -- i) { if(a[i])f = 1; if(f)pr("%lld",a[i]); } } signed main() { int N = readInt(), X = readInt(); for(int i = 1;i <= 510; ++ i) { a[i] = X % 10; X /= 10; } char s[maxn];cin >> s + 1; for(int i = 1;i <= N; ++ i) { if(s[i] == 'U' && (stk[top] == 'L' || stk[top] == 'R'))top --; else stk[++ top] = s[i]; } for(int i = 1;i <= top; ++ i) { char op = stk[i]; if(op == 'U')divide(a, 2); else if(op == 'L')multi(a, 2); else if(op == 'R') { multi(a, 2); add(a, 1); } } out(a); return 0; }
E - Edge Deletion
题目意思是说删掉x条边后,图依然是连通图,且任意两点之间的最短距离不变。
题目给的图是一个无自环,无重边的无向图。
思路
因为需要任意两点之间的距离,并且节点数较少,所以容易想到floyd算法。
floyd就是让 k 做中转点,不断遍历 i j 进行状态转移的算法。
最后进行一个判断,对于边 x y w,如果存在另外一个点 i ,使得x -> i -> y的距离小于 w ,说明x y w这条边被松弛了,可以删除。
代码
/*Copyright (C) Eriktse 2022*/ #include <iostream> #include <cstdio> #include <stack> #include <queue> #include <cmath> #include <cstring> #include <string> #include <vector> #include <map> #include <algorithm> #include <bitset> #include <utility> #define fi first #define se second #define gc getchar #define pr printf #define sc scanf #define pb push_back #define int long long //用%lld输出long long类型数据 using namespace std; inline int readInt() { int s = 0,w = 1;char c = gc(); while(c < '0' || c > '9'){if(c == '-')w = -1;c = gc();} while('0' <= c && c <= '9'){s = s * 10 + c - '0',c = gc();} return s * w; } /*--------全局变量--------*/ typedef pair<int, int> PII; const int maxn = 310, inf = 1e10; int N, M; struct Edge { int x, y, w; }; int d[maxn][maxn]; bool del[maxn][maxn]; /*--------自定义函数-------*/ inline void floyd() { for(int k = 1;k <= N; ++ k) for(int i = 1;i <= N; ++ i) for(int j = 1;j <= N; ++ j) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } signed main() { N = readInt(), M = readInt(); for(int i = 1;i <= N; ++ i) for(int j = 1;j <= N; ++ j) d[i][j] = inf; vector<Edge> v; for(int i = 1;i <= M; ++ i) { int x = readInt(), y = readInt(), w = readInt(); d[x][y] = d[y][x] = w; v.pb({x, y, w}); } floyd(); int ans = 0; for(auto i : v) { int x = i.x, y = i.y, w = i.w; for(int j = 1;j <= N; ++ j) if(d[x][j] + d[j][y] <= w) { ans ++; break; } } pr("%lld\n",ans); return 0; }
Comments NOTHING