解题思路
滑动窗口法，因为我进关注当前值，上一个数的值，以及上一个数和上上一个数的差值，以及窗口的左侧位置。因此没必要使用一个数组来专门存储这个数列的值。
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 <iostream>
#include <vector>
#include <map>
typedef long long ll;
using namespace std;
ll cal() {
int N;
cin >> N;
int start = 0;
ll dif = 0;
ll pre = 0;
ll cur = 0;
int maxLen = 2;
cin >> pre >> cur;
dif = cur - pre;
pre = cur;
for (int i = 2; i < N; ++i) {
cin >> cur;
if (cur - pre != dif) {
maxLen = max(maxLen, i - start);
dif = cur - pre;
start = i - 1;
}
pre = cur;
}
maxLen = max(maxLen, N - start);
return maxLen;
}
int main() {
int T;
cin >> T;
for (int i = 1; i <= T; ++i) {
cout << "Case #" << i << ": " << cal() << endl;
}
return 0;
}
|
解题思路
可以观察得出，从左到右，有A个数递增，有B个数递减，A和B的交集为C。然后可以计算得出有$N - (A + B - C)$个数全程不可见。并且，很容易发现，仅有最大值才可以被A和B同时看到。
这道题很容易分析出的是当$N < A + B - C$时，是不可能的情况。但是对于$A = 1, B = 1, N > 1$的情况容易遗漏，因为只要最大值位于一端，另一端的结果必然大于2。
这里补充一个，个人很容易遗落的情况：N = 5, A = 3, B = 3, C = 3是可能的。也即最大值不一定相邻。
一个可能的解为[5, 1, 5, 1, 5]。
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
| #include <iostream>
#include <vector>
typedef long long ll;
using namespace std;
template<typename T>
std::ostream& operator<<(std::ostream& o, std::vector<T> const& v)
{
for (const auto &item : v) {
o << " " << item;
}
return o;
}
vector<int> cal() {
int N, A, B, C;
cin >> N >> A >> B >> C;
int invisible = N - A - B + C;
if (invisible < 0 || (A == 1 && B == 1 && N > 1)) {
return {};
}
A -= C;
B -= C;
vector<int> path(N, 0);
int L = 0;
int R = N - 1;
if (A == 0) {
++L;
path[0] = N;
--C;
}
if (B == 0) {
--R;
path[N - 1] = N;
--C;
}
for (int i = 0; i < A; ++i, ++L) {
path[L] = N - 1;
}
for (int i = 0; i < invisible; ++i, ++L) {
path[L] = 1;
}
for (int i = 0; i < C; ++i, ++L) {
path[L] = N;
}
for (int i = L; i <= R; ++i) {
path[i] = N - 1;
}
return path;
}
int main() {
int T;
cin >> T;
for (int i = 1; i <= T; ++i) {
auto path = cal();
if (path.empty()) {
cout << "Case #" << i << ": " << "IMPOSSIBLE" << endl;
} else {
cout << "Case #" << i << ":" << path << endl;
}
}
return 0;
}
|
解题思路
这道题求解，要使玩玩具的时间尽可能长的情况，以及满足最长时间的保留最多（删除最少）的玩具数量。根据题目的意思能够得到一个最为重要的结论：最多两轮，就可以知道玩具能否无限玩下去。
设sum的初值为初始所有玩具的游玩时间总和。那么一旦存在$E_i + R_i > sum$的情况，就说明玩具i会导致不能无限玩下去；那么就可以删除玩具i，从而导致sum被更新。而sum的更新处理，可以从$max(E_i + R_i)$开始；因为如果非最大值的玩具j要被删除，从而导致了sum变得更小，那么最大玩具s的必然也要被删除。经过上述的删除处理，如果仍有玩具存在，那么必然是可以无限玩下去的。
反之，则需要找出那个最大值。根据sum部分的处理，可以得出一个结论，一个玩具的删除与它的游玩顺序没有关系。因此可以令当前游玩时间cur_time的初值为sum，从第二轮开始分析。第二轮设置一个序列，将玩具逐一插入，并将其的游玩时间累加到cur_time中。如果该玩具不满足$E_i + R_i \leqslant sum$要被删除，则cur_time不记录它的第二轮时间并减去第一轮计算它的时间，同时更新sum。
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
| #include <iostream>
#include <list>
#include <vector>
#include <limits.h>
#include <queue>
using namespace std;
#define INF -1
struct node {
int E;
int R;
node(int x, int y) : E(x), R(y) {}
bool operator< (const node& b) const {
return E + R < b.E + b.R;
}
};
pair<int64_t, int> solve(vector<node>& toys) {
int64_t cur_time = 0;
int cur_remove = 0;
int64_t max_time = 0;
int min_remove = 0;
int64_t sum = 0;
bool inf_flag = true;
priority_queue<node> Q;
for (int i = 0; i < toys.size(); ++i) {
sum += toys[i].E;
if (toys[i].E + toys[i].R > sum) {
inf_flag = false;
}
}
if (inf_flag) {
return make_pair(INF, 0);
}
cur_time = sum;
max_time = sum;
for (int i = 0; i < toys.size(); ++i) {
Q.push(toys[i]);
cur_time += toys[i].E;
while (!Q.empty()) {
auto p = Q.top();
if (p.E + p.R > sum) {
Q.pop();
cur_time -= 2 * p.E;
sum -= p.E;
++cur_remove;
continue;
}
break;
}
if (cur_time > max_time) {
max_time = cur_time;
min_remove = cur_remove;
}
}
if (!Q.empty()) {
max_time = INF;
min_remove = toys.size() - Q.size();
}
return make_pair(max_time, min_remove);
}
int main()
{
int T;
int N;
cin >> T;
for (int i = 1; i <= T; ++i) {
cin >> N;
vector<node> toys;
for (int j = 0; j < N; ++j) {
int E, R;
cin >> E >> R;
toys.emplace_back(E, R);
}
auto r = solve(toys);
if (r.first== INF) {
cout << "Case #" << i << ": " << r.second << " INDEFINITELY" << endl;
} else {
cout << "Case #" << i << ": " << r.second << " " << r.first << endl;
}
}
return 0;
}
|
###解题思路
这道题求解的是合成金块的最小代价。
那么可以构造一个代价矩阵$C_{junction, stone_type}$，该矩阵存储的是在街口$junction_i$获取$stone_type_i$所需的代价。又因为这个代价的数值是与将石头移动的距离成正比的，所以需要求两点间的最短路径。
（求最短路径可以用Dijkstra或者Bellman–Ford算法，但由于Dijkstra可以用小顶堆优化，因此Dijkstra更优。）
因此松弛操作就涉及两部分：
根据边来缩短代价，即$C_{from,stone_type} + 1 < C_{to,stone_type}$
尝试用配方来缩短代价，即$recipt_cost < C_{junction, stone_type}$
与之对应的，这里就涉及到了另外几个问题：
某一种矿也许能在多个路口获得，这也就意味着，源可能不止一个。但是代价矩阵C仅有一个（使用多个再合并的代价有点高），该如何处理
配方也同样可以存在多种不同的配方得到同一种矿，那么该如何存储和处理配方。
第一个问题可以用在节点入队的时候携带其最短路径的距离，以及Dijkstra的特性处理即可。即如果某个节点的代价比其从队列取出来的更低时，意味着该节点已经被更新，且能确保是最优的。这是由于Dijkstra是由近到远进行更新的，并且每条边的权重相同，先访问的必然不会比后访问的更远。
第二个问题则参考了ecnerwala的处理（自己真想不到）。他的核心在于构建了4个数组：
users用于记录某种石头s相关的配方r；num_inputs表示配方r所需的石头数量；product表示配方r所产生的石头t；recipe_dist用于记录在路口v合成配方r所需的总代价，同时维护一个已使用石头的计数器
这样就可以在遍历节点的过程中，同时尝试配方。即某种配方所需的石头均已被遍历（满足$recipe_dist[r][v].count == num_inputs[r]$），那么尝试使用配方的代价能否降低获取该石头t的代价。同样，第一次满足配方为最优，也是由Dijkstra算法保证的，即在此之前条件还未满足。
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
| #include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
using i64 = int64_t;
const i64 INF = 0x007fffffffffffff;
void solve(i64 which) {
i64 V, E, S, R;
cin >> V >> E >> S >> R;
vector<vector<i64>> graph(V);
for (i64 i = 0; i < E; ++i) {
i64 u, v;
cin >> u >> v;
--u; --v;
graph[u].push_back(v);
graph[v].push_back(u);
}
vector<vector<i64>> stones(V);
for (i64 i = 0; i < V; ++i) {
i64 k;
cin >> k;
for (i64 j = 0; j < k; ++j) {
i64 s;
cin >> s;
--s;
stones[i].push_back(s);
}
}
vector<vector<i64>> user(S);
vector<i64> num_input(R);
vector<i64> product(R);
for (i64 i = 0; i < R; ++i) {
i64 k;
cin >> k;
num_input[i] = k;
for (i64 j = 0; j < k; ++j) {
i64 s;
cin >> s;
--s;
user[s].push_back(i);
}
i64 t;
cin >> t;
--t;
product[i] = t;
}
vector<vector<i64>> stone_cost(S, vector<i64>(V, INF));
vector<vector<pair<i64, i64>>> recipe_cost(R, vector<pair<i64, i64>>(V, make_pair(0, 0)));
priority_queue<pair<i64, pair<i64, i64>>, vector<pair<i64, pair<i64, i64>>>, greater<>> Q;
for (i64 i = 0; i < V; ++i) {
for (i64 j : stones[i]) {
stone_cost[j][i] = 0;
Q.push(make_pair(0, make_pair(j, i)));
}
}
while (!Q.empty()) {
i64 c = Q.top().first;
i64 s = Q.top().second.first;
i64 v = Q.top().second.second;
Q.pop();
if (stone_cost[s][v] < c) {
continue;
}
for (i64 r : user[s]) {
recipe_cost[r][v].first++;
recipe_cost[r][v].second += c;
if (recipe_cost[r][v].first == num_input[r]) {
i64 t = product[r];
i64 nc = recipe_cost[r][v].second;
if (nc < stone_cost[t][v]) {
stone_cost[t][v] = nc;
Q.push(make_pair(nc, make_pair(t, v)));
}
}
}
for (i64 to : graph[v]) {
if (c + 1 < stone_cost[s][to]) {
stone_cost[s][to] = c + 1;
Q.push(make_pair(c + 1, make_pair(s, to)));
}
}
}
i64 r = INF;
for (i64 i = 0; i < V; ++i) {
r = min(stone_cost[0][i], r);
}
if (r >= (i64)1e12) {
r = -1;
}
cout << "Case #" << which << ": " << r << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 T;
cin >> T;
for (i64 i = 1; i <= T; ++i) {
solve(i);
}
return 0;
}
|