模拟与高精度
作为入门，本人选择了模拟与高精度作为学习之始，做完了这一板块的洛谷官方题单。
模拟题不涉及算法，考验的是代码能力，自不必多说，所以仅总结一些在做题时学到的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;
} - 为了方便进位，将字符串转为数字的时候倒序存储
- 两个数相加，最高位数只可能是两个数位数最大的加一
- 最后别忘了将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;
}-
两数相乘的结果的位数最多不超过两个数的位数之和
-
模拟乘法的运算
c[i+j-1] += a[i] * b[j]; -
单独处理进位， 不易出错
-
最后别忘了将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;
}-
计算阶乘之和的简便运算
int s = 1, ans = 0; for(int i = 1; i <= n; i++) { s *= i; ans += s; } -
别忘了把计算乘法的数组的初始值设为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;
}非递归
#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;
}- 快速幂的两种模板
- 的含义是取出b在二进制下的最后一位
- 具体解释可以参考此文章
麦森数
输入p，输出的位数和后五百位
#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;
}- 数字很大，用纯高精TLE，此处用快速幂的非递归版本
- 此处仅要求输出结果的后500位，由于取模运算的分配律，在计算过程中只要计算每个中间结果的后500位即可
- tmp为保存中间结果的数组，别忘了每次运算前将其清零
- 别忘了每次运算结束后把tmp赋值给结果数组
- 可以证明，的位数和相同，而的位数可直接由公式算出来，故位数可以直接输出
模拟
快读
由于使用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;
}- 只能读入整数
- 可以吸收行末空格
数组旋转
#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;
}-
整个数组旋转90度很简单
//R*R矩阵，下标从1开始 //顺时针 tmp2[j][R+1-i] = tmp1[i][j]; //逆时针 tmp2[R+1-j][i] = tmp1[i][j];但本题要求局部旋转，需要自己推下标变换公式。为了省事，可以先把要旋转的部分复制出来，整体旋转，之后再赋值给原数组（如上所示）。
-
该做法毕竟有偷懒之嫌，不过本题的下标公式也很好推，代码如下：
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]; }
结构体排序
#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;
} -
c++中sort()的用法：
//前两个参数是指向排序起始位置和结束位置的指针，左闭右开 //第三个参数是自定义的比较函数，不填则默认升序 sort(arr, arr+n, comparision); -
比较函数的写法：
bool comparsion(int a, int b) { return a > b; //大的排前面，降序 return a < b; //小的排前面，升序 } -
c++中sort()函数用快排实现，不稳定，需要稳定用stable_sort()
构造特征值
#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;
}此题唯一的难点就在于如何判断John和牛永远不会相遇。虽说可以记录循环次数，如果超过一定数量（比如10000）就认为永远不会相遇，但毕竟过于牵强。可以用构造特征值的方法：
-
首先，如果在某一时刻，John和牛所处的位置和他们的朝向都与之前某一时刻相同，也就是说他们二者进入了死循环，我们可以认为他们永远不会相遇。
-
基于此，我们可以用这六个变量构造出一个特征值nt，如果出现了重复的nt值，则停止循环。
-
特征值的构造要满足的条件是：不同情况的特征值不能相同。可以通过给每个变量乘上一个不同的权重实现。
一共有种情况。构造函数：//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;此函数的最大值为，且保证一个变量加一所引起的函数值变化不会和其他变量加一相同，保证唯一性。
一道不错的模拟题
#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;
}模拟与高精度
https://lmc20020909.github.io/模拟与高精度/