T1.集会

题目：

Description

有$N$个人住在一条数轴上。第$i$个人住在坐标$X_i$处。你需要举办一个所有$N$个人都必须参加的集会。 集会可以在任意整数坐标处举行。如果你选择在坐标$P$处举行集会，第$i$个人将花费$(X_i - P) ^ 2$点体力来参加集会。 求出$N$个人必须花费的最小总体力点数。

Input

输入通过标准输入给出，格式如下：

$N\\X_1 X_2 X_3 ··· X_N$

Output

输出$N$个人必须花费的 最大 最小总体力点数。

Example

Input 1

2
4 1

Output 1

5

Input 2

7
14 14 2 13 56 2 37

Output 2

2354

Note

• $输入中的所有值均为整数$
• $1 ≤ N ≤ 100$
• $1 ≤ X_i ≤ 100$

思路：

直接把$1$到$N$的所有情况都试一遍，再选最小的。

(这里是是因为数据范围较小才能这样的，不然就会 $\bcancel{\rm{\green{Accepted}}}~~~\red{\rm{Time~Limit~Exceeded}}$)

错因：

freopen写错了，本来能$\green{\rm{Accepted}}$的，结果$\rm{\red{Runtime~Error}}$······

(TAT)

代码：

#include <bits/stdc++.h>
using namespace std;

int n, x[110], ans = 2e9, l = 200, r = -1;

int main ()
{
	freopen("jihui.in", "r", stdin);
	freopen("jihui.out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> x[i];
		l = min(x[i], l);
		r = max(x[i], r);
	}
	for (int i = l; i <= r; i++)
	{
		int cnt = 0;
		for (int j = 1; j <= n; j++) cnt += pow((x[j] - i), 2);
		ans = min(ans, cnt);
	}
	cout << ans;
	return 0;
}

T2.统计区间

题目：

Description

给定一个长度为$N$的序列$A=(A_1,A_2,…,A_N)$和一个整数$K$。问$A$中有多少个连续子序列的和等于$K$？换句话说，有多少对整数$(l,r)$满足以下所有条件？

$$1≤l≤r≤N$$ $$\sum_{i=l}^rA_i=K$$

Input

$N~K\\A_1~A_2~A_3...~A_N$

Output

打印答案。

Example

Input 1

6 5
8 -3 5 7 0 -4

Output 1

3

Input 2

2 -1000000000000000
1000000000 -1000000000

Output 2

0

Note

• $1 ≤ N ≤ 2 \times 10 ^ 5$
• $|A_i| ≤ 10 ^ 9$
• $|K| ≤ 10 ^ {15}$
• 输入中的所有值都是整数。

思路：

这道题其实非常简单，考的就是前缀和，随便写几行完事。 什么？你不懂前缀和？赶紧给我去看讲义！

代码：

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int N = 2e5 + 5;
ll n, a[N];
ll k, pre[N], ans = 0;

int main ()
{
	freopen("tjqj.in", "r", stdin);
	freopen("tjqj.out", "w", stdout);
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		pre[i] = pre[i - 1] + a[i];
	}
	unordered_map<ll, ll> mp;
	for (int i = 0; i <= n; i++)
	{
		ans = ans + mp[pre[i] - k];
		mp[pre[i]]++;
	}
	cout << ans;
	return 0;
}

$$\orange{\rm{8472690697868}}$$

$$\orange{\rm{THE~~END}}$$