2021“MINIEYE杯”中国大学生算法设计超级联赛（1）
link:HDU
A Mod, Or and Everything
题意：
给一个数(n)，求(n)对(1)到(n-1)取模得到的(n-1)个数的或。
解法：
当(n)为偶数时，设(m=n/2-1)
当(n)为奇数时，设(m=(n-1)/2)
可以发现，(n mod i<=m)，且当(i<=m)时，有(n mod (n-i)=i)。于是可以得出(n mod i)取到(0~m)的所有整数，因此答案会是(2^k-1)，(k)的具体值判断一下即可。
AC代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve() {
ll n;
scanf("%lld",&n);
if ((n&(-n)) == n) {
printf("%lld
",max(0ll,n/2-1));
return;
}
while ((n&(-n)) != n) n-=(n&(-n));
printf("%lld
",n-1);
}
int main() {
int t;
scanf("%d",&t);
while (t--) solve();
return 0;
}
E Minimum spanning tree
题意：
给(n-1)个点(2~n)，建成一颗树，这颗树的边的权值是(lcm(a,b))，求这颗树边权值和的最小。
解法：
对于编号为(3~n)的节点，是合数的点与其约数连边，边权值就是这个数，是质数的点就与2连边，边权值是这个数的两倍。总的边权值和为（质数的和*2+合数的和），用欧拉筛预处理前缀和。
AC代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=10000010;
int prime[maxn],vis[maxn],x=0;
ll ans[maxn];
int Is_prime(int n) {
for(int i=1; i*i <= n; ++i) {
if(n%i==0) return 0;
}
return 1;
}
void oulasai(int n) //欧拉筛(线性筛)
{
for(int i=2; i <= n; i++) {
if(!vis[i]) prime[++x]=i;
for(int j=1; j <= x ;j++) {
if(i*prime[j] > n) break;
vis[i*prime[j]]=1;
if(i%prime[j] == 0) break;
}
}
ans[2]=0;
for (ll i=3; i <= n; ++i) {
if (vis[i]) ans[i]=ans[i-1]+i;
else ans[i]=ans[i-1]+i*2;
}
}
void solve() {
int n;
scanf("%d",&n);
printf("%lld
",ans[n]);
}
int main() {
oulasai(maxn);
int t;
scanf("%d",&t);
while(t--) solve();
return 0;
}
F Xor sum
题意：
给一个数组，求这数组异或和不小于k的最小连续子序列的长度。
解法：
对数列做前缀异或，题目就转化为找两个距离最近的数，使他们的异或值不小于k。
枚举靠右的那个数，维护字典数，字典数每个节点保存范围内最靠右的那个点的位置。
AC代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
const int M=3e6+10;
const int mod=998244353;
int a[N],p[M][2],mx[M];
void solve() {
int n,k;
scanf("%d%d",&n,&k);
for (int i=1; i <= n; ++i) {
scanf("%d",&a[i]);
a[i]=a[i]^a[i-1];
}
int tot=1,ansl=-1,ansr=n;
p[1][0]=p[1][1]=0;mx[tot]=-1;
for (int i=0; i <= n; ++i) {
int x=1,res=-1;
for (int j=29; j >= 0; --j) {
int w=(a[i]>>j)&1;
if (!((k>>j)&1)) {
if (p[x][w^1]) res=max(res,mx[p[x][w^1]]);
x=p[x][w];
}
else x=p[x][w^1];
if (!x) break;
}
if (x) res=max(res,mx[x]);
if (res >= 0 && i-res < ansr-ansl) {
ansl=res;
ansr=i;
}
x=1;
for (int j=29; j >= 0; --j) {
int w=(a[i]>>j)&1;
if (!p[x][w]) {
p[x][w]=++tot;mx[tot]=-1;
p[tot][0]=p[tot][1]=0;
}
x=p[x][w];
mx[x]=max(mx[x],i);
}
}
if (ansl >= 0) printf("%d %d
",ansl+1,ansr);
else printf("-1
");
}
int main() {
int t;
scanf("%d",&t);
while (t--) solve();
return 0;
}
H Maximal submatrix
题意：
给一个(n*m)的矩阵，求每一列都是非递减的子矩阵的最大面积。
解法：
先转化成01矩阵，每个位置的0表示该位置比上面一位小，1表示该位置大于等于上面一位。再用dp维护h数组，h数组表示该位置向上满足非递减的最大长度，这样就可以将问题优化成求每一行，柱状图中最大矩形面积，h[j]看成这一行第j列柱子的高度。最后遍历每一行用单调栈求每一行柱状图中最大矩形面积即可。（除了单调栈还可以直接用悬线法求最大矩形面积）
AC代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5010;
int a[N][N],b[N][N];
int h[N];
int que[N];
void solve() {
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]);
b[i][j]=0;
if (i > 1) b[i][j]=(a[i][j] >= a[i-1][j]);
}
}
for (int i=1; i <= m; ++i) h[i]=0;
int ans=0;
for (int i=1; i <= n; ++i) {
for (int j=1; j <= m; ++j) {
if (!b[i][j]) h[j]=1;
else h[j]++;
}
int tot=0;
h[m+1]=0;
for(int j=1; j <= m+1; ++j) {
while (tot && (h[que[tot]] > h[j])) {
ans=max(ans,(j-que[tot-1]-1)*h[que[tot]]);
tot--;
}
que[++tot]=j;
}
}
printf("%d
",ans);
}
int main() {
int t;
scanf("%d",&t);
while(t--) {
solve();
}
return 0;
}