526互联

暑假专题训练 计算几何与字符串 2023-7-20

发布时间 2023-07-22 17:00:46作者: dkdklcx

未补完

B. Queue

概要：找出每一个人（坐标为i）从n到i + 1的第一个比他年纪小的人，坐标为j，他的不愉悦值为j - i - 1。注意有相同大小要靠右取，并且最年轻的人若与当前这个人年纪相同则答案为-1。

算法：二分。

做法：用tag数组来记录从n到1的最小年纪。对每一个人（坐标i），从i + 1到n二分查找出最接近这个人年龄且比这个人年龄要小且最靠近右边的人的坐标，求他们之间的人数即为答案。

code 
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <string>
#include <set>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };

const int N = 100010;

int n;
map<int, int> mp;
int w[N], ans[N], tag[N];

int sr(int x, int l, int r)
{
	while (l < r)
	{
		int mid = (l + r + 1) >> 1;
		if (tag[mid] < x)l = mid;
		else r = mid - 1;
	}
	return l;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++)cin >> w[i];

	for (int i = n; i >= 1; i--)
	{
		if (i + 1 <= n)
		{
			if (w[i] > tag[i + 1])
			{
				int p = sr(w[i], i + 1, n);
				ans[i] = p - i - 1;
				tag[i] = tag[i + 1];
			}
			else if (w[i] == tag[i + 1])ans[i] = -1, tag[i] = tag[i + 1];
			else ans[i] = -1, tag[i] = w[i];
		}
		else ans[i] = -1, tag[i] = w[i];
	}

	for (int i = 1; i <= n; i++)printf("%d ", ans[i]);

	return 0;
}

 

C. Repetitive Elements

概要：给定一个字符串，找出这个串中相同且最长的不重合的子串。

算法：二分。

做法：对于这个字符串我们二分的串的长度为[1, s.size() / 2]。这是因为大的两个符合题意的串必定包含小的两个符合题意的串。然后注意边界问题就可以了。

code 
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <string>
#include <set>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };

const int N = 100010;

int len, ans;
string s;

bool check(int ln)
{
	for (int i = 0; i <= (int)s.size() - 2 * ln; i++)
	{
		for (int j = i + ln; j <= s.size() - ln; j++)
		{
			if (s.substr(i, ln) == s.substr(j, ln))
			{
				if (ln > len)len = ln, ans = i;
				return true;
			}
		}
	}

	return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t;
	cin >> t;
	while (t--)
	{
		len = -1e9, ans = -1;
		cin >> s;

		int l = 1, r = (int)s.size() / 2;
		while (l < r)
		{
			int mid = (l + r + 1) >> 1;
			if (check(mid))l = mid;
			else r = mid - 1;
		}

		for (int i = ans; i < ans + len; i++)cout << s[i];
		cout << endl;
	}

	return 0;
}

 

E.Nearest vectors

概要：找出两个向量的夹角最小。

算法：排序、数学

做法：对于每一个坐标我们用atan2(x, y)算出其从弧度。对每一个向量的弧度按照从小到大来排序。依次遍历每一个向量，我们总是用下一个向量的弧度减去我们当前遍历的向量的弧度，即为两者最小夹角。最后特别处理一下最后一个向量和第一个向量的夹角，再排个序就可以得到最小夹角。

code 
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <string>
#include <set>
#define double long double
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<double, double> PDD;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };

const int N = 100010;
const double eps = 1e-200;

int n;
PDI tangle[N];
PII w[N];

struct Node
{
	int a, b;
    double du;
}node[N];

bool cmp1(PDI x, PDI y)
{
	return x.first < y.first;
}

bool cmp2(Node x, Node y)
{
	return x.du < y.du;
}

