昨天考试这道题也是难倒了很多同学，但这并没有妨碍的某LJS AK(顺便%一波)

但是LJS的题解对我这种数学渣到不行蒟蒻实在不太友好，于是我干脆不看了。

LJS题解传送门

于是我就想，这道题既然能够用暴力，那么就一定能够用各种奇淫技巧优化。

☆ O(N^3)

首先我们只考虑$O(N^3)$的裸暴力，枚举每个x,y,z。这样就有20分了。

☆ O(N^2)

接下来仔细观察题目，发现题目限制$y-x=z-y$，通过移项，可以得到$z+x=2y$

那么我们就可以去掉枚举$y$的循环，时间复杂度$O(N^2)$

这样就有40分了，再加上一些花里胡哨的优化，可以骗到60分

☆ 歪正解

再来观察$z+x=2y$这个式子，$2y$一定是一个偶数，那么则$z$和$x$满足同奇偶。

再次阅读题目，观察三元组的限制条件，我们很容易就可以想到按照颜色和每个格子的下标进行分组，那么像这样看来，我们就应该把重点放在cmp排序函数上。

既然$z$和$x$满足同奇偶，那么我们就可以按照这个来进行排序。

排序后，我们就可以很方便的判断哪些情况是不可能的，则枚举每一个$z$和$x$，判断不可能的情况，然后直接$break$，听起来有些像搜索的剪枝

§ 照这个思路写出来的40分代码:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define MOD 10007

using namespace std;

const int MAXN = 100000 + 5;
struct Node {
	int color;
	int number;
	int ID;
} a[MAXN];
int n, m;

bool Rule(const Node &a, const Node &b) {
	return ((a.ID % 2 == b.ID % 2) && (a.color == b.color) && (a.ID < b.ID)) 
		|| ((a.ID % 2 == b.ID % 2) && (a.color < b.color)) || (a.ID % 2 < b.ID % 2);
}

int result(int x, int z) {
	return (a[x].ID + a[z].ID) * (a[x].number + a[z].number);
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &a[i].number), a[i].ID = i;
	for (int i = 1; i <= n; ++i)
		scanf("%d", &a[i].color);
	int ans = 0;
	sort(a + 1, a + 1 + n, Rule);
	for (int i = 1; i <= n; ++i)
			for (int k = i + 1; k <= n; ++k) {
				if ((a[i].ID + a[k].ID) & 1) break;
				if (a[i].color != a[k].color) break; 
				ans += result(i, k) % MOD;
			}
	printf("%d\n", ans % MOD);
	return 0;
}

结果:

这是为什么呢？原来没开$long$ $long$见祖宗了

90分代码:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define MOD 10007

using namespace std;

const long long MAXN = 100000 + 5;
struct Node {
	long long color;
	long long number;
	long long ID;
} a[MAXN];
long long n, m;

bool Rule(const Node &a, const Node &b) {
	return ((a.ID % 2 == b.ID % 2) && (a.color == b.color) && (a.ID < b.ID)) 
		|| ((a.ID % 2 == b.ID % 2) && (a.color < b.color)) || (a.ID % 2 < b.ID % 2);
}

long long result(long long x, long long z) {
	return (a[x].ID + a[z].ID) * (a[x].number + a[z].number);
}

int main() {
	scanf("%d%d", &n, &m);
	for (long long i = 1; i <= n; ++i)
		scanf("%d", &a[i].number), a[i].ID = i;
	for (long long i = 1; i <= n; ++i)
		scanf("%d", &a[i].color);
	long long ans = 0;
	sort(a + 1, a + 1 + n, Rule);
	for (long long i = 1; i <= n; ++i)
			for (long long k = i + 1; k <= n; ++k) {
				if ((a[i].ID + a[k].ID) & 1) break;
				if (a[i].color != a[k].color) break; 
				ans += result(i, k) % MOD;
			}
	printf("%d\n", ans % MOD);
	return 0;
}

结果:

有一个点超时了，于是开始卡常:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define MOD 10007

using namespace std;

const int MAXN = 100000 + 5;
struct Node {
	long long color;
	long long number;
	long long ID;
} a[MAXN];
long long n, m;

inline bool Rule(const Node &a, const Node &b) {
	return ((a.ID % 2 == b.ID % 2) && (a.color == b.color) && (a.ID < b.ID)) 
		|| ((a.ID % 2 == b.ID % 2) && (a.color < b.color)) || (a.ID % 2 < b.ID % 2);
}

inline long long result(register long long x, register long long z) {
	return (a[x].ID + a[z].ID) * (a[x].number + a[z].number);
}

signed main() {
	scanf("%d%d", &n, &m);
	for (register int i = 1; i <= n; ++i)
		scanf("%d", &a[i].number), a[i].ID = i;
	for (register int i = 1; i <= n; ++i)
		scanf("%d", &a[i].color);
	register long long ans = 0;
	sort(a + 1, a + 1 + n, Rule);
	for (register int i = 1; i <= n; ++i)
			for (register int k = i + 1; k <= n; ++k) {
				if ((a[i].ID + a[k].ID) & 1) break;
				if (a[i].color ^ a[k].color) break; 
				ans += result(i, k) % MOD;
			}
	printf("%d\n", ans % MOD);
	return 0;
}

依旧是90分，脑子快爆了的我只好祭出这个

#pragma GCC optimize (2)

AC代码:

#pragma GCC optimize (2)
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define MOD 10007

using namespace std;

const int MAXN = 100000 + 5;
struct Node {
	long long color;
	long long number;
	long long ID;
} a[MAXN];
long long n, m;

inline bool Rule(const Node &a, const Node &b) {
	return ((a.ID % 2 == b.ID % 2) && (a.color == b.color) && (a.ID < b.ID)) 
		|| ((a.ID % 2 == b.ID % 2) && (a.color < b.color)) || (a.ID % 2 < b.ID % 2);
}

inline long long result(register long long x, register long long z) {
	return (a[x].ID + a[z].ID) * (a[x].number + a[z].number);
}

signed main() {
	scanf("%d%d", &n, &m);
	for (register int i = 1; i <= n; ++i)
		scanf("%d", &a[i].number), a[i].ID = i;
	for (register int i = 1; i <= n; ++i)
		scanf("%d", &a[i].color);
	register long long ans = 0;
	sort(a + 1, a + 1 + n, Rule);
	for (register int i = 1; i <= n; ++i)
			for (register int k = i + 1; k <= n; ++k) {
				if ((a[i].ID + a[k].ID) & 1) break;
				if (a[i].color ^ a[k].color) break; 
				ans += result(i, k) % MOD;
			}
	printf("%d\n", ans % MOD);
	return 0;
}