A - A Hard Problem

题意：从 {1,2,⋯,n}中任意选择长度为 k的子集， 保证存在两个数 a, b，a是b的因子。求出最小的 k值。

题解：规律题 k = (n+3)/2
n = 2 3 4 5 6 7 8 9 …
k = 2 3 3 4 4 5 5 6 …

代码：

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 endl "\n"
#define ll long long
#define inf 0x3f3f3f3f
#define IOS ios::sync_with_stdio(0); cin.tie(0)
#define debug(a) cout<<"*****\tdebug: "<<a<<"\t*****"<<endl;
const double eps = 1e-10;
const int mod = 1e9+7;
const int N = 5 + 1e6;

int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.in", "r", stdin);
	freopen("out.out", "w", stdout);
#endif
	IOS;

// ---------------------------------------------------------------
	int T; cin>>T;
	while(T--)
	{
		int n; cin>>n;
		cout<<(n+3)/2<<endl;
	}
	return 0;
}

C - Digital Path

题意：给定一个 n*m的数字矩阵，从入度为 0的点开始，向上下左右四个方向且增值为 1的方向走，求所有长度大于等于 4的路径数。
答案为 4的示例：

题解：从入度为 0的点向四周搜索，用 dp[i][j][x]代表到点 (i,j)的路径长度为 x的路径数，特别说明 dp[i][j][4]代表路径长度大于等于4的路径数。
递推方程：
dp[xx][yy][k] += dp[x][y][k-1] (2<k<4)
dp[xx][yy][4] += dp[x][y][3] + dp[x][y][4]

代码：

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<bits/stdc++.h>
using namespace std;

#define endl "\n"
#define ll long long
#define inf 0x3f3f3f3f
#define IOS ios::sync_with_stdio(0); cin.tie(0)
#define debug(a) cout<<"*****\tdebug: "<<a<<"\t*****"<<endl;
const double eps = 1e-10;
const int mod = 1e9+7;
const int N = 5 + 1e3;

int n, m;
int g[N][N], in[N][N], out[N][N], vis[N][N];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int dp[N][N][4];

void dfs()
{
	queue<pair<int, int> > q;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			if(!in[i][j])
			{
				dp[i][j][1] = 1;
				q.push(make_pair(i, j));
			}
		}
	}
	while(q.size())
	{
		int x = q.front().first, y = q.front().second;
		q.pop();
		for(int k = 0; k < 4; k++)
		{
			int xx = x + dx[k], yy = y + dy[k];
			if(xx < 1 || xx > n || yy < 1 || yy > m) continue;
			if(g[x][y]+1 == g[xx][yy])
			{
				(dp[xx][yy][2] += dp[x][y][1]) %= mod;
				(dp[xx][yy][3] += dp[x][y][2]) %= mod;
				(dp[xx][yy][4] += dp[x][y][3] + dp[x][y][4]) %= mod;
				if(--in[xx][yy] == 0) q.push(make_pair(xx, yy));
			}
		}
	}
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.in", "r", stdin);
	freopen("out.out", "w", stdout);
#endif
	IOS;
// ---------------------------------------------------------------
	cin>>n>>m;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin>>g[i][j];
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			for(int k = 0; k < 4; k++)
			{
				int x = i+dx[k], y = j+dy[k];
				if(x < 1 || x > n || y < 1 || y > m) continue;
				if(g[i][j] == g[x][y]-1) out[i][j]++;
				if(g[i][j] == g[x][y]+1) in[i][j]++;
			}
		}
	}
	dfs();
	int ans = 0;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			if(!out[i][j]) (ans += dp[i][j][4]) %= mod;
		}
	}
	cout<<ans<<endl;
	return 0;
}

H - Prince and Princess

题意：你要在 n个房间中找到公主在哪，每个房间有一个人，他们彼此知道谁在哪个房间。你可以每次问任意一个房间里的人三个问题之一：
1、你的名字是什么？
2、在第 x个房间里的人的名字是什么？
3、公主在哪个房间？

这n个人可以分为三类：一类一定说真话；一类一定说假话；一类可能说真话可能说假话。你知道这三类人的人数分别为 a,b,c，求能否通过问若干个问题，保证一定能找到公主在哪，如果能，输出YES和最少需要的问题数；如果不能，输出NO。

题解：既然要保证能找到，所以就分析最坏的请况：第三类人全说的谎话。然后先问了(b+c)次第三个问题，全是错的（把错的全问完）， 然后再问 (b+c+1)次问题， 全是正确的，这样就刚好能确定公主的位置（正确的 > 错误的），这种情况只有在 a > b+c时才可能发生，答案为 2*(b+c)+1。
还有一个重要的点：公主在房间中****。所以 a = 1 b = 0 c = 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
#include<bits/stdc++.h>
using namespace std;

#define endl "\n"
#define ll long long
#define inf 0x3f3f3f3f
#define IOS ios::sync_with_stdio(0); cin.tie(0)
#define debug(a) cout<<"*****\tdebug: "<<a<<"\t*****"<<endl;
const double eps = 1e-10;
const int mod = 1e9+7;
const int N = 5 + 1e6;



