比赛传送门：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