CSP模拟21
T1 Get P5999
把跳的顺序转换为填数。
对于一个位置，两边填的数都要小于或都大于它才符合题意。
我们按照从小到大的顺序插入数字，这样保证填的位置左右都小于它。设 \(dp_{i,j}\) 表示填了 \(i\) 个数，分成了 \(j\) 个块的方案数。
考虑添加一个数，我们有三种情况。
- \(i\) 自己成为一个新段，我们已经填的 \(j-1\) 段把区域分成了 \(j\) 部分，我们可以在这 \(j\) 部分中选一个插入 \(i\)，有 \(j\) 种情况。但是当 \(s\) 或 \(t\) 已经出现时，我们就不能添加开头和结尾，也就是说不能在边界添加 \(i\)。
-
\(i\) 添加进一个已经存在的段。此时不满足两边填的数都要小于或都大于它。
-
\(i\) 合并两个存在的段，在 \(j+1\) 个段的基础上有 \(j\) 种方式。
-
如果 \(i=s\) 或 \(i=t\)，只能新建边界段或添加到边界段。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
int n,s,t,f[2010][2010],mod=1e9+7;
signed main(){
scanf("%d%d%d",&n,&s,&t);
f[1][1]=1;
for(int i=2;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==s||i==t){
f[i][j]+=f[i-1][j-1]+f[i-1][j];
f[i][j]%=mod;
}
else{
int m=(i>s)+(i>t);
f[i][j]+=f[i-1][j-1]*(j-m);
f[i][j]+=f[i-1][j+1]*j;
f[i][j]%=mod;
}
}
}
cout<<f[n][1];
return 0;
}
T2 On P9350
我们考虑拆分绝对值，
\[|x_i-x_j|\le{e_i-e_j}\iff {x_i-x_j\le{e_i-e_j}} 且 x_j-x_i\le{e_i-e_j} \]移项，
\[e_j-x_j\le{e_i-x_i} \]且
\[e_j+x_j\le{e_i+x_i} \]我们把 \(e_i+x_i\) 和 \(e_i-x_i\) 当作两个维度，排序后按照单调队列做即可。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,tot,p[500010];
struct nod{
int x,e;
}a[500010];
bool cmp(nod x,nod y){
if(x.x==y.x) return x.e<y.e;
return x.x<y.x;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].x,&a[i].e);
int t=a[i].e-a[i].x;
a[i].e=a[i].e+a[i].x;
a[i].x=t;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
while(tot&&a[p[tot]].e<=a[i].e) tot--;
p[++tot]=i;
}
cout<<tot;
return 0;
}
T3 Your
我们可以发现对于每个交点，都在圆上有 \(4\) 个点对应。所以交点个数就是$$\dbinom{n}{4}$$
有交点的图不能用欧拉定理，我们考虑把它转化为没有交点的图，我们把每个交点都看成一个新的点，容易发现每个交点都增加了两条边，所以边的个数为
\[\dbinom{n}{2}+2\dbinom{n}{4} \]利用欧拉定理，点数-边数+区域数是 \(2\)，所以区域数为
\[2-\dbinom{n}{4}-n+\dbinom{n}{2}+2\dbinom{n}{4}=2+\dbinom{n}{2}+\dbinom{n}{4}-n \]由于不包括圆外的的区域，圆和多面形有 \(n\) 个区域，所以答案为
\[1+\dbinom{n}{2}+\dbinom{n}{4} \]#include<iostream>
#include<cstdio>
using namespace std;
int n,ans,tot,mod=998244353,inv24=291154603,inv2=499122177;
int main(){
scanf("%d",&n);
int ans1=(1ll*n*(n-1)%mod*(n-2)%mod*(n-3)%mod*inv24%mod+mod)%mod;
int ans2=(1ll*ans1+1ll*n*(n-1)%mod*inv2%mod+mod+1)%mod;
printf("%d\n%d",ans1,ans2);
return 0;
}