/ Vijos / 题库 / My Story Your Song-雨天 /

题解

26 条题解

  • 0
    @ 2021-10-13 22:18:59

    #include<bits/stdc++.h>
    #define cmin(a,b) (a>(b)?a=(b),1:0)
    #define cmax(a,b) (a<(b)?a=(b),1:0)
    #define dmin(a,b) ((a)<(b)?(a):(b))
    #define dmax(a,b) ((a)>(b)?(a):(b))
    namespace io
    {
    int F()
    {
    int F=1,n=0;
    char ch;
    while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
    ch=='-'?F=0:n=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
    return F?n:-n;
    }
    }
    int f[14][361];
    const int C=120;
    int s[333],ps;
    const int c[33]={25,23,19,17,16,13,11,9,7};
    int gcd(int x,int y)
    {
    int r;
    while(r=x%y)x=y,y=r;
    return y;
    }
    struct fr
    {
    int u,d;
    };
    fr operator -(const fr &x,const fr &y)
    {
    fr ans=(fr){x.u*y.d-y.u*x.d,x.d*y.d};
    int g=gcd(ans.u,ans.d);
    ans.u/=g,ans.d/=g;
    return ans;
    }
    fr operator +(const fr &x,const fr &y)
    {
    fr ans=(fr){x.u*y.d+y.u*x.d,x.d*y.d};
    int g=gcd(ans.u,ans.d);
    ans.u/=g,ans.d/=g;
    return ans;
    }
    bool operator <=(const fr &x,const fr &y)
    {
    return (long long)x.u*y.d<=(long long)y.u*x.d;
    }
    int ok[11][333];
    fr val[11][333];
    int cnt[10];
    int ans;
    int v[666],pv;
    fr sum[333];
    int siz[333];
    void en(int d,fr now,int siz)
    {
    if(d==9)
    {
    int g=C/now.d;
    now.u*=g;
    if(now.u<=360)ans+=f[siz][now.u];
    return;
    }
    for(register int i=1;i<=cnt[d];++i)
    if(val[d][i]<=now&&ok[d][i]<=siz)
    en(d+1,now-val[d][i],siz-ok[d][i]);
    }
    void solve(int n,int m,fr x)
    {
    for(register int i=1;i<=m;++i)
    if(C%i==0)s[++ps]=C/i;
    f[0][0]=1;
    int Sum=0;
    for(register int j=ps;j;--j)
    {
    for(register int *i=f[n];i>f[0];i-=361)
    for(register int k=s[j];k<=Sum+s[j];++k)
    i[k]+=(i-361)[k-s[j]];
    Sum+=s[j];
    }
    for(register int i=0;i<9;++i)
    {
    if(x.d%c[i])++cnt[i],val[i][1]=(fr){0,1};
    if(c[i]>m)continue;
    pv=0;
    for(register int j=c[i];j<=m;j+=c[i])v[pv++]=j;
    for(register int j=1;j<1<<pv;++j)
    {
    sum[j]=sum[j^j&-j]+(fr){1,v[__builtin_ctz(j)]};
    siz[j]=__builtin_popcount(j);
    if(sum[j]<=x)
    {
    fr tmp=x-sum[j];
    if(tmp.d%c[i]&&siz[j]<=n)ok[i][++cnt[i]]=siz[j],val[i][cnt[i]]=sum[j];
    }
    }

    }
    en(0,x,n);
    }
    int main()
    {
    sum[0]=(fr){0,1};
    int n=io::F(),m=io::F(),x=io::F(),y=io::F();
    int g=gcd(x,y);
    x/=g,y/=g;
    solve(n,m,(fr){x,y});
    printf("%d\n",ans);
    return 0;
    }

    #include<bits/stdc++.h>
