https://ac.nowcoder.com/acm/contest/1080
C. tokitsukaze and Soldier
题意：挑选一些士兵，每个人由战力，并且选了一个人后要满足他“总人数不超过 s[i] ”的要求，问最大总战力。
按照人数从小到大遍历，维护一个单调队列，满足队列里的人的s都大于等于目前人数。再贪心选战力最大的。
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int n;
ll ans;
typedef pair<int, int>pii;
priority_queue<pii>q1;
priority_queue<pii, vector<pii>, greater<pii> >q2;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int v, s;
scanf("%d%d", &v, &s);
q1.push(pii(v, s));
}
ll sum = 0;
for (int i = 1; i <= n; i++) {
while (!q2.empty() && q2.top().first < i) {
sum -= q2.top().second;
q2.pop();
}
while ((int)q2.size() < i && !q1.empty()) {
pii p = q1.top(); q1.pop();
if (p.second < i)continue;
sum += p.first;
q2.push(pii(p.second, p.first));
}
ans = max(ans, sum);
}
printf("%lld\n", ans);
return 0;
}
|
D. tokitsukaze and Event
题意：一个无向图有起点终点，每条边有两种模式，可以在某点切换为第二种模式，以后就不能再切回来了，要求在第 1,2,3,⋯,i−1 不能切换，求对每个 i 的最短路。
最短路
能且只能在一点切换。那么只要知道在每点切换的最短路，最后取最小值就好了。
在某点切换就是先在初始模式下从起点到这一点，再在第二种模式下从这一点到终点，那么两次单源最短路就能处理出所有点。
要求在一些点不能切换，那么先从只有一点可选的情况开始，不断增多可选，就是向队列里压入更多点作为切换点的最短路，始终选最小值即可。
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
const ll INF = 1e18;
int n, m, s, t;
struct E{
int v, w;
};
vector<E>G[2][N];
ll d[2][N], ans[N];
typedef pair<ll, int>pii;
void bfs(int i, int s) {
priority_queue<pii, vector<pii>, greater<pii> >q;
for (int j = 1; j <= n; j++)d[i][j] = INF;
d[i][s] = 0;
q.push(pii(0, s));
while (!q.empty()) {
int u = q.top().second; ll di = q.top().first; q.pop();
if (d[i][u] < di)continue;
for (E e : G[i][u]) {
if (d[i][e.v] > d[i][u] + e.w) {
d[i][e.v] = d[i][u] + e.w;
q.push(pii(d[i][e.v], e.v));
}
}
}
}
priority_queue < ll, vector<ll>, greater<ll> >q;
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
int u, v, a, b;
scanf("%d%d%d%d", &u, &v, &a, &b);
G[0][u].push_back(E{ v,a });
G[0][v].push_back(E{ u,a });
G[1][u].push_back(E{ v,b });
G[1][v].push_back(E{ u,b });
}
scanf("%d%d", &s, &t);
bfs(0, s);
bfs(1, t);
for (int i = n; i >= 1; i--) {
q.push(d[0][i] + d[1][i]);
ans[i] = q.top();
}
for (int i = 1; i <= n; i++)printf("%lld\n", ans[i]);
return 0;
}
|
E. tokitsukaze and Segmentation
题意：有一个只含数字的字符串，可以切成任意段，要求每段都能被3整除，且没有前导0，问切割方案数。
dp
dp[i][j] 表示到第 i 位，且第 i 位所在的块模3为 j，且之前所有块模3都为0.
分成两种情况：第 i 位并入第 i−1 位所在的块；第 i 位单独成一块。
主要是要处理前导0的情况，当当前位为0时，要和最近的非零位合并，或者独立一块。
当当前位非0，当时前一位为0时，也要和最近的非零位合并。
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
const ll INF = 1e18;
const ll mod = 998244353;
int n;
ll dp[N][3];
char s[N];
int a[N], b[N];
int main() {
scanf("%d", &n);
scanf("%s", s + 1);
b[1] = 0; a[1] = s[1] - '0';
for (int i = 2; i <= n; i++) {
a[i] = s[i] - '0';
if (a[i - 1] != 0 || a[i] != 0)b[i] = i - 1;
else b[i] = b[i - 1];
}
dp[1][a[1] % 3] = 1;
for (int i = 2; i <= n; i++) {
if (a[i] == 0) {
for (int j = 0; j < 3; j++) {
dp[i][j] = dp[b[i]][j];
}
dp[i][0] += dp[i - 1][0];
dp[i][0] %= mod;
}
else {
for (int j = 0; j < 3; j++) {
if (a[i - 1] != 0)
dp[i][(j + a[i]) % 3] = dp[i - 1][j];
else dp[i][(j + a[i]) % 3] = dp[b[i - 1]][j];
}
dp[i][a[i] % 3] += dp[i - 1][0];
dp[i][a[i] % 3] %= mod;
}
}
cout << dp[n][0] << endl;
return 0;
}
|
