班级里有 n 名同学，第 i 名同学每隔 ai 天锻炼一次。某一天所有同学都一起锻炼了，求下一次所有同学再次一起锻炼至少要过多少天。
解题思路
所有同学再次同时锻炼的时间，必须同时是所有 ai 的倍数。
所以答案就是：
lcm(a1,a2,⋯,an)
由于 ai≤50，但多个数的最小公倍数可能比较大，记得使用 long long 防止溢出。
代码
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
int x = 0,f = 1; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
LL gcd(LL a, LL b) {
while (b) {
LL t = a % b;
a = b;
b = t;
}
return a;
}
int n;
inline void solve() {
cin >> n;
LL Ans = 1;
for (int i = 1; i <= n; i++) {
LL x; cin >> x;
LL g = gcd((LL)(Ans % x), x);
Ans = Ans / g * x;
}
printf("%lld\n", Ans);
}
int main() {
int _ = 1;
while (_--) solve();
return 0;
}
2. 小杨的队列
题目大意
有 N 名同学，每名同学有一个身高。老师依次点名若干名同学入队。每次新同学先站到队尾，然后队伍要按身高从低到高重新排序。问每次新同学加入后，最少需要交换几次位置。
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
int x = 0,f = 1; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
bool pri(int x) {
if (x < 2) return false;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) return false;
}
return true;
}
int a, b;
inline void solve() {
cin >> a >> b;
for (int x = a; x <= b; x++) {
int y = x % 10 * 10 + x / 10;
if (pri(x) && pri(y)) {
printf("%d\n", x);
}
}
}
int main() {
int _ = 1;
while (_--) solve();
return 0;
}
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e2 + 10;
int read(){
int x = 0,f = 1; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
int n, a[N][N];
inline void solve() {
cin >> n;
int r = 0;
int c = n / 2;
for (int x = 1; x <= n * n; x++) {
a[r][c] = x;
int nr = (r - 1 + n) % n;
int nc = (c + 1) % n;
if (a[nr][nc] == 0) {
r = nr;
c = nc;
} else {
r = (r + 1) % n;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (j) printf(" ");
printf("%d", a[i][j]);
}
printf("\n");
}
}
int main() {
int _ = 1;
while (_--) solve();
return 0;
}
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
int x = 0,f = 1; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
int digsum(int x) {
int s = 0;
while (x > 0) {
s += x % 10;
x /= 10;
}
return s;
}
int trans(int d) {
int x = d * 7;
while (x > 9) {
x = digsum(x);
}
return x;
}
string s;
inline void solve() {
cin >> s;
int sum = 0;
int pos = 1;
for (int i = (int)s.size() - 1; i >= 0; i--) {
int d = s[i] - '0';
if (pos % 2 == 1) sum += trans(d);
else sum += d;
pos++;
}
if (sum % 8 == 0) printf("T\n");
else printf("F\n");
}
int main() {
int _ = 1; cin >> _;
while (_--) solve();
return 0;
}
小明有 X 元钱，依次遇到 N 件想买的物品。
如果当前钱够买某件物品，就买下来，并扣掉对应价格；否则跳过。
求最后一共买了多少件物品。
解题思路
按顺序模拟即可。
对于每个价格 ai：
如果 X≥ai，说明可以买；
答案加 1；
钱数减少 ai。
代码
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
int x = 0,f = 1; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
int n, a[N], x;
inline void solve() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> x;
int Ans = 0;
for (int i = 1; i <= n; i++) {
if (x >= a[i]) {
x -= a[i];
Ans++;
}
}
printf("%d\n", Ans);
}
int main() {
int _ = 1;
while (_--) solve();
return 0;
}
2. 进制转换
题目大意
给定十进制正整数 N 和进制 R，其中 2≤R≤36，输出 N 的 R 进制表示。
超过 9 的数字用大写字母表示：
10 用 A；
11 用 B；
⋯
35 用 Z。
解题思路
不断对 R 取余。
例如：
NmodR
就是当前最低位。
然后令：
N=N/R
继续处理。
由于先得到的是低位，所以最后要反转字符串。
代码
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
int x = 0,f = 1; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
char gc(int x) {
if (x <= 9) return char('0' + x);
return char('A' + x - 10);
}
int n, r;
inline void solve() {
cin >> n >> r;
string Ans;
while (n > 0) {
Ans += gc(n % r);
n /= r;
}
reverse(Ans.begin(), Ans.end());
cout << Ans << '\n';
}
int main() {
int _ = 1;
while (_--) solve();
return 0;
}
3. 春游
题目大意
班上有 N 位同学，编号为 0 到 N−1。
集合时，同学们一共报出了 M 次编号，已经到达的同学可能会重复报编号。
要求输出没有到达的同学编号。
如果所有同学都到了，输出 N。
解题思路
用数组 vis 记录某个编号是否出现过。
读入每个编号 x 后，令：
vis[x] = true;
最后从 0 到 N−1 检查哪些编号没有出现。
代码
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
int x = 0,f = 1; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
int n, m, vis[N];
inline void solve() {
cin >> n >> m;
for (int i = 1, x; i <= m; i++) {
cin >> x;
vis[x] = 1;
}
bool all = true;
bool first = true;
for (int i = 0; i < n; i++) {
if (!vis[i]) {
all = false;
if (!first) printf(" ");
printf("%d", i);
first = false;
}
}
if (all) printf("%d\n", n);
}
int main() {
int _ = 1;
while (_--) solve();
return 0;
}
4. 密码合规
题目大意
输入一个用英文逗号分隔的字符串，每一段都是一个待检测密码。
合规密码需要满足：
长度在 6 到 12 之间；
只能包含小写字母、大写字母、数字、\texttt{!@#\$}；
大写字母、小写字母、数字三类中至少包含两类；
至少包含一个特殊字符 \texttt{!@#\$}。
输出所有合规密码。
解题思路
先按照逗号 , 把字符串切分成多个密码。
对每个密码检查：
长度是否合法；
是否有非法字符；
是否包含大写字母；
是否包含小写字母；
是否包含数字；
是否包含特殊字符。
如果满足条件，就输出。
代码
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
int x = 0,f = 1; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
int x = 0,f = 1; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
int n;
inline void solve() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
char ch = 'A' + (i + j - 2) % 26;
printf("%c", ch);
}
printf("\n");
}
}
int main() {
int _ = 1;
while (_--) solve();
return 0;
}
2. 勾股数
题目大意
给定 n，统计有多少组三元组 (a,b,c) 满足：
a2+b2=c2
并且：
1≤a≤b≤c≤n
这样的三元组叫做勾股数。
解题思路
枚举 a 和 b，计算：
c2=a2+b2
如果 c2 是完全平方数，并且 c≤n，则找到一组答案。
注意要求 a≤b，所以枚举时令 b 从 a 开始。
C++ 代码
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
int x = 0,f = 1; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
int n;
inline void solve() {
cin >> n;
int Ans = 0;
for (int a = 1; a <= n; a++) {
for (int b = a; b <= n; b++) {
int c2 = a * a + b * b;
int c = sqrt(c2);
if (c * c == c2 && c <= n) Ans++;
}
}
printf("%d\n", Ans);
}
int main() {
int _ = 1;
while (_--) solve();
return 0;
}
3. 百鸡问题
题目大意
每只公鸡 x 元，每只母鸡 y 元，每 z 只小鸡 1 元。现在有 n 元，要买 m 只鸡，问共有多少种购买方案。
解题思路
设公鸡数量为 a，母鸡数量为 b，小鸡数量为 c。
需要满足：
a+b+c=m
并且：
a×x+b×y+zc=n
由于每 z 只小鸡 1 元，所以 c 必须是 z 的倍数。
直接枚举公鸡和母鸡数量，小鸡数量由 m−a−b 得出。
C++ 代码
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
int x = 0,f = 1; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
int x, y, z, n, m;
inline void solve() {
cin >> x >> y >> z >> n >> m;
int Ans = 0;
for (int a = 0; a <= m; a++) {
for (int b = 0; b <= m - a; b++) {
int c = m - a - b;
if (c % z == 0) {
int cost = a * x + b * y + c / z;
if (cost == n) Ans++;
}
}
}
printf("%d\n", Ans);
}
int main() {
int _ = 1;
while (_--) solve();
return 0;
}
4. 画三角形
题目大意
输入 n，输出一个由大写字母组成的三角形。第 1 行 1 个字母，第 2 行 2 个字母，依此类推。字母从 A 到 Z 循环使用。
解题思路
用一个变量记录当前应该输出的字母编号。
每输出一个字符，编号加 1。
编号对 26 取模即可实现 A 到 Z 的循环。
C++ 代码
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
int x = 0,f = 1; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
int n;
inline void solve() {
cin >> n;
int Now = 0;
for
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
int x = 0,f = 1; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
int a, b;
bool ok(int y) {
return y % 400 == 0 || (y % 4 == 0 && y % 100 != 0);
}
inline void solve() {
cin >> a >> b;
int Ans = 0;
for (int y = a + 1; y <= b - 1; y++) {
if (ok(y)) Ans += y;
}
printf("%d\n", Ans);
}
int main() {
int _ = 1;
while (_--) solve();
return 0;
}
2. 当天的第几秒
题目大意
输入一个时刻的时、分、秒，以及字符 A 或 P。A 表示上午，P 表示下午。求这个时刻是当天的第几秒。
题解
把时、分、秒统一转成秒。
如果是下午 P，小时数要加 12。
答案为：
h×3600+m×60+s
代码
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
int x = 0,f = 1; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
int h, m, s;
char c;
inline void solve() {
cin >> h >> m >> s >> c;
if (c == 'P') h += 12;
printf("%d\n", (h * 3600 + m * 60 + s));
}
int main() {
int _ = 1;
while (_--) solve();
return 0;
}
3. 长方形面积
题目大意
给定长方形面积 A，求有多少种长和宽都是整数的长方形。要求长大于等于宽。
题解
如果 i 是面积 A 的因数，那么可以令宽为 i，长为 A/i。
由于要求长大于等于宽，只需要枚举 i 从 1 到 A。
如果 A%i==0，就找到一种。
代码
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
int x = 0,f = 1; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
int A;
inline void solve() {
cin >> A;
int Ans = 0;
for (int i = 1; i * i <= A; i++) {
if (A % i == 0) Ans++;
}
printf("%d\n", Ans);
}
int main() {
int _ = 1;
while (_--) solve();
return 0;
}
4. 每月天数
题目大意
输入年份和月份，输出这个月有多少天。
题解
普通月份天数固定。
二月需要判断闰年：
闰年二月 29 天，平年二月 28 天。
代码
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
int x = 0,f = 1; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
int y, m;
bool ok(int y) {
return y % 400 == 0 || (y % 4 == 0 && y % 100 != 0);
}
inline void solve() {
cin >> y >> m;
if (m == 2) {
if (ok(y)) printf("29\n");
else printf("28\n");
} else if (m == 1 || m == 3 || m == 5 || m == 7 || m == 8 || m == 10 || m == 12) {
printf("31\n");
} else {
printf("30\n");
}
}
int main() {
int _ = 1;
while (_--) solve();
return 0;
}
5. 时间规划
题目大意
输入开始时刻和结束时刻，求中间相差多少分钟。
题解
把两个时刻都转成 从当天 0 点开始经过的分钟数 。
然后用结束分钟数减去开始分钟数。
代码
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
int x = 0,f = 1; char ch = getchar();
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
bool f[100005];
void mkk() {
fill(f + 2, f + 100005, true);
for (int i = 2; i * i <= 100000; i++) {
if (f[i]) {
for (int j = i * i; j <= 100000; j += i) f[j] = false;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
mkk();
int t;
cin >> t;
while (t--) {
int h;
cin >> h;
int ans = 1e9;
for (int k = 0; k <= 17; k++) {
int p2 = 1 << k;
if (h + 1 == p2) {
ans = min(ans, k);
}
int x = h + 1 - p2;
if (x >= 2 && x <= h && f[x]) {
ans = min(ans, k + 1);
}
}
if (ans > 1e8) cout << -1 << "\n";
else cout << ans << "\n";
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
using i128 = __int128;
void put(i128 x) {
if(x == 0) {
cout << 0;
return;
}
if(x < 0) {
cout << '-';
x = -x;
}
string s;
while(x) {
s += char(x % 10 + '0');
x /= 10;
}
reverse(s.begin(), s.end());
cout << s;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long a, b;
cin >> a >> b;
i128 ans = (i128)a * b;
put(ans);
return 0;
}
如果输入：
1000000000000000000 1000000000
程序会输出：
1000000000000000000000000000
也就是：
1027
如果输入本身也可能超过 long long，就需要手写读入函数。
using i128 = __int128;
i128 read() {
string s;
cin >> s;
i128 x = 0;
int p = 0;
int f = 1;
if(s[0] == '-') {
f = -1;
p = 1;
}
for(int i = p; i < (int)s.size(); i++) {
x = x * 10 + s[i] - '0';
}
return x * f;
}
不过在大多数算法题里，通常只需要手写输出，不需要手写读入。
四、__int128 的常见使用场景
第一类场景是两个大数相乘。
比如：
a,b≤1018
如果要计算：
a×b
那么最大可能达到：
1036
这个结果一定会超过 long long。
即使最后要对某个数取模，中间乘法也可能先溢出。
例如：
long long a, b, mod;
cin >> a >> b >> mod;
long long ans = a * b % mod;
YIZHIYANG
司马只因锥
黑大帅