Codeforces Round #552 (Div. 3)

偏执的太偏执、 2021-11-10 12:48 194阅读 0赞

**B. Make Them Equal**

## Description ##

给定一个长度为 nn 的序列，请你选择一个非负整数 DD，然后将序列中的所有元素要么加上 DD，要么减去 DD，要么不做改变，使得修改后的序列所有元素都相等。最小化 DD

## Input ##

第一行是一个整数 nn

第二行 nn 个整数描述这个序列

## Output ##

输出一行一个整数代表 DD

思路：

这道题其实主要的就是去重，然后之后模拟就好了。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

Ackerman

**D. Walking Robot**

## Description ##

在一个数轴上，有一个机器人要从 x = 0x=0 处移动到 x = nx=n 处。机器人身上有两种电池，第一种是普通电池，第二种是太阳能可充电电池，普通电池的容量上限为 bb 点电量，太阳能电池的容量上限为 aa 点电量。

定义数轴上的第 ii 段线段代表左端点为 x = i - 1x=i−1，右端点为 x = ix=i 的线段。

这 nn 条线段中，有一些线段可以被太阳照射到。

当机器人向右移动一个单位时，它会消耗一点电量。

当机器人走到一个可以被太阳照射到的线段上时，如果他是使用普通电池走到这条线段的并且太阳能电池的电量不满，则可以增加一点电量。这里的线段特指长度为 11 的线段。即如果它从一条被照射到的线段上走到另一条被照射的线段上，依然有可能增加电量。

机器人总电量为 00 或到达终点时会停下。现在请你求出机器人最远可以走多远。

## Input ##

第一行三个整数代表 n,~b,~an, b, a

下面一行 nn 个整数，第 ii 个整数 s\_isi 描述第 ii 条线段是否被阳光照射，如果被照射则为 11，否则为 00。

## Output ##

一行一个整数，代表答案。

# #

思路：

其实就是一个简单的贪心的思想。没阳光的地方，我们让太阳能电池先走。 有阳光的地方，我们让普通电池先走

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

Ackerman

**E. Two Teams**

## Description ##

有 nn 个人站成一排，他们每个人都有一个能力值，能力值互不相同。

有两个教练，分别是 11 队教练和 22 队教练。由 11 队教练先挑，每次教练会将场上剩下的人中能力值最高的和他左右各 kk 个人从场上挑出，加入自己的队伍，然后由另一名教练再挑。

在挑选时如果一侧不足 kk 个人则将这些人都挑入队伍。

请求出每个人最终加入的是哪个队伍

## Input ##

第一行是两个整数 n,~kn, k

下面一行是一个 11 到 nn 的排列，描述每个人的能力值

## Output ##

输出一行一个字符串。如果第 ii 个人最终加入 11 队，则字符串第 ii 位为 11，否则为 22。

思路：

