前天有点问题没发
耽搁了
第一题
感觉一点都不水
要把小船的左坐标和右坐标记录下来，在小船左边就移动左坐标啥的
#include <iostream>
#include <cstdio>
using namespace std;
int n,a[10000001],i,j,f[1000001][4];
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++)
scanf("%d",&a[i]);
f[1][0]=a[1];
for (i=2;i<=n;i++)
for (j=0;j<=3;j++)
{
if (j==0)
{
f[i][j]=max(f[i-1][1]+a[i],f[i-1][3]+a[i]);
}
else
if (j==1)
{
f[i][j]=max(f[i-1][0]-a[i],f[i-1][2]-a[i]);
}
else
if (j==2)
f[i][j]=max(f[i-1][0],f[i-1][2]);
else
f[i][j]=max(f[i-1][1],f[i-1][3]);
}
printf("%d",max(max(max(f[n][0],f[n][1]),f[n][2]),f[n][3]));
}第二题
没做出来
太长了，没时间补
但是思路还是知道的，先分解质因数，多的数量减去少的，最后快速幂，高精度乘法还有压位
第三题
比较难，跟中位数有关
因为要求1~n每个前缀的中位数（因为后文要求在这些中位数中找最小的中位数，因此这个需要每个前缀中最大的中位数），所以想用快排的就算了吧
我们发现，如果小根堆和大根堆遵守了规则的话，小根堆的对顶就是最大的中位数
所以维护好，添加好就OK了
#include <iostream>
#include <cstdio>
using namespace std;
int n,i,a[1000001],b[1000001],s[1000001],o[1000001],ia,ib,t;
void aup(int d)
{
while (d>1&&a[d]<a[d/2])
{
t=a[d];
a[d]=a[d/2];
a[d/2]=t;
d=d/2;
}
}
void ado(int d)
{
int x;
while (d*2<=ia&&a[d*2]<a[d]||a[d*2+1]<a[d]&&d*2+1<=ia)
{
x=d*2;
if (a[x]>a[x+1]&&x+1<=ia) x+=1;
t=a[x];a[x]=a[d];a[d]=t;
d=x;
}
}
void bdo(int d)
{
int x;
while (d*2<=ib&&b[d*2]>b[d]||b[d*2+1]>b[d]&&d*2+1<=ib)
{
x=d*2;
if (b[x]<b[x+1]&&x+1<=ib) x+=1;
t=b[x];b[x]=b[d];b[d]=t;
d=x;
}
}
void bup(int d)
{
while (d>1&&b[d]>b[d/2])
{
t=b[d];
b[d]=b[d/2];
b[d/2]=t;
d=d/2;
}
}
void qs(int l,int h)
{
int i=l,j=h,mid=o[(l+h)/2],t;
if (l>=h) return;
do
{
while (mid>o[i]) i++;
while (mid<o[j]) j--;
if (i<=j)
{
t=o[i];
o[i]=o[j];
o[j]=t;
i++;j--;
}
}
while (i<=j);
qs(i,h);
qs(l,j);
}
int main()
{
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d",&s[i]);
if (i%2==1)
{
ia++;
a[ia]=s[i];
aup(ia);
if (a[1]<b[1])
{
t=a[1];a[1]=b[1];b[1]=t;
ado(1);
bdo(1);
}
o[i]=a[1];
}
else
{
ib++;
b[ib]=s[i];
bup(ib);
if (b[1]>a[1])
{
t=b[1];b[1]=a[1];a[1]=t;
ado(1);
bdo(1);
}
o[i]=a[1];
}
}
qs(1,n);
printf("%d",o[n/2]);
}第四题
另类的前缀和
把0看为-1，1看为1
这样，相加的和如果在后面再次找到，就证明这个区间内的01数量是相等的
因此只要每次存和，m1[和]就是右坐标，m2[和]就是左坐标，最后一个for过去找最多就可以了
#include <iostream>
#include <cstring>
#include <memory.h>
#include <cstdio>
using namespace std;
char s[1000001];
int m1[1000001],m2[1000001],i,j,m,ma,mi=2147483647,l;
int main()
{
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
scanf("%s",&s);
m=500000;
memset(m2,21474836,sizeof(m2));
m2[500000]=0;
l=strlen(s);
for (i=1;i<=l;i++)
if (s[i-1]=='1')
{
m++;
if (m>ma) ma=m;
if (m<mi) mi=m;
if (i>m1[m]) m1[m]=i;
if (i<m2[m]) m2[m]=i;
}
else
{
m--;
if (m>ma) ma=m;
if (m<mi) mi=m;
if (i>m1[m]) m1[m]=i;
if (i<m2[m]) m2[m]=i;
}
m=0;
for (i=mi;i<=ma;i++)
m=max(m1[i]-m2[i],m);
printf("%d",m);
}