PKUSC2018题解

当时太菜了没有去,题解合集

begay稳扎稳打的游记,如果不是数学就有一本了

5/5

CF1204E Natasha, Sasha and the Prefix Sums

这题不是PKUSC2018的,但有兴趣的可以看看

请先思考后再展开

$$
考虑在第一个max处计数,f(a,b)表示前缀 \le0,g(a,b)表示后缀>0的方案数 \\
f(a>b)=0,f(a,b)=C_{a+b}^a-C_{a+b}^{b+1},类似卡特兰数的推导方式 \\
g(0,0)=g(a<b)=0,在后面先放一个1,g(a,b)=C_{a+b-1}^{a-1}-C_{a+b-1}^a \\
然后枚举前缀mx,前面g后面f拼接起来,O(n^2),g和f也可以dp计算
$$
code
$$
k(a,b)=a个1,b个-1下f<0的方案数 \\
k(a>b)=0,k(a<b)考虑从后面添加=k(a-1,b)+k(a,b-1) \\
其实用类似卡特兰数的推导方式可知 k(a<b)=C_{a+b}^a-C_{a+b}^{a-1} \\
f(a,0)=a,f(0,b)=0,考虑从前面添加(奇妙的思路) \\
f(a,b)=(f(a-1,b)+C_{a+b-1}^b)+(f(a,b-1)-(C_{a+b-1}^a-k(a,b-1)))
$$
code

线性做法:就是求一个至少i+1,可以看「OI之路」03数学-7组合数学中Catalan数拓展部分

1
2
3
4
5
6
7
for(int i=0;i<=n;i++)
{
int x=n,y=m+i+1;//注意要这样比大小
if(min(x,n+m-x)<min(y,n+m-y)) continue;
cnt[i]=C[n+m][x]-C[n+m][y];
}
ll ans=0;for(int i=1;i<=n;i++) ans+=(cnt[i]-cnt[i-1])*i,ans%=MOD;write((ans+MOD)%MOD);

PKUSC2018D1T2 最大前缀和

和上题做法类似

请先思考后再展开

需要注意一个细节,整个S的和不算是后缀和的一部分,否则前缀和可能取在题面中i=0
code

PKUSC2018D1T1 真实排名

细节:ai相同、=0(特判)

若x不变,则 $[x/2,x)不变,ans=C_{all-cnt-1}^k$

若x变,则 $[x,2x)变,ans=C_{all-cnt}^{k-cnt}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int a[MAX_N],b[MAX_N];
int main()
{
int n=qread(),k=qread();
for(int i=1;i<=n;i++) a[i]=b[i]=qread();
sort(b+1,b+n+1);
for(int i=1;i<=n;i++)
{
int ans=0,x=a[i];
if(x==0) ans=C(n,k);
else
{
int aa=lower_bound(b+1,b+n+1,x)-1-lower_bound(b+1,b+n+1,(int)ceil(x/2.0))+1;
int bb=lower_bound(b+1,b+n+1,2*x)-1-lower_bound(b+1,b+n+1,x)+1;
ans=C(n-aa-1,k)+C(n-bb,k-bb);
}
printf("%d\n",(ans%MOD+MOD)%MOD);
}
}

PKUSC2018D2T2 神仙的游戏

这套的E那里改改就行了,因为border=n-period

PKUSC2018D2T1 星际穿越

一个显然而我没看出来的结论是:前往左边某点的最短路径,要么一直向左,要么走一步右然后一直向左,然后就能借助rmq拿70

先考虑询问点到点的距离怎么做,你发现除了第一步稍有特殊外,后面每步都可以转化成这样一种形式:在位置i,找到右端点$ \ge i$的一切线段中左端点最小的那个并跳到那里,然后划归到那种情况+1;至于第一步的处理就是看目标点是否第一步就可达,否则$dist(i,j)=solve(L_i,j)+1$

线性预处理出每个点能跳到的位置$to_i$,然后加速跳的过程很自然的想法就是倍增

