C - Joyride

题意:

游乐园有nn个游乐设施,mm条路,游玩第ii个游乐设施需要TiT_i的时间和PiP_i的金钱,走过一条路需要tt的时间,每遇到一个游乐设施强制游玩,问从1号游乐设施开始到1号游乐设施结束,花费时间为xx的最小金钱花费。

解析:

这道题xx较小,可以枚举每一个xx所对应的从11号设施开始的最小花费,可以直接跑最短路。

代码:
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
#include <bits/stdc++.h>

using namespace std;
#define fast \
ios_base::sync_with_stdio(false); \
cin.tie(NULL);
const int N = 3e3 + 10;
const int M = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-3;
int ans;
struct node{
int u,v,w,next;
}a[M];
int f[N],cnt;
void add(int u,int v,int w){
a[++cnt].v = v;
a[cnt].w = w;
a[cnt].next = f[u];
f[u] = cnt;
}
long long T[N], P[N];
int x, n, m, t;
long long dis[N][N], vis[N][N];
void dijkstra() {
priority_queue<pair<int,pair<int,int>>> q;
memset(dis, 0x3f, sizeof dis);
memset(vis, 0, sizeof vis);
q.push({0, {1,T[1]}});
dis[T[1]][1] = P[1];
while(!q.empty()) {
int u = q.top().second.first;
int X = q.top().second.second;
q.pop();
if(X > x) continue;
if(vis[X][u]) continue;
vis[X][u] = 1;
for (int i = f[u]; i; i = a[i].next) {
int v = a[i].v;
int w = X + a[i].w + T[v];
if(dis[w][v] > dis[X][u] + P[v]) {
dis[w][v] = dis[X][u] + P[v];
q.push({-dis[w][v], {v, w}});
}
}
}
}

int main(){
ans = INF;
cin >> x >> n >> m >> t;
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v, t);
add(v, u, t);
}
for (int i = 1; i <= n; i++) {
add(i, i, 0);
scanf("%d%d", &T[i], &P[i]);
}
dijkstra();
if(dis[x][1] == LINF) puts("It is a trap.");
else cout << dis[x][1] << '\n';
return 0;
}

D - Pants On Fire

题意:

给定一些逻辑判断询问的逻辑是否正确

分析:

直接暴力找是否正确即可,需要对每个string取一个ID进行优化,不然会TLE

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
#include <bits/stdc++.h>

using namespace std;
#define fast \
ios_base::sync_with_stdio(false); \
cin.tie(NULL);
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-3;
map<string, int> mp;
vector<int> id[N];
bool find(int u, int tar) {
if (u == tar) return true;
for (auto it : id[u]) {
int w = find(it, tar);
if (w) return true;
}
return false;
}
int main() {
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
string s1, s2, s3;
int cnt = 0;
for (int i = 1; i <= n; i++) {
cin >> s1 >> s3 >> s3 >> s3 >> s2;
if(mp.find(s1) == mp.end()) mp[s1] = ++cnt;
if(mp.find(s2) == mp.end()) mp[s2] = ++cnt;
int id1 = mp[s1], id2 = mp[s2];
id[id2].push_back(id1);
}
for (int i = 1; i <= m; i++) {
cin >> s1 >> s3 >> s3 >> s3 >> s2;
if (mp.find(s1) == mp.end()) mp[s1] = ++cnt;
if (mp.find(s2) == mp.end()) mp[s2] = ++cnt;
int id1 = mp[s1], id2 = mp[s2];
int w1 = find(id2, id1), w2 = find(id1, id2);
if (w1) {
cout << "Fact\n";
} else if (w2) {
cout << "Alternative Fact\n";
} else {
cout << "Pants on Fire\n";
}
}
return 0;
}

F - Plug It In

题意:

mm个插座,需要供应nn个电器工作,有1个转换头,可以使一个插座供应3个电器,问最多可以供应多少电器。

分析:

网络流或者二分图板子题,每次枚举一个插座,增加容量找增广路,最后把容量都为1时的答案和增广后的答案相加即可。

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
#include <bits/stdc++.h>

