寒假练习题解 第三周 2.1-2.7

时间:2022-01-09 22:15:32

尽快将前面的练习补上!

 

每日一练

2.1

Problem A Laurenty and Shop

题意:选择不同的两条路线使得总等待时间最小。

简析:路线不同在于过马路的地方不同。

   预处理前缀和,可以O(1)得到走每条路时间,挑选最小的两个即可。

寒假练习题解 第三周 2.1-2.7寒假练习题解 第三周 2.1-2.7
 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 int a[2][50], b[50];
 5 const int INF = 1e9;
 6 
 7 int main(void)
 8 {
 9     int n;
10     scanf("%d", &n);
11     for(int i = 1; i < n; i++) scanf("%d", &a[0][i]), a[0][i] += a[0][i-1];
12     for(int i = 1; i < n; i++) scanf("%d", &a[1][i]), a[1][i] += a[1][i-1];
13     for(int i = 0; i < n; i++) scanf("%d", b + i);
14     int A = INF, B = INF;
15     for(int i = 0; i < n; i++)
16     {
17         int pos = a[0][i] + b[i] + a[1][n-1] - a[1][i];
18         if(pos <= A) B = A, A = pos;
19         else if(pos < B) B = pos;
20     }
21     printf("%d\n", A + B);
22     return 0;
23 }
参考代码

 

Problem B Gennady the Dentist

题意:模拟牙医看病。

简析:可以维护一个标记来判断小孩有没有逃走,然后从前往后扫这个队列。

   过程中进行两个操作:

   ①看病:按题意减去后面小孩的信心,然后处理逃走。

   ②逃走:给小孩标记出队,给后面的人减去信心,同时处理连锁反应。

寒假练习题解 第三周 2.1-2.7寒假练习题解 第三周 2.1-2.7
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <vector>
 4 using namespace std;
 5 const int maxn = 5000;
 6 int v[maxn], d[maxn], p[maxn];
 7 vector<int> ans;
 8 bool out[maxn];
 9 int n;
10 
11 void run(int pos)
12 {
13     out[pos] = 1;
14     for(int i = pos + 1; i < n; i++)
15     {
16         if(out[i]) continue;
17         p[i] -= d[pos];
18         if(p[i] < 0) run(i);
19     }
20     return;
21 }
22 
23 void cure(int pos)
24 {
25     for(int i = pos + 1; i < n; i++)
26     {
27         if(v[pos] == 0) break;
28         if(out[i]) continue;
29         p[i] -= v[pos], v[pos]--;
30     }
31     for(int i = pos + 1; i < n; i++)
32     {
33         if(out[i]) continue;
34         if(p[i] < 0) run(i);
35     }
36     return;
37 }
38 
39 int main(void)
40 {
41     scanf("%d", &n);
42     for(int i = 0; i < n; i++) scanf("%d%d%d", v+i, d+i, p+i);
43     for(int i = 0; i < n; i++)
44     {
45         if(out[i]) continue;
46         ans.push_back(i);
47         cure(i);
48     }
49     printf("%d\n", ans.size());
50     for(int i = 0; i < ans.size(); i++) printf("%d ", ans[i] + 1);
51     puts("");
52     return 0;
53 }
参考代码

 

2.2

Problem A Duff in Love

题意:给出 一个 n ,找到最大的 x ,使得 x 满足 ,x 是 n 的因子,并且x 的因子中没有平方数

简析:将 n 分解质因数,每个质因数取一个

寒假练习题解 第三周 2.1-2.7寒假练习题解 第三周 2.1-2.7
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<vector>
 7 #include<set>
 8 using namespace std;
 9 
