SCUACM 2016集训 7.4【AK】

ACM_集训

集训期间完成15道，补题2道。
比赛链接：http://vjudge.net/contest/120693#overview

A. A Dangerous Maze（求期望，解方程）

题意：

有$n$个门，一种门可以让你在$x_i$分钟后走出迷宫，还有一种门会让你回到距离起点$x_i$分钟后的位置，问走出迷宫的期望时间。

分析：

分析题目说，每个门被选择的概率相等且走回起点后一切从头开始，
那么设走出迷宫的期望为$X$，选择第一种门的概率为$P1$，平均用时$T1$，第二种门的概率为$P2$， 平均用时$T2$，我们可以得到$$X = P1 \times T1 + P2 \times (T2 + X)$$
然后展开，解这个方程即可。最后进行一下约分处理。

代码：

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
/*************************************************************************
	> File Name: A.cpp
	> Author: jiangyuzhu
	> Mail: 834138558@qq.com 
	> Created Time: Mon 04 Jul 2016 09:17:05 AM CST
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
typedef pair<int, int>p;
const int maxn = 1e2 + 5 , mod = 1e9 + 7, oo = 0x3f3f3f3f;
int x[maxn];
int gcd(int a, int b){
	return b?gcd(b, a % b):a;
}
int main (void)
{
	int T;cin>>T;
	for(int tt = 1; tt <= T; tt++){
		int n;
		cin>>n;
		int neg = 0;
		int tot = 0;
		for(int i = 0; i < n; i++){
			cin>>x[i];
			if(x[i] < 0){
				x[i] = -x[i];
				neg++;
			}
			tot += x[i];
		}
		cout<<"Case "<<tt<<": ";
		if(neg == n) cout<<"inf"<<endl;
		else{
			int up = tot;
			int down = n - neg;
			cout<<up / gcd(up, down)<<"/"<<down / gcd(up, down)<<endl;
		}
	}
	return 0;
}

B - Article Decryption(KMP + DP)

题意：

给定几种单词，问给定的文本串有几种翻译方式。

分析：

KMP预处理出每个单词在文本串中的匹配情况，然后$dp$一下即可。
手写个kmp，然后就狂wa4发。。。

代码：

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
/*************************************************************************
    > File Name: A.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com
    > Created Time: Fri 08 Jul 2016 03:31:58 PM CST
 ************************************************************************/
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define sa(n) scanf("%d", &(n))
const int maxn = 1e3 + 5, mod = 835672545;
int len, len1;
int next[maxn];
int dp[maxn];
char t[maxn];
char s[maxn][maxn];
bool match[maxn][maxn];
void KMP_pre(int id)
{
    int j = next[0] = -1;
    int i = 0;
	len1 = strlen(s[id]);
    while(i < len1){
        while(j != -1 && s[id][i] != s[id][j])  j = next[j];
        next[++i] = ++j;
    }
}
void KMP(int id)
{
    int i = 0, j = 0;
    len = strlen(t);
    len1 = strlen(s[id]);
    while(i < len){
        while(j != -1 && t[i]!= s[id][j]){
            j = next[j];
        }
         j++;
        if(j == len1){
			match[id][i] = true;
			j = next[j];
        }
        i++;
    }
}
int main (void)
{
	int T;sa(T);
	while(T--){
		int n;sa(n);
		for(int i = 0; i < n; i++){
			scanf("%s", s[i]);
		}
		scanf("%s", t);
		len = strlen(t);
		memset(match, false, sizeof(match));
		for(int i = 0; i < n; i++){
			KMP_pre(i);
			KMP(i);
		}
		memset(dp, 0, sizeof(dp));
		for(int i = 0; i < len; i++){
			for(int j = 0; j < n; j++){
				if(match[j][i]){
					int l = strlen(s[j]);
					if(i - l == -1) dp[i]  = (dp[i] + 1) % mod;
					else dp[i] = (dp[i - l] + dp[i]) % mod;
				}
			}
		}
		printf("%d\n", dp[len - 1] % mod);
	}
	return 0;
}

C.Rochambeau（带权并查集）

题意：

$N$个学生玩剪刀石头布，其中有一个裁判，剩余学生一共分三组，同一组出的姿势一样，不同组出的姿势不同，裁判可以任意出，给定学生编号及他们的输赢情况，问能否判断出唯一的裁判。

分析：

$N$最大500，可以枚举。
枚举每个裁判的时候新建一个并查集，然后里面的东西就跟食物链完全一个套路了。
蓝儿当初那道食物链我是按照挑战上的方法直接水过的，并没有研究带权并查集到底是个啥。。这里有个关于带权并查集讲的非常清晰的博客。
明白了就很容易写出代码了。

