2019西北工业大学程序设计创新实践基地春季选拔赛(重现赛)
分类:
IT文章
•
2022-05-06 21:41:45
A、Chino with Geometry
思路：简单数学。过点A作直线BC的垂线交于点F，然后根据勾股定理就可以化简出 $ |BD| imes |BE| = |AB|^2 - r^2$ 。注意要开long long！
AC代码：
![]()
1 #include <cstdio>
2 #include <cstring>
3 #include <cstdlib>
4 #include <cmath>
5 #include <iostream>
6 #include <algorithm>
7 #include <iomanip>
8 #include <complex>
9 #include <string>
10 #include <vector>
11 #include <set>
12 #include <map>
13 #include <list>
14 #include <deque>
15 #include <queue>
16 #include <stack>
17 #include <bitset>
18 using namespace std;
19 typedef long long LL;
20 typedef unsigned long long ULL;
21 const int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 上右下左
22 const int mx[8] = {-1, -2, -2, -1, 1, 2, 2, 1}; // 马可走的八个方向
23 const int my[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
24 const double eps = 1e-6;
25 const double PI = acos(-1.0);
26 const int maxn = 1e5+5;
27 const int inf = 0x3f3f3f3f;
28
29 LL x_0, y_0, r, x_1, y_1, y_2;
30
31 int main() {
32 while(cin >> x_0 >> y_0 >> r >> x_1 >> y_1 >> y_2) {
33 cout << ((x_0 - x_1) * (x_0 - x_1) + (y_0 - y_1) * (y_0 - y_1)) - r * r << endl;
34 }
35 return 0;
36 }
View Code
B、Chino with Repeater
思路：简单贪心。每次翻倍复读即可。
AC代码：
![]()
1 #include <cstdio>
2 #include <cstring>
3 #include <cstdlib>
4 #include <cmath>
5 #include <iostream>
6 #include <algorithm>
7 #include <iomanip>
8 #include <complex>
9 #include <string>
10 #include <vector>
11 #include <set>
12 #include <map>
13 #include <list>
14 #include <deque>
15 #include <queue>
16 #include <stack>
17 #include <bitset>
18 using namespace std;
19 typedef long long LL;
20 typedef unsigned long long ULL;
21 const int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 上右下左
22 const int mx[8] = {-1, -2, -2, -1, 1, 2, 2, 1}; // 马可走的八个方向
23 const int my[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
24 const double eps = 1e-6;
25 const double PI = acos(-1.0);
26 const int maxn = 1e5+5;
27 const int inf = 0x3f3f3f3f;
28
29 LL n, sum, ans;
30
31 int main() {
32 while(cin >> n) {
33 sum = 1LL;
34 ans = 0LL;
35 while(sum < n) {
36 sum <<= 1;
37 ++ans;
38 }
39 cout << ans << endl;
40 }
41 return 0;
42 }
View Code
D、Chino with Equation
思路：经典的隔板法。
咋们来举2个简单的栗子：
①求方程 $ x + y + z = 10 $ 的正整数解的个数。
解：相当于先将10个1摆好，然后在9个空隙中插入2块隔板，则将10个1分成3部分，每部分至少有1个1，取法有 $ C_{10-1}^{3-1} = C_{9}^{2} $。
②求方程 $ x + y + z = 10 $ 的非负整数解的个数。
解：相当于将10个1和2块隔板随便摆（一共12个位置），最终总能分成3部分，且至少有1部分有1~n个1，其余部分不要求（可以为0也可以不为0）。于是先从12个位置中挑2个位置放隔板，剩下的位置放1，取法有$ C_{10+3-1}^{3-1} = C_{12}^{2} $。
了解了上面2个栗子之后，这道题就轻而易举了，该方程的正整数解有 $ C_{n-1}^{m-1} $ 个，非负整数解有 $ C_{n+m-1}^{m-1} $ 个。因为 m和n的值不超过 $ 10^6 $，且是组合数取模大质数，所以用卢卡斯定理求解即可。
AC代码：
![]()
1 #include <cstdio>
2 #include <cstring>
3 #include <cstdlib>
4 #include <cmath>
5 #include <iostream>
6 #include <algorithm>
7 #include <iomanip>
8 #include <complex>
9 #include <string>
10 #include <vector>
11 #include <set>
12 #include <map>
13 #include <list>
14 #include <deque>
15 #include <queue>
16 #include <stack>
17 using namespace std;
18 typedef long long LL;
19 typedef unsigned long long ULL;
20 const double eps = 1e-6;
21 const double PI = acos(-1.0);
22 const int maxn = 1e5+5;
23 const int inf = 0x3f3f3f3f;
24 const int p = 1e9+7;
25
26 LL m, n;
27
28 LL quick_mul(LL a, LL b, LL mod){
29 LL res = 0LL;
30 while(b) {
31 if(b & 1) res = (res + a) % mod;
32 a = (a + a) % mod;
33 b >>= 1;
34 }
35 return res;
36 }
37
38 LL quick_mod(LL a, LL b, LL mod) {
39 LL res = 1LL;
40 while(b) {
41 if(b & 1) res = quick_mul(res, a, mod);
42 a = quick_mul(a, a, mod);
43 b >>= 1;
44 }
45 return res;
46 }
47
48 LL comb(LL n, LL m, LL mod) {
49 if(n < m) return 0LL;
50 if(n - m < m) m = n - m;
51 LL x = 1LL, y = 1LL;
52 for(LL i = 1LL; i <= m; ++i) x = x * (n - i + 1LL) % mod, y = y * i % mod;
53 return x * quick_mod(y, mod - 2LL, mod) % mod;
54 }
55
56 LL Lucas(LL n, LL m, LL mod) {
57 if(n < mod && m < mod) return comb(n, m, mod);
58 return comb(n % mod, m % mod, mod) * Lucas(n / mod, m / mod, mod) % mod;
59 }
60
61
62 int main() {
63 while(cin >> m >> n) {
64 cout << Lucas(n - 1, m - 1, p) << ' ' << Lucas(n + m - 1, m - 1, p) << endl;
65 }
66 return 0;
67 }
View Code
F、Chino with Expectation
思路：简单数学求期望值。对于询问"1 2 3"，不难想到有以下5种情况：(2,2,3,4,5)，(1,3,3,4,5)，(1,2,4,4,5)，(1,2,3,5,5)，(1,2,3,4,6)。显然，每种情况等概率出现即 $ frac{1}{n} $，于是将红色部分求和（用前缀和的差求子区间和）除以 $ (rt-lt+1) $ 再乘上其概率 $frac{1}{n} $ 即可。
AC代码：
![]()
1 #include <cstdio>
2 #include <cstring>
3 #include <cstdlib>
4 #include <cmath>
5 #include <iostream>
6 #include <algorithm>
7 #include <iomanip>
8 #include <complex>
9 #include <string>
10 #include <vector>
11 #include <set>
12 #include <map>
13 #include <list>
14 #include <deque>
15 #include <queue>
16 #include <stack>
17 #include <bitset>
18 using namespace std;
19 typedef long long LL;
20 typedef unsigned long long ULL;
21 const int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 上右下左
22 const int mx[8] = {-1, -2, -2, -1, 1, 2, 2, 1}; // 马可走的八个方向
23 const int my[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
24 const double eps = 1e-6;
25 const double PI = acos(-1.0);
26 const int maxn = 1e5+5;
27 const int inf = 0x3f3f3f3f;
28
29 int n, q, lt, rt, len;
30 double x, a, now, per[maxn], sum[maxn];
31
32 int main() {
33 while(~scanf("%d%d", &n, &q)) {
34 per[0] = 0;
35 for(int i = 1; i <= n; ++i) {
36 scanf("%lf", &a);
37 per[i] = per[i - 1] + a;
38 }
39 while(q--) {
40 scanf("%lf%d%d", &x, <, &rt);
41 len = rt - lt + 1;
42 now = per[rt] - per[lt - 1];
43 printf("%.6f
", ((n - len) * now + len * (now + x)) / len / n);
44 }
45 }
46 return 0;
47 }
View Code
思路：简单的bfs。先将起点出发的4个方向加入队列中，然后用优先队列每次维护当前转弯次数最少的坐标点，注意走过的坐标点可能再次走到，因为我们的目标是转弯次数最少而不是步数最少，这点应该不难想到。对于是否转弯只需简单判断一下上一个方向dir与当前方向i的和值是奇数还是偶数即可。
![]()
1 #include <cstdio>
2 #include <cstring>
3 #include <cstdlib>
4 #include <cmath>
5 #include <iostream>
6 #include <algorithm>
7 #include <iomanip>
8 #include <complex>
9 #include <string>
10 #include <vector>
11 #include <set>
12 #include <map>
13 #include <list>
14 #include <deque>
15 #include <queue>
16 #include <stack>
17 #include <bitset>
18 using namespace std;
19 typedef long long LL;
20 typedef unsigned long long ULL;
21 const int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 上右下左
22 const int mx[8] = {-1, -2, -2, -1, 1, 2, 2, 1}; // 马可走的八个方向
23 const int my[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
24 const double eps = 1e-6;
25 const double PI = acos(-1.0);
26 const int maxn = 2005;
27 const int inf = 0x3f3f3f3f;
28
29 int n, m, sx, sy, ex, ey, ans, carry, vis[maxn][maxn][4];
30 char mp[maxn][maxn];
31
32 struct node{int x, y, dir, cnt;} per, now;
33 deque<node> que;
34
35 bool check(int x, int y) {
36 if(x < 0 || y < 0 || x >= n || y >= m) return false;
37 return true;
38 }
39
40 int bfs(int x, int y) {
41 while(!que.empty()) que.pop_front();
42 now.x = x, now.y = y, now.cnt = 0;
43 for(int i = 0; i < 4; ++i) {
44 now.dir = i;
45 vis[x][y][i] = 0;
46 que.push_back(now);
47 }
48 while(!que.empty()) {
49 per = que.front(), que.pop_front();
50 if(per.x == ex && per.y == ey) return per.cnt;
51 for(int i = 0; i < 4; ++i) {
52 now.x = per.x + dir[i][0], now.y = per.y + dir[i][1], now.cnt = per.cnt, now.dir = i, carry = (per.dir + i) & 1;
53 if(carry) ++now.cnt;
54 if(check(now.x, now.y) && mp[now.x][now.y] != '*' && vis[now.x][now.y][i] > now.cnt) {
55 // cout << now.x << ' ' << now.y << ' ' << now.cnt << endl;
56 carry ? que.push_back(now) : que.push_front(now);
57 vis[now.x][now.y][i] = now.cnt;
58 }
59 }
60 }
61 return -1;
62 }
63
64 int main() {
65 while(~scanf("%d%d", &n, &m)) {
66 for(int i = 0; i < n; ++i) scanf("%s", mp[i]);
67 for(int i = 0; i < n; ++i) {
68 for(int j = 0; j < m; ++j) {
69 if(mp[i][j] == 'S') sx = i, sy = j;
70 else if(mp[i][j] == 'T') ex = i, ey = j;
71 }
72 }
73 memset(vis, 0x3f, sizeof(vis));
74 ans = bfs(sx, sy);
75 if(ans != -1) printf("%d
", ans);
76 else puts("troil");
77 }
78 return 0;
79 }