10 typedef long long LL;
11 const int maxn = 100005;
12 int dp[maxn];
13 int Max[maxn];
14 vector<int> p;
15 
16 int vis[maxn];
17 int T,a[105];
18 int cnt[maxn];
19 set<long long > s;
20 LL n;
21 
22 void solve( long long  x){
23     LL y = x;
24    // printf("y = %I64d\n",y);
25     for(long long  j = 2;1LL*j*j <= y;j++){
26         if(y%j == 0){
27         //    printf("j = %I64d\n",j);
28             while(y%j == 0){
29                 s.insert(j);
30                 y = y/j;
31             }
32         }        
33     }
34     if(y > 1) s.insert(y);
35     
36    // for(set<long long >::iterator it = s.begin();it != s.end();++it){
37     //    printf("*it = %d\n",*it);
38     //}
39     
40 }
41 
42 void work(){
43     if(n == 1){
44         puts("1");
45         return;
46     }
47     if(s.size() < 2){
48         printf("%I64d\n",*s.begin());
49         return;
50     }
51     LL res = 1;
52     for(set<long long >::iterator it = s.begin();it != s.end();++it){
53         res = res*(*it);
54     }
55     printf("%I64d\n",res);
56 }
57 
58 int main(){
59     while(scanf("%I64d",&n) != EOF){
60         s.clear();
61         solve(n);
62         work();
63     }
64     return 0;
65 }
参考代码

 

Problem B Duff and Weight Lifting

题意:给出 n 个数,如果满足 2^a1 + 2^a2 +...+2^ak = 2^x = S,则可以将 a1,a2,...ak消掉,问最少需要多少次消掉所有的数

简析:从小到大的消,两个 1 变成一个 2,两个2变成一个3,模拟这样的过程,剩下的不能再合并的数的个数就是需要的操作数

寒假练习题解 第三周 2.1-2.7寒假练习题解 第三周 2.1-2.7
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<vector>
 6 #include<queue>
 7 using namespace std;
 8 
 9 const int maxn = 1000005;
10 int a[maxn];
11 int n;
12 
13 priority_queue<int,vector<int>,greater<int> > q;
14 
15 int main(){
16     while(scanf("%d",&n) != EOF){
17         while(!q.empty()) q.pop();
18         
19         for(int i = 1;i <= n;i++) scanf("%d",&a[i]),q.push(a[i]);
20         
21         int c = 0;
22         while(!q.empty()){
23             if(q.size() >= 2){
24                 int x = q.top();q.pop();
25                  int y = q.top();q.pop();
26                  if(x == y) q.push(x+1);
27                  else {
28                      q.push(y);
29                      c++;
30                  }
31                  
32             //    printf("x = %d  y = %d\n",x,y);
33             }
34             if(q.size() == 1) {
35                 int x = q.top();q.pop();
36                 c++;
37             }
38             if(q.size() == 0) break;    
39         }
40         printf("%d\n",c);
41         
42     }
43     
44 }
参考代码

然后,可以发现是在 统计 S 的二进制表现形式中 1 的个数

寒假练习题解 第三周 2.1-2.7寒假练习题解 第三周 2.1-2.7
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 const int maxn = 5e6+5;
 8 int a[maxn],bit[maxn];
 9 int n;
10 
11 void solve(){
12     int ans = 0;
13     for(int i = 0;i < maxn;i++){
14         bit[i+1] += bit[i]/2;
15         bit[i] = bit[i]%2;
16         ans += bit[i];
17     }
18     printf("%d\n",ans);
19 }
20 
21 int main(){
22     while(scanf("%d",&n)!= EOF){
23         memset(bit,0,sizeof(bit));
24         for(int i = 1;i <= n;i++){
25             scanf("%d",&a[i]);
26             bit[a[i]]++;
27         }
28         solve();
29     }
30     return 0;
31 }
参考代码

 

可以再做一下这两题,也和进制有关

Vanya and Scales

Slime Combining

 

2.3

Problem A Rebranding

题意:给一个长度为n的字符串,做m次字母替换,求替换后的字符串。

简析:先初始化一个字母表到自己本身的映射,每一次替换,把相应字母的象做一次交换。

   最后根据交换完成后的映射,将字符串转化成新串。

寒假练习题解 第三周 2.1-2.7寒假练习题解 第三周 2.1-2.7
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 const int maxn = 2e5 + 10;
 6 int pos[26], re[26];
 7 char s[maxn];
 8 
 9 int main(void)
