NOIP2017模拟赛(2) 总结

时间：2022-12-17 08:47:43

前言：没参赛的我~~

a 星星光芒

题目描述

给你一个N个结点的有向图，而且给你一个N * N的邻接矩阵，表示两个结点之间是否有边。star是这样定义的 : 它有一个中心结点，并且中心结点至少有3个出度，出度用于计算star的光芒程度。 对于一个结点V来说，它可以有多颗star, 记为结点V的star number. 例如, 如果结点V 的出度是5， 那么结点V的 star number 通过计算等于16， 因为以V为中心结点而且光芒程度是3的有C(5,3) =10颗star, 光芒程度是4 的有C(5,4)=5颗star,光芒程度是5 的有C(5,5)=1颗star. 所以，结点V共有10 + 5 + 1 = 16颗不同的star。如果一个结点的出度是X，且X>=3，那么该结点共有：C(X,3) + C(X,4) + C(X,5) + …+ C(X,X)颗不同的star。上面提到的C其实就是组合数。
下面我们定义有向图中的全明星路径：如果某条路径同时满足下面两个条件，则认为是全明星路径:
(1) 路径上的任意一个结点的star number大于0且不超过给定的整数G.
(2) 路径上的结点 Vi 和 Vi+1，要保证Vi+1 的star number不小于 Vi 的star number。
你的任务是：计算给出的有向图，最长的全名星路径有多少个结点。如果全明星路径可以无限长，输出-1.如果没有全明星路径 (也就是给出的图中的所有结点的star number要么是0，要么大于G),则输出 0。

输入格式

多组测试数据。
第一行：一个整数ng, 1 <= ng <= 5. 表示有ng组测试数据。
每组测试数据格式如下：
第一行：两个整数N、C. 2 <= N <= 50, 1 <= G <= 10^9.
接下来有N行，每行有N列，表示邻接矩阵，如果有边则是1，否则是0。保证第i行的第i个是0.

输出格式

最长的全名星路径有多少个结点。
ng行，每行对应一组输入数据。

输入样例

2
5 1000
01110
10111
00000
00000
00000
4 1
0111
0000
0000
0000

输出样例

2 （第一组测试数据：结点0的star number是1, 结点1的star number是5，其他结点的star number都是0）
1 （第二组测试数据）

解题思路(组合数+floyd)

这题作为本场比赛的签到题，思维难度并不大。
我们首先很快想到记录出度和预处理组合数。然后按题目要求加入组合数，由于超过G即非法那么一旦大于G就令其等于G+1就可以不用考虑long long。然后就是找满足要求的最长路，要求是两两的就像连边，于是直接用floyd跑最长路就可以了，时间不是问题。
最后小细节才是决定你是会做并顺利AC还是会做但爆炸的关键。注意一个点的情况，很危险 。还有最后判0和-1，有”负环”，在这里即 f[i][i]>1 则代表有个圈儿。然后ans与任意两点(可重)看一下能否更新，都不能才输出0。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#define N 60
#define oo 1e9

using namespace std;

int ng;
int n, G, f[N][N], deg[N];
int C[N][N], sum[N], ans;
char Map[N][N];

int main(){

    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);

    C[0][0] = 1;
    for(int i = 1; i < N; i++){
      C[i][0] = 1;
      for(int j = 1; j < N; j++){
        C[i][j] = C[i-1][j] + C[i-1][j-1];
        if(C[i][j] > oo)  C[i][j] = oo + 1;
      }
    }
    scanf("%d", &ng);
    while(ng --){
      scanf("%d%d", &n, &G);
      for(int i = 1; i <= n; i++){
        deg[i] = 0;
        scanf("%s", &Map[i]);
        for(int j = 1; j <= n; j++)
          if(Map[i][j-1] == '1')  deg[i] ++;
      }

      for(int i = 1; i <= n; i++){
        sum[i] = 0;
        for(int j = 3; j <= deg[i]; j++){
          sum[i] += C[deg[i]][j];
          if(sum[i] > oo){
            sum[i] = oo + 1;
            break;
          }
        }
      }

      for(int i = 1; i <= n; i++)
       for(int j = 1; j <= n; j++)
         f[i][j] = 0;

      for(int i = 1; i <= n; i++) 
        if(0 < sum[i] && sum[i] <= G)  f[i][i] = 1;
      for(int i = 1; i <= n; i++)
       for(int j = 1; j <= n; j++)
         if(Map[i][j-1] == '1' && sum[i] <= sum[j] && 0 < sum[i] && sum[j] <= G)  f[i][j] = 2;

      for(int k = 1; k <= n; k++)
       for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++){
          if(!f[i][k] || !f[k][j])  continue;
          f[i][j] = max(f[i][j], f[i][k] + f[k][j] - 1);
        }


      bool sign = true;
      ans = 0;

      for(int i = 1; i <= n && sign; i++)  if(f[i][i] > 1){
        printf("-1\n");
        sign = false;
      }
      if(sign){
        for(int i = 1; i <= n; i++)
         for(int j = 1; j <= n; j++)
           ans = max(ans, f[i][j]);
        printf("%d\n", ans);
      }
    }

    return 0;
}