using namespace std;
#define fast \
ios_base::sync_with_stdio(false); \
cin.tie(NULL);
const int N = 3e3 + 10;
const int M = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-3;
struct node {
int u, v, w, next;
} a[M], b[M];
int f[N], cnt;
inline void add(int u, int v, int w) {
a[++cnt].v = v;
a[cnt].w = w;
a[cnt].next = f[u];
f[u] = cnt;
a[++cnt].v = u;
a[cnt].w = 0;
a[cnt].next = f[v];
f[v] = cnt;
}
int d[N], cur[N];
int n, m, s, t;
bool bfs() {
queue<int> q;
memset(d, -1, sizeof d);
q.push(s);
d[s] = 0;
cur[s] = f[s];
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = f[u]; i; i = a[i].next) {
int v = a[i].v;
if (d[v] == -1 && a[i].w) {
d[v] = d[u] + 1;
cur[v] = f[v];
if (v == t) return true;
q.push(v);
}
}
}
return false;
}
int find(int u, int limit) {
if (u == t) return limit;
int flow = 0;
for (int i = cur[u]; i && flow < limit; i = a[i].next) {
cur[u] = i;
int v = a[i].v;
if (d[v] == d[u] + 1 && a[i].w) {
int ff = find(v, min(a[i].w, limit - flow));
if (!ff) d[v] = -1;
a[i].w -= ff, a[i ^ 1].w += ff, flow += ff;
}
}
return flow;
}
int dinic() {
int flow, res = 0;
while (bfs())
while (flow = find(s, INF)) res += flow;
return res;
}
int main() {
int k;
cnt = 1;
cin >> m >> n >> k;
s = 0, t = n + m + 1;
for (int i = 1; i <= m; i++) {
add(s, i, 1);
}
for (int i = 1; i <= n; i++) add(i + m, t, 1);
for (int i = 1; i <= k; i++) {
int u, v;
scanf("%d%d", &u, &v);
add(u, m + v, 1);
}
int ans = 0, ans1 = 0;
ans = dinic();
memcpy(b, a, sizeof a);
for (int i = 1; i <= m; i++) {
memcpy(a, b, sizeof b);
a[i * 2].w += 2;
ans1 = max(ans1, dinic());
}
cout << ans + ans1 << '\n';
return 0;
}

G - Water Testing

题意:

给定一个多边形,问多边形里共有多少整数点。

分析:

有公式:S=a+1b1S=a+\frac{1}{b}-1,其中SS为多边形面积,aa为多边形内部整数点数,bb为多边形边上的整数点数。多边形面积可以每两个点与原点组成三角形,直接进行面积相加,多余面积会被抵消。由于题目给出的方式有顺时针或逆时针两种,所以最后答案需要取绝对值。两点间边的整数点数为向量的绝对值的gcd值。

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
#include <bits/stdc++.h>

using namespace std;
#define fast \
ios_base::sync_with_stdio(false); \
cin.tie(NULL);
typedef long long LL;
const int N = 5e5 + 10;
const int M = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const LL LINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-3;
#define x first
#define y second
LL count(pair<LL, LL> a) {
LL gcd = __gcd(abs(a.x), abs(a.y));
return gcd;
}
LL operator*(pair<LL, LL> a,
pair<LL, LL> b) {
return a.x * b.y - a.y * b.x;
}
pair<LL, LL> operator-(pair<LL, LL> a,
pair<LL, LL> b) {
return {a.x - b.x, a.y - b.y};
}
pair<LL, LL> a[N];
int main() {
int n;
cin >> n;
LL point = 0;
for (int i = 1; i <= n; i++) {
scanf("%lld%lld", &a[i].x, &a[i].y);
}
LL sum = 0;
a[0] = a[n];
for (int i = 1; i <= n; i++) {
sum += (a[i]) * (a[i - 1]);
point += count(a[i] - a[i - 1]);
}
sum = abs(sum);
printf("%lld\n", sum / 2 - point / 2 + 1);
return 0;
}

I - Uberwatch

题意:

nn个时间片段,每个是片段有若干敌人,间隔mm个时间片段可以进行一次攻击,问最多可以击败多少敌人。

分析:

简单dp,dpidp_i为从第一个时间片段到第ii个时间片段最多可以击败多少敌人。每个时间片段可以进行攻击或不进行攻击,进行攻击从dpimdp_{i-m}转移,不进行攻击从dpi1dp_{i-1}转移。

代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>

using namespace std;
#define fast \
ios_base::sync_with_stdio(false); \
cin.tie(NULL);
const int N = 5e5 + 10;
const int M = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-3;
int a[N];
int dp[N];
int main(){
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = m + 1; i <= n; i++) {
dp[i] = max(dp[i - m] + a[i], dp[i - 1]);
}
cout << dp[n] << '\n';
return 0;
}