EOJ Monthly 2018.7

准备继续大学acm啦

又要开始愉快的码码码啦

第一次在华东师大OJ上面做题

看来EOJ上的积分体质是假的，我怎么一把上红？？？

A.数三角形

神tm的防AK题放在A，出题人很不友好啊...

先写了个暴力，算出了1-5的结果，然后在OEIS上面搜了一下（雾）

\(a(n) = ((n - 1)^2*n^2*(n + 1)^2)/6 - 2*Sum(Sum((n - k + 1)*(n - l + 1)*gcd(k - 1, l - 1), k, 2, n), l, 2, n)\).

拍了一下，似乎没什么问题，但是复杂度是\(O(n^2)\)，看了一下，似乎可以用莫比乌斯反演来枚举gcd，但好像已经太久没写，意识模糊，不会了...

先弃着...

B.锐角三角形

签到题

对于偶数\((0,0)\)\((0,2)\)\((n/2,1)\)即可

对于奇数\((0,1)\)\((1,0)\)\((n/2+1,n/2+1)\)即可

LL n;

int main()

{

	read(n);

	if (n<=2){puts("No");return 0;}

	if (n%2==0)

	{

		puts("Yes");

		puts("0 0");puts("0 2");

		print(n/2);puts(" 1");

	}

	else

	{

		puts("Yes");

		puts("0 1");puts("1 0");

		print(n/2+1);putchar(' ');print(n/2+1);puts("");

	}

	return 0;

}

C.大鱼吃小鱼

D.数蝌蚪

考虑枚举首项，显然首项\(∈[0,10000]\)，不然代价显然是非常大的

可以脑补一下，很显然地，对于首项而言，代价是一个凹函数

可以考虑用三分来解决，三分+暴力计算结果即可

int n;

LL m,a[300010];

LL calc(LL x)

{

	LL res=0,k=x;

	for (int i=1;i<=n;i++)

		res+=abs(a[i]-k),k+=m;

	return res;

}

int main()

{

	read(n);read(m);

	for (int i=1;i<=n;i++)

		read(a[i]);

	int l=0,r=1000000,mid1,mid2,ans;LL x,y;

	while (l<=r)

	{

		if (r-l<=10) break;

		mid1=l+(r-l)/3;mid2=l+(r-l)/3*2;

		x=calc(mid1),y=calc(mid2);

		if (x<y) r=mid2;

		else l=mid1;

	}

	LL res=calc(l);

	for (int i=l+1;i<=r;i++)

		res=min(res,calc(i));

	print(res),puts("");

	return 0;

}

不过似乎不用这么麻烦？看看出题人的题解。

令 bi=ai−ki (0-indexed)，然后就转化为把所有数变为相同的非负整数至少要操作多少步。直接取中位数即可(注意要特判小于 0 的情况)，当然也可以排个序前缀和维护一下。

E.对称与科学美

直接随机化？

考虑对每一个不同数，随机分配一个随机数，然后的问题就是区间xor为0的个数

区间xor为0的情况，我们可以前缀和，然后排个序解决，当然也可以用map来存贮一下，然后对map遍历即可

但是对于随机分配的随机数，似乎数据比较坑，一开始一直Wa at test14，直到不断的把随机产生数不断地扩大，才勉强AC，雾....Wa了8次，有点惨烈

map<int,LL> a;

map<LL,int> c;

int n;

LL b[300010];

int main()

{

	read(n);

	srand(time(NULL));

	int x;LL y;

	for (int i=1;i<=n;i++)

	{

		read(x);

		if (a.count(x)) y=a[x];

		else{y=1LL;for (int j=1;j<=10;j++) y=y*rand();a[x]=y;}

		b[i]=b[i-1]^y;

	}

	for (int i=0;i<=n;i++) c[b[i]]++;

	LL ans=0;

	for (map<LL,int>::iterator it=c.begin();it!=c.end();it++)

		ans+=1ll*(it->second)*(it->second-1)/2ll;

	print(ans),puts("");

	return 0;

}

巴特西