频道栏目
首页 > 考试 > 其他 > 正文

zzuli oj 985专场

2016-08-11 10:03:12         来源:maqinyao5566的博客  
收藏   我要投稿

Problem C: 985的方格难题

Time Limit:1 SecMemory Limit:128 MB
 

Description

985走入了一个n * n的方格地图,他已经知道其中有一个格子是坏的。现在他要从(1, 1)走到(n, n),每次只可以向下或者向右走一步,问他能否到达(n,n)。若不能到达输出-1,反之输出到达(n,n)的方案数。

 

 

Input

第一行输入一个整数t,代表有t组测试数据。

每组数据第一行输入三个整数n,x,y,分别代表方格地图的大小以及坏掉格子的位置。

注:1 <= t <= 20,1 <= n <= 30,1 <= x,y <= n。

 

Output

若可以到达(n,n)则输出方案数对1e9 + 7取余的结果,反之输出-1。

 

 

Sample Input

2 2 1 2 2 2 2

Sample Output

1 -1

 

 

ps:简单dp..


#include #include #define mod 1000000007 long long s[50][50]; int n,x,y; int main() { int t; scanf("%d",&t); while(t--) { scanf("%d %d %d",&n,&x,&y); memset(s,0,sizeof(s)); s[1][1]=1; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==x&&j==y) s[i][j]=0; else s[i][j]+=(s[i-1][j]%mod+s[i][j-1]%mod)%mod; } } if(x==1&&y==1||x==n&&y==n) printf("-1\n"); else printf("%lld\n",s[n][n]); } }



Problem D: 985的0-1串难题

Time Limit:1 SecMemory Limit:128 MB
Submit:249Solved:70

SubmitStatusWeb Board

Description

985有一个长度为n的0-1串,已知他最多可以修改k次(每次修改一个字符即0->1 或者 1->0),他想知道连续的全1子串最长是多少。

 

Input

第一行输入一个整数t,代表有t组测试数据。

每组数据第一行输入两个整数n,k分别代笔上面的信息。

注:1 <= t <= 12,1 <= n <= 100000,0 <= k <= 100000。

 

Output

一个整数代表可以得到的最大长度。

 

Sample Input

2 6 3 010100 6 2 010100

Sample Output

5 4

 


 

ps:前后各加一个0,并以k为0的个数去寻找最长子串

#include
int max1(int a,int b)
{
    return a>b?a:b;
}
char a[100020];
int s[100020];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m,maxx=0,sum=0,z=0;
        scanf("%d %d",&n,&m);
        scanf("%s",a);
        s[z++]=0;
        for(int i=0;i

Problem E: 985的买饮料难题

Time Limit:1 SecMemory Limit:128 MB Submit:238Solved:126 SubmitStatusWeb Board

Description

天气太热了,985制定了对未来的规划即第i天喝a[i]瓶饮料。为了节约开支,他打听到了第i天每瓶饮料的价格p[i]。

为了不让自己的规划落空,他想知道这n天他至少要花多少钱。

精明的985可以选择在任意一天买数目不限的饮料,而且他有一个神奇的冰箱,可以将提前购买的饮料保存下来(至少在这n天里是可以饮用的)。

 

Input

第一行输入一个整数t,代表有t组测试数据。

每组数据第一行输入一个整数n代表规划的总天数,接下来有n行,每行输入两个整数a[],p[]分别代表上面提到的信息。

注:1 <= t <= 30,1 <= n <= 1000,1 <= a[],p[] <= 100。

 

Output

输出一个整数代表最后的结果。

 

Sample Input

2 2 25 56 94 17 5 39 21 95 89 73 90 9 55 85 32

Sample Output

2998 6321

 

ps:一直以所遇到的最小单价为单价。

#include
int main()
{
    int t,n,a,b;
    scanf("%d",&t);
    while(t--)
    {
        int minn=120;
        long long sum=0;
        scanf("%d",&n);
        for(int i=0;ib)
                    minn=b;
               sum+=a*minn;
        }
        printf("%lld\n",sum);
    }
}

Problem F: 985的红绿灯难题

Time Limit:1 SecMemory Limit:128 MB
Submit:208Solved:129

SubmitStatusWeb Board

Description

 

已知红、绿、黄灯各持续r、g、y秒,985发现此时灯刚刚变绿,他想知道x秒后灯是什么颜色。

 

Input

第一行输入一个整数t,代表有t组测试数据。

每组数据输入四个整数x,g,y,r。

注:1 <= t <= 30,1 <= x,g,r,y <= 1e9。

 

Output

若x秒后变成红色输出R,变成绿色输出G,反之输出Y。

 

 

Sample Input

3 5 5 2 8 7 5 2 8 16 5 2 8

Sample Output

Y R G

HINT

 

红绿灯顺序:绿->黄->红->绿


 

ps:找规律

