准备放弃一段时间算法。
西农2022级ACM招新上周结束了，五一假期研究了一下题解，整理发在博客。
1. 这真的是签到题
print("\"ACM welcomes you\\n\"")
2. 4和数
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int f[maxn + 1];
int l, r;
bool check(int num)
{
int sum = 0;
while (num)
{
sum += num % 10;
num /= 10;
}
if (sum % 4 == 0)
return true;
else
return false;
}
int main()
{
scanf("%d%d", &l, &r);
for (int i = 4; i <= maxn; i += 4)
{
// 4和数必是4的倍数，缩小范围
if (check(i))
{
// 如果是4和数，标记为1
f[i] = 1;
}
}
for (int i = 4; i <= maxn; i++)
{
// 求前缀和
f[i] += f[i - 1];
}
printf("%d\n", f[r] - f[l - 1]);
return 0;
}
3. 小D买文具
#include <bits/stdc++.h>
#define maxn 50000
using namespace std;
int n, a, b, c, ans[3];
int m = -1;
int min(int a, int b, int c)
{
int t;
if (b > a)
{
t = a;
a = b;
b = t;
}
if (c > b)
{
t = b;
b = c;
c = t;
}
if (b > a)
{
t = a;
a = b;
b = t;
}
return c;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i * 5 <= n; i++)
{
for (int j = 0; j * 3 <= n - i * 5; j++)
{
// 枚举圆规和签字笔，剩余的钱全买稿纸
if ((n - i * 5 - j * 3) % 2 == 0)
{
int k = (n - i * 5 - j * 3) / 2;
// 如果钱刚好花完
if (m < min(i, j, k))
{
// 成套的数量尽可能大
a = i;
b = j;
c = k;
m = min(i, j, k);
}
else if (m == min(i, j, k))
{
if (i + j + k > a + b + c)
{
// 在满足以上条件情况下，物品的总数尽可能大，即a+b+c尽可能大。
a = i;
b = j;
c = k;
}
}
}
}
}
printf("%d %d %d", a, b, c);
return 0;
}
4. 大阳分大洋
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6;
int n, x, ans;
int f[maxn]; // 前缀和数组
int get(int l, int r)
{
// 获取l到r之间有多少大洋
return f[r] - f[l - 1];
}
signed main()
{
scanf("%lld", &n);
for (int i = 1; i <= n; i++)
{
scanf("%lld", &x);
f[i] = f[i - 1] + x; // 求前缀和
}
for (int i = 1; i < n; i++)
{
// i<n，如果i=n，i+1就大于n了
if (get(1, i) == get(i + 1, n))
{
ans++;
}
}
printf("%d\n", ans);
}
5. 汉诺塔
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
typedef long long ll;
int quickpow(ll a, ll b, ll p = mod)
{
int ans = 1;
while (b)
{
if (b & 1)
ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans;
}
int main()
{
int n;
scanf("%d", &n);
ll ans = quickpow(2, n) - 1;
printf("%d\n", ans);
return 0;
}
6. 突击考试
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
int N, K, L = -1;
int A[maxn + 1], B[maxn + 1];
int main()
{
cin >> N;
for (int i = 1; i <= N; i++)
{
cin >> A[i] >> B[i];
}
for (int i = 1; i <= 5; i++)
{
int sum = 0;
for (int j = 1; j <= N; j++)
{
if (i == A[j] || i == B[j])
{
sum++;
}
else
{
if (L < sum)
{
L = sum;
K = i;
}
sum = 0;
}
if (L < sum)
{
L = sum;
K = i;
}
}
}
cout << L << " " << K << endl;
return 0;
}
7. 小华的立方数
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll getAns(ll k)
{
ll l = -1;
ll r = 1e6 + 1;
while (l < r)
{
ll mid = (l + r + 1) / 2;
if (mid * mid * mid <= k)
{
l = mid;
}
else if (mid * mid * mid > k)
{
r = mid - 1;
}
}
return l;
}
int main()
{
ll n;
cin >> n;
while (n--)
{
ll L, R;
scanf("%lld%lld", &L, &R);
ll a = getAns(L - 1);
ll b = getAns(R);
ll ans = b - a;
printf("%lld\n", ans);
}
return 0;
}
8. 小华的幸福
!> 这道题我只能过70%
#include <bits/stdc++.h>
#define mod 1000000007
#define int long long
typedef long long ll;
using namespace std;
const int maxn = 1e6;
int n, k;
int a[maxn];
int quickpow(int a, int b)
{
int ans = 1;
while (b)
{
if (b & 1)
{
ans = a * ans % mod;
}
a = a * a % mod;
b >>= 1;
}
return ans;
}
signed main()
{
scanf("%lld%lld", &n, &k);
int fm = ((n - 1) * n) / 2;
int fz = 0;
for (int i = 1; i <= n; i++)
{
scanf("%lld", &a[i]);
}
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
if (a[i] + a[j] == k)
{
fz++;
}
}
}
int ans = quickpow(fm, mod - 2) * fz % mod;
printf("%lld\n", ans);
return 0;
}
9. 元素周期表
!> 抄的题解，我读不懂题
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e3 + 10;
char s[1010][10] =
{"1s", "2s", "2p", "3s", "3p", "4s", "3d", "4p", "5s", "4d", "5p", "6s", "4f", "5d", "6p", "7s", "5f", "6d", "7p"};
// s数组优先处理出排列顺序
struct Node
{
char s[10];
int cnt;
} a[N];
// 结构体存放每层元素和所具有的原子个数
char st[5] = {'s', 'p', 'd', 'f'}; // 用于对spdf的排序处理
bool cmp(Node x, Node y)
{
if (x.s[0] != y.s[0])
return x.s[0] < y.s[0];
return x.s[1] < y.s[1];
} // 排序规则函数
int main()
{
int t;
cin >> t;
while (t--)
{
int n, idx = 0;
cin >> n;
for (int i = 0; i < 19; i++)
{
a[i].s[0] = s[i][0];
a[i].s[1] = s[i][1];
a[i].cnt = 0;
} // 因为有多组测试用例，初始化结构体
while (n)
{ // 模拟电子排列顺序
if (a[idx].s[1] == 's')
{
if (n >= 2)
{
a[idx].cnt = 2;
n -= 2;
}
else
{
a[idx].cnt = n;
n = 0;
}
}
else if (a[idx].s[1] == 'p')
{
if (n >= 6)
{
a[idx].cnt = 6;
n -= 6;
}
else
{
a[idx].cnt = n;
n = 0;
}
}
else if (a[idx].s[1] == 'd')
{
if (n >= 10)
{
a[idx].cnt = 10;
n -= 10;
}
else
{
a[idx].cnt = n;
n = 0;
}
}
else if (a[idx].s[1] == 'f')
{
if (n >= 14)
{
a[idx].cnt += 14;
n -= 14;
}
else
{
a[idx].cnt = n;
n = 0;
}
}
idx++; // 逐层填充电子，充当指针作用
}
sort(a, a + idx, cmp); // 排序
for (int i = 0; i < idx; i++)
{
if (a[i].cnt == 0)
continue;
if (i != 0)
cout << " ";
cout << a[i].s[0] << a[i].s[1] << a[i].cnt;
// 处理输出和格式问题
}
cout << endl;
}
return 0;
}
10. 剑刃风暴
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e6 + 5;
struct node
{
int h; // 血量
int k; // 亡语数量
} a[maxn];
bool cmp(node x, node y) // 以血量从小到大排序
{
return x.h < y.h;
}
int idx;
int main()
{
int n, x;
cin >> n >> x;
for (int i = 1; i <= n; i++)
{
int A, k;
cin >> A >> k;
a[++idx] = {A, k};
for (int j = 1; j <= k; j++)
{
// 因为亡语随从需要等A死后才会收到伤害
// 所以将亡语所从的血量设置为A+B
int B;
cin >> B;
a[++idx] = {A + B, 0};
}
}
// 按血量排序
sort(a + 1, a + 1 + idx, cmp);
// 答案初始化为n
int ans = n;
// 开始遍历扣血
for (int i = 1; i <= idx; i++)
{
if (a[i].h != a[i - 1].h) // 如果i和i-1的血量不同，则更新答案
{
// 如果剑刃风暴用完了，则不更新答案
if (x == 0)
break;
x--;
}
// 每次更新答案 + 亡语随从 - 1（死亡随从）
ans = ans + a[i].k - 1;
}
// 输出答案
cout << ans;
}