排位赛，好难啊！！！
2024-04-14 22:58:34
发布于：广东
61阅读
0回复
0点赞
排位赛太难了，做不出来，哪位大佬帮我指点一下
第一题：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 计算最大公约数
long long gcd(long long a, long long b) {
return b == 0 ? a : gcd(b, a % b);
}
// 计算线段 AB 上的格点数量
int countGridPoints(int x1, int y1, int x2, int y2) {
// 确保 x1 <= x2
if (x1 > x2) {
swap(x1, x2);
swap(y1, y2);
}
// 如果两个点相同，则只有一个格点
if (x1 == x2 && y1 == y2) return 1;
// 计算斜率
long long dx = x2 - x1;
long long dy = y2 - y1;
// 如果 dx 和 dy 都为 0，则没有格点
if (dx == 0 && dy == 0) return 0;
// 如果 dx 为 0，则检查 y 坐标是否为整数
if (dx == 0) {
for (int y = y1; y <= y2; y++) {
if (y == (long long)(y1 + dy * (y - y1) / dx)) return y2 - y1 + 1;
}
return 0;
}
// 如果 dy 为 0，则检查 x 坐标是否为整数
if (dy == 0) {
for (int x = x1; x <= x2; x++) {
if (x == (long long)(x1 + dx * (x - x1) / dy)) return x2 - x1 + 1;
}
return 0;
}
// 将斜率约分为整数
long long g = gcd(abs(dx), abs(dy));
dx /= g;
dy /= g;
// 检查每个 x 坐标对应的 y 坐标是否为整数
int count = 0;
for (int x = x1; x <= x2; x++) {
if ((long long)(x - x1) * dy % dx == 0) {
int y = y1 + (x - x1) * dy / dx;
if (y >= min(y1, y2) && y <= max(y1, y2)) count++;
}
}
return count;
}
int main() {
int T;
cin >> T;
while (T--) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << countGridPoints(x1, y1, x2, y2) << endl;
}
return 0;
}
第二题：
#include <iostream>
#include <vector>
using namespace std;
// 高精度整数加法
vector<int> add(vector<int>& a, vector<int>& b) {
vector<int> result(max(a.size(), b.size()) + 1, 0);
for (int i = 0; i < a.size(); i++) {
result[i] += a[i];
}
for (int i = 0; i < b.size(); i++) {
result[i] += b[i];
}
for (int i = 0; i < result.size() - 1; i++) {
if (result[i] >= 10) {
result[i + 1] += result[i] / 10;
result[i] %= 10;
}
}
while (result.size() > 1 && result.back() == 0) {
result.pop_back();
}
return result;
}
// 高精度整数乘法
vector<int> multiply(vector<int>& a, int b) {
vector<int> result(a.size() + 1, 0);
for (int i = 0; i < a.size(); i++) {
result[i] += a[i] * b;
}
for (int i = 0; i < result.size() - 1; i++) {
if (result[i] >= 10) {
result[i + 1] += result[i] / 10;
result[i] %= 10;
}
}
while (result.size() > 1 && result.back() == 0) {
result.pop_back();
}
return result;
}
// 高精度整数除法
vector<int> divide(vector<int>& a, int b, int& remainder) {
remainder = 0;
for (int i = a.size() - 1; i >= 0; i--) {
remainder = remainder * 10 + a[i];
a[i] = remainder / b;
remainder %= b;
}
while (a.size() > 1 && a.back() == 0) {
a.pop_back();
}
return a;
}
// 计算等差数列求和并对 M 取模
int sumModM(__int128 N, int M) {
__int128 sum = N * (N + 1) / 2 % M;
return sum;
}
int main() {
int T;
cin >> T;
while (T--) {
__int128 N;
int M;
cin >> N >> M;
cout << sumModM(N, M) << endl;
}
return 0;
}
后面懒得做
一直到第六题：
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 998244353;
int countIntegersWithKNonZeroDigits(int N, int K) {
int digits = 0;
int temp = N;
while (temp) {
digits++;
temp /= 10;
}
vector<vector<int>> dp(digits+1, vector<int>(K+1, 0));
dp[0][0] = 1;
for (int i = 1; i <= digits; i++) {
for (int j = 0; j <= K; j++) {
dp[i][j] = dp[i-1][j]; // 不放置非零数字的情况
if (j > 0) {
dp[i][j] = (dp[i][j] + dp[i-1][j-1] * 9) % MOD; // 放置非零数字的情况
}
}
}
temp = N;
for (int i = digits; i >= 1; i--) {
int digit = temp % 10;
temp /= 10;
for (int j = 0; j <= K; j++) {
if (j > 0 && digit > 0) {
dp[i-1][j] = (dp[i-1][j] + dp[i][j-1]) % MOD;
}
if (digit == 0) {
dp[i-1][j] = dp[i][j];
}
}
}
return dp[0][K];
}
int main() {
int T;
cin >> T;
while (T--) {
int N, K;
cin >> N >> K;
cout << countIntegersWithKNonZeroDigits(N, K) << endl;
}
return 0;
}
啊啊啊啊啊啊啊啊，太难了！我只是个四年级的xxs呀！！！
全部评论 9
四年级做成这个样子已经很不错了。第一题是数论，简单求一下gcd就行。第二道题是高精度取模。第三道题可以用dfs/bfs连通块染色来做。第四题比较难，要用折半搜索（我反正比赛的时候没用，（数据不强））。第五题位运算优化与。第六题数位dp。
2024-04-15 来自
0
有帮助，赞一个