b 职员分配

题目描述

由于Blue Mary呕心沥血的管理，Blue Mary的网络公司蒸蒸日上。现在一共拥有了n名职员，可惜没有任何的金钱和声誉。平均每名每天职员都可以给公司带来x单位金钱或者y单位声誉（名利不能双全）。并且可以花费z单位的金钱在人才交易市场发布广告招聘职员，每次发布广告三天以后就会招聘到一名职员，并且必须在发布广告并且招聘到职员的那一天才能发布下一次广告。
Blue Mary计划以最快的时间获得至少A单位金钱和至少B单位声誉，请你计算一下他至少需要多少时间才能达到他的目标。

输入格式

输入有且仅有一行，包含六个整数n,x,y,z,A和B，意义如题目描述所述。

输出格式

要求输出一行，包含一个整数，表示Blue Mary至少需要多少时间才能达到他的目标。

输入样例

输入样例一：

1 2 3 4 5 6

输入样例二：

3 2 3 2 19 18

输出样例

5

6

约定：
1<=n,x,y,z,A,B<=20
说明：
规定每天先去人才市场，然后再去赚钱（或名誉）。

解题思路(dp)

首先真心的，这是一道好题。题目简洁明了，dp模型明显。
我体育课想了一节课(一边打球一边想)，最终想出来一种简单易懂的方法。
我们记 dp[i][j][k] 为有i个人，有j单位金钱及k单位声誉时的最少时间。就是完全根据题目要求的简朴地去记。
然后发现这很好转移。
首先 dp[n][0][0]=0;
然后员工数最多不超过A+B，枚举当前状态去不去买“人才”，如果不买就枚举当前员工有多少贡献金钱，剩下的就负责“声誉”。超出的部分就折到A或B就可以了。然后得到收益会使时间推移一天。
即 dp[i][nm][nn]=min(dp[i][nm][nn],dp[i][j][k]+1);
其中 nm=min(A,j+m∗x),nn=min(B,k+(i−m)∗y);
m 是本次枚举的负责金钱的那批人数。
要是要去人才市场呢？照做呗。只不过这次直接一次处理三天。由于题目规定要先去人才市场，所以用的钱必须得是今天收益前的，而不是今天收益后的(更不是三天后的。。)。
一定不能透支购买啊，非法的！！30分惨痛教训！！
和不买一样，我们有
nm=min(A,j+m∗x−z),nn=min(B,k+(i∗3−m)∗y);dp[i+1][nm][nn]=min(dp[i+1][nm][nn],dp[i][j][k]+3);
这里m从0枚举到3i。
最后只需枚举员工数选取最小值就行了。
时间复杂度 O(204∗6)
其实这只是最暴力的一种作法(当延迟天数多了就很慢)，应该还有更优、更巧妙的作法。很多人状态记法都不同。甚至某神犇告诉我可以直接省掉一维，声誉转化为金钱计算(其实金钱声誉可以看作等价的)， k<=>⌈k/y⌉∗x ，%%%。

甚至这题好像还有贪心的作法。。。我们枚举去人才市场的天数，然后贪心的先搞钱，够钱就去人才市场，钱搞够了后再去搞声誉就行了。因为声誉和金钱的获得次序是随便的(现实中的话。。)，我们易发现这是一个单峰函数(yy一下)，然后将枚举改成三分就快会很多。这是一道很灵活的（水）题。ps:某人写了爆搜都卡过了，RT。。。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#define N 50
#define oo 0x7fffffff

using namespace std;


int n, x, y, z, A, B, ans = oo;
int dp[N][N][N];