10 {
11     int n, m;
12     scanf("%d %d %s", &n, &m, s);
13     for(int i = 0; i < 26; i++) pos[i] = i;
14     for(int i = 0; i < m; i++)
15     {
16         char x[5], y[5];
17         scanf("%s %s", x, y);
18         swap(pos[x[0]-'a'], pos[y[0]-'a']);
19     }
20     for(int i = 0; i < 26; i++) re[pos[i]]=i;
21     for(int i = 0; i < n; i++) putchar(re[s[i]-'a']+'a');
22     puts("");
23     return 0;
24 }
参考代码

 

Problem B Median Smoothing

题意:给一个二进制串,定义一种操作:将101变为111,010变为000.问几次操作后该串不再变化。

简析:首先要发现只有101和010会发生变化,也即是说一旦出现了连续两个相同字符,这两个字符就不会变。

   我们除去所有连续相同的字符,剩下的就只有01交错的串,它们在经过一系列操作后会最终变为相同。

   很容易发现要将一个长度为x的01交错串变为相同需要(x - 1) / 2次操作。

   所以考虑所有的01交错串,最长的那个决定了答案。

寒假练习题解 第三周 2.1-2.7寒假练习题解 第三周 2.1-2.7
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 const int maxn = 5e5 + 10;
 6 int a[maxn];
 7 
 8 bool ok(int i)
 9 {
10     return a[i] != a[i-1] && a[i] != a[i+1];
11 }
12 
13 int main(void)
14 {
15     int n;
16     scanf("%d", &n);
17     for(int i = 1; i <= n; i++) scanf("%d", a + i);
18     int ans = 0;
19     for(int i = 2; i < n; i++)
20     {
21         if(ok(i))
22         {
23             int cnt = 0, p = i;
24             while(p < n && ok(p)) p++, cnt++;
25             ans = max(ans, ( cnt + 1 ) / 2);
26             for(int j = 0; j < ( cnt + 1 ) / 2; j++)
27                 a[i+j] = a[i+j-1], a[i+cnt-j-1] = a[i+cnt-j];
28         }
29     }
30     printf("%d\n", ans);
31     for(int i = 1; i <= n; i++) printf("%d ",a[i]);
32     return 0;
33 }
参考代码

 

2.4

Problem A The Monster and the Squirrel

题意:给出一个 n 边形,问收集完所有核桃需要跳多少次

简析:找规律是 (n-2)*(n-2)

寒假练习题解 第三周 2.1-2.7寒假练习题解 第三周 2.1-2.7
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 #include<queue>
 7 using namespace std;
 8 
 9 
10 typedef long long LL;
11 const int maxn = 1e5+5;
12 int n,m;
13 int a[maxn];
14 
15 void solve(){
16     if(n == 3){
17         puts("1");
18         return;
19     }
20     
21     printf("%I64d\n",1LL*(n-2)*(n-2));
22 }
23 
24 int main(){
25     
26     while(scanf("%d",&n) != EOF){
27         solve();
28     }
29     return 0;
30 } 
参考代码

 

Problem B The Big Race

题意:A,B两人赛跑,速度相等,但是A的步长是 w,B 的步长是 b,跑道的长度 是 L,在大于L的地方都是深渊,A,B两人打成平手的条件是两人同时落入深渊

给出 t ,问[1,t] 内可以选择出多少个L,输出个数与 t 的比

简析:L 满足 L % w = L % b,即L 满足

 L = x*w + r  = y*b + r  -------------- (1)

在一个周期M = lcm(w,b)内,满足 (1) 式的r 的个数 为 k = min(w,b)

证明:在第一个 周期 [1,M] 内,r 的取值范围是 [0,min(w,b)-1]

又因为需要 满足 (1)式子

所以,L - r = x*w = y*b >= M

所以在 一个周期 lcm 内只有 min(w,b) 个

如果 t > M, 那么 ans = t/M * k + min(min(w,b)-1, t%M)

