A sprial
找规律。
直接做。
#include <bits/stdc++.h>
#define int long long
using namespace std;int t, n;int sqrtll(int n) {int l = 1, r = 1000000, ans = 0;for(; l <= r; ) {int mid = (l + r) >> 1;if(mid * mid >= n) {ans = mid, r = mid - 1;}else {l = mid + 1;}}return ans;
}signed main() {freopen("spiral.in", "r", stdin);freopen("spiral.out", "w", stdout);for(cin >> t; t--; ) {cin >> n;int i = sqrtll(n);int tmp = n - (i - 1) * (i - 1);if((i & 1)) {if(tmp <= i) {cout << i << ' ' << tmp << '\n';}else {cout << 2 * i - tmp << ' ' << i << '\n';}}else {if(tmp <= i) {cout << tmp << ' ' << i << '\n';}else {cout << i << ' ' << 2 * i - tmp << '\n';}}}return 0;
}
B write
C curve
\[\because \frac{x}{3} \le \lfloor \frac{x}{2} \rfloor \le \frac{x}{2}
\]
\[\therefore \frac{x}{3^{r - l + 1}} + \sum \limits_{i = l}^r \frac{a_i}{3^{r - i + 1}} \le \lfloor \frac{x}{2^{r - l + 1}} + \sum \limits_{i = l}^r \frac{a_i}{2^{r - i + 1}} \rfloor \le \frac{x}{2^{r - l + 1}} + \sum \limits_{i = l}^r \frac{a_i}{2^{r - i + 1}}
\]
\[\because a_i, x \le 10^9
\]
\[\therefore \text{当 } r - i + 1 \ge 30 \ge \log_2 10^9, \frac{x}{3^{r - i + 1}} \to 0, \frac{x}{2^{r - i + 1}} \to 0,
\]
\[\therefore \lfloor \frac{x}{2^{r - i + 1}} \rfloor \to 0
\]
直接暴力。
#include <bits/stdc++.h>
using namespace std;int n, arr[200020], q, x, l, r;int main() {freopen("curve.in", "r", stdin);freopen("curve.out", "w", stdout);cin >> n;for(int i = 1; i <= n; i++) {cin >> arr[i];}for(cin >> q; q--; ) {cin >> x >> l >> r;l = max(l, r - 50);for(int i = l; i <= r; i++) {x = (x + arr[i]) / 2;}cout << x << '\n';}return 0;
}
D coin
乱搞
我们充分发挥人类智慧，根据数学直觉，不能凑出的数必然在 \(2.69 \times 10^7\) 以上。
直接对于 \(2.69 \times 10^7\) 下面的数暴力 dp，上面的都凑的出来。
/*** @brief "According" to my direst sence,* @brief the maximum number which "will output -1" is not greater than 2.69*(10^7).
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;const int kCstf = 2.69e7;int n, l, arr[22], dp[kCstf + 20];signed main() {freopen("coin.in", "r", stdin);freopen("coin.out", "w", stdout);cin >> n >> l;for(int i = 1; i <= n; i++) {cin >> arr[i];}if(l <= kCstf) {dp[0] = 1;for(int i = 1; i <= n; i++) {for(int j = arr[i]; j <= l; j++) {dp[j] |= dp[j - arr[i]];}}int ans = 0;for(int i = 1; i <= l; i++) {ans += dp[i];}cout << ans << '\n';}else {dp[0] = 1;for(int i = 1; i <= n; i++) {for(int j = arr[i]; j <= kCstf; j++) {dp[j] |= dp[j - arr[i]];}}int ans = 0;for(int i = 1; i <= kCstf; i++) {ans += dp[i];}cout << ans + (l - kCstf) << '\n';}return 0;
}
正解
同余最短路，模数是最大值。