#include
int main()
{
    int t,x,g,r,y;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d %d %d",&x,&g,&r,&y);
        int sum=g+r+y;
        int k=x%sum;
        if(k>=0&&k=g&&k=g+r&&k



Problem G: 985的数字难题

Time Limit:1 SecMemory Limit:128 MB
Submit:281Solved:102

SubmitStatusWeb Board

Description

985有n个数,已知每次操作可以将其中不相同的两个数一个加一、一个减一,操作次数不限。

问他最多可以得到多少个相同的数。

 

Input

第一行输入一个整数t,代表有t组测试数据。

每组数据占两行,第一行输入一个n代表元素个数,下面一行输入n个整数a[]。

注:1 <= t <= 30,1 <= n <= 1e4,1 <= a[] <= 1e3。

 

 

Output

输出一个整数代表最多可以得到多少个相同的数。

 

Sample Input

2 3 1 1 1 2 2 3

Sample Output

3 1

 

ps:求n个数之和。若为偶数就输出n,否则输出n-1;

#include
#include
#include
using namespace std;
int main()
{
    int t,n,b;
    scanf("%d",&t);
    while(t--)
    {
        int sum=0;
        int num,maxn=0;
        scanf("%d",&n);
        for(int i=0; i

Problem H: 985的最大和难题

Time Limit:1 SecMemory Limit:128 MB Submit:310Solved:35 SubmitStatusWeb Board

Description

985有2 * n - 1个整数,他每次可以将其中n个数变号,操作次数不限,问他可以得到的最大和。

 

Input

第一行输入一个整数t,代表有t组测试数据。

每组数据占两行,第一行输入一个整数n,下面一行输入2*n-1个整数a[]。

注:1 <= t <= 32,1 <= n <= 1e3,-1e3 <= a[] <= 1e3。

 

Output

输出一个整数代表可以得到的最大和。

 

Sample Input

2 2 1 1 1 2 -10 20 -10

Sample Output

3 40

HINT

 

ps:

对于给数,我们记录里面负数的个数ant,绝对值之和sum,和绝对值最小值minn

正数集合为x,负数集合为y:

一 :我们每次要从x集合拿a个数,y集合拿b个数,且a+b == n,那么如果n为奇数的话,y集合的负数是可以都变成正数的(方法合理即可)。

二 :如果n为偶数,那么我们只能改变偶数个数,那么就判断y集合的元素是奇数还是偶数,如果是偶数,那么也可以全部变成正数;如果是奇数,那么总有一个数不能变成正数,那么我们为了得到最优解,就让绝对值最小的为负数,sum- 2*minn即可。

 

#include
int main()
{
    int t,n,a;
    scanf("%d",&t);
    while(t--)
    {
        int sum=0,inf=99999999;
        int z=0;
        scanf("%d",&n);
        for(int i=1; i<2*n; i++)
        {
            scanf("%d",&a);
            if(a<0)
            {
                a=-a;
                z++;
            }
            sum+=a;
            if(inf>a)
                inf=a;
        }
        if(z%2==0||n&1)
            printf("%d\n",sum);
        else
            printf("%d\n",sum-2*inf);
    }
}

 

1902: 985的因子对难题

Time Limit:2 SecMemory Limit:128 MB
Submit:143Solved:39

SubmitStatusWeb Board

Description

985有n个正整数,他想知道存在多少个不同的因子对(a[i], a[j])使得

1 <= i, j <= n && i != j && a[j] % a[i] == 0,其中i和j是元素的下标。

特别地,他认为(a[i],a[j])与(a[j],a[i])是一样的因子对。

 

Input

第一行输入一个整数t,代表有t组测试数据。

每组数据占两行,第一行输入一个n代表元素个数,下面一行输入n个整数a[]。

注:1 <= t <= 30,1 <= n <= 1e5,1 <= a[] <= 1e6。

 

 

Output

一个整数代表最后的答案。

 

Sample Input

2 5 1 2 3 4 5 5 2 2 2 2 2

Sample Output

5 10

HINT

ps:数组num[]记录每一个数的出现次数,然后数组fac[]记录某一个数的因子数,然后就可以求出。。

 

 

#include 
#include 
#include 
#include 
using namespace std;
#define M 1000010
#define INF 0x3f3f3f
#define RCL(a, b) memset(a, b, sizeof(a))
int num[M], fac[M];
int main()
{
    int t, n, maxx, a;
    scanf("%d", &t);
    while(t--)
    {
        maxx = 0;
        RCL(num, 0);
        RCL(fac, 0);
        scanf("%d", &n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d", &a);
            if(a > maxx)
            {
                maxx = a;
            }
            num[a]++;//记录 a 出现了多少次
        }
        for(int i=1; i 1)
            {
                ans += (num[i] * (num[i] - 1)) >> 1;//数学组合 相同的数出现了好多次就要先考虑
            }
            ans += fac[i] * num[i];//因子与母体相乘
        }

        printf("%d\n", ans);
    }

    return 0;
}

 

相关TAG标签 专场
上一篇:HDU1253 胜利大逃亡
下一篇:UVA-11021 - Tribles(概率期望)
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站