第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-131 Beaver‘s Calculator-阿里云开发者社区

第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-131 Beaver's Calculator

前言

这段时间我会把蓝桥杯官网上的所有非VIP题目都发布一遍，让大家方便去搜索，所有题目都会有几种语言的写法，帮助大家提供一个思路，当然，思路只是思路，千万别只看着答案就认为会了啊，这个方法基本上很难让你成长，成长是在思考的过程中找寻到自己的那个解题思路，并且首先肯定要依靠于题海战术来让自己的解题思维进行一定量的训练，如果没有这个量变到质变的过程你会发现对于相对需要思考的题目你解决的速度就会非常慢，这个思维过程甚至没有纸笔的绘制你根本无法在大脑中勾勒出来，所以我们前期学习的时候是学习别人的思路通过自己的方式转换思维变成自己的模式，说着听绕口，但是就是靠量来堆叠思维方式，刷题方案自主定义的话肯定就是从非常简单的开始，稍微对数据结构有一定的理解，暴力、二分法等等，一步步的成长，数据结构很多，一般也就几种啊，线性表、树、图、再就是其它了。顺序表与链表也就是线性表，当然栈，队列还有串都是属于线性表的，这个我就不在这里一一细分了，相对来说都要慢慢来一个个搞定的。蓝桥杯中对于大专来说相对是比较友好的，例如三分枚举、离散化，图，复杂数据结构还有统计都是不考的，我们找简单题刷个一两百，然后再进行中等题目的训练，当我们掌握深度搜索与广度搜索后再往动态规划上靠一靠，慢慢的就会掌握各种规律，有了规律就能大胆的长一些难度比较高的题目了，再次说明，刷题一定要循序渐进，千万别想着直接就能解决难题，那只是对自己进行劝退处理。加油，平常心，一步步前进。

Beaver's Calculator

资源限制

内存限制：256.0MB C/C++时间限制：3.0s Java时间限制：9.0s Python时间限制：15.0s

问题描述

　　从万能词典来的聪明的海狸已经使我们惊讶了一次。他开发了一种新的计算器，他将此命名为"Beaver's Calculator 1.0"。它非常特别，并且被计划使用在各种各样的科学问题中。

　　为了测试它，聪明的海狸邀请了n位科学家，编号从1到n。第i位科学家给这个计算器带来了 ki个计算题。第i个科学家带来的问题编号1到n，并且它们必须按照编号一个一个计算，因为对于每个问题的计算都必须依赖前一个问题的计算结果。

　　每个教授的每个问题都用一个数 ai, j 来描述，i（1≤i≤n）是科学家的编号，j（1≤j≤ ki ）是问题的编号， ai, j 表示解决这个问题所需资源单位的数量。

　　这个计算器非常不凡。它一个接一个的解决问题。在一个问题解决后，并且在下一个问题被计算前，计算器分配或解放资源。

　　计算器中最昂贵的操作是解放资源，解放远远慢于分配。所以对计算器而言，每一个接下来的问题所需的资源不少于前一个，是非常重要的。

　　给你关于这些科学家所给问题的相关信息。你需要给这些问题安排一个顺序，使得“坏对”尽可能少。

　　所谓“坏对”，就是相邻两个问题中，后一个问题需求的资源比前一个问题少。别忘了，对于同一个科学家给出的问题，计算它们的相对顺序必须是固定的。

输入格式

　　第一行包含一个整数n，表示科学家的人数。接下来n行每行有5个整数，ki, ai, 1, xi, yi, mi (0 ≤ ai, 1 < mi ≤ 109, 1 ≤ xi, yi ≤ 109) ，分别表示第i个科学家的问题个数，第1个问题所需资源单位数，以及3个用来计算 ai, j 的参量。ai, j = (ai, j - 1 * xi + yi)mod mi。

输出格式

　　第一行输出一个整数，表示最优顺序下最少的“坏对”个数。

　　如果问题的总个数不超过200000,接下来输出

行，表示解决问题的最优顺序。每一行两个用空格隔开的整数，表示这个问题所需的资源单位数和提供这个问题的科学家的编号。

样例输入

2

2 1 1 1 10

2 3 1 1 10

样例输出

0

1 1

2 1

3 2

4 2

数据规模和约定

　　20%的数据 n = 2, 1 ≤ ki ≤ 2000；

　　另外30%的数据 n = 2, 1 ≤ ki ≤ 200000；