int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.in", "r", stdin);
	freopen("out.out", "w", stdout);
#endif
	IOS;

// ---------------------------------------------------------------
	int a, b, c; cin>>a>>b>>c;
	if(a > b+c) 
	{
		if(a == 1) cout<<"YES"<<endl<<0<<endl;
		else cout<<"YES"<<endl<<2*(b+c)+1<<endl;
	}
	else cout<<"NO"<<endl;
	return 0;
}

J - Spy

题意：你和我要打架，我有一队人 n个，武力值为 a[]，赏金为 p[]。你有两队人 2n个，武力值为 b[]和 c[]，现在你要把两队人合并为一队（两两配对），新武力值为本来两人之和。每个人只能战斗一次。
你的人打赢我的人，就获得相应的赏金，战斗随机，求你得到的赏金的期望值乘以n。

题解：把队伍 b[] 和 c[]当作二部图，边的权值为这对组合能获得的赏金之和。然后跑一遍KM。最佳匹配的边的权值之和即为答案。 n<400， 用O($n^3$)的KM算法

链接：$O(n^3)$的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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<bits/stdc++.h>
using namespace std;

#define endl "\n"
#define ll long long
#define inf 0x3f3f3f3f
#define infll 1e15+7
#define IOS ios::sync_with_stdio(0); cin.tie(0)
#define debug(a) cout<<"*****\tdebug: "<<a<<"\t*****"<<endl;
const double eps = 1e-10;
const int mod = 1e9+7;
const int N = 5 + 400;

ll w[N][N]; 
ll la[N], lb[N], upd[N]; 
bool va[N], vb[N]; 
ll match[N]; 
ll last[N]; 
int n;

ll a[N], p[N], b[N], c[N];

bool dfs(ll x, ll fa) 
{
    va[x] = 1;
    for(int y = 1; y <= n; y++)
    {
		if(!vb[y])
        {
			if(la[x] + lb[y] == w[x][y]) 
			{ 
                vb[y] = 1; last[y] = fa;
                if(!match[y] || dfs(match[y], y)) 
				{
                    match[y] = x;
                    return true;
                }
            }
            else if(upd[y] > la[x] + lb[y] - w[x][y]) 
			{
                upd[y] = la[x] + lb[y] - w[x][y];
                last[y] = fa;
            }
		}
	}
    return false;
}

ll KM() 
{
    for(int i = 1; i <= n; i++) 
	{
        la[i] = -infll;	// !!!
        lb[i] = 0;
        for(int j = 1; j <= n; j++) la[i] = max(la[i], w[i][j]);
    }
    for(int i = 1; i <= n; i++) 
	{
        memset(va, 0, sizeof(va));
        memset(vb, 0, sizeof(vb));
        for(int j = 1; j <= n; j++) upd[j] = infll;	// !!!
       
        int st = 0; match[0] = i;
        while(match[st]) 	
		{ 
            ll delta = infll; // !!!
            if(dfs(match[st], st)) break;
            for(int j = 1; j <= n; j++)
                if(!vb[j] && delta > upd[j]) 
				{
                    delta = upd[j];
                    st = j; 		
                }
            for(int j = 1; j <= n; j++)  
			{
                if(va[j]) la[j] -= delta;
                if(vb[j]) lb[j] += delta; 
				else upd[j] -= delta;
            }
            vb[st] = true;
        }
        while(st)	
		{ 
            match[st] = match[last[st]];
            st = last[st];
        }
    }
	ll ans = 0;
	for(int i = 1; i <= n; i++) 
		if(match[i]) ans += w[match[i]][i];
	return ans;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.in", "r", stdin);
	freopen("out.out", "w", stdout);
#endif
	IOS;
// ---------------------------------------------------------------
	cin>>n;
	for(int i = 1; i <= n; i++) cin>>a[i];
	for(int i = 1; i <= n; i++) cin>>p[i];
	for(int i = 1; i <= n; i++) cin>>b[i];
	for(int i = 1; i <= n; i++) cin>>c[i];

	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			ll sum = 0;
			for(int k = 1; k <= n; k++)
				if(a[k] < b[i]+c[j]) sum += p[k];
			w[i][j] = sum;
		}
	}
	cout<<KM()<<endl;
	return 0;
}

K - Triangle

题意：给定一个三角形ABC的三个顶点，再给定一个点 p，求另一个点 x的坐标，使得 px的连线平分三角形ABC的面积。假如点 p不在三角形的边上就不合法，输出 -1。

题解：分类讨论 + 二分（也可以通过解方程求）。分类在于，先判断点 p在哪条边上，然后通过点 p离所在边的两个端点的距离大小，判断点 x在对面的哪一条边上。对每一类，二分点 x所在的边，通过面积关系做判断依据，找到点 x的坐标。
注意交版本低一点的，例如G++14能过，但G++20过不了。

代码：

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
#include<bits/stdc++.h>
using namespace std;