#define cmin(a,b) (a>(b)?a=(b),1:0)
#define cmax(a,b) (a<(b)?a=(b),1:0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
namespace io
{
    int F()
    {
         int F=1,n=0;
         char ch;
         while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
         ch=='-'?F=0:n=ch-'0';
         while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
         return F?n:-n;
    }
}
int f[14][361];
const int C=120;
int s[333],ps;
const int c[33]={25,23,19,17,16,13,11,9,7};
int gcd(int x,int y)
{
    int r;
    while(r=x%y)x=y,y=r;
    return y;
}
struct fr
{
    int u,d;
};
fr operator -(const fr &x,const fr &y)
{
    fr ans=(fr){x.u*y.d-y.u*x.d,x.d*y.d};
    int g=gcd(ans.u,ans.d);
    ans.u/=g,ans.d/=g;
    return ans;
}
fr operator +(const fr &x,const fr &y)
{
    fr ans=(fr){x.u*y.d+y.u*x.d,x.d*y.d};
    int g=gcd(ans.u,ans.d);
    ans.u/=g,ans.d/=g;
    return ans;
}
bool operator <=(const fr &x,const fr &y)
{
    return (long long)x.u*y.d<=(long long)y.u*x.d;
}
int ok[11][333];
fr val[11][333];
int cnt[10];
int ans;
int v[666],pv;
fr sum[333];
int siz[333];
void en(int d,fr now,int siz)
{
    if(d==9)
    {
        int g=C/now.d;
        now.u*=g;
        if(now.u<=360)ans+=f[siz][now.u];
        return;
    }
    for(register int i=1;i<=cnt[d];++i)
        if(val[d][i]<=now&&ok[d][i]<=siz)
            en(d+1,now-val[d][i],siz-ok[d][i]);
}
void solve(int n,int m,fr x)
{
    for(register int i=1;i<=m;++i)
        if(C%i==0)s[++ps]=C/i;
    f[0][0]=1;
    int Sum=0;
    for(register int j=ps;j;--j)
    {
        for(register int *i=f[n];i>f[0];i-=361)
            for(register int k=s[j];k<=Sum+s[j];++k)
                i[k]+=(i-361)[k-s[j]];
        Sum+=s[j];
    }
    for(register int i=0;i<9;++i)
    {
        if(x.d%c[i])++cnt[i],val[i][1]=(fr){0,1};
        if(c[i]>m)continue;
        pv=0;
        for(register int j=c[i];j<=m;j+=c[i])v[pv++]=j;
        for(register int j=1;j<1<<pv;++j)
        {
            sum[j]=sum[j^j&-j]+(fr){1,v[__builtin_ctz(j)]};
            siz[j]=__builtin_popcount(j);
            if(sum[j]<=x)
            {
                fr tmp=x-sum[j];
                if(tmp.d%c[i]&&siz[j]<=n)ok[i][++cnt[i]]=siz[j],val[i][cnt[i]]=sum[j];
            }
        }   
    }
    en(0,x,n);
}
int main()
{
    sum[0]=(fr){0,1};
    int n=io::F(),m=io::F(),x=io::F(),y=io::F();
    int g=gcd(x,y);
    x/=g,y/=g;
    solve(n,m,(fr){x,y});
    printf("%d\n",ans);
    return 0;
}
  • 0
    @ 2021-10-13 22:18:40

    #include<bits/stdc++.h>
    #define cmin(a,b) (a>(b)?a=(b),1:0)
    #define cmax(a,b) (a<(b)?a=(b),1:0)
    #define dmin(a,b) ((a)<(b)?(a):(b))
    #define dmax(a,b) ((a)>(b)?(a):(b))
    namespace io
    {
    int F()
    {
    int F=1,n=0;
    char ch;
    while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
    ch=='-'?F=0:n=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
    return F?n:-n;
    }
    }
    int f[14][361];
    const int C=120;
    int s[333],ps;
    const int c[33]={25,23,19,17,16,13,11,9,7};
    int gcd(int x,int y)
    {
    int r;
    while(r=x%y)x=y,y=r;
    return y;
    }
    struct fr
    {
    int u,d;
    };
    fr operator -(const fr &x,const fr &y)
    {
    fr ans=(fr){x.u*y.d-y.u*x.d,x.d*y.d};
    int g=gcd(ans.u,ans.d);
    ans.u/=g,ans.d/=g;
    return ans;
    }
    fr operator +(const fr &x,const fr &y)
    {
    fr ans=(fr){x.u*y.d+y.u*x.d,x.d*y.d};
    int g=gcd(ans.u,ans.d);
    ans.u/=g,ans.d/=g;
    return ans;
    }
    bool operator <=(const fr &x,const fr &y)
    {
    return (long long)x.u*y.d<=(long long)y.u*x.d;
    }
    int ok[11][333];
    fr val[11][333];
    int cnt[10];
    int ans;
    int v[666],pv;
    fr sum[333];
    int siz[333];
    void en(int d,fr now,int siz)
    {
    if(d==9)
    {
    int g=C/now.d;
    now.u*=g;
    if(now.u<=360)ans+=f[siz][now.u];
    return;
    }
    for(register int i=1;i<=cnt[d];++i)
    if(val[d][i]<=now&&ok[d][i]<=siz)
    en(d+1,now-val[d][i],siz-ok[d][i]);
    }
    void solve(int n,int m,fr x)
    {
    for(register int i=1;i<=m;++i)
    if(C%i==0)s[++ps]=C/i;
    f[0][0]=1;
    int Sum=0;
    for(register int j=ps;j;--j)
    {
    for(register int *i=f[n];i>f[0];i-=361)
    for(register int k=s[j];k<=Sum+s[j];++k)
    i[k]+=(i-361)[k-s[j]];
    Sum+=s[j];
    }
    for(register int i=0;i<9;++i)
    {
    if(x.d%c[i])++cnt[i],val[i][1]=(fr){0,1};
    if(c[i]>m)continue;
    pv=0;
    for(register int j=c[i];j<=m;j+=c[i])v[pv++]=j;
    for(register int j=1;j<1<<pv;++j)
    {
    sum[j]=sum[j^j&-j]+(fr){1,v[__builtin_ctz(j)]};
    siz[j]=__builtin_popcount(j);
    if(sum[j]<=x)
    {
    fr tmp=x-sum[j];
    if(tmp.d%c[i]&&siz[j]<=n)ok[i][++cnt[i]]=siz[j],val[i][cnt[i]]=sum[j];
    }
    }

    }
    en(0,x,n);
    }
    int main()
    {
    sum[0]=(fr){0,1};
    int n=io::F(),m=io::F(),x=io::F(),y=io::F();
    int g=gcd(x,y);
    x/=g,y/=g;
    solve(n,m,(fr){x,y});
    printf("%d\n",ans);
    return 0;
    }

  • 0
    @ 2010-04-06 20:42:48

    解题报告：

    http://www.docin.com/p-48587379.html

  • 0
    @ 2010-04-07 20:34:14

    把比17大的素数筛掉(WARNING:flag[y]:=false;),上下界剪枝.

  • 0
    @ 2009-11-07 16:40:54

    Accepted 有效得分：100 有效耗时：3481ms

    感谢MIKE_NZK神牛

    判断可以用1e-9

    如

    ABS(A-B)

  • 0
    @ 2009-10-10 20:00:46

    秒杀！数据太弱了！

    上下界剪枝，对于当前分母：

    后面的分母全选最大的还要超，剪枝；

    后面的分母全选最小的（但比当前分母大的）还不够，剪枝。

    只要这个沙茶剪枝就够了（只不过如果只加这个要先预处理倒数）；不过可以加一个神new剪枝，这样可以秒杀此题。

    另外，如果数据出个12 60 1 1估计会挂掉很多程序，即使用这个剪枝也要1s以上。

  • 0
    @ 2009-08-18 16:35:01

    哈哈

  • 0
    @ 2009-08-18 16:38:54

    呵呵

  • 0
    @ 2009-07-27 16:30:37

    神经了,自己电脑上随便拿组数据就......交上去竟然AC,害我一直不敢交啊......

  • 0
    @ 2009-05-21 16:46:18

    在curimit大牛的指导下,终于A了

    重要的一点:尽量减少DFS中的除法,预处理,DFS中采取调用

    自己机子上测测差不多

    交上来就是过与不过的差别

  • 0
    @ 2009-04-21 17:58:24

    Orz cgy.

  • 0
    @ 2009-04-21 17:57:19

    orz curimit

  • 0
    @ 2009-10-09 18:21:42

    编译通过...

    ├ 测试数据 01：运行超时...

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：运行超时...

    ├ 测试数据 04：运行超时...

    ├ 测试数据 05：运行超时...

    ├ 测试数据 06：运行超时...

    ├ 测试数据 07：运行超时...

    ├ 测试数据 08：运行超时...

    ├ 测试数据 09：运行超时...

    ├ 测试数据 10：运行超时...

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分：10 有效耗时：0ms

    直接生成组合然后找的后果...

    编译通过...

    ├ 测试数据 01：答案正确... 338ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 72ms

    ├ 测试数据 06：答案正确... 41ms

    ├ 测试数据 07：答案正确... 259ms

    ├ 测试数据 08：答案正确... 541ms

    ├ 测试数据 09：答案正确... 556ms

    ├ 测试数据 10：答案正确... 556ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：2363ms

    这样也能过?

  • 0
    @ 2007-11-05 13:23:15

    double比两个int的结构要快。。。无语。。。

  • 0
    @ 2007-10-02 14:43:25

    看到0ms的大牛真的心虚的

  • 0
    @ 2006-11-15 21:18:12

    easy.....

    这首歌蛮好听的......

    站在十字路的交点

    该怎么走

    我却只剩回头

    除了你给的伞我再也没有

    别的借口

    去拥有你的什么

    你能体谅我有雨天

    偶尔胆怯你都了解

    过去那些大雨落下的瞬间

    我突然发现

    谁能体谅我的雨天

    所以情愿回你身边

    此刻脚步会慢一些

    如此坚决

    你却越来越远

    牵手和分手来自同一双手

    做回朋友

    我却为何不懂挽留

    你能体谅我有雨天

    偶尔胆怯你都了解

    过去那些大雨落下的瞬间

    我突然发现

    谁能体谅我的雨天

    所以情愿回你身边

    此刻脚步会慢一些

    如此坚决

    你却越来越远

    是否太晚路已走远

    我的眼眶泪太满

    走不回你身边

    你能体谅我有雨天

    偶尔胆怯你都了解

    过去那些大雨落下的瞬间

    我突然发现

    谁能体谅我的雨天

    此刻脚步会慢一些

    如此坚决

    你却越来越远

  • 0
    @ 2006-11-03 13:41:54

    经典彩票问题在奥赛经典的新书上

  • 0
    @ 2006-11-01 18:52:09

    没想法了,我做只得了50分.想不出不出可以如何来优化了,现在开始想数学方法.

  • 0
    @ 2006-10-30 22:28:54

    这题怎么做?大牛说说吧,谁过把一些核心思路发一下嘛,大家一起共享,++RP..

  • 0
    @ 2006-10-30 21:38:22

    有点像经典的埃及分数……

My Story Your Song-雨天

信息

ID
1278
难度
8
分类
搜索 | 搜索与剪枝 点击显示
标签
(无)
递交数
389
已通过
48
通过率
12%
被复制
3
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1