Codeforces Round 993 (Div. 4)

https://codeforces.com/contest/2044

A. Easy Problem

签到题。对于大小为n的矩阵，有n-1个a>0&&b>0的(a,b)pair，满足b=n-a。

#include <iostream>
#include <map>
#include <string>
using namespace std;
 
int main()
{
  int t;
  cin>>t;
  while(t--){
    int n;
    cin>>n;
    cout<<n-1<<endl;
  }
  return 0;
}

B. Normal Problem

给定字符串，求其中心对称后的字符串。将i和n-i-1换位置，再对所有单个字符镜像即可。

#include <iostream>
#include <map>
#include <string>
using namespace std;
void mirror(string& s,int i){
    if(s[i]=='q') s[i]='p';
    else if(s[i]=='p') s[i]='q';
}
int main()
{
    int t;
    cin>>t;
    while(t--){
        string s;
        cin>>s;
        int n=s.size();
        for(int i=0;i<(s.size()+1)/2;i++){
            swap(s[i],s[n-i-1]);
            mirror(s,i);
            if(i!=n-i-1)
                mirror(s,n-i-1);
        }
        cout<<s<<endl;
    }
    return 0;
}

C. Hard Problem

两列m个座位，a个同学只坐第一列，b个同学只做第二列，c个同学都能做，问最多坐下多少个人。

优先让a、b坐，然后c补余下的位置。

#include <iostream>
#include <map>
#include <string>
using namespace std;
 
int main()
{
    int t;
    cin>>t;
    while(t--){
        int m,a,b,c;
        cin>>m>>a>>b>>c;
        int res=0;
        int r1=m,r2=m;
        res+=min(a,r1);
        r1-=min(a,r1);
        res+=min(b,r2);
        r2-=min(b,r2);
        res+=min(c,r1+r2);
        cout<<res<<endl;
    }
    return 0;
}

D. Harder Problem

给定数组a，构造数组b，使得数组b的1~bi的子数组的众数为ai。

因为允许b中数的大小为1~n，而且若两数出现的次数相同，他们都为众数。所以可以直接将1~n填入b中，构造一个无重复数的数组。

当ai未在前面出现的话，bi赋值为ai，否则，选择一个随机的数赋值，这个b前面没用到，a后面也不会出现。

#include <iostream>
#include <map>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int N = 2e5+10;
int a[N];
int main()
{
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        set<int> s;
        for(int i=0;i<n;i++){
            cin>>a[i];
            s.insert(a[i]);
        }
        int t=1;
        set<int> s2;
        for(int i=0;i<n;i++){
            if(s2.count(a[i])){
                while(s.count(t))
                    t++;
                cout<<t<<" ";
                s.insert(t);
            }else{
                cout<<a[i]<<" ";
                s2.insert(a[i]);
            }
        }
        cout<<endl;
    }
    return 0;
}

E. Insane Problem

给定k和x，y的范围，求(x,y)满足y/x=k^n的个数，n>=0.

y=x*k^n，枚举n，n确定后，二分x，找到使得y落到指定区间内的最大x和最小x。即为pair的数量。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL y(LL x,LL k,LL n){
    return x*pow(k,n);
}
int main()
{
    LL t;
    cin>>t;
    while(t--){
        LL k,l1,r1,l2,r2;
        cin>>k>>l1>>r1>>l2>>r2;
        LL ans=0;
        for(LL i=0;i<=32;i++){
            LL l=l1,r=r1;
            while(l<r){
                LL mid=l+r+1>>1;
                if(y(mid,k,i)>r2)
                    r=mid-1;
                else
                    l=mid;
            }

            if(y(l,k,i)<l2) continue;

            LL right = l;//最大的x

            l=l1,r=r1;
            while(l<r){
                LL mid=l+r>>1;
                if(y(mid,k,i)<l2)
                    l=mid+1;
                else
                    r=mid;
            }
            if(y(l,k,i)>r2) continue;

            LL left = l;//最小的x

            //cout<<left<<" "<<right<<endl;
            ans+=right-left+1;

        }
        cout<<ans<<endl;
    }
    return 0;
}