如果 t < M,那么 ans = min(min(w,b)-1, t)

在判断 t 和 M 的大小的时候,可能会爆long long,可以两边取一下 log 来判断大小关系

寒假练习题解 第三周 2.1-2.7寒假练习题解 第三周 2.1-2.7
 1 #include<cstdio>
 2 #include<cmath>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 
 8 typedef long long LL;
 9 LL t,w,b;
10 
11 LL gcd(LL a,LL b){
12     return (!b)?a:gcd(b,a%b);
13 }
14 
15 int sgn(double x){
16     if(fabs(x) < 1e-6) return 0;
17     return x > 0?1:-1;
18 }
19 
20 void solve(){
21     LL g = gcd(w,b);
22     LL fz = 0;
23     LL fm = t;
24     double cha = log(1.0*w)+log(1.0*b)-log(1.0*g)-log(1.0*t);
25     if(sgn(cha)>0){
26         fz = min(t,min(w,b)-1);
27     }
28     else{
29         LL lcm = (w/gcd(w,b))*b;
30         LL c = (t/lcm);
31         fz = c*min(w,b);
32         LL l1 = t%lcm;
33         LL l2 = t-c*lcm;
34         t = t%lcm;
35         fz += min(t,min(w,b)-1);
36     }
37     LL gg = gcd(fz,fm);
38     printf("%I64d/%I64d\n",fz/gg,fm/gg);
39 }
40 
41 int main(){
42     while(scanf("%I64d %I64d %I64d",&t,&w,&b) != EOF){
43         solve();
44     }
45     return 0;
46 }
参考代码

 

2.5

Problem A BerSU Ball

题意:男女skill相差不能超过1,求最大匹配。

简析:男女分别排序后,从小到大扫一遍男,贪心的尽可能先与小的女匹配。

寒假练习题解 第三周 2.1-2.7寒假练习题解 第三周 2.1-2.7
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cmath>
 5 using namespace std;
 6 int a[111], b[111];
 7 
 8 int main(void)
 9 {
10     int n, m;
11     scanf("%d", &n);
12     for(int i = 0; i < n; i++) scanf("%d", a + i);
13     scanf("%d", &m);
14     for(int i = 0; i < m; i++) scanf("%d", b + i);
15     sort(a, a + n);
16     sort(b, b + m);
17     int j = 0, ans = 0;
18     for(int i = 0; i < n; i++)
19     {
20         if(j == m) break;
21         if(abs(a[i] - b[j]) <= 1) j++, ans++;
22         else
23         {
24             while(j < m - 1 && b[j] < a[i] - 1) j++;
25             if(abs(a[i] - b[j]) <= 1) j++, ans++;
26         }
27     }
28     printf("%d\n", ans);
29     return 0;
30 }
参考代码

 

Problem B Given Length and Sum of Digits...

题意:求一共m位,且每位数字和为s的最小的数与最大的数。

简析:首先如果s为0且m大于1,或者s大于9m是无解的。

   最小的数只要先在最高位填1,然后从最低位开始尽可能填9。

   最大的数只要从最高位开始往后尽可能填9即可。

寒假练习题解 第三周 2.1-2.7寒假练习题解 第三周 2.1-2.7
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 int a[111], b[111];
 6 
 7 int main(void)
 8 {
 9     int m, s;
10     scanf("%d %d", &m, &s);
11     if(!s && m > 1 || s > m * 9) puts("-1 -1");
12     else
13     {
14         int tmp = s;
15         for(int i = 1; i <= m; i++)
16             tmp -= a[i] = min(tmp, 9);
17         tmp = s - 1;
18         b[1] = 1;
19         for(int i = m; i; i--)
20             b[i] += min(tmp, 9), tmp -= min(tmp, 9);
21         for(int i = 1; i <= m; i++) printf("%d", b[i]);
22         putchar(' ');
23         for(int i = 1; i <= m; i++) printf("%d", a[i]);
24     }
25     return 0;
26 }
参考代码

 

2.6

Problem A Valuable Resources

