首页 > 代码库 > [FJSC2014]折线统计

[FJSC2014]折线统计

2024-07-12 09:17:10   220人阅读

【题目描述】

二维平面上有n 个点(xi, yi)，现在这些点中取若干点构成一个集合S，对它们按照x 坐标排序，顺次连接，将会构成一些连续上升、下降的折线，设其数量为f(S)。如下图中，1->2,2->3,3->5,5->6（数字为下图中从左到右的点编号），将折线分为了4 部分，每部分连续上升、下降。

现给定k，求满足f(S) = k 的S 集合个数。

【输入格式】

第一行两个整数n 和k，以下n 行每行两个数(xi, yi)表示第i 个点的坐标。

所有点的坐标值都在[1, 100000]内，且不存在两个点，x 坐标值相等或y 坐标值相等。

【输出格式】

输出满足要求的方案总数 mod 100007 的结果。

【样例输入】

5 1

5 5

3 2

4 4

2 3

1 1

【样例输出】

19

【数据范围】

对于 10% 的数据， n <= 10 , k = 1

对于 30% 的数据， n <= 1000, k = 1

对于 50% 的数据， n <= 1000, k <= 10

对于 100% 的数据， n <= 50000，0 < k <= 10

 

Solution

考场上mod少打一个0导致只有10分T T

10%:暴力

50%:考虑DP，记f[i][j][k]表示1~i中包含i的集合S，f(S)=j，k=0表示最后为上升趋势，k=1表示最后为下降趋势。显然有：

f[i][j][0]=Σ(f[k][j][0]+f[k][j-1][1])(yi>yk)

f[i][j][1]=Σ(f[k][j][1]+f[k][j-1][0])(yi<yk)

直接转移即可。

100%:注意到这个方程是在求前缀和，于是搞一颗树状数组维护一下即可。

 

 1 #include<cstdio> 2 #include<ctime> 3 #include<cstdlib> 4 #include<algorithm> 5 int n,m; 6 struct P{int x,n;}x[100010],y[101000]; 7 bool operator<(const P&i,const P&j){return i.x<j.x;} 8 int main() 9 {10     srand(time(0));11     freopen("line.in","w",stdout);12     n=2000,m=10;int i;13     for(i=1;i<=n;i++)x[i].n=y[i].n=i,x[i].x=rand(),y[i].x=rand();14     std::sort(x+1,x+1+n);std::sort(y+1,y+1+n);15     printf("%d %d\n",n,m);16     for(i=1;i<=n;i++)printf("%d %d\n",x[i].n,y[i].n);17 }
Data Maker

 

 1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 struct P{int x,y;}a[100],tmp[100];int n,k,ans[100]; 5 bool operator<(const P&i,const P&j){return i.x<j.x||(i.x==j.x&&i.y<j.y);} 6 void work(int x) 7 { 8     int i,f=1,t=0,fl; 9     for(i=1;x;x>>=1,i++)10     if(x&1)tmp[++t]=a[i];if(t<=1)return;11     if(tmp[1].y<tmp[2].y)fl=1;else fl=0;12     for(i=2;i<t;i++)13     {14         if(fl==1){if(tmp[i+1].y<tmp[i].y)f++,fl=0;}15         else if(tmp[i].y<tmp[i+1].y)f++,fl=1;16     }17     ans[f]++;ans[f]%=100007;18 }19 int main()20 {21     scanf("%d%d",&n,&k);int i,j,d=1<<n;22     for(i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);23     std::sort(a+1,a+1+n);24     for(i=0;i<d;i++)work(i);printf("%d\n",ans[k]);25 }
10%

 

 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 const int mod=100007; 5 int n,m,f[11][50010][2],ans;struct P{int x,y;}a[50010]; 6 bool operator<(const P&i,const P&j){return i.x<j.x||(i.x==j.x&&i.y<j.y);} 7 int main() 8 { 9     scanf("%d%d",&n,&m);int i,j,k,l;10     for(i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);11     std::sort(a+1,a+1+n);12     for(i=1;i<=n;i++)f[0][i][0]=f[0][i][1]=1;13     for(k=1;k<=m;k++)14     {15         for(i=2;i<=n;i++)16         for(j=1;j<i;j++)17         {18             if(a[j].y<a[i].y)f[k][i][0]=(f[k][i][0]+f[k][j][0]+f[k-1][j][1])%mod;19             if(a[j].y>a[i].y)f[k][i][1]=(f[k][i][1]+f[k][j][1]+f[k-1][j][0])%mod;20         }21     }22     for(i=2;i<=n;i++)ans=(ans+f[m][i][0]+f[m][i][1])%mod;printf("%d\n",ans);23 }
50%

 

 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 const int mod=100007; 5 int n,m,f[11][50010][2],ans,maxy;struct P{int x,y;}a[50010]; 6 bool operator<(const P&i,const P&j){return i.x<j.x||(i.x==j.x&&i.y<j.y);} 7 int z0[100010],z1[100010]; 8 void add0(int x,int t){for(t%=mod;x<=maxy;x+=x&-x)z0[x]=(z0[x]+t)%mod;} 9 void add1(int x,int t){for(x=maxy-x,t%=mod;x<=maxy;x+=x&-x)z1[x]=(z1[x]+t)%mod;}10 int gs0(int x){int f=0;for(;x;x-=x&-x)f=(f+z0[x])%mod;return f;}11 int gs1(int x){int f=0;for(x=maxy-x;x;x-=x&-x)f=(f+z1[x])%mod;return f;}12 int main(){13     scanf("%d%d",&n,&m);int i,j,k,l;14     for(i=1;i<=n;i++){scanf("%d%d",&a[i].x,&a[i].y);if(a[i].y>maxy)maxy=a[i].y;}maxy++;15     std::sort(a+1,a+1+n);16     for(i=1;i<=n;i++)f[0][i][0]=f[0][i][1]=1;17     for(k=1;k<=m;k++)18     {19         memset(z0,0,sizeof(z0));20         memset(z1,0,sizeof(z1));21         for(i=1;i<n;i++)22         {23             add0(a[i].y,f[k][i][0]+f[k-1][i][1]);24             add1(a[i].y,f[k][i][1]+f[k-1][i][0]);25             f[k][i+1][0]=gs0(a[i+1].y);26             f[k][i+1][1]=gs1(a[i+1].y);27         }28     }29     for(i=2;i<=n;i++)ans=(ans+f[m][i][0]+f[m][i][1])%mod;printf("%d\n",ans);30 }
100%


联系
我们