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

#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;
}

#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;
}

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();
			}

		}
	}
}