2021“MINIEYE杯”中国大学生算法设计超级联赛（1）
1001 Mod, Or and Everything
题意：给你一个n，计算（n mod 1）or (n mod 2) or...or(n mod (n-1)) or (n mod n)。
思路：我们可以发现余数以此为0，1，2，3,...,(n-1)/2,...,3，2，1，0。即包含了0~(n-1)/2中的所有数，由此可以推得答案为,其中
是第一个大于(n-1)/2的二次幂。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t; cin >> t;
while(t--) {
ll n; cin >> n;
ll tmp=(n-1)/2;
ll ans = 1;
while(ans <= tmp) {
ans*=2;
}
cout << ans - 1 << endl;
}
return 0;
}1005 Minimum spanning tree
题意：一个图中有n-1个点，每个点的权值为2~n，在顶点a和顶点之间连一条边的代价是lcm(a,b)，计算将所有点连成一个树的最小代价。
思路：所有质数都连接到2上来，所有合数都连接到它的最小质因数上。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10000000+5;
ll sum[N];
ll st[N],prime[N],cnt;
ll vis[N];
void ola() {
for(int i=2;i<=10000000;i++) {
if(!st[i]) prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<=10000000;j++) {
st[i*prime[j]]=1;
vis[i*prime[j]]=i;
//vis[i*prime[j]]=i;
//cout << "ceshi : " << i*prime[j] << " " << i << endl;
if(i%prime[j]==0) {
break;
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t; cin >> t;ola();
for(int i=3;i<=N;i++) {
if(st[i]==0) sum[i]=sum[i-1]+i*2;
else sum[i]=sum[i-1]+i;
}
while(t--) {
int n; cin >> n;
cout << sum[n] << endl;
}
return 0;
}1008 Maximal submatrix
题意：给你一个n*m的矩阵，输出每列不递减的最大面积子矩阵的面积。
思路：我们先对每一列的值进行一个处理，如果当前位置的值小于上一个位置的值我们令它为1，否则为上一个+1。例如某一列的值为2，3，5，4，5，6，那么处理完之后应该为1，2，3，1，2，3，这样我们就得到了这一列到该元素的一个不递减长度。最后循环每行，判断一下连续个数。注意不要忘记将算出来的答案与m相比。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3+5;
int a[N][N],h[N][N];
int main()
{
int t; scanf("%d",&t);
while(t--) {
int n,m; scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
scanf("%d",&a[i][j]);
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(i==1||a[i][j]<a[i-1][j]) {
h[i][j]=1;
}
else h[i][j]=h[i-1][j]+1;
}
}
int cnt=0,minn=n,ans=0;
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(h[i][j]!=1) {
cnt++;
minn=min(minn,h[i][j]);
if(j==m&&cnt) {
ans=max(ans,minn*cnt);
cnt=0;
minn=N;
}
}
else {
ans=max(ans,minn*cnt);
cnt=0;
minn=n;
}
}
}
printf("%d\n",max(ans,m));
}
return 0;
}1009 KD-Graph
题意：n个点，m条边，将n个点严格分为k组。是否存在一个最小的D值恰好使原图变为k个连通的部分。题目中连通的定义：
①对于任意一组，组内的顶点两两之间至少存在一条权值小于等于w的路径
②对于任意两组，组间的顶点两两之间不存在任何一条权值小于等于w的路径
思路：将权值按照从小到大排序，用now记录当前组数，取出相同权值的所有边，将这些边的顶点用并查集两两合并，没合并一次组数now-1，因为每合并一次独立的顶点就少了一个，同时记录此时的权值ans，当枚举到下一阶段时，此时边权与上次不一样，判断此时now的值，如果等于k，则输出此时的ans。
赛后补这道题wa了十多次，结果改用C++，t了，再改scanf，过了。。。跟六月份打CCPC正好反过来，当时有一道题用C++一直wa,改用G++就a了。。。
代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6+10;
struct node{
int u,v,c;
}p[N];
int fa[N];
bool cmp(node x, node y)
{
return x.c<y.c;
}
int get(int x) {
return fa[x]==x?fa[x]:fa[x]=get(fa[x]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t; scanf("%d",&t);
while(t--) {
int n,m,k;scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++) {
scanf("%d %d %d",&p[i].u,&p[i].v,&p[i].c);
}
sort(p + 1, p + 1 + m, cmp);
int now=n,ans=0;
bool flag=false;
for(int i=1;i<=m;i++) {
if(p[i].c!=p[i-1].c) {
if(now==k) {
break;
}
}
int x=get(p[i].u);
int y=get(p[i].v);
if(x==y) continue;
now--;
fa[x]=y;
ans=p[i].c;
}
if(now==k) cout << ans << endl;
else cout << -1 << endl;
}
return 0;
} 
投递京东等公司10个岗位 >