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;
}
正解
同余最短路，模数是最大值。