2021“MINIEYE杯”中国大学生算法设计超级联赛(1)
link:HDU
A
题意:
给一个数\(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\n",max(0ll,n/2-1));
return;
}
while ((n&(-n)) != n) n-=(n&(-n));
printf("%lld\n",n-1);
}
int main() {
int t;
scanf("%d",&t);
while (t--) solve();
return 0;
}
E
题意:
给\(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\n",ans[n]);
}
int main() {
oulasai(maxn);
int t;
scanf("%d",&t);
while(t--) solve();
return 0;
}
F
题意:
给一个数组,求这数组异或和不小于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\n",ansl+1,ansr);
else printf("-1\n");
}
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\n",ans);
}
int main() {
int t;
scanf("%d",&t);
while(t--) {
solve();
}
return 0;
}