模拟与高精度

  作为入门，本人选择了模拟与高精度作为学习之始，做完了这一板块的洛谷官方题单。

  模拟题不涉及算法，考验的是代码能力，自不必多说，所以仅总结一些在做题时学到的tricks。

高精度

A+B Problem（高精）

#include <iostream>
#include <string>
#define MAXN 1000
using namespace std;
string a, b;
int x[MAXN], y[MAXN], ans[MAXN], la, lb, lans, temp;
int main() {
	cin >> a >> b;
	la = a.length(), lb = b. length();
	for(int i = 0 ; i < la; i++)
		x[la - i] = a[i] - '0';
	for(int i = 0 ; i < lb; i++)
		y[lb - i] = b[i] - '0';
	lans = la > lb ? la+1 : lb+1;
	for(int i = 1; i <= lans; i++) {
		ans[i] = x[i] + y[i] + temp;
		temp = ans[i] / 10;
		ans[i] %= 10;
	}
	if(!ans[lans]) lans--;
	for(int i = lans; i >= 1; i--)
		cout << ans[i];
	return 0;
} 
CPP

• 为了方便进位，将字符串转为数字的时候倒序存储
• 两个数相加，最高位数只可能是两个数位数最大的加一
• 最后别忘了将lans更新到正确的位置上（最高非零位）

A*B Problem

#include <iostream>
#include <algorithm>
#include <string>
#define MAXN 2100
using namespace std;
string A, B;
int a[MAXN], b[MAXN], c[MAXN];
int main(){
	cin >> A >> B;
	for(int i = A.length() -1; i >= 0; i--)
		a[A.length() - i] = A[i] - '0';
	for(int i = B.length() - 1; i >= 0; i--)
		b[B.length() - i] = B[i] - '0';
	int len = A.length() + B.length();
	for(int i = 1; i <= A.length(); i++)
		for(int j = 1; j <= B.length(); j++)
			c[i+j-1] += a[i] * b[j];
	for(int i = 1; i <= len; i++){
		c[i+1] += c[i] / 10;
		c[i] %= 10;
	}
	for(; !c[len] && len > 1;)
		len--;
	for(int i = len; i > 0; i--)
		cout << c[i];
	return 0;
}
CPP

• 两数相乘的结果的位数最多不超过两个数的位数之和

• 模拟乘法的运算

  c[i+j-1] += a[i] * b[j];
  CPP

• 单独处理进位， 不易出错

• 最后别忘了将lans更新到正确的位置上（最高非零位）

阶乘之和

#include <iostream>
#define MAXN 100
using namespace std;
int a[MAXN], s[MAXN], n, la = 1, ls = 1;
void multi(int m) {
	int temp = 0, i;
	for(i = 1; i <= la; i++) {
		a[i] = a[i] * m + temp;
		temp = a[i] / 10;
		a[i] %= 10;
	}
	while(temp) {
		a[i] += temp;
		temp = a[i] / 10;
		a[i] %= 10;
		i++;
	}
	la = i - 1;
}
void add() {
	int temp = 0;
	ls = ls > la ? ls + 1 : la + 1;
	for(int i = 1; i <= ls; i++) {
		s[i] = s[i] + a[i] + temp;
		temp = s[i] / 10;
		s[i] %= 10;
	}
	if(!s[ls]) ls--;
}
int main() {
	cin >> n;
	a[1] = 1;
	for(int i = 1; i <= n; i++) {
		multi(i);
		add();
	}
	for(int i = ls; i >= 1; i--)
		cout << s[i];
	return 0;
}
CPP

• 计算阶乘之和的简便运算

  int s = 1, ans = 0;
  for(int i = 1; i <= n; i++) {
      s *= i;
      ans += s;
  }
  CPP

• 别忘了把计算乘法的数组的初始值设为1！

• 在运算中维护数组的长度，避免全部遍历

快速幂

【模板】快速幂||取余运算

递归

#include <iostream>
using namespace std;
long long a, b, p;
long long fast(long long m, long long n) {
	if(n == 0) return 1;
	if(n % 2 == 1) return fast(m, n-1) * m % p;
	else {
		long long temp = fast(m, n/2) % p;
		return temp * temp % p;
	}
} 
int main() {
	cin >> a >> b >> p;
	cout << a << "^" << b << " mod " << p << "=" << fast(a,b);
	return 0;
}
CPP

