2018 Multi-University Training Contest 3 Solution

A - Problem A. Ascending Rating

题意：给出n个数，给出区间长度m。对于每个区间，初始值的max为0，cnt为0.遇到一个a[i] > ans, 更新ans并且cnt++。计算

$A = sum_{i = 1}^{i = n - m +1} (max oplus i)$

$B = sum_{i = 1}^{i = n - m +1} (cnt oplus i)$

思路：单调队列，倒着扫一遍，对于每个区间的cnt就是队列的长度，扫一遍即可。

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 const int maxn = 1e7 + 10;
 6 typedef long long ll;
 7 
 8 int t;
 9 int n,m,k;
10 ll p, q, r, mod;
11 ll arr[maxn];
12 ll brr[maxn];
13 
14 int main()
15 {
16     scanf("%d", &t);
17     while(t--)
18     {
19         scanf("%d %d %d %lld %lld %lld %lld", &n, &m, &k, &p, &q, &r, &mod);
20         for(int i = 1; i <= n; ++i)
21         {
22             if(i <= k) scanf("%lld", arr + i);
23             else arr[i] = (p * arr[i - 1] + q * i + r) % mod;
24         }
25         ll A = 0, B = 0;
26         int head = 0, tail = -1;
27         for(int i = n; i > (n - m + 1); --i)
28         {
29             while(head <= tail && arr[i] >= arr[brr[tail]]) tail--;
30             brr[++tail] = i;
31         }
32         for(int i = n - m + 1; i >= 1; --i)
33         {
34             while(head <= tail && arr[i] >= arr[brr[tail]]) tail--;
35             brr[++tail] = i;
36             while(brr[head] - i >= m) head++;
37             A += arr[brr[head]] ^ i;
38             B += (tail - head + 1) ^ i;
39         }
40         printf("%lld %lld
", A, B);
41     }
42     return 0;
43 }

View Code

B - Problem B. Cut The String

留坑。

C - Problem C. Dynamic Graph Matching

题意：给出n个点，两种操作，一种是加边，一种是减边，每次加一条或者减一条，每次操作后输出1, 2, ..., n/2 表示对应的数量的边，有几种取法，并且任意两个边不能相邻

思路：每加一条边，都可以转移状态比如说 110100 到 111110 就是 dp[111110] += dp[110100]

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 typedef long long ll;
 6 const int maxn = 1 << 10;
 7 const int MOD = 1e9 + 7;
 8 
 9 int t, n, m;
10 ll dp[maxn];
11 ll ans[12];
12 
13 inline int cal(int x)
14 {
15     int cnt = 0;
16     while(x)
17     {
18         if(x & 1) cnt++;
19         x >>= 1;
20     }
21     return cnt;
22 }
23 
24 int main()
25 {
26     scanf("%d", &t);
27     while(t--)
28     {
29         memset(ans, 0, sizeof ans);
30         memset(dp, 0, sizeof dp);
31         dp[0] = 1;
32         scanf("%d %d", &n, &m);
33         while(m--)
34         {
35             char op[10];
36             int u, v;
37             scanf("%s %d %d", op, &u, &v);
38             --u,--v;
39             for(int s = 0 ; s < (1 << n); ++s)
40             {
41                 if((s & (1 << u)) || (s & (1 << v))) continue;
42                 int S = s | (1 << u);
43                 S |= (1 << v);
44                 if(op[0] == '+')
45                 {
46                     dp[S] = (dp[S] + dp[s]) % MOD;
47                     ans[cal(S)] = (ans[cal(S)] + dp[s]) % MOD;
48                 }
49                 else if(op[0] == '-')
50                 {
51                     dp[S] = (dp[S] - dp[s] + MOD) % MOD;
52                     ans[cal(S)] = (ans[cal(S)] - dp[s] + MOD) % MOD;
53                 }
54             }
55             for(int i = 2; i <= n; i += 2)
56             {
57                 printf("%lld%c", ans[i], " 
"[i == n]);
58             }
59         }
60     }
61     return 0;
62 }

View Code

D - Problem D. Euler Function

打表找规律

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 #define N 100010
 6 
 7 inline int gcd(int a, int b)
 8 {
 9     return b == 0 ? a : gcd(b, a % b);
10 }
11 
12 inline void Init()
13 {
14     for (int i = 1; i <= 100; ++i)
15     {
16         int res = 0;
17         for (int j = 1; j < i; ++j)
18             res += (gcd(i, j) == 1);
19         printf("%d %d
", i, res);
20     }
21 }
22 
23 int t, n;
24 
25 int main()
26 {
27     scanf("%d", &t);
28     while (t--)
29     {
30         scanf("%d", &n);
31         if (n == 1) puts("5");
32         else printf("%d
", n + 5);
33     }
34     return 0;
35 }

View Code

E - Problem E. Find The Submatrix

留坑，

F - Problem F. Grab The Tree

题意：一棵树，每个点有点权，小Q可以选择若干个点，并且任意两个点之间没有边，小T就是剩下的所有点，然后两个人的值就是拥有的点异或起来，求小Q赢还是输还是平局

思路：显然，只有赢或者平局的情况，只要考虑是否有平局情况就可以，当所有点异或起来为0便是平局

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 100010
 5 
 6 int t, n;
 7 int arr[N];
 8 
 9 int main()
10 {
11     scanf("%d", &t);
12     while (t--)
13     {
14         scanf("%d", &n);
15         int res = 0;
16         for (int i = 1; i <= n; ++i)
17         {
18             scanf("%d", arr + i);
19             res ^= arr[i];
20         }
21         for (int i = 1, u, v; i < n; ++i) scanf("%d%d", &u, &v);
22         if (res == 0) 
23         {
24             puts("D");
25             continue;
26         }
27         puts("Q");    
28     }
29     return 0;
30 }

View Code

G - Problem G. Interstellar Travel

题意：给出n个点，要从$i -> j$ 当且仅当 $x_i < x_j$ 花费为 $x_i cdot y_j - x_j cdot y_i$ 求从$1 -> n$ 求权值最小如果多解输出字典序最小的解

思路：可以发现权值就是叉积，求个凸包，然后考虑在一条线上的情况

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 #define N 200010
  5 
  6 const double eps = 1e-8;
  7 
  8 inline int sgn(double x)
  9 {
 10     if (fabs(x) < eps) return 0;
 11     if (x < 0) return -1;
 12     else return 1;
 13 }
 14 
 15 struct Point
 16 {
 17     double x, y; int id;
 18     inline Point () {}
 19     inline Point(double x, double y) : x(x), y(y) {}
 20     inline void scan(int _id)
 21     {
 22         id = _id;
 23         scanf("%lf%lf", &x, &y);
 24     }
 25     inline bool operator == (const Point &r) const { return sgn(x - r.x) == 0 && sgn(y - r.y) == 0; }
 26     inline bool operator < (const Point &r) const { return x < r.x || x == r.x && y < r.y || x == r.x && y == r.y && id < r.id; }
 27     inline Point operator + (const Point &r) const { return Point(x + r.x, y + r.y); }
 28     inline Point operator - (const Point &r) const { return Point(x - r.x, y - r.y); }
 29     inline double operator ^ (const Point &r) const { return x * r.y - y * r.x; }
 30     inline double distance(const Point &r) const { return hypot(x - r.x, y - r.y); }
 31 };
 32 
 33 struct Polygon
 34 {
 35     int n;
 36     Point p[N];
 37     struct cmp
 38     {
 39         Point p;
 40         inline cmp(const Point &p0) { p = p0; }
 41         inline bool operator () (const Point &aa, const Point &bb)
 42         {
 43             Point a = aa, b = bb;
 44             int d = sgn((a - p) ^ (b - p));
 45             if (d == 0)
 46             {
 47                 return sgn(a.distance(p) - b.distance(p)) < 0;
 48             }
 49             return d < 0;
 50         }
 51     };
 52     inline void norm()
 53     {
 54         Point mi = p[0];
 55         for (int i = 1; i < n; ++i) mi = min(mi, p[i]);
 56         sort(p, p + n, cmp(mi)); 
 57     }
 58     inline void Graham(Polygon &convex)
 59     {
 60         sort(p + 1, p + n - 1);
 61         int cnt = 1;
 62         for (int i = 1; i < n; ++i)
 63         {
 64             if (!(p[i] == p[i - 1]))
 65                 p[cnt++] = p[i];
 66         }
 67         n = cnt;
 68         norm();
 69         int &top = convex.n;
 70         top = 0;
 71         if (n == 2)
 72         {
 73             top = 2;
 74             convex.p[0] = p[0];
 75             convex.p[1] = p[1];
 76             return;
 77         }
 78         if(n == 3)
 79         {
 80             top = 3;
 81             convex.p[0] = p[0];
 82             convex.p[1] = p[1];
 83             convex.p[2] = p[2];
 84             return ;
 85         }
 86         convex.p[0] = p[0];
 87         convex.p[1] = p[1];
 88         top = 2;
 89         for (int i = 2; i < n; ++i)
 90         {
 91             while (top > 1 && sgn((convex.p[top - 1] - convex.p[top - 2]) ^ (p[i] - convex.p[top - 2])) >= 0) 
 92             {
 93                 if(sgn((convex.p[top - 1] - convex.p[top - 2]) ^ (p[i] - convex.p[top - 2])) == 0)
 94                 {
 95                     if(p[i].id < convex.p[top - 1].id) --top;
 96                     else break;
 97                 }
 98                 else
 99                 {
100                     --top;
101                 }
102             }
103             convex.p[top++] = p[i];
104         }
105         if (convex.n == 2 && (convex.p[0] == convex.p[1])) --convex.n;
106     }
107 }arr, ans;
108 
109 int t, n;
110 
111 int main()
112 {
113     scanf("%d", &t);
114     while (t--)
115     {
116         scanf("%d", &n); arr.n = n;
117     //    cout << n << endl;
118         for (int i = 0; i < n; ++i) arr.p[i].scan(i + 1); 
119         arr.Graham(ans);
120         for (int i = 0; i < ans.n; ++i) printf("%d%c", ans.p[i].id, " 
"[i == ans.n - 1]);
121     }
122     return 0;
123 }

View Code

H - Problem H. Monster Hunter

留坑。

I - Problem I. Random Sequence

留坑。

J - Problem J. Rectangle Radar Scanner

留坑。

K - Problem K. Transport Construction

留坑。

L - Problem L. Visual Cube

按题意模拟即可，分块解决

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

View Code

M - Problem M. Walking Plan

题意：给出一张图，询问从$u -> v 至少经过k条路的最少花费$

思路：因为$k <= 10000$ 那么我们可以拆成 $k = x * 100 + y$ 然后考虑分块

$G[k][i][j] 表示 i -> j 至少经过k条路$

$dp[k][i][j] 表示 i -> j 至少经过 k * 100 条路$

然后查询的时候枚举中间点

 1 #include <bits/stdc++.h>
 2 using namespace std; 
 3 
 4 #define N 210
 5 #define INFLL 0x3f3f3f3f3f3f3f3f
 6 #define ll long long
 7 
 8 int t, n, m, q;
 9 ll G[N][55][55], dp[N][55][55];
10 
11 inline void Init()
12 {
13     memset(G, 0x3f, sizeof G);
14     memset(dp, 0x3f, sizeof dp); 
15 }
16 
17 inline void Floyd() 
18 {
19     for (int l = 2; l <= 200; ++l)
20         for (int k = 1; k <= n; ++k)
21             for (int i = 1; i <= n; ++i)
22                 for (int j = 1; j <= n; ++j)
23                     G[l][i][j] = min(G[l][i][j], G[l - 1][i][k] + G[1][k][j]);
24     for (int i = 1; i <= n; ++i)
25         for (int j = 1; j <= n; ++j)
26             for (int l = 199; l >= 0; --l) 
27                 G[l][i][j] = min(G[l][i][j], G[l + 1][i][j]); // at least K roads;
28     for (int i = 1; i <= n; ++i)
29         for (int j = 1; j <= n; ++j)
30             dp[1][i][j] = G[100][i][j];
31     for (int l = 2; l <= 100; ++l)
32         for (int k = 1; k <= n; ++k)
33             for (int i = 1; i <= n; ++i)
34                 for (int j = 1; j <= n; ++j)
35                     dp[l][i][j] = min(dp[l][i][j], dp[l - 1][i][k] + dp[1][k][j]);
36 }
37 
38 inline void Run() 
39 {
40     scanf("%d", &t);
41     while (Init(), t--) 
42     {
43         scanf("%d%d", &n, &m); 
44         for (int i = 1, u, v, w; i <= m; ++i)
45         {
46             scanf("%d%d%d", &u, &v, &w);  
47             G[1][u][v] = min(G[1][u][v], (ll)w);
48         }
49         Floyd(); scanf("%d", &q);
50         for (int i = 1, u, v, k; i <= q; ++i)
51         {
52             scanf("%d%d%d", &u, &v, &k);
53             int unit =  floor (k * 1.0 / 100), remind = k - unit * 100; 
54             ll ans = INFLL; 
55             if (k <= 100) ans = G[k][u][v];  
56             else
57             {
58                 for (int j = 1; j <= n; ++j)
59                     ans = min(ans, dp[unit][u][j] + G[remind][j][v]); 
60             }
61             if (k > 100 && remind == 0) ans = min(ans, dp[unit][u][v]); 
62             printf("%lld
", ans >= INFLL ? -1 : ans);
63         }
64     }
65 }
66  
67 int main()
68 {
69     #ifdef LOCAL 
70         freopen("Test.in", "r", stdin);
71     #endif  
72 
73     Run();
74     return 0;
75 }

View Code