[数据结构与算法]牛客挑战赛56AB题

A题：
思路：
这道题首先观察题目性质可以得到：只有当ai 和 aj存在倍数关系时才能得到 ai | aj >= lcm(ai, aj);
证明：
ai | aj <= ai + aj 因为按位或是不进位加法，所以两个数按位或一定小于等于两个数相加
若ai 和 aj 均大于 1 时，ai * aj >= ai + aj >= ai | aj;
lcm(ai,aj) >= ai * aj, 当取等于时，ai 和 aj存在倍数关系，所以只有当ai 和 aj存在倍数关系时，才可能取到ai | aj >= lcm(ai, aj);
若ai 和 aj存在一个数位1时，ai 与 aj之间肯定存在倍数关系
至此可以证明只有ai 和 aj 之间存在倍数关系时，可以得到ai | aj >= lcm(ai, aj）；

#include"bits/stdc++.h"

using namespace std;

const int N = 2e5 + 10, M = 2E6 + 10;
int a[N];
bool st[M];
map<int,int>f;
int main()
{
    int n;
    cin >> n;
    int maxn = 0;
    for(int i = 0; i < n; i ++)
    {
         scanf("%d", &a[i]), maxn = max(maxn, a[i]);//输入a[i]，且找到a序列中最大值
        if(st[a[i]])//判断a序列中是否存在两个a[i]，若存在两个a[i]，则两个a[i]之间存在倍数关系直接输出答案
        {
            cout << f[a[i]] + 1 << ' ' << i + 1 << endl;
            return 0;
        }
        f[a[i]] = i;//存储每个a[i]出现的位置
        st[a[i]] = true;//记录每个值是否出现过
    }
    
   
   sort(a , a + n);    
    for(int i = 0; i < n ;i ++)
    {
        if(a[i] * 2 > maxn)break;//因为之前判断了一倍的倍数关系，所以这里最小是两倍的倍数关系，若两倍a[i]大于序列的最大值，则直接退出循环
        int k = 2;
        while(a[i] * k <= maxn)
        {
            if(st[a[i] * k])//判断k倍a[i]是否出现过
            {
                cout << min(f[a[i]], f[a[i] * k]) + 1 << ' ' << max(f[a[i]], f[a[i] * k]) + 1;
                return 0;
            }
            ++ k;
        }
    }
    cout << -1;
}

B题：
思路：直接模拟。（每个人可以根据自己的想法来完成代码）
注意事项：
你所构造的m中排序中，必须满足每个人在这m种排序中的位置的最小值等于题目所给定的最小值
也就是说你构造的序列
a11…a1n
a21…a2n
…
am1…amn
任意的第i列的最小值必须等于x[i] （1 <= i <= n)
x[i]为题目所给定的每个人的位置

#include"bits/stdc++.h"

using namespace std;
const int N = 2010;
vector<int>f[N];//存储题目给定的每个要求
vector<int>res[N];//存储m中排序的答案
vector<int>ans[N];//存储每个人在m中排序中的答案
set<int>s[N];//存储每个人在m中排序中是否已经出现
int n , m, x[N], mini[N];
void solve(int nn,int k)
{
    if(nn == 0)return ;//若n个条件全部处理完则直接退出递归
    nn -= f[k].size();//减去本轮处理的条件
    
    if(f[k].size() > m)
    {
        cout << "No";//若当前想要排名位第k位的人大于m，则直接输出答案退出程序
        exit(0);
    }
    for(int i = 0; i < f[k].size(); i ++)
        res[i].push_back(f[k][i]), s[i].insert(f[k][i]);//把每个想要排名位K的人安排进m个排序中
    
    int t = f[k].size();
    while(t < m)//若想要排名位k的人小于m，则拿想要排名<=k的人来填补剩下没有填满的位置
    {
        bool flag = false;
        for(int i = 0; i <= k ;i ++)
        {
            for(int j = 0; j < f[i].size(); j ++)
            {
                if(!s[t].count(f[i][j]))
                {
                    res[t].push_back(f[i][j]);
                    s[t].insert(f[i][j]);
                    flag = true;
                    break;
                }
            }
            if(flag)break;
        }
        if(!flag)
        {
            cout << "No";//若找不到人填补位置则直接输出答案退出
            exit(0);
        }
        t ++;
    }
    solve(nn, k + 1);
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n ;i ++)
    {
        s[i].clear();
        cin >> x[i];
        f[x[i]].push_back(i);//把每个人的要求存储到相应的vector中
    }
        solve(n, 1);//递归处理题目给定的n个条件
    
    for(int i = 0 ;i < m ;i ++)
    {
        if(res[i].size() < n)
        {
            for(int j = 1; j <= n ;j ++)
                if(!s[i].count(j))
                    res[i].push_back(j);
        }
    }
    memset(mini, 0x3f, sizeof mini);
    for(int i = 0 ;i < m ;i ++)//把题目没有限定的位置填补满
    {
        for(int j = 0; j < n ;j ++)
        {
            ans[res[i][j]].push_back(j + 1);
            mini[res[i][j]] = min(mini[res[i][j]], j + 1);
        }
    }
    for(int i = 1; i <= n ;i ++)
        if(mini[i] != x[i])//若i这个人在我们安排的位置中的最小值小于了题目给定的最小值，则无解
        {
            cout << "No";
            return 0;
        }
    cout << "Yes" << endl;//输出答案
    for(int i = 1; i <= n ;i ++)
    {
        for(int j = 0 ;j < m ;j ++)
            if(j == 0)printf("%d", ans[i][j]);
            else printf(" %d", ans[i][j]);
        cout << endl;
    }
}```