设$f_{i,j}表示向左跳2^j步的所有点的距离和,f_{i,j}=f_{i,j-1}+f_{to_{i,j-1},j-1}+(to_{i,j-1}-to_{i,j})*2^{j-1}$

将询问区间距离和差分为询问后缀距离和,倍增跳过去回答询问,$O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int n,L[N],to[N][30];ll f[N][30];
ll solve(int pos,int R)
{
ll ans=0;fd(i,20,0) if(to[pos][i]>=R) ans+=(to[pos][i]-R)*bin(i)+f[pos][i],pos=to[pos][i];
ans+=pos-R;return ans;
}
void main()
{
n=qread();fo(i,2,n) L[i]=qread(),to[i][0]=L[i];fd(i,n,2) chmin(to[i-1][0],to[i][0]),f[i][0]=i-to[i][0];
fo(j,1,20) fo(i,1,n) to[i][j]=to[to[i][j-1]][j-1],f[i][j]=f[i][j-1]+f[to[i][j-1]][j-1]+(to[i][j-1]-to[i][j])*bin(j-1);
int q=qread();
while(q--)
{
int l=qread(),r=qread(),pos=qread();
if(l>=L[pos]){printf("1/1\n");continue;}
ll x=r-l+1,y=r-l+1;chmin(r,L[pos]-1);
x+=solve(L[pos],l);x-=solve(L[pos],r+1);
ll d=gcd(x,y);printf("%lld/%lld\n",x/d,y/d);
}
}

PKUSC2018D2T3 PKUSC

计算几何补习,注意简单多边形的话边不会交

感觉这题口胡很容易,写起来还是不少细节的,要不是我能下载loj数据调可能要搞一天

很自然的想法是拆开计算每个人的贡献,而每个人其实就是一个圆,问圆周上在多边形内的范围占比

将多边形的面积定义为在里面的圆弧弧度和,那么就能用任意多边形计算面积的方法计算这玩意,那么现在转化为计算两点与原点形成三角形与圆周交的弧度。

这东西基本上可以自己想,主要就是讨论一下

具体而言(省略板子的内容):
若两点都在圆内,0
若恰一点在圆内,则为sp(外点、两点连线与圆交点)

若两点都在圆外,判一下连线到圆心的距离,如果小的话有可能是两段区间,用「直线与圆求交」做交点就好了

除了这种较为特殊的情况,剩下的都是sp(a,b)

$O(nm)$,需要特判原点即R=0;完整code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//上面是计算几何板子
double solve(V a,V b)
{
if(a.ss()<=R+eps) swap(a,b);
if(a.ss()<=R+eps) return 0;
V c=chui_zu(a,b);double len=(a-b).ss();
V go=(b-a)*(sqrt(R*R-c.ss()*c.ss())/len);
if(b.ss()<=R+eps) return sp(a,c-go);//a外b内
//需保证a->b为逆时针
if(c.ss()>=R) return sp(a,b);
if(a*(c-go)>0 and (c-go)*(c+go)>0 and (c+go)*b>0) return sp(a,c-go)+sp(b,c+go);
return sp(a,b);
}
V a[N],b[N];
void main()
{
int n=qread(),m=qread();
fo(i,0,n-1) a[i].x=qread(),a[i].y=qread();
fo(i,0,m-1) b[i].x=qread(),b[i].y=qread();
double ans=0;
fo(_i,0,n-1)
{
R=a[_i].ss();
double zero=0;fo(j,0,m-1) zero+=(b[j]*b[(j+1)%m]>eps?1:-1)*sp(b[j],b[(j+1)%m]);
if(fabs(zero-PI*2)>eps) zero=0;//原点要特判,用角度搞即可
fo(j,0,m-1)
{
double cr=b[j]*b[(j+1)%m];if(fabs(cr)<=eps) continue;
if(cr>0) {double now=solve(b[j],b[(j+1)%m]);ans+=now;}
else {double now=solve(b[(j+1)%m],b[j]);ans-=now;}
}
}printf("%.5Lf",ans/(PI*2));
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/71bd.html
转载请注明出处,谢谢!