[FJSC2014]折线统计
【题目描述】
二维平面上有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 }
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 }
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 }
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 }
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
