您的位置: 首页 > IT文章 > 2018 Multi-University Training Contest 5 Solution

2018 Multi-University Training Contest 5 Solution

分类: IT文章 • 2025-01-09 09:00:50

A - Always Online

Unsolved.

B - Beautiful Now

Solved.

题意：

给出一个n, k 每次可以将n这个数字上的某两位交换，最多交换k次，求交换后的最大和最小值

思路：

很明显有一种思路，对于最小值，尽可能把小的放前面，对于最大值，尽可能把打的放前面。但是如果有多个最小数字或者最大数字会无法得出放哪个好，因此BFS一下即可

  1 #include<bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 const int INF = 0x3f3f3f3f;
  6 const int maxn = 1e5 + 10;
  7 
  8 struct node{
  9     int num, idx, step;
 10     node(){}
 11     node(int num, int idx, int step) :num(num), idx(idx), step(step){}
 12 };
 13 
 14 int n, k;
 15 int cnt;
 16 int arr[maxn];
 17 
 18 int BFS1()
 19 {
 20     queue<node>q;
 21     q.push(node(n, cnt, 0));
 22     int ans = INF;
 23     while(!q.empty())
 24     {
 25         node now = q.front();
 26         q.pop();
 27         ans = min(ans, now.num);
 28         if(now.step == k) continue;
 29         if(now.idx == 1) continue;
 30         int tmp = now.num;
 31         cnt = 0;
 32         while(tmp)
 33         {
 34             arr[++cnt] = tmp % 10;
 35             tmp /= 10;
 36         }
 37         int Min = now.idx;
 38         for(int i = now.idx - 1; i >= 1; --i)
 39         {
 40             if(arr[i] == arr[now.idx]) continue;
 41             if(arr[i] == 0 && now.idx == cnt) continue;
 42             if(arr[i] < arr[Min]) Min = i;
 43         }
 44         if(Min == now.idx)
 45         {
 46             q.push(node(now.num, now.idx - 1, now.step));
 47         }
 48         else
 49         {
 50             for(int i = now.idx - 1; i >= 1; --i)
 51             {
 52                 if(arr[i] == arr[Min])
 53                 {
 54                     swap(arr[i], arr[now.idx]);
 55                     tmp = 0;
 56                     for(int j = cnt; j >= 1; --j)
 57                     {
 58                         tmp = tmp * 10 + arr[j];
 59                     }
 60                     q.push(node(tmp, now.idx - 1, now.step + 1));
 61                     swap(arr[i], arr[now.idx]);
 62                 }
 63             }
 64         }
 65     }
 66     return ans;
 67 }
 68 
 69 int BFS2()
 70 {
 71     queue<node>q;
 72     q.push(node(n, cnt, 0));
 73     int ans = -INF;
 74     while(!q.empty())
 75     {
 76         node now = q.front();
 77         q.pop();
 78         ans = max(ans, now.num);
 79         if(now.step == k) continue;
 80         if(now.idx == 1) continue;
 81         int tmp = now.num;
 82         cnt = 0;
 83         while(tmp)
 84         {
 85             arr[++cnt] = tmp % 10;
 86             tmp /= 10;
 87         }
 88         int Max = now.idx;
 89         for(int i = now.idx - 1; i >= 1; --i)
 90         {
 91             if(arr[i] == arr[now.idx]) continue;
 92             if(arr[i] > arr[Max]) Max = i;
 93         }
 94         if(Max == now.idx)
 95         {
 96             q.push(node(now.num, now.idx - 1, now.step));
 97         }
 98         else
 99         {
100             for(int i = now.idx - 1; i >= 1; --i)
101             {
102                 if(arr[i] == arr[Max])
103                 {
104                     swap(arr[i], arr[now.idx]);
105                     tmp = 0;
106                     for(int j = cnt; j >= 1; --j)
107                     {
108                         tmp = tmp * 10 + arr[j];
109                     }
110                     q.push(node(tmp, now.idx - 1, now.step + 1));
111                     swap(arr[i], arr[now.idx]);
112                 }
113             }
114         }
115     }
116     return ans;
117 }
118 
119 int main()
120 {
121     int t;
122     scanf("%d", &t);
123     while(t--)
124     {
125         scanf("%d %d", &n ,&k);
126         int tmp = n;
127         cnt = 0;
128         while(tmp)
129         {
130             cnt++;
131             tmp /= 10;
132         }
133         k = min(k, cnt - 1);
134         int ans1 = BFS1();
135         int ans2 = BFS2();
136         printf("%d %d
", ans1, ans2);
137     }
138     return 0;
139 }

View Code

C - Call It What You Want

Unsolved.

D - Daylight

Unsolved.

E - Everything Has Changed

Solved.

题意：

求多个圆的周长并

思路：

对于不想交和内含的直接continue，相切的直接相加。对于相交的可以减去大圆上的弧长，加上小圆的弧长

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 const double PI = acos(-1.0);
 6 const double eps = 1e-8;
 7 
 8 int sgn(double x)
 9 {
10     if(fabs(x) < eps) return 0;
11     else return x > 0 ? 1 : -1;
12 }
13 
14 struct Point{
15     double x, y;
16     Point(){}
17     Point(double _x, double _y)
18     {
19         x = _x;
20         y = _y;
21     }
22 
23     double distance(Point p)
24     {
25         return hypot(x - p.x, y - p.y);
26     }
27 }P;
28 
29 int n;
30 double R, r;
31 
32 int main()
33 {
34     int t;
35     scanf("%d", &t);
36     while(t--)
37     {
38         scanf("%d %lf", &n, &R);
39         double ans = 2 * R * PI;
40         for(int i = 1; i <= n; ++i)
41         {
42             scanf("%lf %lf %lf", &P.x, &P.y, &r);
43             double dis = P.distance(Point(0.0, 0.0));
44             if(sgn(dis - (r + R)) >= 0) continue;
45             else if(sgn(dis - (R - r)) < 0) continue;
46             else if(sgn(dis - (R - r)) == 0)
47             {
48                 ans += 2 * PI * r;
49                 continue;
50             }    
51             double arc1 = (R * R + dis * dis - r * r) / (2.0 * R * dis);
52             arc1 = 2 * acos(arc1);
53             double arc2 = (r * r + dis * dis - R * R) / (2.0 * r * dis);
54             arc2 = 2 * acos(arc2);
55             ans -= R * arc1;
56             ans += r * arc2;
57         }
58         printf("%.10f
", ans);
59     }    
60     return 0;
61 }

View Code

F - Fireflies

Unsolved.

G - Glad You Came

Upsolved.

题意：

m个区间操作，每次给$[L, R]区间内小于v 的数变为v$

思路：

线段树，维护最大最小值+剪枝，因为数据随机才可以这样做。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 5000010
 5 #define M 100010
 6 #define ui unsigned int
 7 #define ll long long
 8 int t, n, m;
 9 ui x, y, z, w;
10 ui f[N << 2];
11 ui MOD = (ui)1 << 30;
12 
13 ui rng61()
14 {
15     x = x ^ (x << 11);
16     x = x ^ (x >> 4);
17     x = x ^ (x << 5);
18     x = x ^ (x >> 14);
19     w = x ^ y ^ z;
20     x = y;
21     y = z;
22     z = w;
23     return z;
24 }
25 
26 struct SEG
27 {
28     ui lazy[M << 2], Max[M << 2], Min[M << 2];
29     void Init() 
30     {
31         memset(lazy, 0, sizeof lazy);
32         memset(Max, 0, sizeof Max);
33         memset(Min, 0, sizeof Min);
34     }
35     void pushup(int id) 
36     { 
37         Max[id] = max(Max[id << 1], Max[id << 1 | 1]); 
38         Min[id] = min(Min[id << 1], Min[id << 1 | 1]);
39     }
40     void pushdown(int id)
41     {
42         if (!lazy[id]) return;
43         lazy[id << 1] = lazy[id];
44         Max[id << 1] = lazy[id];
45         Min[id << 1] = lazy[id];
46         lazy[id << 1 | 1] = lazy[id];
47         Max[id << 1 | 1] = lazy[id];
48         Min[id << 1 | 1] = lazy[id];
49         lazy[id] = 0;
50     }
51     void update(int id, int l, int r, int ql, int qr, ui val)
52     {
53         if (Min[id] >= val) return;
54         if (l >= ql && r <= qr && Max[id] < val)
55         {
56             lazy[id] = Max[id] = val;
57             return;
58         }
59         pushdown(id);
60         int mid = (l + r) >> 1;
61         if (ql <= mid) update(id << 1, l, mid, ql, qr, val);
62         if (qr > mid) update(id << 1 | 1, mid + 1, r, ql, qr, val);
63         pushup(id);
64     }
65     int query(int id, int l, int r, int pos)
66     {
67         if (l == r) return Max[id];
68         pushdown(id);
69         int mid = (l + r) >> 1;
70         if (pos <= mid) return query(id << 1, l, mid, pos);
71         else return query(id << 1 | 1, mid + 1, r, pos); 
72     }
73 }seg;
74 
75 int main()
76 {
77     scanf("%d", &t);
78     while (t--)
79     {
80         scanf("%d%d%u%u%u", &n, &m, &x, &y, &z);
81         for (int i = 1; i <= 3 * m; ++i) f[i] = rng61();
82         seg.Init();
83         for (int i = 1, l, r, v; i <= m; ++i)
84         {
85             l = f[3 * i - 2] % n + 1;
86             r = f[3 * i - 1] % n + 1;
87             v = f[3 * i] % MOD;
88             if (l > r) swap(l, r);
89             seg.update(1, 1, n, l, r, v);
90         }
91         ll res = 0;
92         for (int i = 1; i <= n; ++i)
93             res ^= (ll)seg.query(1, 1, n, i) * (ll)i;
94         printf("%lld
", res);
95     }
96     return 0;
97 }

View Code

2018 Multi-University Training Contest 5 Solution

相关推荐