Endless Ladders
打表易发现，缺失 1 和 2 + 4 * 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
|
#include <bits/stdc++.h>
#define rep(x,l,r) for(int x=l;x<=r;++x)
#define per(x,r,l) for(int x=r;x>=l;--x)
#define mk(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define max(x,y) ((x)<(y)?(y):(x))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
typedef long long ll;
typedef double db;
const ll N=2e5+7,mod=1e9+7;
const int inf=1e9;
const double eps=1e-11;
void solve()
{
ll a,b;
cin >> a >> b;
ll x=abs(a*a-b*b);
ll ans=x-2;
if(x>4) --ans;
if(x>6) ans-=(x-6)/4+1;
printf("%lld\n",ans);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T=1;
cin>>T;
while(T--) {
solve();
}
return 0;
}
|
Symmetry Intervals
边扫边维护
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
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
void solve() {
int n, q;
string s;
cin >> n >> q >> s;
vector<int> len(n + 1, 0);
for (int i = 1; i <= q; i++) {
ll ans = 0;
int m;
string t;
cin >> t >> m;
int l = t.length();
for (int j = 0; j < l; j++) {
if (s[m - 1 + j] != t[j]) len[j + 1] = 0;
else len[j + 1] = len[j] + 1;
ans += len[j + 1];
}
cout << ans << endl;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
|
Numb Numbers
以中位为分界，维护左右两侧，用 map 维护每种数出现的次数
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
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
void solve() {
int n, q;
cin >> n >> q;
vector<ll> a(n + 1);
map<ll, int> mp;
for (int i = 1; i <= n; i++) {
cin >> a[i];
mp[a[i]]++;
}
int lim = n / 2, lit = 0;
auto it = mp.begin();
while (it != mp.end() && n - lit - it->second >= lim) {
lit += it->second;
it++;
}
int p, v;
for (int p, v; q--;) {
cin >> p >> v;
if (a[p] < it->first) lit--;
mp[a[p]]--;
a[p] += v;
if (a[p] < it->first) lit++;
mp[a[p]]++;
while (it != mp.end() && n - lit - it->second >= lim) {
lit += it->second;
it++;
}
cout << lit << endl;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
Museum Acceptance
从每个房间都走一遍即可，因为走的道路是固定的。
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
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
void solve() {
int n;
cin >> n;
vector<int> d[n + 1];
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
for (int j = 1; j <= x; j++) {
int y;
cin >> y;
d[i].push_back(y);
}
}
map<int, map<int, bool>> mp;
vector<vector<int>> ans(n + 1, vector<int>(3));
vector<vector<bool>> vis(n + 1, vector<bool>(3));
function<int(int, int, int)> dfs = [&](int u, int p, int dep) {
vis[u][p] = 1;
int v = d[u][p], s;
int sz = d[v].size();
for (int i = 0; i < sz; i++) {
if (d[v][i] == u) s = (i + 1) % sz;
}
int t = mp[u][v];
mp[u][v] = mp[v][u] = 1;
if (vis[v][s]) return ans[u][p] = (!t) + dep;
else return ans[u][p] = dfs(v, s, dep + (!t));
};
for (int i = 1; i <= n; i++) {
if (!ans[i][0]) {
mp.clear();
dfs(i, 0, 0);
}
cout << ans[i][0] << endl;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
|
Iron Bars Cutting
考虑 DP， 记 $DP_{i,j}$ 为 l 到 r 之间铁条完全分割的最小代价。
易得到转移方程： $dp[l][r] = \min_{l \le k < r} { dp[l][k] + dp[k+1][r] + \text{cost}(l, k, r) }$
但是要考虑不平衡度的影响，这启发我们从不平衡度的角度思考，即不按照区间长度来思考，而是按照不平衡度从小到大来计算。
将所有的切割操作预处理，利用这些有序的切割来构建 DP 值，一次切割操作由 l, r, k 构建。
动态规划的大致流程如下：
- 初始化 $dp_{i,j} = \infin, dp_{i,i} = 0$
- 遍历排好序的切割列表，对于 $c = (l, r, k)$：
检查 dp[l][k] 和 dp[k+1][r] 是否都已经被计算过（即不为无穷大，如果已计算，说明找到了一条有效路径，用这个成本更新 $dp_{l,r}$
- 因为是按照不平衡度从小到大的顺序来进行的，所以一定满足题目的限制条件。
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 13000000;
struct Node {
int l, r, k;
ll v, sum;
};
Node p[N];
bool cmp(const Node &a, const Node &b) {
if (a.sum == b.sum) {
return (a.r - a.l) < (b.r - b.l);
}
return a.sum < b.sum;
}
void solve() {
int n;
cin >> n;
vector<ll> a(n + 1), pre(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
}
vector<vector<ll>> dp(n + 2, vector<ll>(n + 2, 1e18));
for (int i = 1; i <= n; i++) {
dp[i][i] = 0;
}
int now = 0;
for (int l = 1; l <= n; l++) {
for (int r = l + 1; r <= n; r++) {
for (int k = l; k < r; k++) {
ll suml = pre[k] - pre[l - 1];
ll sumr = pre[r] - pre[k];
ll total_sum = suml + sumr;
ll log_val = 0;
if (total_sum > 1) {
log_val = 64 - __builtin_clzll(total_sum - 1);
}
ll v = min(suml, sumr) * log_val;
ll sum = abs(suml - sumr);
p[++now] = {l, r, k, v, sum};
}
}
}
sort(p + 1, p + now + 1, cmp);
vector<ll> ans(n + 1, 1e18);
for (int i = 1; i <= now; i++) {
int l = p[i].l, r = p[i].r, k = p[i].k;
ll v = p[i].v;
if (dp[l][k] != 1e18 && dp[k + 1][r] != 1e18) {
ll tmp = dp[l][k] + dp[k + 1][r] + v;
dp[l][r] = min(dp[l][r], tmp);
if (l == 1 && r == n) {
ans[k] = min(ans[k], tmp);
}
}
}
for (int i = 1; i < n; i++) {
if (ans[i] == 1e18) {
cout << -1 << " ";
} else {
cout << ans[i] << " ";
}
}
cout << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
|
Symmetry Intervals 2
神必分块加数据结构，搞不懂，之后有空补。