JOI2018 Final Solution

寒冬暖炉

CF某场B题原题,sort就好了。

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
#include <bits/stdc++.h>
using namespace std;
#define IL inline
typedef long long ll;
IL ll read() {
char ch = getchar(); ll u = 0, f = 1;
while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
while (isdigit(ch)) { u = (u << 1) + (u << 3) + ch - 48; ch = getchar(); }
return u * f;
}
#define rep(i, j, k) for (int i = j; i <= k; ++i)
#define repd(i, j, k) for (int i = j; i >= k; --i)
const int maxn = 5e5 + 10;

ll a[maxn], b[maxn], rd[maxn];
bool cmp(int x, int y) { return a[x] < a[y]; }
int main() {
int n = read(), k = read();
rep(i, 1, n) a[i] = read();
rep(i, 1, n - 1) b[i] = a[i + 1] - a[i] - 1;
sort(b + 1, b + 1 + n - 1, greater<int>());
//cerr << b[1] << " " << b[2] << " " << endl;
int ans = n;
rep(i, 1, n - 1) if (i >= k) ans += b[i];
cout << ans << endl;
return 0;
}

美术展览

按照Asort以后枚举Amax,前面算一下

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
#include <bits/stdc++.h>
using namespace std;
#define IL inline
typedef long long ll;
IL ll read() {
char ch = getchar(); ll u = 0, f = 1;
while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
while (isdigit(ch)) { u = (u << 1) + (u << 3) + ch - 48; ch = getchar(); }
return u * f;
}
#define rep(i, j, k) for (int i = j; i <= k; ++i)
#define repd(i, j, k) for (int i = j; i >= k; --i)
const int maxn = 5e5 + 10;

ll a[maxn], b[maxn], rd[maxn];
bool cmp(int x, int y) { return a[x] < a[y]; }
int main() {
int n = read();
rep(i, 1, n) a[i] = read(), b[i] = read(), rd[i] = i;
sort(rd + 1, rd + 1 + n, cmp);
ll fr = a[rd[1]], ans = 0, tot = 0;
// rep(i, 1, n) ans = max(ans, b[i]);
rep(i, 1, n) {
int v = rd[i]; tot += b[v];
ans = max(ans, tot + fr - a[v]);
fr = max(fr, a[rd[i + 1]] - tot);
}
cout << ans << endl;
return 0;
}

团子制作

一眼网络流,一看数据范围不行。

拆成点,转化了一下问题变成每个点度数小于等于3的无向图的最大独立集。貌似没有啥多项式时间内的算法。

其实考虑对于任何一对在从右向左对角线上的团子之间是互相不影响的,类似这样

1
2
3
--RGW
-RGW-
RGW--

但是不在同对角线是互补影响的。

那么对于每个对角线DP一下单独加起来就好了。其实可以考虑R,但是那样的话DP就会多一维状态,最方便的时考虑G。

设$f[i][0/1/2]$表示对角线上前$i$个,第$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
#include <bits/stdc++.h>
using namespace std;
#define IL inline
IL int read() { int x; int _w = scanf("%d", &x); return x; }
#define rep(i, j, k) for (int i = j; i <= k; ++i)
#define repd(i, j, k) for (int i = j; i >= k; --i)
#define pb push_back
#define mp make_pair
#define fr first
#define se second
const int maxn = 3005;
int n, m;
char s[maxn][maxn];
bool r[maxn][maxn], d[maxn][maxn];
int main() {
n=read(),m=read();
rep(i,1,n){scanf("%s",s[i]+1);rep(j,1,m)if(s[i][j-1]=='R'&&s[i][j]=='G'&&s[i][j+1]=='W')r[i][j]=1;}
rep(i,1,m)rep(j,2,n-1)if(s[j-1][i]=='R'&&s[j][i]=='G'&&s[j+1][i]=='W')d[j][i]=1;
int out=0;
rep(j,2,n+m){
vector<pair<int,int> >lst;
rep(x,1,n){ int y=j-x; if(y>=1&&x<=n&&y<=m) lst.pb(mp(x,y)); }
if(!lst.size())continue;
vector<int>dp[3]; dp[0].resize(lst.size()); dp[1].resize(lst.size()); dp[2].resize(lst.size());
dp[0][0]=0;dp[1][0]=r[lst[0].fr][lst[0].se];dp[2][0]=d[lst[0].fr][lst[0].se];
rep(i,1,(int)lst.size()-1){
int tx = lst[i].fr, ty = lst[i].se;
dp[0][i]=max(dp[0][i-1],max(dp[1][i-1],dp[2][i-1]));
if(r[tx][ty])dp[1][i]=max(dp[0][i-1],dp[1][i-1])+1;
if(d[tx][ty])dp[2][i]=max(dp[0][i-1],dp[2][i-1])+1;
}
int totans = max(max(dp[0][lst.size()-1],dp[1][lst.size()-1]),dp[2][lst.size()-1]);
out+=totans;
}
cout<<out<<endl;
return 0;
}

月票购买

