【codeforces之路】（简单的数学题）（6367字）（更新至2023.1.17）
目录
第一题：A. Divide and Conquer（通过操作使得数列和为偶数）
第二题：B. Make Array Good（构造数列使得两者之间必然可以整除）
第三题：A. Extremely Round（找规律）
第四题：通过操作使得数列的和最大（基本不等式+找规律）
第五题：在一个矩阵中找到和最大的路径（找规律求通项）
第六题：清点网格中矩形的数目
第七题：完全点亮（考虑相邻的）
第八题：填满01背包
第九题：简单的阶乘问题（打表）
第十题：排序（注意分类，注意溢出）
第十一题：排序（求周长最小）
第十二题：最短路径（分类讨论）
第十三题：调整数组使得两个数组相等
时间2022.12.16，rating:1186。
第一题：A. Divide and Conquer（通过操作使得数列和为偶数）
求使得数列和为偶数的最小操作次数，如果原来是偶数的话为0，如果是奇数的话，只需要找到最小的改变奇偶性的次数，由于数比较小可以直接暴力枚举解决。
实现：
#include
#define ll long long
using namespace std;
const int N = 55;
int a[N];
int main() {ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while (t--) {int n;cin >> n;int sum = 0;for (int i = 0; i < n; i++) {cin >> a[i];sum += a[i];}if (sum % 2 == 0) {cout << 0 << '\n';} else {int ans = 0x3f3f3f3f;for (int i = 0; i < n; i++) {int cnt = 0;if (a[i] & 1) {while (a[i] & 1) {a[i] >>= 1;cnt++;}} else {while (a[i] % 2 == 0) {a[i] >>= 1;cnt++;}}ans = min(ans, cnt);}cout << ans << '\n';}}return 0;
} 第二题：B. Make Array Good（构造数列使得两者之间必然可以整除）
这道题的目的是构造出一个数列，使得任取两个数其中较小的可以整除较大的，我们可以想到构造出一个2的等比数列，显然高次的可以被低次的整除。
对于任意的一个数可以写成1010010101010101的二进制数乘2 ->1010010101010101 + 0，两者之间必然闭区间，必然有1000000000000000 + 0 <= 1010010101010101 + 0 可以到达。
于是实现：
#include
#include
#define ll long long
using namespace std;
const int N = 1e5 + 5;
ll a[N];
int main() {ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while (t--) {int n;cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}cout << n << '\n';for (int i = 1; i <= n; i++) {cout << i << ' ' << (1 << __lg(a[i]) + 1) - a[i] << '\n';} }return 0;
} 第三题：A. Extremely Round（找规律）
找规律，1是特殊的，10有9个这样的数，100有9个这样的数，得实现。
#include
#define ll long long
#define inf 0x3f3f3f3f
//const int N =
using namespace std;
int main() {ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while (t--) {int n;cin >> n;if (n <= 10) {cout << n << '\n';continue;}int cnt = 0;while (n >= 10) {n /= 10;cnt++;}cout << cnt * 9 + n << '\n';}return 0;
} 第四题：通过操作使得数列的和最大（基本不等式+找规律）
，当xy取等时候x+y最小，当取到两侧极端值时最大，多次操作后恰好为连续积加若干个一，我的实现。
#include
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
//const int N =
int main() {ios::sync_with_stdio(false);cin.tie(0);int t = 1;cin >> t;while (t--) {int n;cin >> n;ll s = 1;for (int i = 0; i < n; i++) {ll c;cin >> c;s *= c;}cout << 2022 * (s + n - 1) << '\n';}return 0;
} 第五题：在一个矩阵中找到和最大的路径（找规律求通项）
可以由递推公式求得
累和求得，n=1的时候也符合，如果直接求的话注意不要越界，要多次取模
这里的精度会出现问题，要用乘法逆元而且注意减法的时候非负或者高精度，笔者用了java。
import java.math.BigInteger;
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner cin = new Scanner(System.in);int t = cin.nextInt();for (int i = 0; i < t; i++) {BigInteger a = cin.nextBigInteger();BigInteger ans = a.multiply(a.add(BigInteger.valueOf(1))).multiply(a.multiply(BigInteger.valueOf(2)).add(BigInteger.valueOf(1))).divide(BigInteger.valueOf(3)).subtract(a.multiply(a.add(BigInteger.valueOf(1l))).divide(BigInteger.valueOf(2)));System.out.println(ans.multiply(BigInteger.valueOf(2022)).mod(BigInteger.valueOf(1000000000 + 7)));}}
}此处用BigInteger.TWO会不给过，可能cf版本不太对。
第六题：清点网格中矩形的数目
众所周知，矩形有四条边，对于的网格，有
条竖线，
条横线，要构造出矩形秩序各选中两条即可，也就是
，如果要求出正方形，只需知道最左上方点（其他位置也可）的最大活动范围，由于正方形本身有长度所以要减去右下方一个L形的块，共有
个正方形，枚举完i即可。
#include
using namespace std;
long long M,N,x,y;
int main() {cin >> M >> N; x = ((M + 1) * M / 2) * ((N + 1) * N / 2);for (long long i = 1; i <= min(M, N); i++) {y += (M - i + 1) * (N - i + 1);}printf("%lld %lld", y, x - y);return 0;
} 第七题：完全点亮（考虑相邻的）
这题的题面有点长，需要耐心阅读，注意的是只能操作一次。
#include
using namespace std;
int main() {ios::sync_with_stdio(false);cin.tie(0);int t = 1;cin >> t;while (t--) {int n;cin >> n;string s;cin >> s;int flag = 0;for (int i = 0; i < n - 1; i++) {if (s[i] == 'L' && s[i + 1] == 'R') {cout << i + 1 << '\n';flag = 1;break;}if (s[i] == 'R' && s[i + 1] == 'L') {cout << 0 << '\n';flag = 1;break;}}if (!flag) cout << -1 << '\n';}return 0;
} 第八题：填满01背包
注意判断无法填满的是负数，而非等于-inf，另外-inf != memset(-0x3f)有一定的差距。
#include
#define inf 0x3f3f3f3f
using namespace std;
const int N = 105;
int a[N], dp[N];
int main() {ios::sync_with_stdio(false);cin.tie(0);int t = 1;cin >> t;while (t--) {int n;cin >> n;int sum = 0;for (int i = 0; i < n; i++) {cin >> a[i];sum += a[i];}if (sum % 2) {cout << "NO\n";continue;}for (int i = 0; i <= sum / 2; i++) dp[i] = -inf;dp[0] = 0;for (int i = 0; i < n; i++) {for (int j = sum / 2; j >= a[i]; j--) {dp[j] = max(dp[j], dp[j - a[i]] + a[i]); }}if (dp[sum / 2] < 0) cout << "NO\n";else {cout << "YES\n";}}return 0;
} 第九题：简单的阶乘问题（打表）
这道题要注意，如果n!>m的话余数为0.
#include
using namespace std;
const int N = 1e6 + 5;
int p;
long long a[N];
void get_a() {a[1] = 1;for (int i = 2; i <= p; i++) {a[i] = a[i - 1] * i;a[i] %= p;}
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t >> p;while (t--) {int n;cin >> n;long long sum = 1;int flag = 0;for (int i = 1; i <= n; i++) {sum *= i;if (sum > p) {flag = 1;break;}}if (flag) {cout << 0 << '\n';continue;}get_a();cout << a[sum] << '\n';}return 0;
} 第十题：排序（注意分类，注意溢出）
这里需要注意的是要先乘一个1ll来避免溢出，或者直接define int long long毒瘤写法，而且要分类，如果全部相等的话种类数是不一样的。
#include
#define ll long long
using namespace std;
const int N = 1e5 + 5;
int a[N];
void solve() {int n;cin >> n;for (int i = 0; i < n; i++) cin >> a[i];sort(a, a + n);if (a[0] == a[n - 1]) cout << 1ll * n * (n - 1) << '\n';else {int cntl = 0, cntr = 0;for (int i = 0; i < n; i++) {if (a[i] == a[0]) cntl++;if (a[i] == a[n - 1]) cntr++;}cout << 1ll * cntl * cntr * 2 << '\n';}
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int t = 1;cin >> t;while (t--) solve();return 0;
} 第十一题：排序（求周长最小）
总周长是不变的，我们要使得相邻重叠部分越大越好。
排序完之后相邻的数的差距是最小的，接近程度最大，在经过排序后相邻重叠最多，而且长度越大重叠越多，根据贪心的思想可以得出实现。
#include
#define ll long long
using namespace std;
void solve() {int n;cin >> n;vector > v;for (int i = 0; i < n; i++) {int a, b;cin >> a >> b;if (a < b) swap(a, b);v.push_back(make_pair(a, b));}sort(v.begin(), v.end());ll sum = 0;for (int i = 0; i < n; i++) {sum += 2LL * v[i].first + 2LL * v[i].second;if (i < n - 1) sum -= 2LL * v[i].first; }cout << sum << '\n';
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int t = 1;cin >> t;while (t--) solve();return 0;
} 第十二题：最短路径（分类讨论）
直接考虑四个方向模拟一下，感受到了tourist满满的恶意。
#include
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
void solve() {int w, d, h;cin >> w >> d >> h;int a, b, f, g;cin >> a >> b >> f >> g;cout << min(b + h + g + abs(a - f), min(f + h + a + abs(g - b), min(w - f + h + w - a + abs(g - b), d - g + h + d - b + abs(a - f)))) << '\n';
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int t = 1;cin >> t;while (t--) solve();return 0;
} 第十三题：调整数组使得两个数组相等
注意调整的是a数组，有两种操作。如果两个数组1的数目相等的话，直接排序即可1次，如果不相等的话有两种情况，一种是先使得数目相等再排序，另一种是直接让对应差异消除。
1 1 0
1 1 1只需1次，不必相等再排序，
0 1 0 0
1 0 0 0只需1次，只需排序，
0 0 1 1 0
1 1 1 0 0
如果都是一种的
1
0
或
0
1
就只需差值抹除即可，不必排序。
如果同时都有的话，数目重复改变了，不如排序。
实现
#include
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int N = 105;
int a[N], b[N];
void solve() {int n;cin >> n;int sum1 = 0, sum2 = 0, cnt = 0;for (int i = 0; i < n; i++) {cin >> a[i];sum1 += a[i]; }for (int i = 0; i < n; i++) {cin >> b[i];if (a[i] != b[i]) cnt++;sum2 += b[i]; }cout << min(abs(sum1 - sum2) + 1, cnt) << '\n';
}
int main() {ios::sync_with_stdio(false);cin.tie(0);int t = 1;cin >> t;while (t--) solve();return 0;
} 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！