CF-673-Div-2-部分

这场发现自己原来还有很多东西是没有思路的，思维题写成这样，每日div2​的训练指标不能停了。

B.Two Arrays

题意：

现给你一个长为$n$的数组$a$和一个数字$k$，定义$f(x)$为一个数组里有多少对元素加起来等于$k$，先要你将数组$a$拆分成两个数组$b,c$，要求$f(b)+f(c)$最小，输出拆分方案。

题解：

将$a$中元素分为三种，即$>k/2,<k/2$和$=k/2$，三类，我们将第一类和第二类分开来放，然后将第三类的平分放入$b,c$数组即可，单次询问时间复杂度为$O(n)$。

ps：细节部分写炸了，但整体思想没错，虽然不是上述的。

AC代码：

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define _for(i,a,b) for(int i = (a);i<(b);++i)
#define endl '\n'
using namespace std;


int a[100005];
signed main() {
  FIO;
  int T;cin>>T;
  while(T--){
    int n,t;cin>>n>>t;
    _for(i,0,n)cin>>a[i];
    int x=INT_MAX,cnt=0;
    if(t%2==0)x=t/2;
    _for(i,0,n){
      if(a[i]==x)++cnt;
    }
    int q=cnt;
    _for(i,0,n){
      if(a[i]==x){
        if(q>cnt/2)cout<<"1 ";
        else cout<<"0 ";
        q--;
      }
      else cout<<(a[i]>t/2?1:0)<<' ';
    }
    cout<<endl;
  }
  return 0;
}

C.k-Amazing Numbers

题意：

现给你一个长为$n$的数组$a$，定义$k-numbers$为数组长为$k$的子串中都出现过的最小数字，若不存在则为$-1$，要你求出$k\in[1,n]$的所有答案，且数组中的元素大小都不超过$n$。

题解：

很容易想到的就是，当一个数字的最大间隔为$x$，则$k\ge x$的答案可为$x$；但是还有一种情况，要判断这个数字最后一次出现的位置到结尾的距离，设为$y$，则$k\ge y$的答案都可为$y$，单次询问时间复杂度为$O(n)$。

AC代码：

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define _for(i,a,b) for(int i = (a);i<(b);++i)
#define endl '\n'
using namespace std;


int a[300005],ans[300005],dist[300005],ind[300005];
signed main() {
  FIO;
  int T;cin>>T;
  while(T--){
    int n;cin>>n;
    _for(i,1,n+1)ans[i]=-1,dist[i]=ind[i]=0;
    _for(i,1,n+1){
      cin>>a[i];
      int x=a[i];
      dist[x]=max(dist[x],i-ind[x]);
      ind[x]=i;
    }
    _for(i,1,n+1){
      int x=dist[i];
      x=max(x,n-ind[i]+1);
      _for(j,x,n+1){
        if(ans[j]!=-1)break;
        ans[j]=i;
      }
    }
    _for(i,1,n+1)cout<<ans[i]<<' ';
    cout<<endl;
  }
  return 0;
}

D.Make Them Equal

题意：

现在给你一个长为$n$的数组$a$，里面的元素都是正整数。现你可以任意选定其中的下标$i,j$满足$a_i\ne a_j$和一个任意的数$x$，进行以下操作：$a_i=a_i-x\times i,b_i=b_i+x\times i$，这样的操作不能超过$3n$次，问是否存在一系列操作使$a$里的所有元素相同，存在则输出操作次数和操作方案，不存在则输出$-1$。

题解：

不难发现的是，如果$a$里的和不是$n$的倍数，那么一定无法完成。既然次数限定在$3n$以内，那么我们可以先把所有数都先加到$a_1$上，具体如何实现呢，如果$a_i\%i=0$则我们可以直接执行这样的操作，否则我们需要先从$a_1$中抽数使$a_i\%i=0$，再进行这样的操作（可行性，因为i-a[i]%i$\in$[1,i)且之前的数肯定是$\ge1$的则到$i$位的时候，$a_1$的值肯定是够的），最后再把$a_1$的数平均分配到各个位置上，最坏的情况下，所需操作数为$2\times(n-1)+(n-1)$，完全够，单次询问时间复杂度为$O(n)$。

AC代码：

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define _for(i,a,b) for(int i = (a);i<(b);++i)
#define endl '\n'
using namespace std;


int a[10005];
signed main() {
  FIO;
  int T;cin>>T;
  while(T--){
    int n;cin>>n;
    int sum=0,cnt=0;
    _for(i,1,n+1){
      cin>>a[i];
      sum+=a[i];
      if(a[i]%i)++cnt;
    }
    if(sum%n){cout<<"-1\n";continue;}
    cout<<2*(n-1)+cnt<<endl;
    int ave=sum/n;
    _for(i,2,n+1){
      if(a[i]%i){
        cout<<1<<' '<<i<<' '<<i-a[i]%i<<endl;
        cout<<i<<' '<<1<<' '<<a[i]/i+1<<endl;
      }else cout<<i<<' '<<1<<' '<<a[i]/i<<endl;
    }
    _for(i,2,n+1)cout<<1<<' '<<i<<' '<<ave<<endl;
  }
  return 0;
}

• 本文作者： baddog
• 本文链接： https://katoli.github.io/2020/09/28/CF-673-Div-2-部分/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！