暑假集训系列题解（二）
暑假集训系列题解（二）¶
题目1¶
题目链接¶
http://icpc.upc.edu.cn/problem.php?cid=2852&pid=5
题目描述¶
Given a sequence of integers of length n, find the shortest consecutive subsequence witch XOR sum not less than k.
If there are multiple consecutive subsequences of the same length, print the consecutive subsequence with the smallest left end point.
If there are no consecutive subsequence witch XOR sum not less than k, just print "-1".
输入¶
The first line contains a single integer t (t<=100) representing the number of test cases in the input. Then t test cases follow.
The first line of each test case contains two integers n (1<=n<=100000) and k (0<=k<2^30), representing the length of sequence.
The second line of each test contains n integers ai (0<=ai<2^30), representing the integers in sequence.
The number of test witch n>1000 does not exceed 5.
输出¶
For each test case, print two integers in one line, representing the left end point and right end point of the consecutive subsequence.
If there are no consecutive subsequence witch XOR sum not less than k, print "-1" in one line.
样例输入¶
样例输出¶
题解¶
构造01字典树，遍历右节点，查找符合条件的左节点最大值，可参照博客：
https://www.cnblogs.com/lipoicyclic/p/15040070.html#4911382
代码¶
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int ch[3005000][2] = {0};
int val[3005000] = {0};
int max_pos[3005000] = {0};
int total = 0;
int sum[100500] = {0}, a[100600] = {0};
int n, k;
void init()
{
ch[0][0] = ch[0][1] = 0;
total = 1;
for (int i = 0; i <= 32 * n; i++)
max_pos[i] = 0;
}
void insert(int x, int pos)
{
int u = 0;
for (int i = 31; i >= 0; i--)
{
int v = (x >> i) & 1;
max_pos[u] = max(max_pos[u], pos);
if (!ch[u][v])
{
ch[total][0] = ch[total][1] = 0; ///初始化
val[total] = 0; ///未到底部节点，为0
ch[u][v] = total++;
}
u = ch[u][v];
}
val[u] = x;
max_pos[u] = max(max_pos[u], pos);
}
int dfs(int p, int sum, int i, int k, int x)
{
int ans = -1;
if (sum >= k)
return max_pos[p];
if (sum + (((1ll << (i + 1)) - 1)) < k)
return -1;
if (ch[p][0])
ans = max(ans, dfs(ch[p][0], sum + (x & (1 << i)), i - 1, k, x));
if (ch[p][1])
ans = max(ans, dfs(ch[p][1], sum + ((x & (1 << i)) ^ (1 << i)), i - 1, k, x));
return ans;
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &k);
init();
insert(0, 0);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
sum[i] = sum[i - 1] ^ a[i];
}
int min_num = inf, ansl = -1, ansr = -1;
for (int i = 1; i <= n; i++)
{
if (a[i] >= k)
{
min_num = 1;
ansl = ansr = i;
break;
}
int lpos = dfs(0, 0, 31, k, sum[i]);
if (lpos != -1 && (sum[i] ^ sum[lpos]) >= k)
{
int len = i - lpos;
if (len < min_num)
{
min_num = len;
ansl = lpos + 1;
ansr = i;
}
else if (len == min_num)
{
if (lpos + 1 < ansl)
ansl = lpos + 1, ansr = i;
}
}
insert(sum[i], i);
}
if (min_num != inf)
{
printf("%d %d\n", ansl, ansr);
}
else
{
printf("-1\n");
}
}
}
题目2¶
题目链接¶
http://icpc.upc.edu.cn/problem.php?cid=2852&pid=7
题目描述¶
Given a matrix of n rows and m columns,find the largest area submatrix which is non decreasing on each column
输入¶
The first line contains an integer T(1≤T≤10)representing the number of test cases. For each test case, the first line contains two integers n,m(1≤n,m≤2∗103)representing the size of the matrix the next n line followed. the i-th line contains m integers vij(1≤vij≤5∗103)representing the value of matrix It is guaranteed that there are no more than 2 testcases with n∗m>10000
输出¶
For each test case, print a integer representing the Maximal submatrix
样例输入¶
样例输出¶
题解¶
找最大的上升子矩阵，利用单调栈维护每一行的列最大上升值和宽度的乘积并求出最大值即可。
代码¶
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[2050][2050] = {0};
int sum[2050][2050] = {0};
struct node
{
int pos, val;
};
node s[100500] = {0};
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i <= n+1; i++)
for (int j = 0; j <= m+1; j++)
a[i][j]=sum[i][j]=0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &a[i][j]);
for (int j = 1; j <= m; j++)
{
for (int i = 1; i <= n; i++)
{
if (a[i][j] >= a[i - 1][j])
sum[i][j] = sum[i - 1][j] + 1;
else
sum[i][j] = 1;
}
}
ll ans = 0;
for (ll i = 1; i <= n; i++)
{
ll top = 0;
for (ll j = 1; j <= m+1; j++)
{
if (top == 0)
{
s[++top] = {j, sum[i][j]};
}
else
{
while (s[top].val > sum[i][j])
{
ll tmp = (ll)(j - s[top-1].pos - 1) * (ll)s[top].val;
top--;
ans = max(ans, tmp);
}
s[++top] = {j, sum[i][j]};
}
}
}
printf("%lld\n", ans);
}
}
题目3¶
题目链接¶
https://ac.nowcoder.com/acm/contest/11255/J
题目截图¶
题解¶
二分答案，查找长度大于某一特定值的子序列平均值最大值。
代码¶
#include <bits/stdc++.h>
using namespace std;
int a[100500]={0},b[100500]={0};
int check(int a[],double mid,int n,int k)
{
double sum[100500]={0};
double min1[100500]={0};
for(int i=1;i<=n;i++)
min1[i]=2e5;
for(int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+a[i]-mid;
min1[i]=min(min1[i-1],sum[i]);
}
for(int i=k;i<=n;i++)
{
if((sum[i]-min1[i-k])>=0.0000)
return 1;
}
return 0;
}
int main()
{
int n,m,x,y;
scanf("%d%d",&n,&m);
scanf("%d%d",&x,&y);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
scanf("%d",&b[i]);
double l=0,r=1e5;
while(abs(l-r)>1e-9)
{
double mid=(l+r)/2.0;
if(check(a,mid,n,x))
l=mid;
else
r=mid;
}
double ans1=l;
l=0,r=1e5;
while(abs(l-r)>1e-9)
{
double mid=(l+r)/2.0;
if(check(b,mid,m,y))
l=mid;
else
r=mid;
}
double ans2=l;
printf("%.10f\n",ans2+ans1);
}