　　剩下50%的数据 1 ≤ n ≤ 5000, 1 ≤ ki ≤ 5000。

题解：

C语言

#include <stdio.h>
#include <stdlib.h>
enum
{
   ZD = 200000 , 
   CS = 0 ,
   ZY = 1 ,
   BH = 2 ,
   XI = 0 ,
   YI = 1 ,
   MI = 2 ,
} ;
int q_zhds(int *,int [][3],int);
void qux(int *,int) ;
int q_dhds(int *,int [][3],int);
void xieru(int *,int [][3],int []);
void shuru(int []);
int q_aij(int, int []);
int bj(const void *,const void *);
void shuchu(int ,int [][3]);
int main(void)
{
   int n ;
   scanf("%d",&n);
   static int jie[ZD][3] , gs = 0 ;
   printf("%d\n",q_zhds(&gs,jie,n));
   if ( gs <= ZD )
   {
      qsort(jie,gs,sizeof *jie,bj);
      shuchu(gs,jie);
   }
  return 0;
}
void shuchu(int n,int a[][3])
{
   while ( n -- > 0 )
   {
      printf("%d %d\n",a[0][ZY],a[0][BH]);
      a++;
   }
}
int bj(const void * vq,const void * vh)
{
   const int (*q)[3]  = (const int (*)[3])vq ,(*h )[3] = (const int (*)[3])vh ;
   if ( q[0][CS] == h[0][CS] )
   {
      return q[0][ZY] - h[0][ZY] ;
   }
   return q[0][CS] - h[0][CS] ;
}
int q_aij(int aij, int xs[])
{
   return ((long long)aij*xs[XI]+xs[YI]) % xs[MI] ;
}
void shuru(int xym[])
{
   scanf("%d",xym+XI);
   scanf("%d",xym+YI);
   scanf("%d",xym+MI);
}
void xieru(int *p_gs,int jie[][3],int x[])
{
   if ( * p_gs < ZD )
   {
      jie[*p_gs][CS] = x[CS];
      jie[*p_gs][ZY] = x[ZY];
      jie[*p_gs][BH] = x[BH];
   }
   ++ * p_gs ;
}
int q_dhds(int *p_gs,int jie[][3],int bh)
{
      int ki ;       //ki, ai,1, xi, yi, mi
      scanf("%d",&ki);
      int tmp[3] = { 0 , 0 , bh };
      scanf("%d",tmp+1);
      xieru(p_gs,jie,tmp);
      int x_yi_mi[3] ;
      shuru(x_yi_mi);
      while ( -- ki > 0 )
      {
         int aij = q_aij(tmp[ZY], x_yi_mi);
         tmp[CS] += aij < tmp[ZY] ;
         tmp[ZY] = aij ;
         xieru(p_gs,jie,tmp);
      }
      return tmp[CS] ;
}
void qux(int *p,int x)
{
   if ( x > * p )
   {
      * p = x ;
   }
}
int q_zhds(int *p_gs,int jie[][3],int n) 
{
   int hds = 0 ;
   int bh ;
   for ( bh = 1 ; bh <= n ; bh ++ )
   {
      qux(&hds,q_dhds(p_gs,jie,bh)) ;
   }
   return hds;
}

C++语言

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long int
using namespace std;
const int N = 200010;
struct S 
{
  int level;
  int need;
  int id;
  
  void set(int level , int need , int id)
  {
    this->level = level;
    this->need = need;
    this->id = id;
  }
};
S s[N];
bool cmp(S a , S b)
{
  if(a.level == b.level)
  {
    if(a.need == b.need)
      return a.id < b.id;
    return a.need < b.need;
  }
  return a.level < b.level;
}
int main()
{
  int n , cnt = 0 , ans = 0;
  ll k , a , x , y , m; 
  scanf("%d" , &n);
  
  for(int i = 0 ; i < n ; i++)
  {
    scanf("%lld %lld %lld %lld %lld" , &k , &a , &x , &y , &m);
    
    int level = 0;
    for(int j = 0 ; j < k ; j++)
    {
      if(cnt < 2e5)           //个数大于200000则不需要输出！！！ 
        s[cnt++].set(level , a , i);
      
      if(j != k - 1)
      {
        ll t = (a * x + y) % m;
        if(t < a)
          level++;
        a = t;
      }
    }
    
    if(level > ans)
      ans = level;
  }
  
  printf("%lld\n" , ans);
  if(cnt < 2e5) 
  {
    sort(s , s + cnt , cmp);
    for(int i = 0 ; i < cnt ; i++)
      printf("%d %d\n" , s[i].need , s[i].id + 1);
  }
  return 0;
}

