注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3688][FJSC2014]折线统计  

2014-07-20 20:40:17|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

【题目描述】

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

[FJSC2014]折线统计 - Trinkle - n+e

  现给定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])(k<i&&yi>yk)

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

  直接转移即可。

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


/*Data Maker*/

#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<algorithm>
int n,m;
struct P{int x,n;}x[100010],y[101000];
bool operator<(const P&i,const P&j){return i.x<j.x;}
int main()
{
srand(time(0));
freopen("line.in","w",stdout);
n=2000,m=10;int i;
for(i=1;i<=n;i++)x[i].n=y[i].n=i,x[i].x=rand(),y[i].x=rand();
std::sort(x+1,x+1+n);std::sort(y+1,y+1+n);
printf("%d %d\n",n,m);
for(i=1;i<=n;i++)printf("%d %d\n",x[i].n,y[i].n);
}

/*10%*/

#include<cstdio>
#include<algorithm>
#include<cstring>
struct P{int x,y;}a[100],tmp[100];int n,k,ans[100];
bool operator<(const P&i,const P&j){return i.x<j.x||(i.x==j.x&&i.y<j.y);}
void work(int x)
{
int i,f=1,t=0,fl;
for(i=1;x;x>>=1,i++)
if(x&1)tmp[++t]=a[i];if(t<=1)return;
if(tmp[1].y<tmp[2].y)fl=1;else fl=0;
for(i=2;i<t;i++)
{
if(fl==1){if(tmp[i+1].y<tmp[i].y)f++,fl=0;}
else if(tmp[i].y<tmp[i+1].y)f++,fl=1;
}
ans[f]++;ans[f]%=100007;
}
int main()
{
scanf("%d%d",&n,&k);int i,j,d=1<<n;
for(i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);
std::sort(a+1,a+1+n);
for(i=0;i<d;i++)work(i);printf("%d\n",ans[k]);
}

/*50%*/

#include<cstdio>
#include<cstring>
#include<algorithm>
const int mod=100007;
int n,m,f[11][50010][2],ans;struct P{int x,y;}a[50010];
bool operator<(const P&i,const P&j){return i.x<j.x||(i.x==j.x&&i.y<j.y);}
int main()
{
scanf("%d%d",&n,&m);int i,j,k,l;
for(i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);
std::sort(a+1,a+1+n);
for(i=1;i<=n;i++)f[0][i][0]=f[0][i][1]=1;
for(k=1;k<=m;k++)
{
for(i=2;i<=n;i++)
for(j=1;j<i;j++)
{
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;
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;
}
}
for(i=2;i<=n;i++)ans=(ans+f[m][i][0]+f[m][i][1])%mod;printf("%d\n",ans);
}

/*100%*/

#include<cstdio>
#include<cstring>
#include<algorithm>
const int mod=100007;
int n,m,f[11][50010][2],ans,maxy;struct P{int x,y;}a[50010];
bool operator<(const P&i,const P&j){return i.x<j.x||(i.x==j.x&&i.y<j.y);}
int z0[100010],z1[100010];
void add0(int x,int t){for(t%=mod;x<=maxy;x+=x&-x)z0[x]=(z0[x]+t)%mod;}
void add1(int x,int t){for(x=maxy-x,t%=mod;x<=maxy;x+=x&-x)z1[x]=(z1[x]+t)%mod;}
int gs0(int x){int f=0;for(;x;x-=x&-x)f=(f+z0[x])%mod;return f;}
int gs1(int x){int f=0;for(x=maxy-x;x;x-=x&-x)f=(f+z1[x])%mod;return f;}
int main(){
scanf("%d%d",&n,&m);int i,j,k,l;
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++;
std::sort(a+1,a+1+n);
for(i=1;i<=n;i++)f[0][i][0]=f[0][i][1]=1;
for(k=1;k<=m;k++)
{
memset(z0,0,sizeof(z0));
memset(z1,0,sizeof(z1));
for(i=1;i<n;i++)
{
add0(a[i].y,f[k][i][0]+f[k-1][i][1]);
add1(a[i].y,f[k][i][1]+f[k-1][i][0]);
f[k][i+1][0]=gs0(a[i+1].y);
f[k][i+1][1]=gs1(a[i+1].y);
}
}
for(i=2;i<=n;i++)ans=(ans+f[m][i][0]+f[m][i][1])%mod;printf("%d\n",ans);
}

  评论这张
 
阅读(53)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018