5 分钟 读完 (大约 721 个字)

2018-09-27考试

序

莫名220???

结果

题面

题解

T1

二分答案 + spfa check

T2

DP，设$f_{i,0/1}$表示前$i$个时刻，当前这个时刻是否打下鸟的最大值
然后就可以乱搞了

T3

结论题???

代码

T1

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
#include<bits/stdc++.h>
#define RG register
#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define clear(x, y) memset(x, y, sizeof(x));
using namespace std;

inline int read()
{
	int data=0, w=1;
	char ch=getchar();
	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
	if(ch=='-') w=-1, ch=getchar();
	while(ch>='0'&&ch<='9') data=(data<<3)+(data<<1)+(ch^48), ch=getchar();
	return data*w;
}

const int maxn(110);
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
int inque[maxn][maxn], n, m, sx, sy, tx, ty, can[maxn][maxn];
double dis[maxn][maxn], s;

queue<pair<int, int> > q;
inline double spfa(double k)
{
	for(RG int i = 1; i <= n; i++) for(RG int j = 1; j <= m; j++) dis[i][j] = 1e15;
	clear(inque, 0);
	dis[sx][sy] = 0; inque[sx][sy] = 1; q.push(make_pair(sx, sy));
	while(!q.empty())
	{
		pair<int, int> x = q.front(); q.pop();
		int xx = x.first, xy = x.second;
		for(RG int i = 0; i < 4; i++)
		{
			int tx = xx + dx[i], ty = xy + dy[i];
			double ex = (i & 1) ? 1. : k;
			if(tx > 0 && ty > 0 && tx <= n && ty <= m && !can[tx][ty] && dis[tx][ty] > dis[xx][xy] + ex)
			{
				dis[tx][ty] = dis[xx][xy] + ex;
				if(!inque[tx][ty]) inque[tx][ty] = 1, q.push(make_pair(tx, ty));
			}
		}
		inque[xx][xy] = 0;
	}
	return dis[tx][ty];
}

int main()
{
	file(maze);
	n = read(); m = read(); sx = read(); sy = read(); tx = read(); ty = read();
	for(RG int i = 1; i <= n; i++) for(RG int j = 1; j <= m; j++) can[i][j] = read();
	scanf("%lf", &s);
	double l = -0.1, r = 1e5 + 1.;
	while(r - l > 1e-5)
	{
		double mid = (l + r) * .5;
		if(spfa(mid) < s) l = mid;
		else r = mid;
	}
	printf("%.3lf\n", l);
	return 0;
}

T2

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
#include<bits/stdc++.h>
#define RG register
#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define clear(x, y) memset(x, y, sizeof(x));
using namespace std;

inline int read()
{
	int data=0, w=1;
	char ch=getchar();
	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
	if(ch=='-') w=-1, ch=getchar();
	while(ch>='0'&&ch<='9') data=data*10+(ch^48), ch=getchar();
	return data*w;
}

const int maxn(100010), maxl(500010);
int tree[maxl << 2], n, _max, lazy[maxl << 2], k;
#define son(i) (root << 1 | i)

inline void pushdown(int root, int l, int r)
{
	if(l == r) return;
	if(!lazy[root]) return;
	tree[son(0)] += lazy[root]; lazy[son(0)] += lazy[root];
	tree[son(1)] += lazy[root]; lazy[son(1)] += lazy[root];
	lazy[root] = 0;
}

inline void update(int ql, int qr, int val, int root = 1, int l = 1, int r = _max + 1)
{
	if(r < ql || qr < l) return;
	if(ql <= l && r <= qr) { tree[root] += val; lazy[root] += val; return; }
	int mid = (l + r) >> 1;
	pushdown(root, l, r);
	update(ql, qr, val, son(0), l, mid);
	update(ql, qr, val, son(1), mid + 1, r);
	tree[root] = max(tree[son(0)], tree[son(1)]);
}

inline int query(int ql, int qr, int root = 1, int l = 1, int r = _max + 1)
{
	if(r < ql || qr < l) return -INT_MAX;
	if(ql <= l && r <= qr) return tree[root];
	int mid = (l + r) >> 1;
	pushdown(root, l, r);
	return max(query(ql, qr, son(0), l, mid), query(ql, qr, son(1), mid + 1, r));
}

struct line { int l, r; } a[maxn];
vector<int> end_s[maxl];
int g[maxl], cnt, c[maxl];

int main()
{
	file(bird); n = read(); k = read();
	for(RG int i = 1; i <= n; i++)
	{
		a[++cnt].l = max(read(), 0); a[cnt].r = read();
		if(a[cnt].r < 0) --cnt;
		_max = max(_max, a[cnt].r);
	}
	for(RG int i = 1; i <= cnt; i++) end_s[a[i].r + 1].push_back(i), update(a[i].l + 1, a[i].r + 1, -1), ++c[a[i].l], --c[a[i].r + 1];
	int tmp = query(1, 1); update(1, 1, -tmp);
	int sum = c[0];
	for(RG int i = 1; i <= _max; i++)
	{
		g[i] = max(g[i - 1], query(i, i) + sum);
		while(!end_s[i].empty())
		{
			int tmp = end_s[i].back(); end_s[i].pop_back();
			update(a[tmp].l + 1, a[tmp].r + 1, 1);
		}
		sum += c[i];
		int q = (i - k + 1) > 0 ? query(1, i - k + 1) : 0; update(i + 1, i + 1, q + sum);
	}
	printf("%d\n", max(g[_max], query(_max + 1, _max + 1) + sum));
	return 0;
}

T3

None

Source --- 考试
2018-09-30考试
【模板】二分图匹配
关注我

标签

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×