2020-team10-001

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2020-team10 返回]

== Rank和提交情况 ==
[[Image(Standings.png,1000px)]] 

[[Image(submit.png,1000px)]] 

Solved: 5/13

AC数与提交次数： 5/13

Rank：560
== 流水账 ==

（written by lxy）

这是我们队的第一场比赛，心里有点小紧张。开始几分钟我们三个人一起看A，是一个有码量的数据结构，遂往后看（事后证明三个人都把题意看成了面积，论学好英语的重要性）。此时我发现不少人已经把J签了，就去打了一下就过了。此时lzh感觉B可以打表过，但由于我们均不知道OJ的代码长度限制，就继续想怎么优化（本质是三个人都不会Min25筛）。

之后我和fr分别签好了C和G，lzh就上机去打表了，最后结果好像不太行的样子。中途我上去写了K题因为不熟悉这个OJ特性贡献了一发PE。fr去写了E，因为TLE又找板子优化了一小会。此时已经过去了两个多小时。B的打表还未解决，我看了会L想出了一些性质但是还是无从下手（事后证明就差个DP）。这时fr和lzh推出了M的做法，就上机写了，而我跑去想F。

M调了很久终于过了样例，但提交WA了，赛后发现似乎是板子的锅。在离结束还有大概45min时我想出了F的做法，但感觉细节过多可能更难调，还不如争取M题通过，于是没有将调M题的fr赶下来自己上去写F。然而最后M也没有调出来，遂五题凉凉。

== 个人小结 ==

lzh：
未A题，在B的打表卡了很久，后来去想了A题（然而读错题意）未果。需要加强自己的读题能力和读题速度，面对英文题目总是难以找到重点读得很慢。

lxy：

这一场我AC了3题，原因可能是我抢着去签到？虽然我是大二，但大一我并没有参加过团队赛的训练，所以我和两个大一小朋友打着还蛮生疏的，感觉大家的交流还有一点不畅（可能只有我自己）。感觉自己的个人能力还很不足，数学方面完全只能依靠队友，这场比赛的成绩自己有蛮大的锅。对新知识的开发也很缓慢，就希望自己不要再懒惰下去了。希望不要再发生L和F的惨案，要靠我自己改变策略。两个多小时后没有过题着实可惜。

fr：

AC了2题（签到的G题和几乎是签到的E题）。本次仍然没摆脱（刚组队时）最后一名的悲剧。虽然和7题只差两个板子，但不会打板子（特别是搞OI期间写过多次的NTT）正说明自己对新科技的学习滞后和对已学完的知识的遗忘，导致了接近3小时的时间浪费在毫无意义的事情上。。。另外E题的TLE也说明了自己一直以来存在的问题，经常忽略算法的常数和低阶复杂度（如 n^\frac{1}{2} 和 n^\frac{1}{3} 等）。还有就是对组队比赛还不熟悉，5个小时几乎都在单打独斗，研究不同的题（除了最后的M）。忽略了团队合作的重要性，还需磨合。。。


== 题解 ==
A:问题可转化为∑|a_{i}-a_{i+1}|，线段树维护区间最小值、区间次小值和“最小值与非最小值相邻”的数量即可（注意特判左右端点），更新时类似于jry线段树。注意pushdown时判断lc和rc最小值是否等于x最小值！！（fr赛后）

B:Min_25的一部分（lzh补知识点）

C:寄出最后一封信前可以不回中转点，所以选坐标最小的，按题意计算即可 （lxy）

D:

E:手推SG函数可知SG(x) = x的奇素因数个数 + x是否为偶数，直接求l的SG值求异或和即可。然而直接分解会TLE，所以分解到三次根号n再用MR判断剩下的是否为质数即可。（fr）

F:依据函数知识，检验每个端点的左右极限是否相等（lxy赛后）

G:答案就是出现最多的字符的出现次数。（fr）

H:

I:

J:（直接模拟就好）（lxy）

K: 推一下式子，可以发现在趋于无穷时只有不变和全为0两种情况，判断一下就好了（lxy）

L:数位DP，记录六维状态，不然会TLE（lxy赛后）

