开学过半 (cf补题和算法训练）

Problem - A - Codeforces

题意： 给你一个n/2个元素的b数组，然后让你构造出一个n个元素的排列数组

其中这些p数组里的数有以下要求

注意这个p数组要求你搞字典序最小，也就是最好小的元素在前面

如果b = [4,3,6]，那么可以从中得到的词法最小排列是p = [1,4,2,3,5,6]，因为：

• b1=max(p1,p2)=max(1,4)=4
• b2=max(p3,p4)=max(2,3)=3
• b3=max(p5,p6)=max(5,6)=6

就是让你搞一个这样的，如果不行就打-1

题解：

首先我们需要知道 搞一个n的排列里面的元素不能大于n所以，我们在题目给出的b数组里判断一些如果b[i]>n  ，我们直接输出-1即可

否则 我们就需要统计一下在这n个排列中我们缺了拿一些数字，我们用set存储，方便我们后面进行删除操作

然后我们就看规则拉

首先我们需要在这些缺的数组里找到要小于b数组的元素然后把他俩放在一起就行了

然后，我们可以二分寻找最大且小于当前元素的值，这里注意，我们应该倒着去扫b数组，这样二分最大元素就在后面

找到以后，我们直接删除这个元素，然后一跑就是字典序最小了，我们在缺的值，大的值都在后面

#include <bits/stdc++.h>
#pragma  GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
//#define endl '\n';
using namespace std;
const int N=2e5+7,M=1e1;
const int INF = 0x3f3f3f3f;
const int mod=100003;
typedef pair<int,int> PII;

int a[N];

void solve()
{
    int n;
    cin>>n;
    int ma=0;
    map<int,int> mp;
    set<int> b;
    int f=1;
    for(int i=1;i<=n/2;i++)
    {
        cin>>a[i];
        if(a[i]>n || mp[a[i]]==1)
        {
            f=0;
        }
        mp[a[i]]=1;
        ma=max(ma,a[i]);
    }
    if(f==0)
    {
        cout<<-1<<endl;
        return;
    }

    for(int i=1;i<=ma;i++)
    {
        if(mp[i]!=1)
        {
            b.insert(i);
        }
    }
    int c[N];
    for(int i=n/2;i>=1;i--)
    {
        auto it=b.upper_bound(a[i]);
        if(it==b.begin())
        {
            f=0;
            break;
        }
        it--;
        c[i]=*it;
        b.erase(c[i]);
    }
    if(f==0)
    {
        cout<<-1<<endl;
        return;
    }
    for(int i=1;i<=n/2;i++)
    {
        cout<<c[i]<<" "<<a[i]<<" ";
    }
    cout<<'\n';
}
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

Problem - D - Codeforces

题意：

给你一个n和一个k，让你找到1到k里的一个数x，让n*x得出的结果尾巴的0要尽可能地多

如果无论这么搞都没有，那么就输出n*k即可

题解：

 我们先想一下  0是怎么来的

是不是由2*5得来，所以我们想要更多地0，我们就需要在n里面找多余地2和5

里面地2和5会相互成0，所以我们找出多余地，然后用在x里面乘就行了，就是用x里面地2  或者   5去帮n补0

这个就是分离因子地思想

然后统计一下10

最后m/x*x就是在k里面找地最大数咯

#include <bits/stdc++.h>
#pragma  GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
//#define endl '\n';
using namespace std;
const int N=2e5+7,M=1e1;
const int INF = 0x3f3f3f3f;
const int mod=100003;
typedef pair<int,int> PII;

int a[N];
int n,m;
void solve()
{

    cin>>n>>m;
    int t=n;

    int ans2=0,ans5=0;
    while (t%2==0)
    {
        ans2++;
        t/=2;
    }
    t=n;
    while (t%5==0)
    {
        ans5++;
        t/=5;
    }
    int x=1;
    while (ans2>ans5 && x*5<=m)
    {
        x*=5;
        ans2--;
    }
    while (ans2<ans5 && x*2<=m)
    {
        x*=2;
        ans5--;
    }

    while (x*10<=m)
    {
        x*=10;
    }

    cout<<m / x * x * n<<'\n';
}
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}