Codeforces Round #465

分类: IT文章 • 2022-08-25 13:33:07

A. Fafa and his Company

方法：暴力枚举leader的个数即可

code：

 1 /*
 2  by skydog
 3  */
 4 #include <iostream>
 5 #include <cstdio>
 6 #include <vector>
 7 #include <utility>
 8 #include <algorithm>
 9 #include <cmath>
10 #include <cstring>
11 #include <map>
12 #include <set>
13 #include <stack>
14 #include <queue>
15 #include <deque>
16 #include <cassert>
17 #include <list>
18 using namespace std;
19 typedef long long ll;
20 typedef pair<int, int> ii;
21 typedef pair<ll, ll> l4;
22 
23 #define mp make_pair
24 #define pb push_back
25 #define db(x) cerr << #x << " = " << x << endl
26 
27 
28 int main()
29 {
30     int n;
31     scanf("%d", &n);
32     int ans = 0;
33     for (int i = 1; i < n; ++i)
34         if ((n-i)%i == 0)
35             ++ans;
36     printf("%d
", ans);
37 }

View Code

B. Fafa and the gates

方法：暴力模拟

code：

 1 /*
 2  by skydog
 3  */
 4 #include <iostream>
 5 #include <cstdio>
 6 #include <vector>
 7 #include <utility>
 8 #include <algorithm>
 9 #include <cmath>
10 #include <cstring>
11 #include <map>
12 #include <set>
13 #include <stack>
14 #include <queue>
15 #include <deque>
16 #include <cassert>
17 #include <list>
18 using namespace std;
19 typedef long long ll;
20 typedef pair<int, int> ii;
21 typedef pair<ll, ll> l4;
22 
23 #define mp make_pair
24 #define pb push_back
25 #define db(x) cerr << #x << " = " << x << endl
26 
27 
28 int n;
29 const int maxn = 1e5+1;
30 char s[maxn];
31 int get(int x, int y)
32 {
33     if (x == y)
34         return 0;
35     if (x > y)
36         return 1;
37     else
38         return -1;
39 }
40 
41 int main()
42 {
43     scanf("%d %s", &n, s);
44     int cur = 0, ans = 0;
45     int x = 0, y = 0;
46     for (int i = 0; i < n; ++i)
47     {
48         if (s[i] == 'U')
49             ++y;
50         else
51             ++x;
52         int tmp = get(x, y);
53         if (tmp)
54         {
55             if (tmp == -cur)
56             {
57                 ++ans;
58             }
59             cur = tmp;
60         }
61     }
62     printf("%d
", ans);
63 }

View Code

C. Fifa and Fafa

题意：给你一个圆和一个点，让你在给定圆内画一个圆，使得答案圆不能包含给定点，而且使得给定圆没有被答案圆覆盖的面积最小。给出答案圆的圆心和半径即可。

观察：给定圆没有被覆盖的面积最小，即使答案圆面积最大。如果给定点在给定圆之外，那么答案圆等于给定圆。如果给定点在给定圆之内，只需特判一下给定点和圆心重合的情况，剩下的情况，答案圆可以被唯一确定，即作给定点到给定圆圆心的射线，交给定圆与一交点。以交点和给定点之间线段为直径的圆就是答案。

code：

 1 /*
 2  by skydog
 3  */
 4 #include <iostream>
 5 #include <cstdio>
 6 #include <vector>
 7 #include <utility>
 8 #include <algorithm>
 9 #include <cmath>
10 #include <cstring>
11 #include <map>
12 #include <set>
13 #include <stack>
14 #include <queue>
15 #include <deque>
16 #include <cassert>
17 #include <list>
18 using namespace std;
19 typedef long long ll;
20 typedef pair<int, int> ii;
21 typedef pair<ll, ll> l4;
22 
23 #define mp make_pair
24 #define pb push_back
25 #define db(x) cerr << #x << " = " << x << endl
26 
27 
28 ll r, x1, yy1, x2, y2;
29 ll dis()
30 {
31     ll dx = x1-x2, dy = yy1-y2;
32     return dx*dx + dy*dy;
33 }
34 void end(double x, double y, double r)
35 {
36     printf("%.6lf %.6lf %.6lf
", x, y, r);
37     exit(0);
38 }
39 int main()
40 {
41     scanf("%lld %lld %lld %lld %lld", &r, &x1, &yy1, &x2, &y2);
42     if (dis() >= r*r)
43         end(x1, yy1, r);
44     if (dis() == 0)
45         end(x1+r/2.0, yy1, r/2.0);
46     double R = (sqrt(dis())+r)/2.0;
47     double dx = (x1-x2), dy = (yy1-y2);
48     dx *= R/sqrt(dis()), dy *= R/sqrt(dis());
49     end(x2+dx, y2+dy, R);
50     
51 
52 }

View Code

D. Fafa and Ancient Alphabet

题意：给你两个长度为n的字符串a, b，字母表大小是m，1 <= n, m <= 1e5。字符串中有一些字符是问号。让你把问好替换成字母表中的数字，问你有多少种方法可以是第一个字符串的字典序大于第二个。

观察：一位一位的讨论即可。

code：

 1 /*
 2  by skydog
 3  */
 4 #include <iostream>
 5 #include <cstdio>
 6 #include <vector>
 7 #include <utility>
 8 #include <algorithm>
 9 #include <cmath>
10 #include <cstring>
11 #include <map>
12 #include <set>
13 #include <stack>
14 #include <queue>
15 #include <deque>
16 #include <cassert>
17 #include <list>
18 using namespace std;
19 typedef long long ll;
20 typedef pair<int, int> ii;
21 typedef pair<ll, ll> l4;
22 
23 #define mp make_pair
24 #define pb push_back
25 #define db(x) cerr << #x << " = " << x << endl
26 
27 const int mod = 1e9+7;
28 ll power(ll base, ll p)
29 {
30     ll ret = 1;
31     while (p)
32     {
33         if (p&1)
34             ret = ret * base % mod;
35         base = base * base % mod;
36         p >>= 1;
37     }
38     return ret;
39 }
40 const int maxn = 1e5+1;
41 int n, m;
42 ll p[maxn<<1];
43 int a[2][maxn];
44 int main()
45 {
46     scanf("%d %d", &n, &m);
47     int tot = 0;
48     for (int i = 0; i < 2; ++i)
49         for (int j = 0; j < n; ++j)
50             scanf("%d", &a[i][j]), tot += !a[i][j];
51     p[0] = 1;
52     for (int i = 1; i < maxn*2; ++i)
53         p[i] = p[i-1] * m % mod;
54     ll ans = 0;
55     ll base = 1;
56     ll cnt = 0;
57     for (int i = 0; i < n; ++i)
58     {
59         cnt += !a[0][i];
60         cnt += !a[1][i];
61         if (!a[0][i] && !a[1][i])
62         {
63             ans = (ans + base * p[tot-cnt] % mod * (1ll * m * (m-1) / 2 % mod) % mod) % mod;
64             base = base * m % mod;
65         }
66         else if (!a[0][i])
67         {
68             ans = (ans + base * p[tot-cnt] % mod * (m-a[1][i]) % mod) % mod;
69         }
70         else if (!a[1][i])
71         {
72             ans = (ans + base * p[tot-cnt] % mod * (a[0][i]-1) % mod) % mod;
73         }
74         else if (a[0][i] > a[1][i])
75         {
76             ans = (ans + base * p[tot-cnt] % mod) % mod;
77             break;
78         }
79         else if (a[0][i] < a[1][i])
80         {
81             break;
82         }
83     }
84     ans = ans * power(p[tot], mod-2) % mod;
85     printf("%lld
", ans);
86 }

View Code

E. Fafa and Ancient Mathematics

题意：定义合法表达式：一个单数位的正整数（即1-9）是一个合法的表达式。对于任意两个表达式E1和E2，(E1+E2), (E1-E2)都是合法的表达式。下面给你一个长度不超过1e4的表达式，其中所有运算符号（即+和-）都被替换成了？。又告诉你这些问号中，p个是+，剩下的n个是-，min(p, n) <= 100。让你输出表达式最大可能的值。

观察：可以发现表达式是一颗二叉树。很容易想到一个dp，maxi[cur][cnt+][cnt-]（(mini[cur][cnt+][cnt-]）表示在cur表达式中，或者说cur表达式对应的子树中，填cnt+个+和cnt-个-，能得到的最大值（最小值）。因为题目保证min(p, n) <= 100，而且是二叉树，所以可以把总数量较小的符号记入状态，比如p <= n, maxi[cur][cnt] /mini[cur][cnt]，表示cur子树中填cnt个加号能得到的最大值/最小值。计算maxi[cur][cnt]/mini[cur][cnt] 只需要枚举左右子树内的加号个数，和中间符号是+还是-就好了。

code：

  1 /*
  2  by skydog
  3  */
  4 #include <iostream>
  5 #include <cstdio>
  6 #include <vector>
  7 #include <utility>
  8 #include <algorithm>
  9 #include <cmath>
 10 #include <cstring>
 11 #include <map>
 12 #include <set>
 13 #include <stack>
 14 #include <queue>
 15 #include <deque>
 16 #include <cassert>
 17 #include <list>
 18 using namespace std;
 19 typedef long long ll;
 20 typedef pair<int, int> ii;
 21 typedef pair<ll, ll> l4;
 22 
 23 #define mp make_pair
 24 #define pb push_back
 25 #define db(x) cerr << #x << " = " << x << endl
 26 
 27 const int maxn = 1e4+1;
 28 char s[maxn];
 29 int sz = 0, ptr = 0;
 30 vector<int> g[maxn];
 31 const int maxp = 101;
 32 int maxi[maxn][maxp];
 33 int mini[maxn][maxp];
 34 int v[maxn];
 35 int p, m;
 36 bool isp;
 37 inline void Max(int &a, int b)
 38 {
 39     if (a < b) a = b;
 40 }
 41 inline void Min(int &a, int b)
 42 {
 43     if (a > b) a = b;
 44 }
 45 int dfs(int cur)
 46 {
 47     fill(maxi[cur], maxi[cur]+maxp, -1e5);
 48     fill(mini[cur], mini[cur]+maxp, 1e5);
 49     if (isdigit(s[ptr]))
 50     {
 51         v[cur] = s[ptr]-'0';
 52         ++ptr;
 53         maxi[cur][0] = mini[cur][0] = v[cur];
 54         return 0;
 55     }
 56     assert(s[ptr] == '(');
 57     ++ptr;
 58     int lhs, rhs, ret = 1;
 59     g[cur].pb(++sz);
 60     ret += dfs(lhs = sz);
 61     assert(s[ptr] == '?');
 62     ++ptr;
 63     g[cur].pb(++sz);
 64     ret += dfs(rhs = sz);
 65     assert(s[ptr] == ')');
 66     ++ptr;
 67     if (isp)
 68     {
 69         //limited positive
 70         for (int tot = 1; tot < maxp; ++tot)
 71         {
 72             //pick mid to be positive
 73             for (int i = 0; i <= tot-1; ++i)
 74             {
 75                 Max(maxi[cur][tot], maxi[lhs][i]+maxi[rhs][tot-1-i]);
 76                 Min(mini[cur][tot], mini[lhs][i]+mini[rhs][tot-1-i]);
 77             }
 78         }
 79         for (int tot = 0; tot < maxp; ++tot)
 80         {
 81             //pick mid to be negative
 82             for (int i = 0; i <= tot; ++i)
 83             {
 84                 Max(maxi[cur][tot], maxi[lhs][i]-mini[rhs][tot-i]);
 85                 Min(mini[cur][tot], mini[lhs][i]-maxi[rhs][tot-i]);
 86             }
 87         }
 88     }
 89     else
 90     {
 91         //limited negative
 92         for (int tot = 0; tot < maxp; ++tot)
 93         {
 94             //pick mid to be positive
 95             for (int i = 0; i <= tot; ++i)
 96             {
 97                 Max(maxi[cur][tot], maxi[lhs][i]+maxi[rhs][tot-i]);
 98                 Min(mini[cur][tot], mini[lhs][i]+mini[rhs][tot-i]);
 99             }
100         }
101         for (int tot = 1; tot < maxp; ++tot)
102         {
103             //pick mid to be negative
104             for (int i = 0; i <= tot-1; ++i)
105             {
106                 Max(maxi[cur][tot], maxi[lhs][i]-mini[rhs][tot-1-i]);
107                 Min(mini[cur][tot], mini[lhs][i]-maxi[rhs][tot-1-i]);
108             }
109         }
110     }
111     return ret;
112 }
113 int main()
114 {
115     scanf("%s %d %d", s, &p, &m);
116     isp = p <= m;
117     sz = 1;
118     ptr = 0;
119     assert(dfs(1) == p+m);
120     
121     printf("%d
", maxi[1][min(p, m)]);
122 }

View Code

WA：+和-写反。dp时候直接按照最大值枚举就好了，不需要特殊处理。

Codeforces Round #465

相关推荐