M:推式子+分治NTT+差卷积（fr赛后）
#include<bits/stdc++.h>
using namespace std;
int p,t,T,n,K,i,j,k,cnt=0;
int s1=0,Rt,L[3200005],R[3200005];
long long Ans[3200005],Max[3200005];
int Root[3200005];
int s2=0,LL[20000005],RR[20000005];
int S[20000005];
int h[1000005];
long long f[100005][2],g[100005],c[100005],v[100005];
int a[1000005];
void ADD(int x,long long d)
{
  for(int i=x;i<=t;i+=(i&(-i)))
   c[i]=max(c[i],d);
}
long long Find(int x)
{
  long long ans=0;
  for(int i=x;i;i-=(i&(-i)))
   ans=max(ans,c[i]);
   return ans;
}
void ADD2(int x,long long d)
{
  for(int i=x;i;i-=(i&(-i)))
   c[i]=max(c[i],d);
}
long long Find2(int x)
{
  long long ans=0;
  for(int i=x;i<=t;i+=(i&(-i)))
   ans=max(ans,c[i]);
   return ans;
}
long long Find(int Rt,int l,int r)
{
cout<<Rt<<" "<<l<<" "<<r<<" "<<S[Rt]<<endl;
  if(!Rt) return 0;
 int mid=(l+r)/2;
  if(l==r) return l;
  if(S[RR[Rt]]) return Find(RR[Rt],mid+1,r);
  return Find(LL[Rt],l,mid+1);
} 
void UP(int x)
{
   int t=Find(Root[x],1,p),l=L[x],r=R[x];
  Max[x]=max(Max[l],Max[r]);
   //cout<<Max[x]<<" "<<Ans[l]<<" g"<<Ans[r]<<endl;
   Ans[x]=Max[x]+g[t];
   Ans[x]=max(Ans[l],Ans[x]);
   Ans[x]=max(Ans[r],Ans[x]);
    //cout<<Ans[x]<<" "<<Ans[l]<<" p"<<Ans[r]<<endl;
}
int ADD(int Rt,int l,int r,int x,long long d)
{
   int mid=(l+r)/2;
   //cout<<l<<" "<<r<<x<<" "<<endl;
   if(!Rt) {
    Rt=++s1;L[Rt]=0;R[Rt]=0;Root[Rt]=Max[Rt]=Ans[Rt]=0;
   }
   if(l==r) {Max[Rt]=max(Max[Rt],d);return Rt;}
   if(x<=mid) L[Rt]=ADD(L[Rt],l,mid,x,d);
   else R[Rt]=ADD(R[Rt],mid+1,r,x,d);
   UP(Rt);
   return Rt;
}
int Ad(int Rt,int l,int r,int x,int d)
{
  long long mid=(l+r)/2;
    if(!Rt)
   {
     Rt=++s2;LL[Rt]=0;RR[Rt]=0;S[Rt]=0;
   }
   S[Rt]+=d;
   if(l==r) return Rt;
   if(x<=mid) LL[Rt]=Ad(LL[Rt],l,mid,x,d);
    else RR[Rt]=Ad(RR[Rt],mid+1,r,x,d);
  //  cout<<Rt<<" "<<l<<" "<<r<<" "<<" "<<S[Rt]<<x<<" "<<d<<endl;
    return Rt;
}
int Insert(int Rt,int l,int r,int ll,int rr,int x,int d)
{ 

   int mid=(l+r)/2;
   if(l>rr||r<ll) return Rt;
   if(!Rt)
   {
     Rt=++s1;L[Rt]=0;R[Rt]=0;Root[Rt]=Max[Rt]=Ans[Rt]=0;
   }
   if(ll<=l&&r<=rr)
   {
//   cout<<" "<<ll<<" "<<rr<<" "<<l<<" "<<r<<" "<<x<<" "<<d<<endl;
     Root[Rt]=Ad(Root[Rt],1,p,x,d);
     UP(Rt);
     return Rt;
   }
   L[Rt]=Insert(L[Rt],l,mid,ll,rr,x,d);
   R[Rt]=Insert(R[Rt],mid+1,r,ll,rr,x,d);
   cout<<l<<" d"<<r<<endl;
   UP(Rt);
   return Rt;
}
void Cal()
{
   int i,j,k;
   for(i=K+1;i<=n;i++)
    {
    f[i][1]=lower_bound(g+1,g+p+1,f[i][1])-g;
    Rt=Insert(Rt,1,t,1,h[i],f[i][1],1);}
   for(i=1;i<=n-K;i++)
   {
    printf("%lld\n",Ans[Rt]);
    Rt=ADD(Rt,1,t,h[i],f[i][0]);//cout<<"X"<<endl;
  //  cout<<Max[Rt]<<endl;
    Rt=Insert(Rt,1,t,1,h[i+K],f[i+K][1],-1);
   }
   printf("%lld\n",Ans[Rt]);
}
int main()
{
   scanf("%d",&T);
   while(T--)
   {
    scanf("%d%d",&n,&K);
    for(i=1;i<=n;i++) scanf("%d%lld",&h[i],&v[i]);
    for(i=1;i<=n;i++) a[i]=h[i];
    sort(a+1,a+n+1);
    t=unique(a+1,a+n+1)-a-1;
    for(i=1;i<=n;i++) c[i]=0;
    Rt=s1=s2=0;
    for(i=1;i<=n;i++)
    {
     h[i]=lower_bound(a+1,a+t+1,h[i])-a;
     f[i][0]=Find(h[i])+v[i];
     ADD(h[i],f[i][0]);
    }
    for(i=1;i<=n;i++) c[i]=0;
    for(i=n;i>=1;i--)
    {
     f[i][1]=Find2(h[i])+v[i];
     ADD2(h[i],f[i][1]);
    }
    for(i=1;i<=n;i++) g[i]=f[i][1];
    sort(g+1,g+n+1);
    p=unique(g+1,g+n+1)-g-1;
    Cal();
   }
}

