[比赛记录]ARC174

Final ranking: \(820\)。

A

平凡题。

不妨设选定操作的区间为 \([l, r]\)，这一段的和为 \(s\)。

如果 \(c > 0\)，则相对于原来的数组来说，操作后的和增加了 \((c - 1) \times s\)。我们期望选择最大的 \(s\) 来获得最大的增量。很显然我们需要求最大子段和。

如果 \(c < 0\)，则相对于原来的数组来说，操作后的和减少了 \((|c| + 1) \times s\)。我们希望是 \(s\) 为负数并且最小，这样就能获得最大的增量。

综上，我们需要根据 \(c\) 的正负，求最大 / 最小子段和。求最大 / 最小子段和可以 dp。复杂度显然线性。submission。

B

简单题。

答案显然满足可二分性。

不妨设当前二分中点为 \(m\)。购买星数 \(\le 3\) 是没有意义的。可以发现，最优策略最多有下面两种可能：全部购买四星或全部购买五星。两种策略都可能出现以下情况：剩下一点点钱不够买这种星星了，这时可以买另外一种星星。

将两种情况能够获得的平均星数取最大值，并与 \(3\) 比较即可。复杂度 \(O(\log n)\)。submission。

C

期望题。不会期望。

D

小清新打表观察性质题。

首先看起来没什么思路。不妨打表，观察那些数满足条件。

int stk[110], top, ans;
int bin[100000], T, n;
bool check(int n) {
	int s = (int)sqrt(n);
	top = 0; while (n) stk[ ++ top] = n % 10, n /= 10;
	int ss = 0; while (top) {
		ss = ss * 10 + stk[top -- ];
		if (ss >= s) break;
	} if (ss == s) return 1; return 0;
}
signed main() {
	rep(i, 1, 10010)
		if (check(i)) cout << i << ' ' << (int)sqrt(i) << endl;
	rep(i, 1, 99999) if (bin[i]) cout << i << ' ' << bin[i] << endl;
}

把所有合法的数打印下来，不难发现，只有下面这样的数是满足条件的：

• \(\texttt{999...8000...0}\)，即一串 \(9\)，一个 \(8\)，后面跟上相同位数的 \(0\)。如 \(998000\)。

• \(\texttt{999...9???...?}\)，即一串 \(9\)，后面跟上等位数的任意数。如 \(999837\)。

• \(\texttt{1000...0???...?}\)，即 \(1\) 后面跟上一串 \(0\)，后面再跟上等位数的任意数。例如 \(1000873\)。

这样问题就变得简单。直接枚举 \(\sqrt{n}\) 的位数，进行暴力判断即可。复杂度 \(O(1)\)。corner case 死多。submission。

E / F

并不会做。