#define endl "\n"
#define ll long long
#define inf 0x3f3f3f3f
#define infll 1e15+7
#define IOS ios::sync_with_stdio(0); cin.tie(0)
#define debug(a) cout<<"*****\tdebug: "<<a<<"\t*****"<<endl;
const double eps = 1e-7;
const double pi = acos(-1.0);
const int mod = 1e9+7;
const int N = 5 + 400;

inline double sqr(double x){return x*x;}
int sgn(double x){
    if(fabs(x) < eps)return 0;
    if(x < 0)return -1;
    else return 1;
}

struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y){
        x = _x;
        y = _y;
    }
    void input(){
        scanf("%lf%lf",&x,&y);
    }

    Point operator -(const Point &b)const{
        return Point(x-b.x,y-b.y);
    }
    //叉积
    double operator ^(const Point &b)const{
        return x*b.y - y*b.x;
    }
    //点积
    double operator *(const Point &b)const{
        return x*b.x + y*b.y;
    }

    //返回两点的距离
    double distance(Point p){
        return hypot(x-p.x,y-p.y);
    }
    Point operator +(const Point &b)const{
        return Point(x+b.x,y+b.y);
    }
    Point operator *(const double &k)const{
        return Point(x*k,y*k);
    }

};


struct Line{
    Point s,e;
    Line(){}
    Line(Point _s,Point _e){
        s = _s;
        e = _e;
    }

    // 点在线段上的判断
    bool pointonseg(Point p){
        return sgn((p-s)^(e-s)) == 0 && sgn((p-s)*(p-e)) <= 0;
    }
   
};

Point mid_(Point a, Point b)
{
	return (a+b)*0.5;
}

double area(Point a, Point b, Point c)
{
	return fabs((b - a) ^ (c - a) * 0.5);
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.in", "r", stdin);
	freopen("out.out", "w", stdout);
#endif
	// IOS;
// ---------------------------------------------------------------
	Point a, b, c ,p;
	Line ab, ac, bc;
	int T; scanf("%d", &T);
	while(T--)
	{
		a.input();
		b.input();
		c.input();
		p.input();
		ab = Line(a, b);
		ac = Line(a, c);
		bc = Line(b, c);
		if(!ab.pointonseg(p) && !bc.pointonseg(p) && !ac.pointonseg(p))
		{
			// cout<<-1<<endl;
			printf("-1\n");
			continue;
		}
		double s = area(a, b, c)/2;
		if(ab.pointonseg(p))
		{
			if(p.distance(a) < p.distance(b))
			{
				Point l = b, r = c;
				Point mid;
				int x = 50;
				while(x--)
				{
					mid = mid_(l, r);
					double ss = area(p, mid, b);
					int flag = sgn(ss-s);
					if(flag == 0) break;
					else if(flag == 1)	r = mid;
					else l = mid;
				}
				printf("%.10lf %.10lf\n", mid.x, mid.y);
			}
			else
			{
				Point l = a, r = c;
				Point mid;
				int x = 50;
				while(x--)
				{
					mid = mid_(l, r);
					double ss = area(p, mid, a);
					int flag = sgn(ss-s);
					if(flag == 0) break;
					else if(flag == 1)	r = mid;
					else l = mid;
				}
				printf("%.10lf %.10lf\n", mid.x, mid.y);
			}
		}
		else if(ac.pointonseg(p))
		{
			if(p.distance(a) < p.distance(c))
			{
				Point l = c, r = b;
				Point mid;
				int x = 50;
				while(x--)
				{
					mid = mid_(l, r);
					double ss = area(p, mid, c);
					int flag = sgn(ss-s);
					if(flag == 0) break;
					else if(flag == 1)	r = mid;
					else l = mid;
				}
				printf("%.10lf %.10lf\n", mid.x, mid.y);
			}
			else
			{
				Point l = a, r = b;
				Point mid;
				int x = 50;
				while(x--)
				{
					mid = mid_(l, r);
					double ss = area(p, mid, a);
					int flag = sgn(ss-s);
					if(flag == 0) break;
					else if(flag == 1)	r = mid;
					else l = mid;
				}
				printf("%.10lf %.10lf\n", mid.x, mid.y);
			}
		}
		else
		{
			if(p.distance(b) < p.distance(c))
			{
				Point l = c, r = a;
				Point mid;
				int x = 50;
				while(x--)
				{
					mid = mid_(l, r);
					double ss = area(p, mid, c);
					int flag = sgn(ss-s);
					if(flag == 0) break;
					else if(flag == 1)	r = mid;
					else l = mid;
				}
				printf("%.10lf %.10lf\n", mid.x, mid.y);
			}
			else
			{
				Point l = b, r = a;
				Point mid;
				int x = 50;
				while(x--)
				{
					mid = mid_(l, r);
					double ss = area(p, mid, b);
					int flag = sgn(ss-s);
					if(flag == 0) break;
					else if(flag == 1)	r = mid;
					else l = mid;
				}
				printf("%.10lf %.10lf\n", mid.x, mid.y);
			}
		}
	}
	return 0;
}