2015年10月04日NOIP模拟赛

by hzwer    (这是小奇=>

小奇挖矿2(mining)

【题目背景】

小奇飞船的钻头开启了无限耐久+精准采集模式！这次它要将原矿运到泛光之源的矿石交易市场，以便为飞船升级无限非概率引擎。

【问题描述】

现在有m+1个星球，从左到右标号为0到m，小奇最初在0号星球。

有n处矿体，第i处矿体有ai单位原矿，在第bi个星球上。

由于飞船使用的是老式的跳跃引擎，每次它只能从第x号星球移动到第x+4号星球或x+7号星球。每到一个星球，小奇会采走该星球上所有的原矿，求小奇能采到的最大原矿数量。

注意，小奇不必最终到达m号星球。

【输入格式】

第一行2个整数n，m。

接下来n行，每行2个整数ai，bi。

【输出格式】

输出一行一个整数，表示要求的结果。

【样例输入】

3 13

100 4

10 7

1 11

【样例输出】

101

【样例解释】

第一次从0到4，第二次从4到11，总共采到101单位原矿。

【数据范围】

对于20%的数据 n=1，m<=10^5

对于40%的数据 n<=15，m<=10^5

对于60%的数据 m<=10^5

对于100%的数据 n<=10^5，m<=10^9，1<=ai<=10^4，1<=bi<=m

对于２０％的数据：

由ｎ＝１　－＞只要找到有矿的那个地方采就好　跑不到那里的话就没矿可采

只需判断有矿的地方标号能否拆成７和４的倍数和　然后输出结果即可

对于４０％的数据：

ｎ＜＝１５　－＞暴力枚举矿所在位置　按照上述方法更新答案

对于６０％的数据：

ｍ不是特别大 搞个dp 设i号矿挖矿x[i]

ans=max（f[i-7],f[i-4]）+x[i]

对于１００％的数据：

m很大 所以先用结构体排序

f[i]为到第i个矿能获得的最大矿数 得到

f[i]=max{f[j]}+x[i]//i-j满足能拆分成4和7

优化：超过17的一定可以到达  那么不超过17的范围内暴力，超过17的取个最大值即可

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 100005

using namespace std;

int n,m;

struct data

{

    int a,b;

    friend bool operator<(data a,data b)

    {

        return a.a<b.a;

    }

}a[maxn];

int v[],f[];

int main()

{

    cin>>n>>m;

    memset(f,-,sizeof(f));

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

    {

        scanf("%d%d",&a[i].b,&a[i].a);

    }

    sort(a+,a++n);

    int now=;

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

    {

        if(a[i].a-a[i-].a>)now+=,v[now]+=a[i].b;

        else now+=a[i].a-a[i-].a,v[now]+=a[i].b;

    }

    int ans=;

    f[]=;

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

    {

        if(f[i]!=-)

        {

            f[i+]=max(f[i+],f[i]+v[i+]);

            f[i+]=max(f[i+],f[i]+v[i+]);

            ans=max(ans,f[now]);

        }

    }

    cout<<ans;

    puts("");

    return ;

}

小奇的矩阵(matrix)

【题目背景】

小奇总是在数学课上思考奇怪的问题。

【问题描述】

给定一个n*m的矩阵，矩阵中的每个元素aij为正整数。

接下来规定

1.合法的路径初始从矩阵左上角出发，每次只能向右或向下走，终点为右下角。

2.路径经过的n+m-1个格子中的元素为A1,A2…A(n+m-1)，Aavg为Ai的平均数，路径的V值为(n+m-1)*∑(Ai-Aavg) ^2

(1<=i<=n+m-1)

求V值最小的合法路径，输出V值即可，有多组测试数据。

【输入格式】

第一行包含一个正整数T，表示数据组数。

对于每组数据：

第一行包含两个正整数n和m，表示矩阵的行数和列数。
接下来n行，每行m个正整数aij，描述这个矩阵。

【输出格式】

对于每次询问，输出一行一个整数表示要求的结果

【样例输入】

1

2 2

1 2

3 4

【样例输出】

14

【数据范围】

对于30%的数据 n<=10，m<=10

有另外40%的数据 n<=15 m<=15，矩阵中的元素不大于5

对于100%的数据 T<=5，n<=30，m<=30，矩阵中的元素不大于30

小奇的仓库(warehouse)

【题目背景】

小奇采的矿实在太多了，它准备在喵星系建个矿石仓库。令它无语的是，喵星系的货运飞船引擎还停留在上元时代！

【问题描述】

喵星系有n个星球，星球以及星球间的航线形成一棵树。

从星球a到星球b要花费[dis(a,b) Xor M]秒。（dis（a,b）表示ab间的航线长度，Xor为位运算中的异或）

为了给仓库选址，小奇想知道，星球i（1<=i<=n）到其它所有星球花费的时间之和。

【输入格式】

第一行包含两个正整数n，M。
接下来n-1行，每行3个正整数a,b,c，表示a，b之间的航线长度为c。

【输出格式】

n行，每行一个整数，表示星球i到其它所有星球花费的时间之和。

【样例输入】

4 0

1 2 1

1 3 2

1 4 3

【样例输出】

6

8

10

12

【数据范围】

保证答案不超过2*10^9