水平不够觉得直接想不是很好想,然后就顺着看每个subtask

subtask2

从 S 到 T 乘车费用最小的路径上有且仅有一条边。直接分类讨论经不经过这个边就好了。

subtask1

S=U。暴力枚举一个最短路上的点p然后把p->v取min。

subtak3

考虑一个性质,(u->v)路径和最短路的交一定是一个连续的一段而且最多只有一段。

这个图中,x在最短路中,y不在最短路中,从(u->x->v)显然比(u->y->v)更优。

那么我们可以枚举这两个端点,Floyd判断是否在最短路中(dis(s,u)+dis(u,v)+dis(v,t)=dis(s,t)),然后取min更新答案。

subtak4

有了上面那个性质就可做了。

我们把S->T的路径看成一个dag,用$f[i]$表示从u到i的最小代价。f可以转移沿着dag转移或者从u走过去,$f[a]=min(f[b],dis(u,a))$。

每次更新f的时候把ans和$f[i]+dis(i,w)$取min。

一个问题是这样只考虑了一个方向的边,可能会这样。

那么从T->S反过来跑一遍就好了。

PS:传dis数组去跑最短路的时候memset(dis,0x3f,sizeof(dis)),由于dis是一个指针所以大小只有8,正确的写法应该是sizeof(int)*(n+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
#include <bits/stdc++.h>
using namespace std;
#define IL inline
IL int read() { int x; int _w = scanf("%d", &x); return x; }
#define rep(i, j, k) for (int i = j; i <= k; ++i)
#define repd(i, j, k) for (int i = j; i >= k; --i)
#define pb push_back
#define mp make_pair
#define int long long
const int maxn = 4e5 + 10;
int id = 0; int n, m, s, t, U, V;
const int INF = (1ll<<60);
pair<pair<int,int>, int>edge[maxn];
vector<pair<int,int> >e[maxn]; vector<int> G[maxn];
int dis_s[maxn], dis_u[maxn], dis_v[maxn], vis[maxn], dis_t[maxn], f[maxn], deg[maxn];
void sp(int s, int *dis) {
priority_queue<pair<int,int> >q;
memset(dis, 0x3f, sizeof (int)*(n+1)); dis[s] = 0;
memset(vis, 0, sizeof vis);
q.push(mp(0, s));
while (q.size()) {
pair<int,int>u=q.top(); q.pop();
//cerr<<u.second<< " " << dis[u.second]<<endl;
if(vis[u.second]) continue;
vis[u.second] = 1;
for(auto PI : e[u.second]) {
int v = PI.first; int c = PI.second;
// cerr<<"to:"<<v<<" " <<c<<endl;
// cerr<<"dis[v]="<<dis[v]<<endl;
// cerr<<"dis[u]+c="<<dis[u.second]+c<<endl;
if (dis[v] > dis[u.second] + c) {
dis[v] = dis[u.second] + c;
// cerr<<"dis[v]="<<dis[v]<<endl;
q.push(mp(-dis[v], v));
}
}
}
}
main() {
// freopen("01-02.in", "r", stdin);
n = read(), m = read();
s = read(), t = read();
U = read(), V = read();
rep(i, 1, m) {
int ai = read(), bi = read(), ci = read();
//cerr<<ai<<" " << bi << " " << ci << endl;
edge[i * 2 - 1] = mp(mp(ai, bi), ci); edge[i * 2] = mp(mp(bi, ai), ci);
e[ai].pb(mp(bi, ci)); e[bi].pb(mp(ai, ci));
}
sp(s, dis_s); sp(t, dis_t); sp(U, dis_u); sp(V, dis_v);
#define fr first
#define se second
rep(i, 1, 2 * m) {
int u = edge[i].fr.fr;
int v = edge[i].fr.se;
if (dis_s[u] + dis_t[v] + edge[i].se == dis_s[t]) {
G[u].push_back(v); deg[v]++;
}
}
int output = dis_s[t];
queue<int>q;
q.push(s); int ans = INF;
rep(i, 1, n) f[i] = dis_u[i],ans=min(ans,f[i]+dis_v[i]);
while (q.size()) {
int u = q.front(); q.pop();
for (int to : G[u]) {
f[to] = min(f[to], f[u]), ans = min(ans, f[to] + dis_v[to]);
deg[to]--;
if (!deg[to]) q.push(to);
}
}
rep(i, 1, n) f[i] = dis_u[i], G[i].clear(), deg[i]=0;
rep(i, 1, 2 * m) {
int u = edge[i].fr.fr;
int v = edge[i].fr.se;
if (dis_t[u] + dis_s[v] + edge[i].se == dis_t[s]) G[u].push_back(v),deg[v]++;
}
q.push(t);
while (q.size()) {
int u = q.front(); q.pop();
for (int to : G[u]) {
f[to] = min(f[to], f[u]), ans = min(ans, f[to] + dis_v[to]);
deg[to]--;
if(!deg[to]) q.push(to);
}
}
cout << ans << endl;
return 0;
}