[/wiki/2020-team10 返回]

Rank和提交情况

Solved: 5/13

AC数与提交次数： 5/13

Rank：560

流水账

（written by lxy）

这是我们队的第一场比赛，心里有点小紧张。开始几分钟我们三个人一起看A，是一个有码量的数据结构，遂往后看（事后证明三个人都把题意看成了面积，论学好英语的重要性）。此时我发现不少人已经把J签了，就去打了一下就过了。此时lzh感觉B可以打表过，但由于我们均不知道OJ的代码长度限制，就继续想怎么优化（本质是三个人都不会Min25筛）。

之后我和fr分别签好了C和G，lzh就上机去打表了，最后结果好像不太行的样子。中途我上去写了K题因为不熟悉这个OJ特性贡献了一发PE。fr去写了E，因为TLE又找板子优化了一小会。此时已经过去了两个多小时。B的打表还未解决，我看了会L想出了一些性质但是还是无从下手（事后证明就差个DP）。这时fr和lzh推出了M的做法，就上机写了，而我跑去想F。

M调了很久终于过了样例，但提交WA了，赛后发现似乎是板子的锅。在离结束还有大概45min时我想出了F的做法，但感觉细节过多可能更难调，还不如争取M题通过，于是没有将调M题的fr赶下来自己上去写F。然而最后M也没有调出来，遂五题凉凉。

个人小结

lzh：

未A题，在B的打表卡了很久，后来去想了A题（然而读错题意）未果。需要加强自己的读题能力和读题速度，面对英文题目总是难以找到重点读得很慢。

lxy：

这一场我AC了3题，原因可能是我抢着去签到？虽然我是大二，但大一我并没有参加过团队赛的训练，所以我和两个大一小朋友打着还蛮生疏的，感觉大家的交流还有一点不畅（可能只有我自己）。感觉自己的个人能力还很不足，数学方面完全只能依靠队友，这场比赛的成绩自己有蛮大的锅。对新知识的开发也很缓慢，就希望自己不要再懒惰下去了。希望不要再发生L和F的惨案，要靠我自己改变策略。两个多小时后没有过题着实可惜。

fr：

AC了2题（签到的G题和几乎是签到的E题）。本次仍然没摆脱（刚组队时）最后一名的悲剧。虽然和7题只差两个板子，但不会打板子（特别是搞OI期间写过多次的NTT）正说明自己对新科技的学习滞后和对已学完的知识的遗忘，导致了接近3小时的时间浪费在毫无意义的事情上。。。另外E题的TLE也说明了自己一直以来存在的问题，经常忽略算法的常数和低阶复杂度（如 n^{\frac{1}{2} 和 n}\frac{1}{3} 等）。还有就是对组队比赛还不熟悉，5个小时几乎都在单打独斗，研究不同的题（除了最后的M）。忽略了团队合作的重要性，还需磨合。。。

题解

A:问题可转化为∑|a_{i}-a_{i+1}|，线段树维护区间最小值、区间次小值和“最小值与非最小值相邻”的数量即可（注意特判左右端点），更新时类似于jry线段树。注意pushdown时判断lc和rc最小值是否等于x最小值！！（fr赛后）

B:Min_25的一部分（lzh补知识点）

C:寄出最后一封信前可以不回中转点，所以选坐标最小的，按题意计算即可 （lxy）

D:

E:手推SG函数可知SG(x) = x的奇素因数个数 + x是否为偶数，直接求l的SG值求异或和即可。然而直接分解会TLE，所以分解到三次根号n再用MR判断剩下的是否为质数即可。（fr）

F:依据函数知识，检验每个端点的左右极限是否相等（lxy赛后）

G:答案就是出现最多的字符的出现次数。（fr）

H:

I:

J:（直接模拟就好）（lxy）

K: 推一下式子，可以发现在趋于无穷时只有不变和全为0两种情况，判断一下就好了（lxy）

L:数位DP，记录六维状态，不然会TLE（lxy赛后）

M:推式子+分治NTT+差卷积（fr赛后）

#include

using namespace std;

int p,t,T,n,K,i,j,k,cnt=0;

int s1=0,Rt,L[3200005],R[3200005];

long long Ans[3200005],Max[3200005];

int Root[3200005];

int s2=0,LL[20000005],RR[20000005];

