D.Satyam and Counting

在\(0\leq x\leq2e5, 0\leq y\leq 1\)中给定n个点，计算最多能有多少个直角三角形

一开始的想法：

  1. 分直角点在 y = 0 和 y = 1 进行讨论
  2. 直角三角形又分横平竖直的直角三角形和斜着的直角三角形，因为高度一定，所以可以计算出来斜着的直角三角形的直角顶点一定在另两个顶点的中间且横坐标相差1
  3. 构造两个数组分别存放y = 0和y = 1的横坐标，然后遍历两次，看某一个横坐标是否在另一行也有对应的横坐标，如果有，那么这一行的x的个数减1就是以该点为顶点的横平竖直的直角三角形；再利用横坐标判断斜直角三角形即可
  4. 在寻找另一行是否有对应横坐标的过程中，使用的方法是双指针，最终会TLE

TLE代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		vector<int> q0, q1;
		int n;	cin >> n;
		long long ans = 0;
		while (n--)
		{
			int x, y;	cin >> x >> y;
			if (y == 0) q0.push_back(x);
			else q1.push_back(x);
		}
		if (!q1.size() || !q0.size())
		{
			cout << 0 << '\n';
			continue;
		}
		sort(q0.begin(), q0.end());
		sort(q1.begin(), q1.end());
		for (int i = 0, j = 0; i < q0.size(); i++)//遍历y = 0
		{
			while (j < q1.size() - 1 && q0[i] > q1[j]) j++;
			if (q0[i] == q1[j]) ans += q0.size() - 1;
			if (find(q1.begin(), q1.end(), q0[i] - 1) != q1.end() && find(q1.begin(), q1.end(), q0[i] + 1) != q1.end())
				ans++;
		}
		for (int i = 0, j = 0; i < q1.size(); i++)//遍历y = 1
		{
			while (j < q0.size() - 1 && q1[i] > q0[j]) j++;
			if (q1[i] == q0[j]) ans += q1.size() - 1;
			if (find(q0.begin(), q0.end(), q1[i] - 1) != q0.end() && find(q0.begin(), q0.end(), q1[i] + 1) != q0.end())
				ans++;
		}
		cout << ans << '\n';
	}
	return 0;
}

优化后：

  1. 使用map来记录坐标对，直接利用count函数来判断是否存在该横坐标
  2. 利用y ^ 1来表示另一行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
void solve()
{
	int cnt[2] = {};
	map<PII, int> e;
	int n;
	cin >> n;
	while (n--)
	{
		int x, y;
		cin >> x >> y;
		cnt[y]++;
		e[{x, y}] = 1;
	}
	long long ans = 0;
	for (auto t : e)
	{
		PII x = t.first;
		if (e.count({ x.first, x.second ^ 1 })) ans += cnt[x.second] - 1;
		if (e.count({ x.first - 1, x.second ^ 1 }) && e.count({ x.first + 1, x.second ^ 1 })) ans += 1;
	}
	cout << ans << '\n';
}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

E.Klee's SUPER DUPER LARGE Array!!!

连续的n个数，从第i个数分开，前i个数的和减去剩下数的和的绝对值最小，求该值

利用二分，最后得到的l和r都可能是答案，计算出来进行比较即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
void solve()
{
	int n, k;
	cin >> n >> k;
	int tot = (k + n + k - 1) * n / 2;
	int l = k, r = k + n - 1, mid;
	while (l + 1 != r)
	{
		mid = l + r >> 1;
		int tot1 = (k + mid) * (mid - k + 1) / 2;
		if (tot1 < tot - tot1) l = mid;
		else r = mid;
	}
	int ltot = (k + l) * (l - k + 1) / 2;
	int ans = abs(tot - ltot - ltot);
	if (r < n + k - 1) ans = min(ans, abs(tot - ltot - r - ltot - r));
	cout << ans << '\n';
}
signed main()
{
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

F.Firefly's Queries

给定一个序列，轮换让每个数当“队头”，并列成一个新的长序列，给定l和r，计算l到r的所有数的和

分别计算\(1\sim l-1,1\sim r\)的和，然后相减即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int a[N];
void solve()
{
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i - 1];
	while (q--)
	{
		int lt = 0, rt = 0;
		int l, r;
		cin >> l >> r;
		//计算1 ~l-1
		l = l - 1;
		lt += l / n * a[n];
		if (l % n)
		{
			int le = (l / n + l % n) % n == 0 ? n : (l / n + l % n) % n;//映射到1-n
			int ls = 1;
			if (l / n) ls = ((l / n * n + 1) / n + (l / n * n + 1) % n) % n == 0 ? n : ((l / n * n + 1) / n + (l / n * n + 1) % n) % n;
			if (le >= ls) lt += a[le] - a[ls - 1];
			else lt += a[n] - a[ls - 1] + a[le];
		}
		//计算1 ~ r
		rt += r / n * a[n];
		if (r % n)
		{
			int re = (r / n + r % n) % n == 0 ? n : (r / n + r % n) % n;
			int rs = 1;
			if(r / n) rs = ((r / n * n + 1) / n + (r / n * n + 1) % n) % n == 0 ? n : ((r / n * n + 1) / n + (r / n * n + 1) % n) % n;
			if (re >= rs) rt += a[re] - a[rs - 1];
			else rt += a[n] - a[rs - 1] + a[re];
		}
		cout << rt - lt << '\n';
	}
}
signed main()
{
	int t;	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

G.Yunli's Subarray Queries

计算最长连续上升子序列的长度

  1. 因为是“连续”上升，所以可以用w[i]-i，然后计算相同的数的个数的最大值
  2. 因为序列的长度是固定的，所以可以利用滑动窗口
  3. 那么就需要一个数据结构来记录每个数出现的次数，一个数据结构用来记录最大的出现次数
  4. 因为数有可能是负值，所以不能用数组，可以用map；记录次数可以用multiset（自行升序排列，可有重复数字）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int w[N], ans[N];
void solve()
{
	int n, k, q;
	cin >> n >> k >> q;
	for (int i = 1; i <= n; i++) cin >> w[i], w[i] -= i;
	map<int, int> m;//存储一个数到它个数的映射
	multiset<int> s;//用来存储各个数的数量，使用multiset可以直接排好序
	for (int i = 1; i < k; i++)
	{
		if (m.find(w[i]) != m.end())//如果m中存在，就先把旧的数量删除，再存储进新的数量
			s.erase(s.find(m[w[i]]));//删除pos
		m[w[i]]++;
		s.insert(m[w[i]]);//存储进新的数量
	}
	for (int l = 1, r = k; l <= n; l++, r++)
	{
		if (r <= n)
		{
			if (m.find(w[r]) != m.end())
				s.erase(s.find(m[w[r]]));
			m[w[r]]++;
			s.insert(m[w[r]]);
		}
		ans[l] = k - *s.rbegin();//因为是升序，找最大值用逆向迭代器
		s.erase(s.find(m[w[l]]));
		m[w[l]]--;
		if (m[w[l]] == 0) m.erase(w[l]);
		else s.insert(m[w[l]]);
	}
	while (q--)
	{
		int l, r;
		cin >> l >> r;
		cout << ans[l] << '\n';
	}
}
signed main()
{
	int t;	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}