非递归

#include <cstdio>
using namespace std;
long long a, b, p, ans = 1;
int main() {
	scanf("%lld%lld%lld", &a, &b, &p);
	printf("%lld^%lld mod %lld=", a, b, p);
	while(b) {
		if(b&1)
			ans = ans * a % p;
		b >>= 1;
		a = a * a % p;
	}
	printf("%lld", ans);
	return 0;
}
CPP

• 快速幂的两种模板
• $b\&1$的含义是取出b在二进制下的最后一位
• 具体解释可以参考此文章

麦森数

输入p，输出$2^p-1$的位数和后五百位

#include <cstdio>
#include <cmath>
#include <string.h>
#define MAXN 2000
using namespace std;
int a[MAXN], ans[MAXN], tmp[MAXN];
long long p, la = 1, lans = 1, lt;
int multi1() {
	memset(tmp, 0, sizeof(tmp));
	for(int i = 1; i <= la; i++)
		for(int j = 1; j <= lans; j++)
			tmp[i+j-1] += a[i] * ans[j];
	lt = la + lans;
	for(int i = 1; i <= lt; i++) {
		tmp[i+1] += tmp[i] / 10;
		tmp[i] %= 10;
	}
	while(!tmp[lt] && lt>0) lt--;
	for(int i = 1; i <= lt; i++)
		ans[i] = tmp[i];
	return lt > 500 ? 500 : lt;
}
int multi2() {
	memset(tmp, 0, sizeof(tmp));
	for(int i = 1; i <= la; i++)
		for(int j = 1; j <= la; j++)
			tmp[i+j-1] += a[i] * a[j];
	lt = la * 2;
	for(int i = 1; i <= lt; i++) {
		tmp[i+1] += tmp[i] / 10;
		tmp[i] %= 10;
	}
	while(!tmp[lt] && lt>0) lt--;
	for(int i = 1; i <= lt; i++)
		a[i] = tmp[i];
	return lt > 500 ? 500 : lt;
}
int main() {
	scanf("%lld", &p);
	printf("%lld\n", (int)(log10(2) * p + 1));
	a[1] = 2;
	ans[1] = 1;
	while(p) {
	    if(p&1) lans = multi1();
		p >>= 1;
		la = multi2();
	}
	ans[1]--;
	for(int i = 500; i >= 1; i--) {
		if(i != 500 && i % 50 == 0) printf("\n%d", ans[i]);
		else printf("%d", ans[i]);
	}	
	return 0;
}
CPP

• 数字很大，用纯高精TLE，此处用快速幂的非递归版本
• 此处仅要求输出结果的后500位，由于取模运算的分配律，在计算过程中只要计算每个中间结果的后500位即可
• tmp为保存中间结果的数组，别忘了每次运算前将其清零
• 别忘了每次运算结束后把tmp赋值给结果数组
• 可以证明，$2^p-1$的位数和$2^p$相同，而$2^p$的位数可直接由公式$log_{10}(2)*p+1$算出来，故位数可以直接输出

模拟

快读

由于使用scanf()需要自己处理空格问题，而cin速度太慢，所以使用快读函数读入整数

inline int read() {
	int X = 0, w = 1;
	char ch = 0;
	while(ch < '0' || ch > '9') {if(ch == '-') w = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {X = (X<<1) + (X<<3) + ch - '0'; ch = getchar();}
	return X*w;
}
CPP

• 只能读入整数
• 可以吸收行末空格

数组旋转

魔法少女小Scarlet

#include <cstdio>
#define MAXN 510
using namespace std;
int a[MAXN][MAXN], tmp1[MAXN][MAXN], tmp2[MAXN][MAXN], n, m, x, y, r, z;
inline int read() {
	int X = 0, w = 1;
	char ch = 0;
	while(ch < '0' || ch > '9') {if(ch == '-') w = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {X = (X<<1) + (X<<3) + ch - '0'; ch = getchar();}
	return X*w;
}
void merge() {
	int R = r << 1 | 1;
	for(int i = x-r; i <= x+r; i++)
		for(int j = y-r; j <= y+r; j++)
			tmp1[i-x+r+1][j-y+r+1] = a[i][j];
	for(int i = 1; i <= R; i++)
		for(int j = 1; j <= R; j++)
			if(!z) tmp2[j][R+1-i] = tmp1[i][j];
			else tmp2[R+1-j][i] = tmp1[i][j];
	for(int i = x-r; i <= x+r; i++)
		for(int j = y-r; j <= y+r; j++)
			a[i][j] = tmp2[i-x+r+1][j-y+r+1];
}
inline void print() {
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++)
			printf("%d%s", a[i][j], j == n ? "" : " " );
		printf("\n");
	}	
}
int main() {
	n = read(), m = read();
	for(int i = 1, count = 1; i <= n; i++)
		for(int j = 1; j <= n; j++, count++)
			a[i][j] = count;
	while(m--) {
		x = read(), y = read(), r = read(), z = read();
		merge();
	}
	print();
	return 0;
}
CPP

