2021牛客暑期多校訓練營4

文章目錄

• ​​C--LCS​​
• ​​F--Just a joke​​
• ​​I--Inverse Pair​​

C–LCS

​​題目連結​​

題意:

表示 和

給定三個字元串 , ,,要求滿足 , ,

輸出滿足要求的

題解:

構造

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,n;
    cin>>a>>b>>c>>n;
    int x=min(a,min(b,c));
    if(c<=n-(b-a)&&a+b-c<=n&&c+a-b<=n) 
    {
        string ans1,ans2,ans3;

        for(int i=1;i<=a;i++) ans1+='a',ans2+='a';
        for(int i=1;i<=x;i++) ans3+='a';


        int aa=ans1.size();
        int bb=ans2.size();
        int cc=ans3.size();

        for(int i=1;i<=b-cc;i++) ans3+='b',ans2+='b'; 


        for(int i=1;i<=c-x;i++) ans1+='c',ans3+='c';

        aa=ans1.size();
        bb=ans2.size();
        cc=ans3.size();

        for(int i=aa;i<n;i++) ans1+='z';
        for(int i=bb;i<n;i++) ans2+='q';
        for(int i=cc;i<n;i++) ans3+='e';

        cout<<ans1<<endl<<ans2<<endl<<ans3<<endl;
    }
    else cout<<"NO"<<endl;
 
    return 0;
}      

F–Just a joke

​​題目連結​​

題意:

在無向圖

選擇 的一條邊，從

選擇 中沒有任何環的連通分量，然後将其從

不能操作的玩家輸

題解:

判斷點加邊的奇偶性即可

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    int x,y;
    for(int i=0;i<m;i++){
        cin>>x>>y;
    }
    if((n+m)&1) cout<<"Alice"<<endl;
    else cout<<"Bob"<<endl;

}      

I–Inverse Pair

​​題目連結​​

題意:

給定一個序列 , 可以對于每一個 , 可以選擇加

#include<bits/stdc++.h>
#define ll long long
using namespace std;


const int N=2e5+5;
const int inf=0x3f3f3f3f;
const int MAX = 5e5 + 10;
int tools[MAX];
long long num;
int a[N];
map<int,int> mp;

void get_num(int l,int r)             
{

  if(l >= r) return;
  
  
  int mid = (l+r) >> 1;
  get_num(l,mid);
  get_num(mid+1,r);
  
  int i = l,j = mid+1,k = l;
  while(i <= mid&&j <= r) {
    if(a[i] <= a[j]){
      num += j - mid - 1;
      tools[k++] = a[i++];
    }
    else tools[k++] = a[j++];
  }
  while(i <= mid){
    num += j - mid - 1;
    tools[k++] = a[i++];
  }
  while(j <= r)  tools[k++] = a[j++];
  
  for(i = l;i <= r;i++)    a[i] = tools[i];
}
int main()
{
  int n;
  cin>>n;
  int can=0;
  for(int i=1;i<=n;i++) cin>>a[i];
  for(int i=1;i<=n;i++)
  {
    
    if(mp[a[i]+1])
    {
      can++;
      continue;
    }else{
      mp[a[i]]++;
    }
  }
  get_num(1,n);
  cout<<num-can<<endl;
  return 0;
}