2018 Multi-University Training Contest 8 Solution

A - Character Encoding

题意：用m个$0-n-1$的数去构成k，求方案数

思路：当没有0-n-1这个条件是答案为C(k+m-1, m-1),减去有大于的关于n的情况，当有i个n时的种类为C(k+m-1-i*n,m-1)个，利用容斥定理可得

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 typedef long long ll;
 6 
 7 const int MOD = 998244353;
 8 const int maxn = 1e6 + 10;
 9 
10 ll fac[maxn];
11 ll inv[maxn];
12 ll invfac[maxn];
13 
14 void Init()
15 {
16     fac[0] = inv[0] = invfac[0] = 1;
17     fac[1] = inv[1] = invfac[1] = 1;
18     for(int i = 2; i < maxn; ++i)
19     {
20         fac[i] = fac[i - 1] * i % MOD;    
21         inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
22         invfac[i] = invfac[i - 1] * inv[i] % MOD;
23     }
24 }
25 
26 ll calc(ll n, ll m)
27 {
28     if(m > n || m < 0 || n < 0) return 0;
29     return fac[n] * invfac[m] % MOD * invfac[n - m] % MOD;
30 }
31 
32 int n, m , k;
33 
34 int main()
35 {
36     Init();
37     int t;
38     scanf("%d", &t);
39     while(t--)
40     {
41         scanf("%d %d %d", &n, &m, &k);
42         ll ans = 0;
43         for(int i = 0; i <= m; ++i)
44         {
45             ll tmp = k - 1ll * i * n + m - 1;
46             if(tmp < 0) break;
47             if(i & 1) ans = (ans - calc(m, i) * calc(tmp, m - 1) % MOD + MOD) % MOD;
48             else ans = (ans + calc(m, i) * calc(tmp, m - 1) % MOD) % MOD;
49         //    cout << i << " " << m << " " << calc(m, i);
50         //    cout << tmp << " " << m - 1 << " " << calc(tmp, m - 1) << endl;
51         }
52         printf("%lld
", ans);
53     }
54     return 0;
55 }

View Code

B - Pizza Hub

题意：给出一个三角形，以及一个矩形的宽度，求一个最小的高度使得矩形能够覆盖三角形

思路：显然一定有一个点在矩形的顶点，枚举计算即可

  1 #include<bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 const int INF = 0x3f3f3f3f;
  6 const double PI = acos(-1.0);
  7 const double eps = 1e-8;
  8 const int maxn = 1e2;
  9 
 10 int sgn(double x)
 11 {
 12     if(fabs(x) < eps) return 0;
 13     else return x > 0 ? 1 : -1;
 14 }
 15 
 16 struct Point{
 17     double x, y;
 18     Point(){}
 19     Point(double _x, double _y)
 20     {
 21         x = _x;
 22         y = _y;
 23     }
 24 
 25     void input()
 26     {
 27         scanf("%lf %lf", &x, &y);
 28     }
 29 
 30     Point operator - (const Point &b) const
 31     {
 32         return Point(x - b.x, y - b.y);
 33     }
 34 
 35     double operator ^ (const Point &b) const
 36     {
 37         return x * b.y - y * b.x;
 38     }
 39 
 40     double distance(Point p)
 41     {
 42         return hypot(x - p.x, y - p.y);
 43     }
 44 
 45     double len()
 46     {
 47         return hypot(x, y);
 48     }
 49 
 50     double operator * (const Point &b) const
 51     {
 52         return x * b.x + y * b.y;
 53     }
 54 }P[maxn];
 55 
 56 int w;
 57 double ans;
 58 double area;
 59 
 60 void calc(Point a, Point b)//low high
 61 {
 62     if(sgn(a * b) < 0) return ;
 63     if(sgn(a * a - w * w) <= 0)
 64     {
 65         if(sgn(a ^ b) < 0) return ;
 66         if(sgn((a * b) * (a * b) - w * w * (a * a)) > 0) return ;
 67         ans = min(ans, (a ^ b) / sqrt(a * a));
 68     }
 69     else
 70     {
 71         double h = sqrt(a * a - w * w);
 72         double src1 = atan(h / w);
 73         if(sgn(a ^ b) >= 0)
 74         {
 75             double src2 = acos((a * b) / (sqrt(a * a) * sqrt(b * b)));
 76             if(sgn(src1 + src2 - PI / 2) > 0) return ;
 77             double len1 = sqrt(b * b) * cos(src1 + src2);
 78             if(sgn(len1 - w) > 0) return ;
 79             ans = min(ans, max(h, sqrt(b * b) * sin(src1 + src2)));
 80         }
 81         else
 82         {
 83             double src2 = acos((a * b) / (sqrt(a * a) * sqrt(b * b)));
 84             if(sgn(src1 - src2) < 0) return ;
 85             double len1 = sqrt(b * b) * cos(src1 - src2);
 86             if(sgn(len1 - w) > 0) return ;
 87             ans = min(ans, h);
 88         }
 89     }
 90 }
 91 
 92 int main()
 93 {
 94     int t;
 95     scanf("%d", &t);
 96     while(t--)
 97     {
 98         for(int i = 1; i <= 3; ++i) P[i].input();
 99     //    double a = p[1].distance(p[2]);
100     //    double b = p[2].distance(p[3]);
101     //    double c = p[3].distance(p[1]);
102     //    double p = (a + b + c) / 2.0;
103     //    area = sqrt(p * (p - a) * (p - b) * (p - c));
104         ans = INF * 1.0;
105         scanf("%d", &w);
106         calc(P[2] - P[1], P[3] - P[1]);
107         calc(P[3] - P[1], P[2] - P[1]);
108         calc(P[1] - P[2], P[3] - P[2]);
109         calc(P[3] - P[2], P[1] - P[2]);
110         calc(P[1] - P[3], P[2] - P[3]);
111         calc(P[2] - P[3], P[1] - P[3]);
112         for(int i = 1; i <= 3; ++i) P[i].y *= -1.0;
113         calc(P[2] - P[1], P[3] - P[1]);
114         calc(P[3] - P[1], P[2] - P[1]);
115         calc(P[1] - P[2], P[3] - P[2]);
116         calc(P[3] - P[2], P[1] - P[2]);
117         calc(P[1] - P[3], P[2] - P[3]);
118         calc(P[2] - P[3], P[1] - P[3]);
119         if(ans >= INF * 1.0) puts("impossible");
120         else printf("%.10f
", ans);
121     }
122     return 0;
123 }

View Code

C - City Development

留坑。

D - Parentheses Matrix

题意：构造一个矩阵，每一行和每一列都会构成一个括号序列，求合法括号序列尽量多

思路：

分类讨论：

n, m 都是奇数随便构造

n, m 有一个奇数那么答案是那个奇数

比如 1 4

()()

两个都是偶数如果有一个为2

比如 2 4

((((

))))

如果两个都大于四

比如六六

((((((

()()()

(()())

()()()

(()())

)))))

像这样构造答案是 n + m - 4

如果 n, m 中有个4

比如 4 4

(())

()()

(())

()()

  1 #include<bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 const int maxn = 200 + 10;
  6 
  7 int n, m;
  8 char str[maxn][maxn];
  9 
 10 int main()
 11 {
 12     int t;
 13     scanf("%d", &t);
 14     while(t--)
 15     {
 16         scanf("%d %d", &n, &m);
 17 //        printf("%d %d
", n, m);
 18         if(n % 2 == 1 && m % 2 == 1)
 19         {
 20             for(int i = 1; i <= n; ++i)
 21             {
 22                 for(int j = 1; j <= m; ++j)
 23                 {
 24                     printf("(");
 25                 }
 26                 printf("
");
 27             }
 28         }
 29         else if(n % 2 == 1)
 30         {
 31             for(int i = 1; i <= n; ++i)
 32             {
 33                 for(int j = 1; j <= m; ++j)
 34                 {
 35                     if(j & 1) printf("(");
 36                     else printf(")");
 37                 }
 38                 printf("
");
 39             }
 40         }
 41         else if(m % 2 == 1)
 42         {
 43             for(int i = 1; i <= n; ++i)
 44             {
 45                 for(int j = 1; j <= m; ++j)
 46                 {
 47                     if(i & 1) printf("(");
 48                     else printf(")");
 49                 }
 50                 printf("
");
 51             }
 52         }
 53         else if(n == 2)
 54         {
 55             for(int i = 1; i <= n; ++i)
 56             {
 57                 for(int j = 1; j <= m; ++j)
 58                 {
 59                     if(i & 1) printf("(");
 60                     else printf(")");
 61                 }
 62                 printf("
");
 63             }
 64         }
 65         else if(m == 2)
 66         {
 67             for(int i = 1; i <= n; ++i)
 68             {
 69                 for(int j = 1; j <= m; ++j)
 70                 {
 71                     if(j & 1) printf("(");
 72                     else printf(")");
 73                 }
 74                 printf("
");
 75             }
 76         }
 77         else if(n == 4)
 78         {
 79             for(int i = 1; i <= m; ++i) printf("(");
 80             printf("
");
 81             for(int i = 1; i <= m; ++i)
 82             {
 83                 if(i & 1) printf("(");
 84                 else printf(")");
 85             }
 86             printf("
");
 87             for(int i = 1; i <= m; ++i)
 88             {
 89                 if(i & 1) printf(")");
 90                 else printf("(");
 91             }
 92             printf("
");
 93             for(int i = 1; i <= m; ++i) printf(")");
 94             printf("
");
 95         }
 96         else if(m == 4)
 97         {
 98             for(int i = 1; i <= n; ++i) str[i][1] = '(';
 99             for(int i = 1; i <= n; ++i)
100             {
101                 if(i & 1) str[i][2] = '(';
102                 else str[i][2] = ')';
103             }
104             for(int i = 1; i <= n; ++i)
105             {
106                 if(i & 1) str[i][3] = ')';
107                 else str[i][3] = '(';
108             }
109             for(int i = 1; i <= n; ++i) str[i][4] = ')';
110             for(int i = 1; i <= n; ++i)
111             {
112                 for(int j = 1; j <= m; ++j)
113                 {
114                     printf("%c", str[i][j]);
115                 }
116                 printf("
");
117             }
118         }
119         else
120         {
121             for(int i = 1; i <= m; ++i) str[1][i] = '(';
122             for(int i = 2; i <= n; ++i)
123             {
124                 for(int j = 1; j <= m; ++j)
125                 {
126                     if(i & 1)
127                     {
128                         if(j == 1) str[i][j] = '(';
129                         else if(j == m) str[i][j] = ')';
130                         else if(j & 1) str[i][j] = ')';
131                         else str[i][j] = '(';    
132                     }
133                     else
134                     {
135                         if(j & 1) str[i][j] = '(';
136                         else str[i][j] = ')';
137                     }
138                 }
139             }
140             for(int i = 1; i <= m; ++i) str[n][i] = ')';
141             for(int i = 1; i <= n; ++i) 
142             {
143                 for(int j = 1; j <= m; ++j)
144                 {
145                     printf("%c", str[i][j]);
146                 }
147                 printf("
");
148             }
149         }
150     }
151     return 0;
152 }

View Code

E - Magic Square

按题意模拟即可。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define pii pair <int, int>
 5 int t, n;
 6 char G[5][5];
 7 
 8 void C(pii a)
 9 {
10     int x = a.first, y = a.second;
11     char tmp[5][5];
12     tmp[1][1] = G[x + 1][y];
13     tmp[1][2] = G[x][y];
14     tmp[2][1] = G[x + 1][y + 1];
15     tmp[2][2] = G[x][y + 1];
16     for (int i = 1; i <= 2; ++i)
17         for (int j = 1; j <= 2; ++j)
18             G[x + i - 1][y + j - 1] = tmp[i][j];
19 }
20 
21 void R(pii a)
22 {
23     int x = a.first, y = a.second;
24     char tmp[5][5];
25     tmp[1][1] = G[x][y + 1];
26     tmp[1][2] = G[x + 1][y + 1];
27     tmp[2][1] = G[x][y];
28     tmp[2][2] = G[x + 1][y];
29     for (int i = 1; i <= 2; ++i)
30         for (int j = 1; j <= 2; ++j)
31             G[x + i - 1][y + j - 1] = tmp[i][j];    
32 }
33 
34 pii pos[4] = 
35 {
36     pii(1, 1),
37     pii(1, 2),
38     pii(2, 1),
39     pii(2, 2),
40 };
41 
42 int main()
43 {
44     scanf("%d", &t);
45     while (t--)
46     {
47         scanf("%d", &n);
48         for (int i = 1; i <= 3; ++i) scanf("%s", G[i] + 1);
49         char op; int x;
50         for (int i = 1; i <= n; ++i)
51         {
52             scanf("%d %c", &x, &op);
53             if (op == 'C') C(pos[x - 1]);
54             else R(pos[x - 1]);
55         }        
56         for (int i = 1; i <= 3; ++i) printf("%s
", G[i] + 1);
57     }
58     return 0;
59 }

View Code

F - Boolean 3-Array

留坑。

G - Card Game

留坑。

H - K-Similar Strings

留坑。

I - Make ZYB Happy

留坑。

J - Taotao Picks Apples

题意：每次可以改变一个值，求改变之后以第一个数开头的最长上升子序列的长度，改变仅当次有效

思路：考虑线段树，维护一个cnt, 和一个Max 两个区间合并的时候

如果左区间的$Max > 右区间的 Max$

那么右区间没有贡献

否则递归查找贡献

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 100010
 5 int t;
 6 int n, m;
 7 int arr[N];
 8 
 9 struct SEG
10 {
11     int cnt[N << 2], Max[N << 2];
12     void build(int id, int l, int r)
13     {
14         cnt[id] = Max[id] = 0;
15         if (l == r) return;
16         int mid = (l + r) >> 1;
17         build(id << 1, l, mid);
18         build(id << 1 | 1, mid + 1, r);
19     }
20     int query(int id, int l, int r, int val)
21     {
22         if (l == r) return Max[id] > val;
23         int mid = (l + r) >> 1;
24         if (Max[id] <= val) return 0;
25         if (Max[id << 1] <= val) return query(id << 1 | 1, mid + 1, r, val);
26         else return cnt[id] - cnt[id << 1] + query(id << 1, l, mid, val);
27     }
28     void update(int id, int l, int r, int pos, int val)
29     {
30         if (l == r)
31         {
32             cnt[id] = 1;
33             Max[id] = val;
34             return;
35         }
36         int mid = (l + r) >> 1;
37         if (pos <= mid) update(id << 1, l, mid, pos, val);
38         else update(id << 1 | 1, mid + 1, r, pos, val);
39         cnt[id] = cnt[id << 1] + query(id << 1 | 1, mid + 1, r, Max[id << 1]);
40         Max[id] = max(Max[id << 1], Max[id << 1 | 1]);
41     }
42 }seg;
43 
44 int main()
45 {
46     scanf("%d", &t);
47     while (t--)
48     {
49         scanf("%d%d", &n, &m);
50         for (int i = 1; i <= n; ++i) scanf("%d", arr + i);
51         seg.build(1, 1, n);
52         for (int i = 1; i <= n; ++i) seg.update(1, 1, n, i, arr[i]);
53         for (int i = 1, x, v; i <= m; ++i)
54         {
55             scanf("%d%d", &x, &v);
56             seg.update(1, 1, n, x, v);
57             printf("%d
", seg.cnt[1]);
58             seg.update(1, 1, n, x, arr[x]);
59         }    
60     }
61     return 0;
62 }

View Code

K - Pop the Balloons

留坑。

L - From ICPC to ACM

留坑。