• 整个数组旋转90度很简单

  //R*R矩阵，下标从1开始
  //顺时针
  tmp2[j][R+1-i] = tmp1[i][j];
  //逆时针
  tmp2[R+1-j][i] = tmp1[i][j];
  CPP

  但本题要求局部旋转，需要自己推下标变换公式。为了省事，可以先把要旋转的部分复制出来，整体旋转，之后再赋值给原数组（如上所示）。

• 该做法毕竟有偷懒之嫌，不过本题的下标公式也很好推，代码如下：

  void merge() {
  	for(int i = x-r; i <= x+r; i++)
  		for(int j = y-r; j <= y+r; j++)
  			if(!z) na[x-y+j][x+y-i] = matrix[i][j];
  			else na[x+y-j][y-x+i] = matrix[i][j];
  	for(int i = x-r; i <= x+r; i++)
  		for(int j = y-r; j <= y+r; j++)
  			matrix[i][j] = na[i][j];
  }
  CPP

结构体排序

帮贡排序

#include <iostream>
#include <algorithm>
#include <string>
#define MAXN 150
using namespace std;
struct Member {
	string name, position;
	int con, grade, h;
	void print() {
		cout << name << " " << position << " " << grade << endl;
	}
}members[MAXN];

int transform(string s) {
	if(s == "BangZhu") return 0;
	if(s == "FuBangZhu") return 1;
	if(s == "HuFa") return 2;
	if(s == "ZhangLao") return 3;
	if(s == "TangZhu") return 4;
	if(s == "JingYing") return 5;
	if(s == "BangZhong") return 6; 
}

bool comparsion(Member a, Member b) {
	if(a.con == b.con) return a.h < b.h;
	return a.con > b.con;
}

bool comparision_2(Member a, Member b) {
	if(a.position == b.position) {
		if(a.grade == b.grade) return a.h < b.h;
		return a.grade > b.grade;
	}
	return transform(a.position) < transform(b.position);
}

int main() {
	int n;
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> members[i].name >> members[i].position >> members[i].con >> members[i].grade;
		members[i].h = i;
	}
	stable_sort(members+3, members+n, comparsion);
	for(int i = 3; i < n; i++) {
		if(i < 5) members[i].position = "HuFa";
		else if(i < 9) members[i].position = "ZhangLao";
		else if(i < 16) members[i].position = "TangZhu";
		else if(i < 41) members[i].position = "JingYing";
		else members[i].position = "BangZhong";
	}
	stable_sort(members+3, members+n, comparision_2);
	for(int i = 0; i < n; i++)
		members[i].print(); 
	return 0;
} 
CPP

• c++中sort()的用法：

  //前两个参数是指向排序起始位置和结束位置的指针，左闭右开
  //第三个参数是自定义的比较函数，不填则默认升序
  sort(arr, arr+n, comparision);
  CPP

• 比较函数的写法：

  bool comparsion(int a, int b) {
  	return a > b;		//大的排前面，降序
      return a < b;		//小的排前面，升序
  }
  CPP

• c++中sort()函数用快排实现，不稳定，需要稳定用stable_sort()

构造特征值

两只塔姆沃斯牛 The Tamworth Two

#include <iostream>
#include <cstdio>
#include <algorithm> 
using namespace std;
int direction[][2] = {{-1,0},{0,1},{1,0},{0,-1}};
struct Player {
	int x, y;
	int index = 0;
	int dir[2] = {direction[index][0], direction[index][1]};
}cow, john;
char map[10][10];
int ans, nt;
bool zt[160005];