int S[20000005];

int h[1000005];

long long f[100005][2],g[100005],c[100005],v[100005];

int a[1000005];

void ADD(int x,long long d)

{

for(int i=x;i<=t;i+=(i&(-i)))

c[i]=max(c[i],d);

}

long long Find(int x)

{

long long ans=0;

for(int i=x;i;i-=(i&(-i)))

ans=max(ans,c[i]);

return ans;

}

void ADD2(int x,long long d)

{

for(int i=x;i;i-=(i&(-i)))

c[i]=max(c[i],d);

}

long long Find2(int x)

{

long long ans=0;

for(int i=x;i<=t;i+=(i&(-i)))

ans=max(ans,c[i]);

return ans;

}

long long Find(int Rt,int l,int r)

{

cout<

if(!Rt) return 0;

int mid=(l+r)/2;

if(l==r) return l;

if(S[RR[Rt]]) return Find(RR[Rt],mid+1,r);

return Find(LL[Rt],l,mid+1);

}

void UP(int x)

{

int t=Find(Root[x],1,p),l=L[x],r=R[x];

Max[x]=max(Max[l],Max[r]);

//cout<

Ans[x]=Max[x]+g[t];

Ans[x]=max(Ans[l],Ans[x]);

Ans[x]=max(Ans[r],Ans[x]);

//cout<

}

int ADD(int Rt,int l,int r,int x,long long d)

{

int mid=(l+r)/2;

//cout<

if(!Rt) {

Rt=++s1;L[Rt]=0;R[Rt]=0;Root[Rt]=Max[Rt]=Ans[Rt]=0;

}

if(l==r) {Max[Rt]=max(Max[Rt],d);return Rt;}

if(x<=mid) L[Rt]=ADD(L[Rt],l,mid,x,d);

else R[Rt]=ADD(R[Rt],mid+1,r,x,d);

UP(Rt);

return Rt;

}

int Ad(int Rt,int l,int r,int x,int d)

{

long long mid=(l+r)/2;

if(!Rt)

{

Rt=++s2;LL[Rt]=0;RR[Rt]=0;S[Rt]=0;

}

S[Rt]+=d;

if(l==r) return Rt;

if(x<=mid) LL[Rt]=Ad(LL[Rt],l,mid,x,d);

else RR[Rt]=Ad(RR[Rt],mid+1,r,x,d);

// cout<

return Rt;

}

int Insert(int Rt,int l,int r,int ll,int rr,int x,int d)

{

int mid=(l+r)/2;

if(l>rr||r

if(!Rt)

{

Rt=++s1;L[Rt]=0;R[Rt]=0;Root[Rt]=Max[Rt]=Ans[Rt]=0;

}

if(ll<=l&&r<=rr)

{

// cout<<" "<

Root[Rt]=Ad(Root[Rt],1,p,x,d);

UP(Rt);

return Rt;

}

L[Rt]=Insert(L[Rt],l,mid,ll,rr,x,d);

R[Rt]=Insert(R[Rt],mid+1,r,ll,rr,x,d);

cout<

UP(Rt);

return Rt;

}

void Cal()

{

int i,j,k;

for(i=K+1;i<=n;i++)

{

f[i][1]=lower_bound(g+1,g+p+1,f[i][1])-g;

Rt=Insert(Rt,1,t,1,h[i],f[i][1],1);}

for(i=1;i<=n-K;i++)

{

printf("%lld\n",Ans[Rt]);

Rt=ADD(Rt,1,t,h[i],f[i][0]);//cout<<"X"<

// cout<

Rt=Insert(Rt,1,t,1,h[i+K],f[i+K][1],-1);

}

printf("%lld\n",Ans[Rt]);

}

int main()

{

scanf("%d",&T);

while(T--)

{

scanf("%d%d",&n,&K);

for(i=1;i<=n;i++) scanf("%d%lld",&h[i],&v[i]);

for(i=1;i<=n;i++) a[i]=h[i];

sort(a+1,a+n+1);

t=unique(a+1,a+n+1)-a-1;

for(i=1;i<=n;i++) c[i]=0;

Rt=s1=s2=0;

for(i=1;i<=n;i++)

{

h[i]=lower_bound(a+1,a+t+1,h[i])-a;

f[i][0]=Find(h[i])+v[i];

ADD(h[i],f[i][0]);

}

for(i=1;i<=n;i++) c[i]=0;

for(i=n;i>=1;i--)

{

f[i][1]=Find2(h[i])+v[i];

ADD2(h[i],f[i][1]);

}

for(i=1;i<=n;i++) g[i]=f[i][1];

sort(g+1,g+n+1);

p=unique(g+1,g+n+1)-g-1;

Cal();

}

}

附加文件

• Standings.png by longxy
• submit.png by longxy