目录多项式输出模拟 / 字符串处理分数线划定排序 / 结构体细胞分裂质因数分解 / 数学道路游戏线性 DP / 环形处理T1 多项式输出题目链接洛谷 P1067https://www.luogu.com.cn/problem/P1067题意给出一个一元多项式的次数 n以及从最高次到常数项的系数。要求按照标准数学格式输出多项式规则如下不输出系数为 0 的项第一项不输出加号系数为 1 或 -1 时不输出 1只输出符号一次项只写 x不写 x^1常数项直接输出数字思路讲解本题是经典模拟题核心是按项处理、分类讨论。按从高次到常数项依次遍历每一项系数为 0 直接跳过符号处理第一项不输出加号正数输出 负数输出 -系数处理次数 0 且系数绝对值为 1不输出 1常数项必须输出数字次数处理次数 0只输出数字次数 1只输出 x次数 ≥ 2输出 x^ 次数只要把符号、系数、次数三部分拆开处理代码就会非常清晰。完整 AC 代码#include iostream #include cstdio using namespace std; int a[110]; int n; int main() { cin n; for (int i 0; i n; i) cin a[i]; bool first true; for (int i 0; i n; i) { int c a[i]; int p n - i; if (c 0) continue; // 符号 if (c 0 !first) cout ; if (c 0) cout -; int ab abs(c); first false; // 系数部分 if (p 0 ab ! 1) cout ab; if (p 0) cout ab; // x 与指数 if (p 0) { cout x; if (p 1) cout ^ p; } } return 0; }T2 分数线划定题目链接洛谷 P1068https://www.luogu.com.cn/problem/P1068题意有 n 个选手给出报名号与成绩。录取名额为 m×1.5向下取整。按成绩从高到低排序同分按报名号从小到大排序。输出分数线、实际录取人数再输出所有录取者。思路讲解这是最基础的排序题核心只有两点结构体排序排序规则成绩降序学号升序步骤读入所有学生信息自定义排序规则算出分数线第 need 名的成绩统计所有 ≥ 分数线的学生输出结果边界注意可能有多人同分压线要全部录取学号小的优先完整 AC 代码#include iostream #include algorithm using namespace std; struct Stu { int id, score; } s[5010]; bool cmp(Stu a, Stu b) { if (a.score ! b.score) return a.score b.score; return a.id b.id; } int main() { int n, m; cin n m; int need m * 1.5; for (int i 1; i n; i) cin s[i].id s[i].score; sort(s 1, s n 1, cmp); int line s[need].score; int cnt 0; for (int i 1; i n; i) { if (s[i].score line) cnt; else break; } cout line cnt endl; for (int i 1; i cnt; i) cout s[i].id s[i].score endl; return 0; }T3 细胞分裂题目链接洛谷 P1069https://www.luogu.com.cn/problem/P1069题意总试管数 M m1^m2。有 n 种细胞第 i 种每秒分裂为 Si 倍。问最少多少秒后细胞总数能被 M 整除。若永远不能输出 -1。思路讲解本题考察质因数分解是数学题而非模拟题。核心结论一个数能被 M 整除当且仅当它包含 M 的所有质因子且次数足够。步骤对 m1 质因数分解再乘以 m2得到 M 的质因子与所需次数对每个细胞 Si 质因数分解若 Si 缺少 M 的任意一个质因子 → 永远不行否则计算每个质因子需要多少秒取最大值所有细胞中取最小时间即为答案关键点必须用质因数分解不能暴力枚举次数向上取整(need has - 1) /has完整 AC 代码#include iostream #include cstring #include algorithm using namespace std; const int INF 1e9; int pri[300], cnt[300], tot; int m1, m2, n; void divide(int x) { tot 0; memset(pri, 0, sizeof(pri)); memset(cnt, 0, sizeof(cnt)); for (int i 2; i * i x; i) { if (x % i 0) { pri[tot] i; while (x % i 0) { cnt[tot]; x / i; } } } if (x 1) { pri[tot] x; cnt[tot] 1; } for (int i 1; i tot; i) cnt[i] * m2; } int solve(int x) { int res 0; for (int i 1; i tot; i) { int p pri[i]; int need cnt[i]; int has 0; while (x % p 0) { has; x / p; } if (has 0) return INF; int t (need has - 1) / has; res max(res, t); } return res; } int main() { cin n; cin m1 m2; if (m1 1) { cout 0 endl; return 0; } divide(m1); int ans INF; for (int i 1; i n; i) { int s; cin s; ans min(ans, solve(s)); } if (ans INF) cout -1 endl; else cout ans endl; return 0; }T4 道路游戏题目链接洛谷 P1070https://www.luogu.com.cn/problem/P1070题意环形道路上有 n 个位置m 个时间单位。每个位置每个时刻会出现金币。机器人可以走 1~k 步也可以花钱换新机器人。求最大收益。思路讲解本题是线性 DP状态非常清晰设dp [i] 第 i 分钟结束时的最大收益转移思路枚举上一次换机器人的时间 j从 j1 走到 i累加金币减去购买机器人的花费。因为道路是环形位置要取模处理。关键点机器人可以连续走但不能超过 k 步每次换机器人都要花钱金币只能在对应时间、对应位置获取答案是 dp [1…m] 中的最大值完整 AC 代码#include iostream #include cstring #include algorithm using namespace std; const int N 1010; const int INF 0x3f3f3f3f; int n, m, K; int coin[N][N]; int cost[N]; int dp[N]; int main() { cin n m K; for (int i 1; i n; i) for (int j 1; j m; j) cin coin[i][j]; for (int i 1; i n; i) cin cost[i]; memset(dp, -INF, sizeof(dp)); dp[0] 0; for (int i 1; i m; i) { for (int st 1; st n; st) { int sum 0; for (int t 0; t K i - t 0; t) { int pos st - t; if (pos 0) pos n; sum coin[pos][i - t]; if (dp[i - t - 1] ! -INF) dp[i] max(dp[i], dp[i - t - 1] sum - cost[st]); } } } int ans 0; for (int i 1; i m; i) ans max(ans, dp[i]); cout ans endl; return 0; }