int main() {
	for(int i = 0; i < 10; i++) {
		for(int j = 0; j < 10; j++) {
			cin >> map[i][j];
			if(map[i][j] == 'F') {
				map[i][j] = '.';
				john.x = i;
				john.y = j;
			}
			else if(map[i][j] == 'C') {
				map[i][j] == '.';
				cow.x = i;
				cow.y = j;
			}
		}
	}

	while(1) {
		int cx = cow.x + cow.dir[0];
		int cy = cow.y + cow.dir[1];
		if(map[cx][cy] == '*' || cx < 0 || cy < 0 || cx > 9 || cy > 9) {
			cow.index++;
			cow.dir[0] = direction[cow.index % 4][0];
			cow.dir[1] = direction[cow.index % 4][1];
		}
		else {
			cow.x = cx;
			cow.y = cy;
		}
		int jx = john.x + john.dir[0];
		int jy = john.y + john.dir[1];
		if(map[jx][jy] == '*' || jx < 0 || jy < 0 || jx > 9 || jy > 9) {
			john.index++;
			john.dir[0] = direction[john.index % 4][0];
			john.dir[1] = direction[john.index % 4][1];
		}
		else {
			john.x = jx;
			john.y = jy;
		}
		ans++;
		nt = john.x + john.y * 10 + cow.x * 100 + cow.y * 1000 + (john.index%4) * 10000 + (cow.index%4) * 40000;
		if(cow.x == john.x && cow.y == john.y) break;
		if(zt[nt]) {
			ans = 0;
			break;
		}
		zt[nt] = 1;
	}
	cout << ans;
	return 0;
}
CPP

此题唯一的难点就在于如何判断John和牛永远不会相遇。虽说可以记录循环次数，如果超过一定数量（比如10000）就认为永远不会相遇，但毕竟过于牵强。可以用构造特征值的方法：

• 首先，如果在某一时刻，John和牛所处的位置和他们的朝向都与之前某一时刻相同，也就是说他们二者进入了死循环，我们可以认为他们永远不会相遇。

• 基于此，我们可以用这六个变量构造出一个特征值nt，如果出现了重复的nt值，则停止循环。

• 特征值的构造要满足的条件是：不同情况的特征值不能相同。可以通过给每个变量乘上一个不同的权重实现。
  一共有$10*10*10*10*4*4=160000$种情况。构造函数：

  //john.index和cow.index取值为0,1,2,3，坐标都是0~9
  nt = john.x + john.y*10 + cow.x*100 + cow.y*1000 + (john.index%4)*10000 + (cow.index%4)*40000;
  CPP

  此函数的最大值为$9+90+900+9000+30000+120000=159999$，且保证一个变量加一所引起的函数值变化不会和其他变量加一相同，保证唯一性。

一道不错的模拟题

作业调度方案

#include <cstdio>
#include <iostream>
#include <string.h>
#define MAXN 21
using namespace std;
int order[401], arrange[MAXN][MAXN], timi[MAXN][MAXN], inde[MAXN], betime[MAXN], machine[MAXN][10000], ans, m, n;
int find(int num, int bet, int last) {
	int res = 0;
	for(int i = bet; i < 10000; i++) {
		int count = 0;
		if(!machine[num][i]) {
			res = i;
			for(int j = i; !machine[num][j]; j++) {
				count++;
				if(count >= last)
					return res;
			}
		}
	}
	return res;
}
int main() {
	cin >> m >> n;
	for(int i = 1; i <= m*n; i++)
		cin >> order[i];
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin >> arrange[i][j];
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
		cin >> timi[i][j];
			
	for(int i = 0; i < MAXN; i++) {
		inde[i] = 1;
		betime[i] = 1;
	}

	for(int i = 1; i <= m*n; i++) {
		int num = arrange[order[i]][inde[order[i]]];
		int t = timi[order[i]][inde[order[i]]];
		int start = find(num, betime[order[i]], t);
		for(int j = start; j < start+t; j++)
			machine[num][j] = 1;
		betime[order[i]] = start + t;
		ans = start+t-1 > ans ? start+t-1 : ans;
		inde[order[i]]++;
	}
	printf("%d", ans);
	return 0;
}
CPP