用线段树去维护区间最大值，然后每次选人的时候就是对区间进行修改罢了。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <stdio.h>
      2 #include <algorithm>
      3 #include <iostream>
      4 #include <stdbool.h>
      5 #include <stdlib.h>
      6 #include <string>
      7 #include <string.h>
      8 #include <math.h>
      9 #include <vector>
     10 #include <queue>
     11 #include <stack>
     12 #include <set>
     13 #include <map>
     14  
     15 #define INF 0x3f3f3f3f
     16 #define LL long long
     17 #define MAXN 200005
     18 using namespace std;
     19  
     20  
     21 struct segment_tree{
     22     int l,r,sum;
     23     int lazy;
     24 }tree[MAXN<<2];
     25  
     26 int pre[MAXN],nex[MAXN],pos[MAXN];
     27 int ans[MAXN];
     28 int a[MAXN];
     29  
     30 void pushup(int nod)
     31 {
     32     tree[nod].sum = max(tree[nod<<1].sum,tree[(nod<<1)+1].sum);
     33 }
     34  
     35 void pushdown(int nod)
     36 {
     37     if (tree[nod].lazy)
     38     {
     39         tree[nod<<1].sum = 0;
     40         tree[(nod<<1)+1].sum = 0;
     41         tree[nod<<1].lazy = 1;
     42         tree[(nod<<1)+1].lazy = 1;
     43         tree[nod].lazy = 0;
     44     }
     45 }
     46  
     47 void build(int l,int r,int nod)
     48 {
     49     tree[nod].lazy = 0;
     50     if (l == r)
     51     {
     52         tree[nod].l = l;
     53         tree[nod].r = r;
     54         tree[nod].sum = a[l];
     55         return ;
     56     }
     57     int mid = (l+r)>>1;
     58     build(l,mid,nod<<1);
     59     build(mid+1,r,(nod<<1)+1);
     60     pushup(nod);
     61 }
     62  
     63 void updata(int l,int r,int ll,int rr,int nod)
     64 {
     65     if (ll == l && rr == r)
     66     {
     67         tree[nod].sum = 0;
     68         tree[nod].lazy = 1;
     69         return ;
     70     }
     71     pushdown(nod);
     72     int mid = (l+r)>>1;
     73     if (rr <= mid)
     74         updata(l,mid,ll,rr,nod<<1);
     75     else if (ll>mid)
     76         updata(mid+1,r,ll,rr,(nod<<1)+1);
     77     else{
     78         updata(l,mid,ll,mid,nod<<1);
     79         updata(mid+1,r,mid+1,rr,(nod<<1)+1);
     80     }
     81     pushup(nod);
     82 }
     83  
     84 int main()
     85 {
     86     //freopen("../in.txt","r",stdin);
     87     int n,k;
     88     scanf("%d%d",&n,&k);
     89     for (int i=1;i<=n;i++)
     90     {
     91         scanf("%d",&a[i]);
     92         pre[i] = i-1;
     93         nex[i] = i+1;
     94         pos[a[i]] = i;
     95     }
     96     build(1,n,1);
     97     int type = 1;
     98     while (1)
     99     {
    100         int maxx = tree[1].sum;
    101         if (maxx == 0)
    102             break;
    103         int id = pos[maxx];
    104         ans[id] = type;
    105         int tmp_l = id;
    106         for (int i=1;i<=k;i++)
    107         {
    108             if (pre[tmp_l]==0)
    109                 break;
    110             ans[pre[tmp_l]] = type;
    111             tmp_l = pre[tmp_l];
    112         }
    113         int tmp_r = id;
    114         for (int i=1;i<=k;i++)
    115         {
    116             if (nex[tmp_r] == n+1)
    117                 break;
    118             ans[nex[tmp_r]] = type;
    119             tmp_r = nex[tmp_r];
    120         }
    121         updata(1,n,tmp_l,tmp_r,1);
    122         int temp1 = nex[tmp_r];
    123         int temp2 = pre[tmp_l];
    124         pre[temp1] = temp2;
    125         nex[temp2] = temp1;
    126         type = (type==1)?2:1;
    127     }
    128     for (int i=1;i<=n;i++)
    129         printf("%d",ans[i]);
    130     printf("\n");
    131     return 0;
    132 }

Ackerman

**F. Shovels Shop**

## Description ##

商店里有 nn 双鞋，每双鞋都有一个价格。你要买其中的严格 kk 双。每双鞋只能被买一次。

你每次购买可以挑选剩余鞋中的任意一个子集来购买集合中所有的鞋。

有 mm 种套餐，第 ii 种套餐代表如果一次性购买 x\_ixi 双鞋则其中最便宜的 y\_iyi 双免费。

这 mm 种套餐每种都可以用任意次。

现在请求出买严格 kk 双鞋的最小化费。

## Input ##

第一行是三个整数 n,~m,~kn, m, k

一行 nn 个整数描述每双鞋的价格

下面 mm 行，每行两个整数 x\_i,~y\_ixi, yi，描述一个套餐。

## Output ##

输出一行一个整数代表答案。

题解：参考官方解释。

**1，我们只需在最便宜的k件商品中，利用满减活动，尽可能的减少花费。**

**2，我们把选出来k件最便宜的商品中，从小到大排个序，此时满减最优惠的就是在相邻的商品中使用，因为它每次只能减掉最便宜的，此时这样的话就最优，这点是不好想到的。**

**3，最后我们就可以dp了，类似于背包，在某一连续商品，判断下使不使用满减活动。**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

Ackerman

**G. Minimum Possible LCM**

### 题意翻译 ###

## Description ##

给定一个长度为 nn 的序列 aa，找出两个数，最小化他们的最小公倍数

## Input ##

第一行是一个整数 nn

下面一行 nn 个整数描述这个序列

## Output ##

输出一行两个整数代表这两个数在序列中的位置。如果有多解则任意输出一个即可。

思路：

枚举所有的gcd的值。

a\[i\]<=1e7，那么gcd也<=1e7，我们就可以枚举gcd，记录一下a\[i\]是否出现，然后用gcd筛出i，j。然后计算出lcm

考虑如果枚举到 x，数列中出现最小的两个 x 的倍数是 y 和 z，若 x 只是 y 和 z 的因数，但不是最大的怎么办：

考虑枚举到 gcd(y,z) 时依然可以更新答案，由于x<gcd(y, z)，所以用 x 求出的答案要大于用 gcd(y, z) 求出的答案，错误的答案会被正确的更新掉。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

Ackerman

转载于:https://www.cnblogs.com/-Ackerman/p/11278940.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211109/aa4343e9cba1490f80565a129d7dff24.png