题意:给出n个点,求包含这 n 个点的最小的正方形的面积

简析:扫一遍求出 xmin 和 xmax,ymin,ymax,取 max(xmax-xmin,ymax-ymin) 作为边长

寒假练习题解 第三周 2.1-2.7寒假练习题解 第三周 2.1-2.7
 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring>  
 4 #include<algorithm>  
 5 using namespace std;
 6 
 7 int a[1005],b[1005];
 8  long long area;
 9 
10 int main()
11 {
12     int i,j,n;
13     long long ans1,ans2;
14     scanf("%d",&n);
15     for(i=0;i<n;i++)
16     {
17         cin>>a[i]>>b[i];
18     }
19     sort(a,a+n);
20     sort(b,b+n);
21     
22     ans1=a[n-1]-a[0];
23     ans2=b[n-1]-b[0];
24     long long t=max(ans1,ans2);
25     printf("%I64d\n",t*t);    
26 }
参考代码

 

Problem B Bits

题意:给出 n 个询问 ,求出在[1,r] 之间的 bitcount(x) 最大的x

简析:从 l 开始一位一位的加 1直到大于 r

寒假练习题解 第三周 2.1-2.7寒假练习题解 第三周 2.1-2.7
 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath>   
 5 #include<algorithm>  
 6 using namespace std;
 7 
 8 typedef long long LL;
 9 
10 int main()
11 {
12     int n;
13     LL l,r;
14     scanf("%d",&n);
15     while(n--)
16     {
17         scanf("%I64d %I64d",&l,&r);
18         for(int i=0;i<63;i++)
19             if((l|(1LL<<i))<=r) l|=(1LL<<i);
20             
21             printf("%I64d\n",l);
22     }
23 }
参考代码

 

2.7

Problem A Towers

题意:最多进行k次移动单块操作,使得最高塔与最低塔高度差最小。

简析:因为数据很小,反复排序把最高的移一个到最低的即可。

寒假练习题解 第三周 2.1-2.7寒假练习题解 第三周 2.1-2.7
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <vector>
 4 #include <algorithm>
 5 using namespace std;
 6 typedef pair<int, int> pii;
 7 vector<pii> ans;
 8 pii t[111];
 9 
10 int main(void)
11 {
12     int n, k;
13     scanf("%d %d", &n, &k);
14     for(int i = 0; i < n; i++)
15     {
16         scanf("%d", &t[i].first);
17         t[i].second = i + 1;
18     }
19     for(int i = 0; i < k; i++)
20     {
21         sort(t, t + n);
22         if(t[0].first == t[n-1].first) break;
23         t[0].first++, t[n-1].first--;
24         ans.push_back(pii(t[n-1].second, t[0].second));
25     }
26     sort(t, t + n);
27     printf("%d %d\n", t[n-1].first - t[0].first, ans.size());
28     for(int i = 0; i < ans.size(); i++) printf("%d %d\n", ans[i].first, ans[i].second);
29     return 0;
30 }
参考代码

 

Problem B Exams

题意:n门考试,第$i$门可以在${a}_{i}$或者${b}_{i}$时考$(a > b)$,但是登记仍按照${a}_{i}$,

   要求登记时间非严格递增,问考完至少要几天。

简析:先按照${a}_{i}$排序,从前往后扫,维护前几门考完的时间,

   如果这门${b}_{i}$大于等于前面考完的时间则提前考,否则按原时间。

寒假练习题解 第三周 2.1-2.7寒假练习题解 第三周 2.1-2.7
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 typedef pair<int, int> pii;
 6 pii c[5555];
 7 
 8 int main(void)
 9 {
10     int n;
11     scanf("%d", &n);
12     for(int i = 0; i < n; i++) scanf("%d %d", &c[i].first, &c[i].second);
13     sort(c, c + n);
14     int ans = c[0].second;
15     for(int i = 1; i < n; i++)
16         ans = c[i].second >= ans ? c[i].second : c[i].first;
17     printf("%d\n", ans);
18     return 0;
19 }
参考代码