当前位置：首页 > article >正文

Codeforces Round 987 (Div. 2)（前四道）

article 2024/11/16 22:25:37

A. Penchick and Modern Monument

翻译：

        在繁华大都市马尼拉的摩天大楼中，菲律宾最新的 Noiph 购物中心刚刚竣工！建筑管理方 Penchick 订购了一座由 n 根支柱组成的先进纪念碑。

        纪念碑支柱的高度可以用一个由 n 个正整数组成的数组 h 来表示，其中 $h_{i}$ 表示 1 到 n 之间所有 i 的第 i 根支柱的高度。

        彭契克希望石柱的高度不递减，即 1 到 n-1 之间所有 i 的高度为 $h_{i}\leq h_{i+1}$ 。然而，由于混淆不清，纪念碑的高度反而是非递增的，即对于 1 到 n-1 之间的所有 i， $h_{i}\geq h_{i+1}$ 。

幸运的是，彭奇克可以修改石碑，并根据需要多次对石柱进行以下操作：

将支柱的高度修改为任意正整数。形式上，选择一个下标 $1\leq i\leq n$ 和一个正整数 x，然后赋值 $h_{i}:=x$ 。

        帮助彭奇克确定使纪念碑支柱的高度不递减所需的最少操作次数 .

思路：

变为同一高度最好，选择同一高度最多的柱子为标准。

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// using pll = pair<ll,ll>;
 
void solve(){
  int n;
  int maxx = 0;  
  vector<int> nums(100,0);
  cin>>n;
  for (int i=0,num;i<n;i++){
    cin>>num;
    nums[num]++;
    maxx = max(maxx,nums[num]);
  }  
  cout<<n-maxx<<endl;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // 中间填保留几位小数，不填默认
    // cout.precision();
    ll t;cin>>t;
    while (t--) solve();
    
}

B. Penchick and Satay Sticks

翻译：

        Penchick 和他的朋友 Kohane 正在印度尼西亚旅游，他们的下一站是泗水！

        在泗水熙熙攘攘的小吃摊上，Kohane 买了 n 根沙爹，把它们排成一行，其中第 i 根沙爹的长度为 $p_{i}$ 。已知 p 是长度为 n 的排列。

        彭奇克想把沙爹棒按长度递增的顺序排列，这样，每 $1\leq i\leq n$ 时， $p_{i}=i$ 。为了好玩，他们制定了一条规则：只能交换长度相差 1 的相邻沙爹棒。从形式上看，他们可以执行以下操作任意多次（包括零次）：

选择一个下标（ $1\leq i\leq n-1$ ），使得 $|p_{i+1}-p_{i}|=1$ ；
交换 $p_{i}$ 和 $p_{i+1}$ 。

判断是否可以通过执行上述操作对排列 p 进行排序，从而对嗲嗲棒进行排序。

思路：

当左边比当前数大2即以上的数时，那个数必定换不到当前数的右边。遍历时维护左边最大值即可。

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// using pll = pair<ll,ll>;
 
void solve(){
  int n;    
  cin>>n;
  vector<int> a(n);
  for (int i=0;i<n;i++) cin>>a[i];
  if (n==2||n==1){
    cout<<"YES"<<endl;
    return;
  }else{
    int maxx = a[0];
    for (int i=1;i<n;i++){
      if (maxx>a[i]+1){
        cout<<"NO"<<endl;
        return;
      }
      maxx = max(a[i],maxx);
    }
    cout<<"YES"<<endl;
  }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // 中间填保留几位小数，不填默认
    // cout.precision();
    ll t;cin>>t;
    while (t--) solve();
}

C. Penchick and BBQ Buns

翻译：

Penchick 喜欢两样东西：方块数字和港式烧腊包！在 Penchick 生日的时候，Kohane 想送他一份礼物：n 个从左到右排列的烧腊包。烧腊包有 $10^{6}$ 种馅料可供选择，从 1 到 $10^{6}$ 。为了确保彭奇克会喜欢这份礼物，科哈尼有几个目标：

每种馅料都不能使用一次；也就是说，每种馅料要么完全不出现，要么至少出现两次。
对于具有相同馅料的两个包子 i 和 j，它们之间的距离 $|i\ -\ j|$ 必须是完全平方。

