AtCoder Beginner Contest 243(C – E)

发布于 2022-03-13  1300 次阅读


比赛传送门: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;
}