Java语言

在扫描输入内容上会有不同的方法，但是与Scanner的用法是相同的。

import java.io.*;
class Expert{
  int indexOfProblem;
  int numOfProblem;
  long[] problem;  // 存放每个问题所消耗的资源数
}
public class Main{
  static Expert[] experts;
  
  public static void merge(int start,int end,long[][] ans) {
    int mid = (start+end)>>1;
    int i = start;
    int j = mid+1;
    int k = 0;
    long[][] temp = new long[end-start+1][2];
    while(i <= mid && j <= end) {
      if(ans[i][0] > ans[j][0]) {
        temp[k][0] = ans[j][0];
        temp[k++][1] = ans[j++][1];
      }else {
        temp[k][0] = ans[i][0];
        temp[k++][1] = ans[i++][1];
      }
    }
    
    while(i <= mid) {
      temp[k][0] = ans[i][0];
      temp[k++][1] = ans[i++][1];
    }
    while(j <= end) {
      temp[k][0] = ans[j][0];
      temp[k++][1] = ans[j++][1];
    }
    for( i = 0 ; i < k; i++) {
      ans[i+start][0] = temp[i][0];
      ans[i+start][1] = temp[i][1]; 
    }
  }
  
  public static void mergeSort(int start,int end, long[][] ans) {
    if(start < end) {
      int mid = (start + end)>>1;
      mergeSort(start, mid, ans);
      mergeSort(mid+1, end, ans);
      merge(start, end, ans);
    }
  }
  
  public static void main(String[] args) throws IOException{
    
    StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    
    in.nextToken();
    int n = (int)in.nval;
    long numOfAllProblems = 0;
    long maxBad = -1;
    experts = new Expert[n];
    for(int i = 0 ; i < n ; i++) {
      experts[i] = new Expert();
    }
    for(int i = 0 ; i < n; i++) {
      long oneBad = 0;
      in.nextToken();
      experts[i].numOfProblem = (int)in.nval;
      numOfAllProblems += (int)in.nval;
      experts[i].problem = new long[(int)in.nval+1];
      experts[i].problem[0] = -1;
      experts[i].indexOfProblem = 1;
      long firstProblem, xi, yi, mi;
      in.nextToken();
      firstProblem = (long)in.nval;
      in.nextToken();
      xi = (long)in.nval;
      in.nextToken();
      yi = (long)in.nval;
      in.nextToken();
      mi = (long)in.nval;
      experts[i].problem[1] = firstProblem;
      for(int j = 2 ; j <= experts[i].numOfProblem ; j++) {
        experts[i].problem[j] = (experts[i].problem[j-1] * xi + yi) % mi; 
        if(experts[i].problem[j] < experts[i].problem[j-1]) {
          oneBad++;
        }
      }
      if(oneBad > maxBad) {
        maxBad = oneBad;
      }
    }
    
    out.println(maxBad);
    out.flush();
    if(numOfAllProblems <= 200000) {
      long[][] ans = new long[(int) numOfAllProblems][2];
      int start = 0, end = 0;
      
      while(end < numOfAllProblems) {
        for(int i = 0 ; i < n; i++) {
          int j;
          for(j = experts[i].indexOfProblem ; j <= experts[i].numOfProblem; j++) {
            if(j != experts[i].indexOfProblem && (experts[i].problem[j] < experts[i].problem[j-1])) {
              experts[i].indexOfProblem = j;
              break;
            }
            ans[end][1] = i;
            ans[end++][0] = experts[i].problem[j];
          }
          if(j > experts[i].numOfProblem) {
            experts[i].indexOfProblem = j;
          }
        }
        
        mergeSort(start, end-1, ans);
        
        start = end;
      }
      
      for(int i = 0 ; i < numOfAllProblems; i++) {
        out.println(ans[i][0] + " " + (ans[i][1]+1));
        out.flush();
      }
    }
  }
}

总结

没有什么不付出就能拿到的结果，我们都是在负重前行，最终结果与自身先天的脑力有一定的关系，但是还是有很大一部分看自己后天的努力，其实从报名到比赛也就5个月左右，真正刷题的事件也就2个月，2个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。

第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-131 Beaver‘s Calculator