帮助 Kohane 找到选择包子馅的有效方法，或者确定是否不可能满足她的目标！如果有多个解决方案，请打印其中任何一个。

思路：

对于n为偶数，相同馅料间隔为i,i+1；

n为奇数时，由于存在 $3^{2}+4^{2}=5^{2}$ ，即可以有三个相同的馅料位置为1,10,26，10到26间为奇数有一个没配对，而11+16=27，即11可以与27配对。那么结论即为n>=27，位置1,10,26填相同馅，11,27填相同馅料，剩下的为偶数可以通过偶数情况求解。

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// using pll = pair<ll,ll>;
 
void solve(){
  int n;  
  cin>>n;
  vector<int> a(n+1,0);
  if (n%2==1){
    if (n>=27){
      a[1] = 1;a[10] = 1;a[26] = 1;a[11] = 2;a[27] = 2;
      int cnt = 3,f = 0;
      for (int i=1;i<=n;i++){
        if (a[i]==0){
          a[i] = cnt;
          f++;
        }
        if (f==2){
          f = 0;
          cnt++;
        }
      }
    }else{
      cout<<-1<<endl;
      return;
    }
  }else{
    int cnt = 1;
    for (int i=1;i<=n;i+=2){
      a[i] = cnt;
      a[i+1] = cnt;
      cnt++;
    }
  }
  for (int i=1;i<n;i++){
      cout<<a[i]<<" ";
    }
  cout<<a[n]<<endl;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // 中间填保留几位小数，不填默认
    // cout.precision();
    ll t;cin>>t;
    while (t--) solve();
    
}

D. Penchick and Desert Rabbit

翻译：

        Penchick 致力于挑战自己的极限，在阿拉伯沙漠的正午阳光下，他向自己发起了挑战！

        当彭奇克沿着一片线状绿洲跋涉时，他发现一只沙漠兔正准备沿着一排棕榈树跳跃。一共有 n 棵棕榈树，每棵树的高度用 $a_{i}$ 表示。

        如果以下条件之一完全为真，兔子就能从第 i 棵树跳到第 j 棵树：

j<i 且 $a_{j}>a_{i}$ ：兔子可以向后跳到更高的树上。
j>i 且 $a_{j}<a_{i}$ ：兔子可以向前跳到较矮的树上。

对于 1 到 n 中的每个 i，确定兔子从第 i 棵树开始所能到达的所有树的最大高度。

思路：

对于每个可跳的位置，可以任意往来，构成连通块。从左到右，维护每个连通块最大值，当前值小于连通块时，合并连通块，并更新连通块最大值。

每个位置的答案就是所属连通块的最大值。

代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// using pll = pair<ll,ll>;
const int N = 5e5+10;
vector<int> f(N),sz(N);
int find(int k){
  return f[k]==k ? f[k] : f[k] = find(f[k]);
}
void add(int x,int y){
  x = find(x);
  y = find(y);
  if (x==y) return;
  if (sz[x]<sz[y]) swap(x,y);
  f[y] = x;
  sz[x] += sz[y];
}

int n;
vector<int> nums(N);

void solve(){
  int n;cin>>n;
  for (int i=1;i<=n;i++){
    cin>>nums[i];
    sz[i] = 1;
    f[i] = i;
  }
  priority_queue<pair<int,int>> piece1;
  for (int i=1;i<=n;i++){
    int temp = nums[i];
    while (!piece1.empty()){
      int x = piece1.top().first, y = piece1.top().second;
      if (x>nums[i]){
        temp = max(x,temp);
        add(y,i);
        piece1.pop();
      }else{
        break;
      }
    }
    piece1.push(make_pair(temp,find(i)));
  }
  map<int,int> mp;
  while (!piece1.empty()){
    int x = piece1.top().first, y = piece1.top().second;
    piece1.pop();
    mp[find(y)] = x;
  }
  for (int i=1;i<n;i++){
    cout<<mp[find(i)]<<" ";
  }
  cout<<mp[find(n)]<<endl;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // 中间填保留几位小数，不填默认
    // cout.precision();
    ll t;cin>>t;
    while (t--) solve();
    
}

查看全文

http://www.kler.cn/a/396411.html