目录【算法1-1】模拟与高精度P1042 [NOIP 2003 普及组] 乒乓球P2670 [NOIP 2015 普及组] 扫雷游戏P1563 [NOIP 2016 提高组] 玩具谜题P1601 高精度加法P1303 A*B ProblemP1009 [NOIP 1998 普及组] 阶乘之和P4924 [1007] 魔法少女小ScarletP1328 [NOIP 2014 提高组] 生活大爆炸版石头剪刀布P1518 [USACO2.4] 两只塔姆沃斯牛 The Tamworth TwoP1067 [NOIP 2009 普及组] 多项式输出P1098 [NOIP 2007 提高组] 字符串的展开P1065 [NOIP 2006 提高组] 作业调度方案待更新P1786 帮贡排序P1591 阶乘数码P1249 最大乘积P1045 [NOIP 2003 普及组] 麦森数【算法1-1】模拟与高精度模拟题意叫你干嘛你就干嘛按 时间 / 步骤 / 规则 一步步实现。高精度long long 也装不下的整数19位怎么办——用 字符串 / 数组 进位借位​ 模拟竖式运算。P1042 [NOIP 2003 普及组] 乒乓球#include stdio.h #include stdlib.h #include string.h int main() { char cur; int game[62525] {0}, count 0, w 0, l 0; scanf(%c, cur); while(cur ! E) { // 11分制-统计 if(cur W) { w; game[count] 1; } else if(cur L){ l; count; } // 11分制-输出 if((w 11 || l 11) abs(l - w) 2) { printf(%d:%d\n, w, l); w 0; l 0; } scanf(%c, cur); } // 11分制-输出剩余0:0也要输出 printf(%d:%d\n\n, w, l); // 21分制 w 0; l 0; for(int i 0; i count; i) { if(game[i] 1) w; else l; if((w 21 || l 21) abs(l - w) 2) { printf(%d:%d\n, w, l); w 0; l 0; } } printf(%d:%d, w, l); return 0; }P2670 [NOIP 2015 普及组] 扫雷游戏#include stdio.h int main() { int a[100][100] {0}, n, m; // 0表示周围地雷数若为-1则是地雷本身 char ch; scanf(%d %d, n, m); for(int i 0; i n; i) { for(int j 0; j m; j) { scanf(%c, ch); if(ch ! * ch ! ?) --j; // 排除\n的影响 if(ch *) { a[i][j] -1; // 周围地雷数 1; for(int x -1; x 1; x) { for(int y -1; y 1; y){ int newX i x, newY j y; if(newX 0 newX n - 1 newY 0 newY m - 1 a[newX][newY] ! -1) a[newX][newY] 1; } } } } } for(int i 0; i n; i) { for(int j 0; j m; j) { if(a[i][j] -1) printf(*); else printf(%d, a[i][j]); } printf(\n); } return 0; }P1563 [NOIP 2016 提高组] 玩具谜题#include stdio.h struct Person{ int face; char profession[20]; }; int main() { int n, m, cur 0; struct Person persons[100000]; scanf(%d %d, n, m); for(int i 0; i n; i) scanf(%d %s, persons[i].face, persons[i].profession); for(int i 0; i m; i) { int direction, x; scanf(%d %d, direction, x); // : 朝内(0), 右数(1) / 朝外(1), 左数(0) if(persons[cur].face ! direction) cur x; else cur - x; if(cur 0) cur n; if(cur n) cur - n; } printf(%s, persons[cur].profession); return 0; }P1601 高精度加法#include stdio.h #include string.h int main() { char a[502], b[502]; int res[502] {0}, length 0, lenA, lenB; scanf(%s%s, a, b); lenA strlen(a) - 1; lenB strlen(b) - 1; int maxLen lenA lenB ? lenA: lenB; for(int i 0; i maxLen; i) { if(i lenA i lenB) res[length] (a[lenA - i] - 0) (b[lenB - i] - 0); else if(i lenA) res[length] b[lenB - i] - 0; else res[length] a[lenA - i] - 0; // 进位 if(res[length - 1] 10) { res[length - 1] - 10; res[length] 1; } } // 从后往前输出 if(res[length] 1) printf(1); for(int i length - 1; i 0; --i) { printf(%d, res[i]); } return 0; }P1303 A*B Problem#include stdio.h #include string.h int main() { char a[2002], b[2002]; int res[4002] {0}, lenA, lenB; scanf(%s%s, a, b); if(strcmp(a, 0) 0 || strcmp(b, 0) 0) { printf(0); return 0; } lenA strlen(a) - 1; lenB strlen(b) - 1; for(int i 0; i lenA; i) { int tempA a[lenA - i] - 0; for(int j 0; j lenB; j) { int tempB b[lenB - j] - 0; res[i j] tempA * tempB; } } // 统一进位 for(int i 0; i lenA lenB; i) { if(res[i] 10) { res[i 1] res[i] / 10; res[i] res[i] % 10; } } // 输出 if(res[lenA lenB 1] 0) printf(%d, res[lenA lenB 1]); for(int i lenA lenB; i 0; --i) { printf(%d, res[i]); } return 0; }P1009 [NOIP 1998 普及组] 阶乘之和#include stdio.h #include string.h #define MAXLEN 1000 struct BigInt { int dig[MAXLEN]; int length; // 最高位因为不是字符串了不方便获取数据实际长度 }; void init(struct BigInt *res, struct BigInt *cur) { int temp[MAXLEN] {0}; // res-dig初始化为0() memcpy(res-dig, temp, sizeof(temp)); res-length 1; // cur-dig初始化为1(*) temp[0] 1; memcpy(cur-dig, temp, sizeof(temp)); cur-length 1; } // a * n与 P1303 略有不同因为只有a是大数 void multiply(struct BigInt *a, int n) { int temp[MAXLEN] {0}; for(int i 0; i a-length; i) { temp[i] n * a-dig[i]; } // 统一进位 int i 0; for(; i a-length || temp[i] 0; i) { // 注意循环终止条件考虑 9*50 450进位是45故还需进位 if(temp[i] 10) { temp[i 1] temp[i] / 10; temp[i] % 10; } } memcpy(a-dig, temp, sizeof(temp)); a-length i; } // a b同 P1601 也略有不同因为都是从低位开始 void add(struct BigInt *a, struct BigInt *b) { int temp[MAXLEN] {0}, length 0, lenA a-length, lenB b-length; int maxLen lenA lenB ? lenA: lenB; for(int i 0; i maxLen; i) { if(i lenA i lenB) temp[length] a-dig[i] b-dig[i]; else if(i lenA) temp[length] b-dig[i]; else temp[length] a-dig[i]; // 进位 if(temp[length - 1] 10) { temp[length - 1] - 10; temp[length] 1; } } memcpy(a-dig, temp, sizeof(temp)); a-length temp[length] 0 ? length : length - 1; } int main() { int n; scanf(%d, n); struct BigInt result; struct BigInt cur; init(result, cur); for(int i 1; i n; i) { multiply(cur, i); add(result, cur); } // 输出 for(int i result.length - 1; i 0; --i) { printf(%d, result.dig[i]); } return 0; }P4924 [1007] 魔法少女小Scarlet#include stdio.h #include string.h #define MAXSIZE 500 int main() { int a[MAXSIZE][MAXSIZE], temp[MAXSIZE][MAXSIZE], n, m; scanf(%d %d, n, m); // 初始化 for(int i 0; i n; i) { for(int j 0; j n; j) { a[i][j] n * i j 1; } } // 施法 for(int i 0; i m; i) { int x, y, r, z; scanf(%d %d %d %d, x, y, r, z); x - 1; y - 1; z z 1 ? 1 : -1; memcpy(temp, a, sizeof(a)); for(int j -r; j r; j) { for(int k -r; k r; k) { temp[x - z * k][y z * j] a[x j][y k]; } } memcpy(a, temp, sizeof(a)); } // 输出 for(int i 0; i n; i) { for(int j 0; j n; j) { printf(%d , a[i][j]); } printf(\n); } return 0; }P1328 [NOIP 2014 提高组] 生活大爆炸版石头剪刀布这道题注意并不是对称矩阵下三角和上三角的输赢是相反的。#include stdio.h int main() { const int RESULT[5][5] {{0, -1, 1, 1, -1}, {1, 0, -1, 1, -1}, {-1, 1, 0, -1, 1}, {-1, -1, 1, 0, 1}, {1, 1, -1, -1, 0}}; // pk结果 int pattern1[201], pattern2[201]; int n, n1, n2, score1 0, score2 0; scanf(%d %d %d, n, n1, n2); // 出拳规律 for(int i 0; i n1; i) scanf(%d, pattern1[i]); for(int i 0; i n2; i) scanf(%d, pattern2[i]); // pk for(int i 0; i n; i) { int res RESULT[pattern1[i % n1]][pattern2[i % n2]]; if(res 1) score1; else if(res -1) score2; } printf(%d %d, score1, score2); return 0; }P1518 [USACO2.4] 两只塔姆沃斯牛 The Tamworth Two#include stdio.h const int DIRECTION[4][2] {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 上右下左 char map[10][10]; void move(int *p) { int curDirection *(p 2); int newX *p DIRECTION[curDirection][0]; int newY *(p 1) DIRECTION[curDirection][1]; if(newX 0 newX 10 newY 0 newY 10 map[newX][newY] ! *) { *p newX; *(p 1) newY; } else *(p 2) (curDirection 1) % 4; return; } int main(){ int time 0, p[3], cow[3]; for(int i 0; i 10 ; i){ scanf(%s, map[i]); for(int j 0; j 10 ; j){ if(map[i][j] F) { p[0] i; p[1] j; p[2] 0; map[i][j] .; // 已记录人和牛的位置无需更新地图 } if(map[i][j] C) { cow[0] i; cow[1] j; cow[2] 0; map[i][j] .; } } } for(; !(p[0] cow[0] p[1] cow[1]); time) { move(p); move(cow); if(time 160000) break; // 一旦状态(p、cow)重复必然陷入循环状态数10*10*4*10*10*4 160000 } if(time 160000) printf(%d, time); else printf(0); return 0; }P1067 [NOIP 2009 普及组] 多项式输出#include stdio.h int main() { int n, a, begin 0; scanf(%d, n); for(int i 0; i n; i) { scanf(%d, a); if(a 0) continue; // 符号 if(a 0 begin 0) printf(); // 系数 if(i n) printf(%d, a); else if(a -1) printf(-); else if(a ! 1) printf(%d, a); // 指数 if(i ! n) printf(i n - 1 ? x : x^%d, n - i); // 常数项、1次项 begin 1; } return 0; }P1098 [NOIP 2007 提高组] 字符串的展开#include stdio.h #include ctype.h int needExpand(char *str, int i) { char prev *(str i - 1), next *(str i 1); if(prev a next z) return next - prev; if(prev 0 next 9) return next - prev; return 0; } int main() { int p1, p2, p3; char line[102]; scanf(%d %d %d, p1, p2, p3); scanf(%s, line); for(int i 0; line[i] ! \n line[i] ! \0; i) { char ch line[i]; if(ch - i 0 needExpand(line, i) 0) { char prev *(line i - 1), next *(line i 1); int step p3 1 ? 1 : -1; // 顺序 if(p3 2) { prev *(line i 1); next *(line i - 1); } for(char j prev step; p3 1 ? j next : j next; j step) { // 要填充的字符 char temp *; if(isalpha(j)) { if(p1 1) temp tolower(j); else if(p1 2) temp toupper(j); } else if(p1 ! 3) temp j; // 输出k次 for(int k 0; k p2; k) { printf(%c, temp); } } } else printf(%c, ch); } return 0; }P1065 [NOIP 2006 提高组] 作业调度方案待更新待更新P1786 帮贡排序#include stdio.h #include stdlib.h #include string.h const char POSITION[7][12] {BangZhu, FuBangZhu, HuFa, ZhangLao, TangZhu, JingYing, BangZhong}; typedef struct{ char name[32]; int position; int donation; int level; } Member; // 帮贡从高到低第一关键字在输入中出现的顺序从前到后第二关键字 // 方便起见也把帮主、副帮主排到最前面共3个 int cmp1(const void *a, const void *b) { if(((Member *)a)-position 1) return -1; return ((Member *)b)-donation - ((Member *)a)-donation; } // 职位从高到低第一关键字等级从高到低第二关键字在输入中出现的顺序从前到后第三关键字 int cmp2(const void *a, const void *b) { Member *member1 (Member *)a, *member2 (Member *)b; if(member1-position ! member2-position) return member1-position - member2-position; // 号小的职位高 return member2-level - member1-level; } int main() { int n; Member members[110], temp[110]; scanf(%d, n); for(int i 0; i n; i) { char temp[12]; scanf(%s %s %d %d, members[i].name, temp, members[i].donation, members[i].level); for(int j 0; j 7; j) { if(strcmp(temp, POSITION[j]) 0) { members[i].position j; break; } } } // 第一次排序更新职位 memcpy(temp, members, sizeof(members)); // 不能直接排members会对第二次的排序结果产生影响 qsort(temp, n, sizeof(Member), cmp1); for(int i 3; i n; i) { int p; if(i - 3 2) p 2; else if(i - 3 6) p 3; else if(i - 3 13) p 4; else if(i - 3 38) p 5; else p 6; // 把名字当成id更新对应成员的职位 for(int j 0; j n; j) { if(strcmp(temp[i].name, members[j].name) 0) { members[j].position p; break; } } } // 第二次排序输出 qsort(members, n, sizeof(Member), cmp2); for(int i 0; i n; i) { printf(%s %s %d\n, members[i].name, POSITION[members[i].position], members[i].level); } return 0; }P1591 阶乘数码#include stdio.h #include string.h #define MAXLEN 3000 // n 1000n!显然是高精度问题n! (10^3)^n 10^3000 struct BigInt { int dig[MAXLEN]; int length; }; void multiply(struct BigInt *a, int n) { int temp[MAXLEN] {0}; int len a-length; for (int i 0; i len; i) { temp[i] n * a-dig[i]; } int i 0; for (;i len || temp[i]; i) { temp[i 1] temp[i] / 10; temp[i] % 10; } memcpy(a-dig, temp, sizeof(temp)); // 一定注意最后一个参数是字节数不是元素个数 a-length i; } int countTimesInBigInt(struct BigInt a, int x) { int cnt 0; for (int i 0; i a.length; i) if (a.dig[i] x) cnt; return cnt; } int main() { int t, n, digit, temp[MAXLEN] {1}; struct BigInt cur; scanf(%d, t); while (t--) { scanf(%d %d, n, digit); memcpy(cur.dig, temp, sizeof(temp)); cur.length 1; for (int i 1; i n; i )multiply(cur, i); printf(%d\n, countTimesInBigInt(cur, digit)); } return 0; }P1249 最大乘积显然乘法(i1)比加法更能让结果变大所以应该尽可能分解n 234...x 。x 10000的连乘显然又是高精度问题。#include stdio.h #define MAXLINE 40000 void multiply(int *a, int n) { for(int i 1; i a[0]; i) a[i] * n; // 进位 int i 1; for(; i a[0] || a[i] 0; i) { a[i 1] a[i] / 10; a[i] % 10; } a[0] i - 1; } int main() { int n, sum 0, res[MAXLINE] {1, 1}; // 新学到的一招res[0]存长度就不用结构体了 int parts[10000], count 0; scanf(%d, n); // 尽可能拆分出不同的数 for(int i 2; sum i n; i) { sum i; parts[count] i; } // 把剩余值回灌从而乘积最大从后往前 int rem n - sum; for(int i count - 1; rem 0; --i, --rem) { if(i 0) i count - 1; // 回灌完一轮重新从后往前 parts[i % count]; } // 输出分解方案 for(int i 0; i count; i) { printf(%d , parts[i]); multiply(res, parts[i]); } // 输出乘积 printf(\n); for(int i res[0]; i 1; --i) printf(%d, res[i]); return 0; }P1045 [NOIP 2003 普及组] 麦森数计算 2^p若每次 *2需要循环 p 次会TLE故需要用到快速幂算法。快速幂基于以下数学性质当b为偶数a^b (a^2)^(b/2)当b为奇数a^b a * a^(b-1)#include stdio.h #include string.h #include math.h #define N 500 // 只用管最后500位 void multiply(int *a, int *b) { int temp[N] {0}; for(int i 0; i N; i) { for(int j 0; i j N; j) temp[i j] a[i] * b[j]; } int i 0; for(; i N - 1; i) { temp[i 1] temp[i] / 10; temp[i] % 10; } temp[N - 1] % 10; memcpy(a, temp, sizeof(temp)); } int main() { int p, res[N] {1}, base[N] {2}, temp[N]; scanf(%d, p); // 位数n floor(lg(2^p-1)) 1 floor(p * lg(2)) 1 printf(%d, (int)(p * log10(2)) 1); //如果是%.0f会WA因为它是四舍五入 // 计算 // 2^p快速幂 while (p 0) { if (p % 2 1) { multiply(res, base); // res * base; } memcpy(temp, base, sizeof(base)); multiply(temp, base); // base * base memcpy(base, temp, sizeof(base)); p / 2; } // -1借位 int i 0; for(; res[i] 0 i N; i) res[i] 9; if(i N) res[i]--; // 输出 printf(\n); for(i N - 1; i 0; --i) { printf(%d, res[i]); if(i % 50 0) printf(\n); } return 0; }