NOIP模拟赛 by hzwer

 

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[2000005],f[2000005];
int main()
{
    cin>>n>>m;
    memset(f,-1,sizeof(f));
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d",&a[i].b,&a[i].a);
    }
    sort(a+1,a+1+n);
    int now=0;
    for(int i=1;i<=n;++i)
    {
        if(a[i].a-a[i-1].a>17)now+=18,v[now]+=a[i].b;
        else now+=a[i].a-a[i-1].a,v[now]+=a[i].b;
    }
    int ans=0;
    f[0]=0;
    for(int i=0;i<=now;++i)
    {
        if(f[i]!=-1)
        {
            f[i+4]=max(f[i+4],f[i]+v[i+4]);
            f[i+7]=max(f[i+7],f[i]+v[i+7]);
            ans=max(ans,f[now]);
        }
    }
    cout<<ans;
    puts("");
    return 0;
}

 

 

---

 

小奇的矩阵(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

 

【数据范围】

测试点编号	N	M
1	6	0
2	100	5
3	2000	9
4	50000	0
5	50000	0
6	50000	1
7	50000	6
8	100000	10
9	100000	13
10	100000	15

 

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

---