int main(){

    freopen("b.in", "r", stdin);
    freopen("b.out", "w", stdout);

    scanf("%d%d%d%d%d%d", &n, &x, &y, &z, &A, &B);

    for(int i = 0; i < N; i++)
     for(int j = 0; j < N; j++)
      for(int k = 0; k < N; k++)
        dp[i][j][k] = oo;

    dp[n][0][0] = 0;

    for(int i = n; i <= A + B; i++){
      for(int j = 0; j <= A; j++){
        for(int k = 0; k <= B; k++){
          if(dp[i][j][k] == oo)  continue;
          for(int m = 0; m <= i; m++){
            int nm = min(A, j + m * x), nn = min(B, k + (i-m) * y);
            dp[i][nm][nn] = min(dp[i][nm][nn], dp[i][j][k] + 1);
          }
          for(int m = 0; m <= i*3; m++){
            if(j < z)  continue;
            int nm = min(A, j + m * x - z), nn = min(B, k + (i*3-m) * y);
            dp[i+1][nm][nn] = min(dp[i+1][nm][nn], dp[i][j][k] + 3);
          }
        }
      }
    }

    for(int i = n; i <= A + B; i++)
      ans = min(ans, dp[i][A][B]);

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

    return 0;
}

c 加油站

题目描述

奶牛们开车到郊外旅游，由于驾驶技术不行，不小心撞到了石头，油箱漏油了。 现在汽车每走一单位距离，油箱就损耗和漏掉共一单位油。
为了修车，必须把车开到最近的小镇(不会超过10,000,000单位距离)，到小镇的路可以认为是在一条直线上。从现在的位置到小镇途中, 共有 N (1 <= N<= 50,000) 个加油点，第i个加油点位于距离小镇有D_i (1 <= D_i < L)单位距离的地方，该加油站储油F_i (1 <= F_i <= 100)单位.由于路途艰险，奶牛们想尽量把加油的次数减到最少.汽车的油箱可以认为是无穷大. 汽车现在为于距离小镇L个单位距离的地方，并且有P单位的油(1 <= P <= 10,000,000).请你计算最少要加多少次油才能到达小镇,或者汽车根本开不到小镇. 注意：在同一地点，可能有多个加油站,但是，在计算时，它们是独立的，认为是两个不同的加油站。

输入格式

  • 第1行: 三个整数: N、 L、P.
  • 第 2..N+1行: 两个整数： D_i 、 F_i. 对应着一个加油站。

输出格式

  • 一行: 到达小镇需要的最少的加油次数，如果无法到达小镇, 输出-1.

输入样例

4 25 10
4 4
5 2
11 5
15 10

输出样例

2

【输入解释】
汽车现在在距离小镇25个单位距离的地方，汽车有10个单位的汽油.
在途中, 有 4 个加油站，他们分别位于距离小镇： 4、 5、 11、15个单位距离的地方。（可以看出，它们跟汽车现在位置的距离分别是：21、20、14、10） 。 这4个加油站的储油量分别是： 4、 2、 5、10。

【输出解释】
汽车开10单位距离后, 停车加10单位的油, 再开4单位距离,停车加5单位的油, 然后就可以开到小镇了。

解题思路(贪心+数据结构)

不按套路出牌的最后一题竟是一道千古水题。
直接贪心，没有就加前面的最多的，写个数据结构(堆、线段树、优先队列，甚至F很小可以用桶)，然后一通乱搞就可以AC了。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#define N 50005

using namespace std;
priority_queue <int> q;

int n, L, p, pos, ans;

struct Data{
    int d, f;
    bool operator < (const Data& W) const{return d < W.d;}
}a[N];

bool f = true;

int main(){

    freopen("c.in", "r", stdin);
    freopen("c.out", "w", stdout);

    scanf("%d%d%d", &n, &L, &p);
    for(int i = 1; i <= n; i++){
      scanf("%d%d", &a[i].d, &a[i].f);
      a[i].d = L - a[i].d;
    }

    sort(a+1, a+n+1);
    a[n+1].d = L;

    for(int i = 1; i <= n+1; i++){
      while(p < a[i].d - pos){
        if(q.empty()){
          f = false;
          break;
        }
        p += q.top();
        q.pop();
        ans ++;
      }
      if(!f)  break;
      p -= (a[i].d - pos);
      pos = a[i].d;
      q.push(a[i].f);
    }

    if(f)  printf("%d\n", ans);
    else  printf("-1\n");


    return 0;
}

总结

由于没去考所以觉得题目都不难，然后还是要多总结各种题型，积累方法，解题方法比知识本身更加重要。

NOIP2017模拟赛(2) 总结

夏之忆，泣凋零，彼日花未名。

标签：

相关文章