代码：

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
/*************************************************************************
	> File Name: C.cpp
	> Author: jiangyuzhu
	> Mail: 834138558@qq.com 
	> Created Time: Mon 04 Jul 2016 01:04:46 PM CST
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
typedef pair<int, int>p;
const int maxn = 5e2 + 5, maxm = 2e3 + 5, mod = 1e9 + 7, oo = 0x3f3f3f3f;
struct FUN{int x, y, op;};
FUN fun[maxm];
int pa[maxn];
int kind[maxn];
int A[maxn];
int _find(int a)
{	
	int fa = pa[a];
	if(pa[a] == a) return a;
	pa[a] = _find(pa[a]);
	kind[a] = (kind[a] + kind[fa]) % 3;
	return pa[a];
}
int main (void)
{
	int n, m;
	while(scanf("%d%d", &n, &m) == 2){
		int x, y;char t;
		for(int i = 1; i <= m; i++){
			scanf("%d%c%d", &x, &t, &y);
			if(t == '>'){
				fun[i] = (FUN){x, y, 1};
			}else if(t == '='){
				fun[i] = (FUN){x, y, 0};
			}else if(t == '<'){
				fun[i] = (FUN){x, y, 2};
			}
		}
		memset(A, 0, sizeof(A));
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				pa[j] = j;
				kind[j] = 0;
			}	
			for(int j = 1; j <= m; j++){
				if(i == fun[j].x || i == fun[j].y) continue;
				int x = fun[j].x, y = fun[j].y;	
				int rx = _find(x);
				int ry = _find(y);
				if(rx != ry){
					pa[rx] = ry;
					// y根 -> y， y->x，x -> x根，即y根->x根
					kind[rx] = (kind[y] + fun[j].op + 3 - kind[x]) % 3;
				}
				if(rx == ry && (kind[y] + fun[j].op) % 3 != kind[x]){
					A[i] = j;
					break;
				}
			}
		}
		int ans = 0;
		int judge;
		int res = 0;
		for(int i = 0; i < n; i++){
			if(A[i] == 0){
				ans++;
				judge = i;
			}
			res = max(res, A[i]);
		}
		if(ans > 1) cout<<"Can not determine"<<endl;
		else if(ans == 0) cout<<"Impossible"<<endl;
		else cout<<"Player "<<judge<<" can be determined to be the judge after "<<res<<" lines"<<endl;
	}
	return 0;
}

D.India and China Origins(二分+bfs or dsu)

题意：

给定中国和印度之间的空白区域及山的位置，最初山的位置可以通行， 随着年份增加，山逐渐变高，变高后的山不可通行，问第几年开始中国和印度不再联通。

分析：

随着年份增加，山的数目单调递增，可以二分年份，然后暴搜判断是否联通。
并查集经常用来处理联通的问题，然后为了方便平原的数目的改变，采用倒着的方法，先让所有的山都长高，然后减小年份， 将相应的山与周围空白区域并在一起，看紧挨着中国$(i=n-1)$的最终能否和紧挨着印度的空白块$(i = 0)$并在一起即可。
不要问我为啥跑的那么慢，因为我写的是dfs。。

代码：

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
/*************************************************************************
	> File Name: D.cpp
	> Author: jiangyuzhu
	> Mail: 834138558@qq.com 
	> Created Time: Mon 04 Jul 2016 11:41:53 AM CST
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
typedef pair<int, int>p;
#define sa(n) scanf("%d", &(n))
const int maxn = 5e2 + 5, mod = 1e9 + 7, oo = 0x3f3f3f3f;
bool map[maxn][maxn];
struct q{int first; int second;} Q[maxn * maxn + 5];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
bool vis[maxn][maxn];
int m, n;
bool dfs(int x, int y)
{
	vis[x][y] = 1;
	if(x == 0) return true;
	for(int i = 0; i < 4; i++){
		int nx = x + dx[i];
		int ny = y + dy[i];
		if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
		if(map[nx][ny]||vis[nx][ny]) continue;
		if(dfs(nx, ny)) return true;
	}
	return false;
}
bool judge(int ans)
{
	for(int i = 1; i <= ans; i++){
		map[Q[i].first][Q[i].second] = 1;
	}
	memset(vis, false, sizeof(vis));
	for(int i = m - 1; i >= 0; i--){
		if(map[n - 1][i]) continue;
		if(dfs(n - 1, i)) return true;
	}
	return false;
}
int main (void)
{
	int T;sa(T);
	while(T--){
		sa(n);sa(m);
		string t;
		for(int i = 0; i < n; i++){
			cin>>t;
			for(int j = 0; j < m; j++){
				map[i][j] = t[j] - '0';
			}
		}
		int QQ;sa(QQ);
		int x, y;
		for(int i = 1; i <= QQ; i++){
			sa(x);sa(y);
			Q[i] = (q){x, y};
		}
		int l = 0, r = QQ;
		while(l < r - 1){
			int mid = l + r >> 1;
			if(!judge(mid)) r = mid; 
			else l = mid;
			for(int i = 1; i <= mid; i++){
				map[Q[i].first][Q[i].second] = 0;
			}
		}
		if(r == QQ && judge(r)) puts("-1");
		else printf("%d\n", r);
	}
	return 0;
}

E.Edit distance（贪心）

题意：

有A,D,M,C,四种操作，将字符串A转化为字符串B，使得A和D的操作数最小，问如何操作？

分析：

样例良心，看着样例就能猜到如何贪心，如果A比B长，就D相应的长度，反之就A相应的长度，然后剩下的字符用M操作，这样能保证A,D的操作数是最小的。
但是这题有几个坑点：

  1. 多组输入！！wa哭了
  2. 其实C完全没有用，因为M操作并未说不可以modify成相同的字符，且C的优先级没有M 高，所以所有C操作完全可以用M操作代替。然后完全没用到C，就这样过了。。

代码：

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
/*************************************************************************
	> File Name: E.cpp
	> Author: jiangyuzhu
	> Mail: 834138558@qq.com 
	> Created Time: Mon 04 Jul 2016 09:28:43 AM CST
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
typedef pair<char, char>p;
const int maxn = 1e3, mod = 1e9 + 7, oo = 0x3f3f3f3f;
int main (void)
{
	string a;
	string b;
	while(cin>>a>>b){
	if(a.length() > b.length()){
		for(int i = 0; i < a.length() - b.length(); i++){
		cout<<"d "<<a[i]<<endl;
		}
	}
	int be = 0;
	if(b.length() > a.length()){
		for(int i = 0; i < b.length() - a.length(); i++){
			cout<<"a "<<b[i]<<endl;
			be = i + 1;	
		}
	}
	for(int i = be; i < b.length(); i++){
		 cout<<'m'<<' '<<b[i]<<endl;
	}
	}
	return 0;
}

F. Task (贪心)

题意：

给定$n$个机器和$m$个任务的时间和难度。每个机器一天只能完成一个任务，一个任务只能被一台机器完成，完成一个任务获得利润$500\times 时间+2 \times level$。问一天内最大利润？

分析：

一道我很容易就想不清楚了的贪心。。。
观察式子的性质，可以发现，起决定性作用的是时间，所以对任务按时间为第一关键字，任务等级为第二关键字从大到小排。对于每个任务，找到时间和等级均大于这该任务的机器，然后选择最小等级的，这样就能保证每个较高时间的机器都能用上。

代码：

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
/*************************************************************************
    > File Name: F.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
#define sal(n) scanf("%I64d", &(n))
#define sa(n) scanf("%d", &(n))
typedef long long ll;
const int maxn = 1e5 + 5, maxm = 100 + 5, inf = 0x3f3f3f3f;
typedef pair<int,int>p;
p a[maxn], b[maxn];
int cnt[maxm];
bool cmp(p a, p b)
{
    if(a.first == b.first) return a.second > b.second;
    return a.first > b.first;
}
int main(void)
{
    int n, m;
    while(~scanf("%d%d", &n, &m)){
        for(int i = 0; i < n; i++){
            sa(a[i].first);sa(a[i].second);
        }//machine
        for(int i = 0; i < m; i++){
            sa(b[i].first);sa(b[i].second);
        }//task
        memset(cnt, 0, sizeof(cnt));
        sort(b, b + m, cmp);
        sort(a, a + n, cmp);
        int j = 0;
        ll ans = 0;
        int res = 0;
        for(int i = 0; i < m; i++){
            while(j < n && b[i].first <= a[j].first)
                cnt[a[j++].second]++;
            for(int k = b[i].second; k <= 100; k++){
                if(cnt[k]){
                    ans += 500ll * b[i].first + 2ll * b[i].second;
                    cnt[k]--;
                    res++;
                    break;
                }
            }
        }
        printf("%d %I64d\n", res, ans);
    }
    return 0;
}

G.Optimal Milking(二分 + 最大流)

题意:

有$K$个机器，$M$个奶牛，给定各个实体之间的距离，要求每个奶牛都到一个机器上喝奶，给定机器的最大容量，问所有奶牛所走的路径中的最长距离的最小值。

分析：

Cows can traverse several paths on the way to their milking machine.
题目给的距离乱起八糟，而由于我们要minimize这个最长距离，所有先floyd一下， 求出每个奶牛到每个机器的最短距离，接下来直接使用这个最短距离即可。
最小的最大值，给定一个值，如果这个值满足条件，那么比他大的值也一定满足条件，所以我们可以二分这个答案，然后判断在这个距离限制下能否使所有奶牛都喝到奶。使用网络流，在超级原点和每一个机器之间建一条容量为$M$的边，每次判断时，如果某个奶牛到某个机器的最短距离小于这个值，就把他加到图中，最后在每个奶牛和超级汇点之间建一条容量为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
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
/*************************************************************************
	> File Name: G.cpp
	> Author: jiangyuzhu
	> Mail: 834138558@qq.com
	> Created Time: Tue 05 Jul 2016 10:18:20 AM CST
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
struct edge{int to, cap, rev;};
const int maxn = 250 + 5, maxm = maxn * maxn + 5, INF = 0x3f3f3f3f;
int d[maxm], iter[maxm * 2];
int s, t;
int k, c, m;
int map[maxn][maxn];
vector<edge>G[maxm * 2];
void addedge(int from, int to, int cap)
{
    G[from].push_back((edge){to, cap, G[to].size()});
    G[to].push_back((edge){from, 0, G[from].size()-1});
}
void bfs()
{
    memset(d, -1, sizeof(d));
    queue<int>q;
    d[s] = 0;
    q.push(s);
    while(!q.empty()){
        int v = q.front();q.pop();
        for(int i = 0; i < G[v].size(); i++){
            edge &e = G[v][i];
            if(e.cap > 0 && d[e.to] < 0){
                d[e.to] = d[v] + 1;
                q.push(e.to);
            }
        }
    }
}
int dfs(int v, int f)
{
    if(v == t) return f;
    for(int &i = iter[v]; i < G[v].size(); i++){
        edge &e = G[v][i];
        if(e.cap > 0 && d[v] < d[e.to]){
            int tf = dfs(e.to, min(f, e.cap));
            if(tf > 0){
                e.cap -= tf;
                G[e.to][e.rev].cap += tf;
                return tf;
            }
        }
    }
    return 0;
}
int max_flow()
{
    int flow = 0;
    for(;;){
        bfs();
        if(d[t]<0) return flow;
        memset(iter, 0, sizeof(iter));
        int f;
        while((f = dfs(s, INF))>0){
            flow += f;
        }
    }
}
bool judge(int mid)
{
    for(int i = 0; i < maxn; i++)
        G[i].clear();
    s = 0, t = k + c + 1;
    for(int i = 1; i <= k; i++){
        addedge(s, i, m);
    }
    for(int i = 1; i <= k; i++){
        for(int j = k + 1; j <= k + c; j++){
            if(map[i - 1][j - 1] <= mid){
                addedge(i, j, map[i - 1][j - 1]);
            }
        }
    }
    for(int i = k + 1; i <= k + c; i++){
        addedge(i, t, 1);
    }
    return max_flow() == c;
}
int main (void)
{
	string ss;
	while(scanf("%d%d%d",&k, &c, &m) == 3){
        memset(map, 0, sizeof(map));
		for(int i = 0; i < k + c; i++){
            for(int j = 0; j < k + c; j++){
                scanf("%d", &map[i][j]);
                if(!map[i][j]) map[i][j] = INF;
			}
		}
		for(int q = 0; q < k + c; q++){
			for(int i = 0; i < k + c; i++){
				for(int j = 0; j < k + c; j++){
                    map[i][j] = min(map[i][j], map[i][q] + map[q][j]);
				}
			}
		}
		int l = 0, r = INF;
		while(l < r - 1){
			int mid = l + r >> 1;
			if(judge(mid)) r = mid;
			else l = mid;
		}
		printf("%d\n", r);
    }
	return 0;
}

H - Special Fish(KM)

题意：

给定$n$条鱼的价值及他们之间的攻击和被攻击关系，一个条鱼仅可以攻击和被攻击一次，攻击产生的价值为两条鱼的异或，问产生的最大结果？

分析：

看了样例才知道题目问的是什么= =
裸KM

代码：

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
/*************************************************************************
    > File Name: 3395.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/9/14 17:34:48
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
int nm, nn;
const int maxn = 1e2 + 5, INF = 0x3f3f3f3f;
int usex[maxn], usey[maxn], match[maxn], lx[maxn], ly[maxn], slack[maxn];
int z[maxn][maxn];
int a[maxn];
bool Find(int x)
{
    usex[x] = 1;
    for(int i = 0; i < nm; i++){
        if(usey[i]) continue;
        int s = lx[x] + ly[i] - z[x][i];
        if(s == 0){
            usey[i] = 1;
            if(match[i] == -1|| Find(match[i] )){
                match[i] = x;
                return true;
            }
        }else if(slack[i] > s){
            slack[i] = s;
        }
    }
    return false;
}
int KM()
{
    memset(ly, 0, sizeof(ly));
    memset(match, -1, sizeof(match));
    for(int i = 0; i <nn; i++){
        lx[i] = - INF;
        for(int j = 0; j < nm; j++){
            if(lx[i] < z[i][j])
                lx[i] = z[i][j];
        }
    }
    for(int a = 0; a < nn; a++){
        memset(slack, 0x3f, sizeof(slack));
        for(;;){
            memset(usex, 0,sizeof(usex));
            memset(usey, 0, sizeof(usey));
            if(Find(a)) break;
            int d = INF;
            for(int i = 0; i < nm; i++){
                if(!usey[i] && d > slack[i]){
                    d = slack[i];
                }
            }
            for(int i = 0; i < nn; i++){
                if(usex[i]) lx[i] -= d;
            }
            for(int i = 0; i < nm; i++){
                if(usey[i]) ly[i] += d;
                else slack[i] -= d;
            }
        }
    }
    int sum = 0;
    for(int i = 0; i < nm; i++){
        if(match[i] > -1){
            sum += z[match[i]][i];
        }
    }
    return sum;
}
char t[maxn];
int main (void)
{
	int n;
	while(~scanf("%d", &n) && n){
		for(int i = 0; i < n; i++) scanf("%d", &a[i]);
		memset(z, 0, sizeof(z));
		for(int i = 0; i < n; i++){
			scanf("%s", t);
			for(int j = 0; j < n; j++){
				if(t[j] == '1') z[i][j] = a[i] ^ a[j]; 
			}
		}
		nn = n, nm =  n;
		printf("%d\n", KM());
	}
	return 0;
}

I.Bear and Bowling 4(斜率优化dp)

题意：

给定序列，求一个子序列，若子序列中有$k$个元素，值分别为$s_i,s_2,…s_{i + k}$，那么结果为$\sum_{j = i}^{i + k} (j - i + 1) * s_j$，问能够得到的序列的最大值。

分析：

容易想到状态$dp[i][j]:= 第i+1个元素到第j个元素之间的序列得到的值$
设$pre[i]:=前i个元素的和，val[i] := \sum_{j = 1} ^{i} j \times s[j]$，
那么$dp[i][j] = val[j] - val[i] - i * (pre[j] - pre[i]);$
若$dp[i][j] > dp[k][j], i > k$
即$ val[j] - val[i] - i \times (pre[j] - pre[i]) > val[j] - val[k] - k \times (pre[j] - pre[k])$
$$grad(i,k)={(val[i] - i \times pre[i]) - (val[k] - k \times pre[k]) \over{i - k}} < -pre[j]$$
这样就转化成一个很斜率的式子了，
即当$i > k且grad(i,k)<-pre[j]$时，$i优于k$
令$i>j>k，grad(i, j )< grad(j, k)$，此时$j$均非最优，故可以舍弃。
最后由于$pre[j]$不单调，所以不必维护$head$，直接每次在单调队列上进行二分即可。
最后注意一下$long long$

代码：

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
/*************************************************************************
	> File Name: I.cpp
	> Author: jiangyuzhu
	> Mail: 834138558@qq.com 
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
typedef pair<int, int>p;
typedef long long ll;
#define sa(n) scanf("%d", &(n))
#define sal(n) scanf("%lld", &(n))
const int maxn = 2e5 + 5, mod = 1e9 + 7, oo = 0x3f3f3f3f;
ll a[maxn], val[maxn], sum[maxn];
int q[maxn];
inline ll up(int a, int b)
{
	ll x1 = val[a] - a * sum[a];
	ll x2 = val[b] - b * sum[b];
	return x2 - x1;
}
inline ll down(int a, int b){return b - a;}
bool judge(int a, int i)
{
	ll x1 = val[q[a]] - q[a] * sum[q[a]];
	ll x2 = val[q[a + 1]] - q[a + 1] * sum[q[a + 1 ]];
	return x2 - x1 > -sum[i] * down(q[a], q[a + 1]);
}
int main (void)
{
	int n;sa(n);
	ll ans = 0;
	for(int i = 1; i <= n; i++){
		sal(a[i]);
		sum[i] = sum[i - 1] + a[i];
		val[i] = val[i - 1] + i * a[i];
		ans = max(ans, a[i]);
	}
	int rear = 0;
	int l, r;
	q[rear++] = 0;
	for(int i = 1; i <= n; i++){
		l = -1, r = rear - 1;
		while(l < r - 1){
			int mid = l + r >> 1;
			if(judge(mid, i)) r = mid;
			else l = mid;
		}
        ans = max(ans, val[i] - val[q[r]] - q[r] * (sum[i] - sum[q[r]]));
		while(rear > 1 && up(q[rear - 1], i) * down(q[rear - 2], q[rear - 1]) < up(q[rear - 2], q[rear - 1]) * down(q[rear - 1], i)) rear--;
		q[rear++] = i;
	}
	printf("%lld\n", ans);
	return 0;
}

J. Domino(欧拉路径)

题意:

N个多米诺骨牌，每个骨牌左右两侧分别有一个0~6的整数（骨牌可以旋转以调换其左右两数），求一种把这些骨牌从左到右排列的方案，使得所有相邻的两数字相等（即左边骨牌右侧的数字等于右边骨牌左侧的数字）。

分析：

把数字当成点，骨牌当做边。构成无向图，求一发欧拉道路即可。
欧拉路径深入讲解：http://blog.chinaunix.net/uid-26380419-id-3164913.html

代码：

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
#include<iostream>
#include<map>
#include<cstring>
#include<stack>
#include<set>
using namespace std;
const int maxn = 200 + 5, maxm = 6 + 5;
struct Edge{int to;int dir; int id;int next;};
int tot = 0;
Edge edge[maxn];
stack<Edge>s;
int pa[maxn], head[maxm], cnt[maxm];
bool vis[maxn];
int _find(int a)
{
    if(a == pa[a]) return a;
    return pa[a] = _find(pa[a]);
}
void unite(int a, int b)
{
    int ra = _find(a);
    int rb = _find(b);
    if(ra == rb) return ;
    pa[rb] = ra;
}
bool same(int a, int b)
{
    return _find(a) == _find(b);
}
void add_edge(int u, int v, int id)
{
    edge[tot].to = v;
    edge[tot].id = id;
    edge[tot].dir = 1;
    edge[tot].next = head[u];
    head[u] = tot++;
    edge[tot].to = u;
    edge[tot].dir = 0;
    edge[tot].id = id;
    edge[tot].next = head[v];
    head[v] = tot++;
}
void dfs(int u)
{
    for(int i = head[u]; i != -1; i = edge[i].next){
        if(!vis[i]){
            vis[i] = true;
            vis[i^1] = true;
            dfs(edge[i].to);
            s.push(edge[i]);
        }
    }
}
int main (void)
{
    int n ;cin>>n;
    memset(head, -1, sizeof(head));
    for(int i = 0; i <= 6; i++) pa[i] = i;
    int a, b;
    for(int i = 0; i < n; i++){
        cin>>a>>b;
        add_edge(a, b, i + 1);
        cnt[a]++;
        cnt[b]++;
        unite(a, b);
    }
    int be = -1;
    int ans = 0;
    for(int i = 0; i <= 6; i++){
        if(cnt[i] & 1){
            ans++;
            if(be == -1) be = i;
        }
    }
    if(ans != 0 && ans != 2) return cout<<"No solution"<<endl, 0;
    for(int i = 0; i <= 6; i++){
        if(cnt[i] &&  be == -1) be = i;
        if(cnt[i] && !same(i, be)){return cout<<"No solution"<<endl, 0;}
    }
    dfs(be);
    while(!s.empty()){
        Edge t = s.top();s.pop();
        cout<<t.id<<' ';
        if(t.dir == 0) cout<<"-"<<endl;
        else cout<<"+"<<endl;
    }
    return 0;
}

K.Triangle Counting(数学)

题意：

从$[1,n]$之间选择三个不同的数，使得以他们为边长可以组成三角形。

分析：

数学题只会暴力，$O(n^3)$的复杂度肯定是过不了的。
看了《训练指南》上的讲解
设$f(x)$表示最长边为$x$的三角形个数，另两条边分别为$y, z$，根据两边之和大于第三边有$x-y<z<x$，固定$x$，改变$y$，可以得到$0+1+2+…+(x-3) + (x-2) = (x - 1)*(x - 2)/2$，这样在改变$y$的过程中，每个三角形都算了两遍，所以我们特别处理$y=z$的情况，然后将结果直接除以二即可。其中$y=z$时，$x / 2 \lt y \lt x$。
还是分析性质，分析特点。

代码：

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
/*************************************************************************
	> File Name: K.cpp
	> Author: jiangyuzhu
	> Mail: 834138558@qq.com 
	> Created Time: Mon 04 Jul 2016 03:41:51 PM CST
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
typedef pair<int, int>p;
typedef long long ll;
const int maxn = 1e6 + 5, mod = 1e9 + 7, oo = 0x3f3f3f3f;
ll f[maxn];
int main (void)
{
	f[3] = 0;
	for(ll x = 4; x <= 1000000; x++){
		f[x] = f[x - 1] + ((x - 1) * (x - 2) / 2 - (x - 1) / 2) / 2;
	}
	ll n;
	while(cin>>n && n >= 3){
		cout<<f[n]<<endl;
	}
	return 0;
}

L.Cheerleaders(容斥)

题意：

一个$n \times m$的矩阵中放$k$个人， 要求矩阵的第一列、最后一列、第一行和最后一行都必须有人。问有多少种放法。

分析：

正难则反。
四边都有人的情况不好判断，四边中有一边没有人的情况好判断，我们可以枚举四边中存在一边没人时四边的情况，然后容斥一下，用全集减去即可。

代码：

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
/*************************************************************************
	> File Name: L.cpp
	> Author: jiangyuzhu
	> Mail: 834138558@qq.com 
	> Created Time: Tue 05 Jul 2016 09:56:56 AM CST
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
typedef pair<int, int>p;
const int maxn = 400 + 5, maxm = 500 + 5, mod = 1e6 + 7, oo = 0x3f3f3f3f;
int C[maxn][maxm];
void init()
{
	memset(C, 0, sizeof(C));
	C[0][0] = 1;
	for(int i = 1; i < maxn; i++){
		C[i][0] = C[i][i] = 1;
		for(int j = 1; j < i; j++){
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
		}
	}
}
int main (void)
{
	int T;scanf("%d",&T);
	init();
	for(int tt = 1; tt <= T; tt++){
		int ans = 0;
		int m, n, k;scanf("%d%d%d",&m, &n,&k);
		int cnt, r, c;
		for(int i = 0; i < 16; i++){
			cnt = 0, r = m, c = n;
			if(i & 1) r--, cnt++;
			if(i >> 1 & 1) r--,cnt++;
			if(i >> 2 & 1) c--, cnt++;
			if(i >> 3 & 1) c--, cnt++;
			if(cnt % 2 == 0) ans = (C[r * c][k] + ans) % mod;
			else ans = (ans - C[r * c][k] + mod) % mod;
		}
		printf("Case %d: %d\n", tt, ans);
	}
	return 0;
	
}

M.Trade(单调队列优化dp)

题意：

每天有三种选择：买入股票，卖出股票和不买不卖，给定每天的最大交易额及每股买入和卖出的价格，两次交易至少相隔$W$天并且任意时刻最多持有$maxp$的股票，问给定天数内获得的最大回报。

分析：

容易想到状态$dp[i][j]:=第i天有j个股份的最大收入,$
转移方程
买入：dp[i][j] = max{dp[i-1][j], dp[q][k]-sta[i]*(j-k)};$(1 \le q \le i -w - 1,0 \le j - k \le a[i])$
卖出：dp[i][j] = max{dp[i-1][j], dp[q][k]+sta[i]*(k-j)};$(1 \le q \le i -w - 1,0 \le k - j \le b[i])$
时间复杂度$O(maxp^2\times n^2)$
我们发现前一天的最优情况是会转移到后一天的，所以可以省去$q$的枚举，因为$i-w-1$之前天数的最优情况已经包含在$dp[i-w-1]$中了，降维后时间复杂度$O(maxp^2\times n)$
此时仅以买入为例
dp[i][j] = max{dp[i-w-1][k]-sta[i]\times (j-k)};
dp[i][j] + j * sta[i] = max{dp[i - w - 1][k] + sta[i] * k};
令$f(j) = dp[i][j] + j \times sta[i]$，
那么$f(j) = max(f(k))$，其中$ 0 \le j-k \le sta[i]$
时间复杂度$O(maxp \times n)$
对于买的情况正序，卖反序维护一下即可。

代码：

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
/*************************************************************************
	> File Name: E.cpp
	> Author: jiangyuzhu
	> Mail: 834138558@qq.com 
	> Created Time: Mon 04 Jul 2016 10:21:35 AM CST
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
typedef pair<int, int>pii;
#define sa(n) scanf("%d", &(n));
#define val second
#define num first
#define pl(a) cout<<#a<<": "<<a<<endl
const int maxn = 2e3 + 5, maxm = 2e3 + 5, mod = 1e9 + 7, oo = 0x3f3f3f3f;
pii q[maxn];
int dp[maxm][maxn];
int sta[maxm], stb[maxm];
int a[maxm], b[maxm];
int main (void)
{
	int T;sa(T);
	while(T--){
		int n, maxp, w;sa(n);sa(maxp);sa(w);
		for(int i = 0; i < n; i++){
			sa(a[i]);sa(b[i]);
			sa(sta[i]);sa(stb[i]);
		}
		for(int i = 0; i <= maxp; i++){
			for(int j = 0; j < n; j++){
				dp[j][i] = -oo;
			}
		}
		for(int i = 0; i <= w; i++){
			for(int j = 0; j <= min(sta[i], maxp); j++){
				dp[i][j] = -a[i] * j;
			}
		}	
		int head, rear;
		for(int i = 1; i < n; i++){
			for(int j = 0; j <= maxp; j++){
				dp[i][j] = max(dp[i][j], dp[i - 1][j]);
			}
			if(i < w + 1) continue;
			head = rear = 0;
			for(int j = 0; j <= maxp; j++){
				while(head < rear && dp[i - w - 1][j] + a[i] * j > q[rear - 1].val) rear--;
				q[rear++] = pii(j, dp[i - w - 1][j] + a[i] * j);
				while(head < rear && j - q[head].num > sta[i]) head++;
				if(q[head].num >= j - sta[i])
					dp[i][j] = max(dp[i][j], q[head].val - a[i] * j);
			}
			head = rear = 0;
			for(int j = maxp; j >= 0; j--){
				while(head < rear && dp[i - w - 1][j] + b[i] * j > q[rear - 1].val) rear--;
				q[rear++] = pii(j, dp[i - w - 1][j] + b[i] * j);
				while(head < rear && q[head].num - j > stb[i]) head++;
				if(q[head].num <= j + stb[i])
					dp[i][j] = max(dp[i][j], q[head].val - b[i] * j);
			}
		}
		int ans = 0;
		for(int i = 0; i <= maxp; i++){
			ans = max(ans, dp[n - 1][i]);
		}
		printf("%d\n", ans);
	}
	return 0;
}

N .Til the Cows Come Home(最短路)

题意：

求最短路

分析：

裸短路

代码：

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
/*************************************************************************
	> File Name: N.cpp
	> Author: jiangyuzhu
	> Mail: 834138558@qq.com 
	> Created Time: Mon 04 Jul 2016 10:56:14 AM CST
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
typedef pair<int, int>p;
const int maxn = 1e3 + 5, maxm = 2e3 + 5, mod = 1e9 + 7, oo = 0x3f3f3f3f;
struct EDGE{
	int to; int val; int next;
};
int tot;
EDGE edge[maxm * 2 + 5];
int head[maxn], dist[maxn];
int n;
void addedge(int u, int v, int val)
{
	edge[tot].to = v;
	edge[tot].val = val;
	edge[tot].next = head[u];
	head[u] = tot++;
	edge[tot].to = u;
	edge[tot].val = val;
	edge[tot].next = head[v];
	head[v] = tot++;
}
int dijkstra()
{
	memset(dist, 0x3f, sizeof(dist));
	priority_queue<p>q;
	q.push(p(0, n));
	dist[n] = 0;
	while(!q.empty()){
		p t = q.top();q.pop();
		if(t.first > dist[t.second]) continue;
		int u = t.second;
		dist[u] = t.first;
		for(int i = head[u]; i != -1; i = edge[i].next){
			int v = edge[i].to;
			if(dist[v] > dist[u] + edge[i].val){
				dist[v] = dist[u] + edge[i].val;
				q.push(p(dist[v], v));
			}
		}
	}
	return dist[1];
}
int main (void)
{
	int m;
	while(cin>>m>>n){
		int u, v,val;
		tot = 0;
		memset(head, -1, sizeof(head));
		for(int i = 0; i < m; i++){
			cin>>u>>v>>val;
			addedge(u, v, val);
		}
		int ans = dijkstra();
		cout<<ans<<endl;
	}
	return 0;
}

O.Heavy Transportation(Dijkstra变形)

题意：

求$1$到$n$的路径上最小值的最大值。

分析：

这题和图论专场的一道题很像，二分+dijkstra，也可以用最大生成树做，
还可以直接用变形的dijkstra做，改变$dist$数组的含义，对dijkstra进行变形是一个很巧妙的套路。令$dist[i]$表示从$1$到$i$的路径上的最小值的最大值，优先考虑$dist$较大的值，剩下的和dijsktra一个套路了。

代码：

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
/*************************************************************************
	> File Name: O.cpp
	> Author: jiangyuzhu
	> Mail: 834138558@qq.com 
	> Created Time: Mon 04 Jul 2016 04:55:03 PM CST
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define sa(x) scanf("%d", &(x))
typedef pair<int, int>p;
const int maxn = 1e3 + 5, mod = 1e9 + 7, oo = 0x3f3f3f3f;
int tot;
int map[maxn][maxn];
bool vis[maxn];
int dist[maxn];
int n, m;
int dijkstra()
{
	memset(dist, 0, sizeof(dist));
	memset(vis, false, sizeof(vis));
	priority_queue<p, vector<p>, less<p> >q;
	q.push(p(oo, 1));
	dist[1] = oo;
	while(!q.empty()){
		p t = q.top();q.pop();
		int u = t.second;		
		if(vis[u]) continue;
		vis[u] = true;
		for(int i = 1; i <= n; i++){	
			if(!map[i][u]) continue;			
			if(dist[i] < min(dist[u], map[i][u])){
				dist[i] = min(dist[u], map[i][u]);
				q.push(p(dist[i], i));
			}
		}
	}
	return dist[n];
}
int main (void)
{
	int T;scanf("%d", &T);
	for(int tt = 1; tt <= T; tt++){
		scanf("%d%d", &n, &m);
		int u, v, val;
		memset(map, 0, sizeof(map));
		for(int i = 0; i < m; i++){
			scanf("%d%d%d", &u, &v, &val);
			map[u][v] = map[v][u] = val;
		}
		cout<<"Scenario #"<<tt<<":"<<endl;
		printf("%d\n\n", dijkstra());
	}
	return 0;
}

P.Toy Storage(计算几何)

题意：

一个矩形被$n$条不相交的线段分成$n+1$个方格，若干个点落在方格中，求出每个方格中点的个数并计数。

分析：

对于每个点，找到该点右边第一条线段，那么该点就落在该线段左边的方格里，
运用叉积判断点是否在线段的左边，对端点排序后二分进行查找。

叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系：
若 P × Q > 0 , 则P在Q的顺时针方向。
若 P × Q < 0 , 则P在Q的逆时针方向。
若 P × Q = 0 , 则P与Q共线，但可能同向也可能反向。

代码：

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
/*************************************************************************
	> File Name: P.cpp
	> Author: jiangyuzhu
	> Mail: 834138558@qq.com 
	> Created Time: Mon 04 Jul 2016 08:02:15 PM CST
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
typedef pair<int, int>p;
const int maxn = 5e3 + 5, mod = 1e9 + 7, oo = 0x3f3f3f3f;
struct Point
{
    int x, y;
    Point(){}
    Point(int _x,int _y){
        x = _x; y = _y;
    }
    Point operator -(const Point &b)const{
        return Point(x - b.x, y - b.y);
    }
    int operator *(const Point &b)const{
        return x * b.x + y * b.y;
    }
    int operator ^(const Point &b)const{
        return x * b.y - y * b.x;
    }
};
struct Line
{
    Point s, e;
    Line(){}
    Line(Point _s,Point _e){
        s = _s;e = _e;
    }
};
Line line[maxn];
int ans[maxn];
int cnt[maxn];
int dot(Point p0, Point p1, Point p2)
{
    return (p1 - p0) ^ (p2 - p0);
}
bool cmp(Line a,Line b)
{
    return a.s.x < b.s.x;
}
int main()
{
    int n, m, x1, y1, x2, y2;
    while(~scanf("%d",&n) && n){
        scanf("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);
        int Ui, Li;
        for(int i = 0;i < n; i++){
            scanf("%d%d",&Ui, &Li);
            line[i] = Line(Point(Ui, y1), Point(Li, y2));
        }
        sort(line, line + n, cmp);
        int x, y;
        Point p;
        memset(ans, 0, sizeof(ans));
        for(int i = 0; i < m; i++){
            scanf("%d%d",&x, &y);
            p = Point(x, y);
            int l = -1, r = n;
            while(l < r - 1){
                int mid = l + r >> 1;
                if(dot(p, line[mid].s, line[mid].e) < 0) r = mid;
                else l = mid;
            }
            ans[r]++;
		}
		memset(cnt, 0, sizeof(cnt));
        for(int i = 0; i <= n; i++){
			if(ans[i] > 0) cnt[ans[i]]++;
		}
        printf("Box\n");
        for(int i = 1; i <= n; i++){
			if(cnt[i] > 0){
				printf("%d: %d\n", i, cnt[i]);
			}
	    }
	}
    return 0;
}

Q - Treasure Hunt(线段交)

题意：

$100 \times 100$的正方形围墙内有$n(n \le 30)$端点在围墙边上的墙。给定终点，问从正方形外部走到终点要经过最少多少堵墙，穿过墙时只能走中点？

分析：

$n$只有30，显然枚举入口。仔细分析我们可以发现只能走墙中点这个信息并没有什么用，因为只要是经过这堵墙，必然要穿过去，实际走的即是直线。
那么我们在枚举入口的时候只需枚举端点，然后求连接起点与终点的线段与其他所有线段的交点个数最小值即可~
顺便复习一下线段交 http://blog.csdn.net/yukizzz/article/details/50816072

代码：

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
/*************************************************************************
    > File Name: 1066.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/9/16 11:03:53
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn = 30 + 5;
double eps = 1e-8;
double add(double a, double b)
{
    if(abs(a + b) < eps * (abs(a) + abs(b)))  return 0;
    else return a + b;
}
struct P{
    double x, y;
    P() {}
    P(double x, double y) : x(x), y(y){}
    P operator + (P p){
        return P(add(x, p.x), add(y, p.y));
    }
    P operator -(P p){
        return P(add(x, -p.x), add(y, -p.y));
    }
    double dot(P p){
        return add(x * p.x, y *p.y);
    }
    double det(P p){
        return add(x * p.y, - y * p.x);
    }
    P operator *(double d){
        return P(x * d, y * d);
    }
}p[maxn << 1];
P des;
bool onseg(P p1, P p2, P q)
{
    return (p1 - q).det(p2 - q) == 0 && (p1 - q).dot(p2 - q) <= 0;
}
P intersection(P p1, P p2, P q1, P q2)
{
    return p1 + (p2 - p1) * ((q2 - q1).det(q1 - p1) / (q2 - q1).det(p2 - p1));
}
int main (void)
{
	int n;scanf("%d", &n);
	for(int i = 0; i < 2 * n; i++){
		scanf("%lf%lf", &p[i].x, &p[i].y);
	}
	int ans, res = n + 1;
	double x, y;scanf("%lf%lf", &des.x, &des.y);
	for(int i = 0; i < 2 * n; ++i){
		ans = 1;
		for(int j = 0; j < 2 * n; j += 2){
			if(j == i || j == i - 1) continue;
			P tmp = intersection(p[i], des, p[j], p[j + 1]);
			ans += onseg(p[j], p[j + 1], tmp) && onseg(p[i], des, tmp); 
		}
		res = min(res, ans);
	}
	printf("Number of doors = %d\n", res);
	return 0;
}
文章目录
  1. 1. A. A Dangerous Maze（求期望，解方程）
    1. 1.1. 题意：
    2. 1.2. 分析：
    3. 1.3. 代码：
  2. 2. B - Article Decryption(KMP + DP)
    1. 2.1. 题意：
    2. 2.2. 分析：
    3. 2.3. 代码：
  3. 3. C.Rochambeau（带权并查集）
    1. 3.1. 题意：
    2. 3.2. 分析：
    3. 3.3. 代码：
  4. 4. D.India and China Origins(二分+bfs or dsu)
    1. 4.1. 题意：
    2. 4.2. 分析：
    3. 4.3. 代码：
  5. 5. E.Edit distance（贪心）
    1. 5.1. 题意：
    2. 5.2. 分析：
    3. 5.3. 代码：
  6. 6. F. Task (贪心)
    1. 6.1. 题意：
    2. 6.2. 分析：
    3. 6.3. 代码：
  7. 7. G.Optimal Milking(二分 + 最大流)
    1. 7.1. 题意:
    2. 7.2. 分析：
    3. 7.3. 代码：
  8. 8. H - Special Fish(KM)
    1. 8.1. 题意：
    2. 8.2. 分析：
    3. 8.3. 代码：
  9. 9. I.Bear and Bowling 4(斜率优化dp)
    1. 9.1. 题意：
    2. 9.2. 分析：
    3. 9.3. 代码：
  10. 10. J. Domino(欧拉路径)
    1. 10.1. 题意:
    2. 10.2. 分析：
    3. 10.3. 代码：
  11. 11. K.Triangle Counting(数学)
    1. 11.1. 题意：
    2. 11.2. 分析：
    3. 11.3. 代码：
  12. 12. L.Cheerleaders(容斥)
    1. 12.1. 题意：
    2. 12.2. 分析：
    3. 12.3. 代码：
  13. 13. M.Trade(单调队列优化dp)
    1. 13.1. 题意：
    2. 13.2. 分析：
    3. 13.3. 代码：
  14. 14. N .Til the Cows Come Home(最短路)
    1. 14.1. 题意：
    2. 14.2. 分析：
    3. 14.3. 代码：
  15. 15. O.Heavy Transportation(Dijkstra变形)
    1. 15.1. 题意：
    2. 15.2. 分析：
    3. 15.3. 代码：
  16. 16. P.Toy Storage(计算几何)
    1. 16.1. 题意：
    2. 16.2. 分析：
    3. 16.3. 代码：
  17. 17. Q - Treasure Hunt(线段交)
    1. 17.1. 题意：
    2. 17.2. 分析：
    3. 17.3. 代码：