牛客挑战赛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;}
}```本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！