2122. 幸运票

(File IO): input:tickets.in output:tickets.out

时间限制: 1000 ms 空间限制: 262144 KB 具体限制

Goto ProblemSet

题目描述

给你一个数N(1<=N<=50),每张票有2N位,同时给你这2N位上的和S,如果这张票的前N位的和等于后N位的和,那我们称这张票是吉祥的,每一位可以取0-9。

你的任务是计算吉祥票的总数。

输入

输入N和S,S是所以位上的和,假设S<=1000

输出

输出吉祥票的总数

样例输入

2 2

样例输出

数据范围限制

见题目描述

Solution

此题很不友好……emmm……

Algorithm1

死命dfs

Code1

 #pragma GCC optimize(2)

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<map>

 #include<set>

 #include<vector>

 #include<queue>

 #define IL inline

 using namespace std;

 unsigned long long n,s,ans,sum;

 IL void dfs(unsigned long long depth,unsigned long long now,unsigned long long sum)

 {

     if(sum*>s) return;

     if(depth==n){

         if(sum==s/)

             ans++;

         return;

     }

     for(int i=;i<;i++)

     {

         dfs(depth+,now*+i,sum+i);

     }

 }

 int main()

 {

 //    freopen("tickets.in","r",stdin);

 //    freopen("tickets.out","w",stdout);

     cin>>n>>s;

     dfs(,,);

     cout<<ans*ans;

      return ;

 }

Code1

Algorithm2

打了一番表，发现真相……

一个斜着的杨辉三角形*2？？？

由于某些原因（换了电脑且插不了U盘）

没法详细的讲规律

这是ans，不是ans的平方！

0 0 0 0 0 0 0 0……
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 0 0 0 0 ……
1 1 3 3 6 6 10 10 15 15 21 21 28 28 36 36 45 45 55 55 63 63 ……0 0 0 0 ……
1 1 4 4 10　　 10　　 20　　 20 ……

可以用s/2向下取整+1先把重复的删除（calc(n,s/2+1)）

然后这个矩阵就有有个规律了：

如果s/2+1小于11的话，memory[i][j]=memory[x-1][y]+memory[x][y-1]

否则memory[i][j]=memory[x-1][y]+memory[x][y-1]-1

#pragma GCC optimize(2)

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<map>

#include<set>

#include<vector>

#include<queue>

#define IL inline

using namespace std;

unsigned long long n,s,ans,sum;

bool vis[][];

unsigned long long memory[][]={

{},

{,,,,,,,,,,,,,,,,,,,,,,,,,,,},

{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,},

{}

};

IL unsigned long long calc(int x,int y)

{

    if(x==||x==)

    {

        if(y<=)

            return ;

        else

            return ;

    }

    if(y==) return ;

    if(vis[x][y]||memory[x][y]) return memory[x][y];

    memory[x-][y]=calc(x-,y);

    memory[x][y-]=calc(x,y-);

    vis[x-][y]=vis[x][y-]=;

    return memory[x][y]=memory[x-][y]+memory[x][y-]-(int)(y>=);

}

IL int read()

{

    char ch;int x=;

    ch=getchar();

    while(ch<''||ch>'') ch=getchar();

    while(ch>=''&&ch<='') x=(x<<)+(x<<)+(ch^),ch=getchar();

    return x;

}

int main()

{

//    freopen("tickets.in","r",stdin);

//    freopen("tickets.out","w",stdout);

    n=read();

    s=read();

    ans=calc(n,s/+);

    cout<<ans*ans;

     return ;

}

但是对拍之后，发现ans*ans很容易会超过unsigned long long！

高精度！

只要加上高精加法和高精乘法就好

巴特西

纪中20日c组T2 2122. 【2016-12-31普及组模拟】幸运票

2122. 幸运票

题目描述

输入

输出

样例输入

样例输出

数据范围限制

Solution

Algorithm1

Code1

Algorithm2

高精度！

最新文章

热门文章