T1
此题考语文，注意题意的理解…
贪心，特判偶数串就行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include <bits/stdc++.h>
using namespace std;
int sum, cnt, k;
int main() {
int t, n;
cin >> t;
while (t--) {
cin >> n;
sum = cnt = 0;
for (int i = 1; i <= n; i++)
cin >> k, sum += k / 2, cnt += k % 2;
if (cnt) cout << 1 + (sum / cnt) * 2 << "\n";
else cout << sum * 2 << "\n";
}
return 0;
}
|
T2
记忆化搜索，下次不作死写十重 $for$ 循环了…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include <bits/stdc++.h>
using namespace std;
const int MAXN = 50;
typedef long long ll;
int f[MAXN];
map<ll, int> dp;
inline ll hash(int t, int k, int x) {
return (ll)t * 11 * 1000000001 + (ll)k * 1000000001 + x;
}
inline int dfs(int now, int x, int k) {
if (!x) return k == 0;
if (now < 0) return 0;
if ((ll)f[now] * k < x) return 0;
ll tmp = hash(now, k, x);
if (dp.count(tmp)) return dp[tmp];
register int ret = 0;
for (register int i = 0; i <= k; i++) {
if (i * f[now] > x) break;
else ret += dfs(now - 1, x - i * f[now], k - i);
}
return dp[tmp] = ret;
}
int main() {
f[0] = 1, f[1] = 2;
register int i, r = 1e9;
for (i = 1; f[i] <= r; i++) f[i + 1] = f[i] + f[i - 1];
register int t;
cin >> t;
while (t--) {
int x, k;
cin >> x >> k;
cout << dfs(i - 1, x, k) << "\n";
}
return 0;
}
|
T3
倍增或神奇的”快速幂”就能实现，复杂度为$O(n \log n)$。
但此题我们可以把一个石头向它第 $k$ 近的石头连边，那么这就形成了一张有向图，每个点只有一个出度，所以这张图必然是一些基环套内向树的形式，那么就可以 $BFS$ 搜出每个点能否进入基环，以及进入基环的位置和步数，就可以求出答案，这样的时间复杂度位$O(n)$。
$O(n \log n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include <bits/stdc++.h>
using namespace std;
const int iol = 1024 * 1024;
bool iosig;
char ch, buf[iol], *s, *t;
inline char read() {
if (s == t) {
t = (s = buf) + fread(buf, 1, iol, stdin);
if (s == t) return -1;
}
return *s++;
}
template<class T>
inline bool read(T &x) {
iosig = 0;
for (ch = read(); !isdigit(ch); ch = read()) {
if (ch == -1) return false;
if (ch == '-') iosig = true;
}
x = 0;
while (ch == '0') ch = read();
for (; isdigit(ch); ch = read())
x = (x << 1) + (x << 3) + (ch ^ '0');
if (iosig) x = -x;
return true;
}
const int MAXN = 1000010;
int n, k, ans[MAXN];
long long a[MAXN], m;
int f[MAXN], g[MAXN];
int main() {
read(n), read(k), read(m);
k++;
for (register int i = 1; i <= n; i++)
read(a[i]);
register int l = 1, r = k;
for (register int i = 1; i <= n; i++) {
while ((r < n) && (a[r + 1] - a[i] < a[i] - a[l]))
l++, r++;
if (a[i] - a[l] >= a[r] - a[i]) f[i] = l;
else f[i] = r;
}
for (register int i = 1; i <= n; i++)
ans[i] = i;
while (m) {
if (m & 1)
for (register int i = 1; i <= n; i++)
ans[i] = f[ans[i]];
m >>= 1;
for (register int i = 1; i <= n; i++)
g[i] = f[f[i]];
memcpy(f, g, sizeof(int) * (n + 1));
}
for (register int i = 1; i <= n; i++)
cout << ans[i] << " ";
cout << "\n";
return 0;
}
|