double get_tangle(double y, double x)
{
	return atan2(y, x);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> w[i].first >> w[i].second;
		tangle[i].first = get_tangle(w[i].second, w[i].first), tangle[i].second = i;
	}

	sort(tangle + 1, tangle + n + 1, cmp1);

	for (int i = 1; i <= n; i++)
	{ 
		if (i + 1 <= n)
		{
			node[i] = { tangle[i].second, tangle[i + 1].second,  tangle[i + 1].first - tangle[i].first};
		}
		else
		{
			node[i] = { tangle[i].second, tangle[1].second, 2 * acos(-1) - (tangle[i].first - tangle[1].first) };
		}
	}

	sort(node + 1, node + n + 1, cmp2);

	printf("%d %d", node[1].a, node[1].b);

	return 0;
}

 

F. Are You Safe?

做法：在给出的c个点中找出凸包，判断p个点是否在凸包中。注意排序的点一定要从最左边开始按逆时针构成一个环。

算法：Andrew、判断点是否在凸包中（用凸包的各条边的向量和各条边的起始点到判断点的向量的叉乘来判断）

code 
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <string>
#include <set>
#define fir first
#define sec second
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<double, double> PDD;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };

const int N = 200010;
double eps = 1e-8;

PDD get_vec(PDD a, PDD b)
{
	return { b.fir - a.fir, b.sec - a.sec };
}

double cross(PDD a, PDD b)
{
	return a.fir * b.sec - a.sec * b.fir;
}

bool check(PDD a, PDD b, PDD c)
{
	PDD ab = get_vec(a, b), bc = get_vec(b, c);
	double res = cross(ab, bc);
	if (fabs(res) < eps || res > 0)return true;
	else return false;
}

vector<PDD> andrew(vector<PDD>& sens)
{
	sort(sens.begin(), sens.end());

	vector<PDD> ans;
	vector<int> I{ 0 }, st(sens.size());
	for (int i = 1; i < sens.size(); i++)
	{
		while (I.size() > 1 && check(sens[I[(int)I.size() - 2]], sens[(int)I.back()], sens[i]))
			st[(int)I.back()] = 0, I.pop_back();
		st[i] = 1, I.push_back(i);
	}

	for (int i = sens.size() - 2; i >= 0; i--)
	{
		if (st[i])continue;
		while (I.size() > 1 && check(sens[I[(int)I.size() - 2]], sens[(int)I.back()], sens[i]))
			st[(int)I.back()] = 0, I.pop_back();
		st[i] = 1, I.push_back(i);
	}


	for (int i = 0; i < I.size() - 1; i++)ans.push_back(sens[I[i]]);
	return ans;
}

void solve(int ca)
{
	int c, p;
	vector<PDD> sensors;
	vector<PDD> points;
	cin >> c >> p;
	for (int i = 0; i < c; i++)
	{
		PDD t;
		cin >> t.fir >> t.sec;
		sensors.push_back(t);
	}

	cout << "Case " << ca << endl;
	auto plg = andrew(sensors);
	reverse(plg.begin() + 1, plg.end());
	for (int i = 0; i < plg.size(); i++)cout << plg[i].fir << ' ' << plg[i].sec << endl;
	cout << plg[0].fir << ' ' << plg[0].sec << endl;
	
	for (int i = 0; i < p; i++)
	{
		PDD t;
		cin >> t.fir >> t.sec;
		bool flag = true;
		for (int j = 0; j < plg.size(); j++)
		{
			PDD ab, ac;
			if (j < plg.size() - 1)ab = get_vec(plg[j], plg[j + 1]), ac = get_vec(plg[j], t);
			else ab = get_vec(plg[j], plg[0]), ac = get_vec(plg[j], t);
			double res = cross(ab, ac);
			if (fabs(res) < eps || res > 0)continue;
			else
			{
				flag = false;
				break;
			}
		}
		if (flag)cout << t.fir << ' ' << t.sec << ' ' << "is unsafe!" << endl;
		else cout << t.fir << ' ' << t.sec << ' ' << "is safe!" << endl;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t, ca = 0;
	cin >> t;
	while (t--)
	{
		solve(++ca);
		cout << endl;
	}

	return 0;
}