#68. 「NOIP2004」津津的储蓄计划 题解
题目传送门
欢迎大家指出错误并联系这个蒟蒻
更新日志
- 2023-02-01 17:20 文章完成
- 2023-02-03 16:09 文章审核通过
- 2023-02-04 22:15 修改了注释
- 2023-05-27 09:27 修改了 $\LaTeX$
- 2023-07-01 15:45 修改了代码
题目知识点
模拟
题目分析
非常的“明显”，这是一道模拟题。
题意说明
有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱(津津可以随时把整百的钱存在她那里，到了年末她会加上 20％ 还给津津)，不够这个月的原定预算(每个月的月初，在得 到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于 $100$ 元或恰好 $100$ 元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中)，判断会不会出现这种情况。如果不会，计算到 $2004$ 年年末，妈妈将津津平常存的钱加上 20％ 还给津津之后，津津手中会有多少钱。（存钱是个好习惯）
代码+解释
// #68. 「NOIP2004」津津的储蓄计划
// code by:st20250113
#include <bits/stdc++.h> //伟大的万能头文件
using namespace std;
int a[12], moneyma = 0, moneyjin = 0; // moneyma表示现在存在妈妈那里的钱，moneyjin表示津津手里的钱，要记得先清零
int main() {
for (int i = 0; i <= 11; i++) {
cin >> a[i]; // 输入每个月的预算
}
for (int i = 0; i <= 11; i++) {
moneyma = ((moneyjin + 300 - a[i]) / 100) * 100 + moneyma; // 计算存在妈妈的钱
moneyjin = (moneyjin + 300 - a[i]) - (moneyjin + 300 - a[i]) / 100 * 100; // 计算手里的钱
if (moneyjin < 0) { // 考虑到不够用的情况
cout << "-" << i + 1;
return 0;
}
}
// 防抄袭
cout << moneyma * 1.2 + moneyjin << endl; // 按要求计算并输出
return 0; // 华丽结束
}
// QYC最帅
#105. 「USACO1.3」Ski Course Design 题解
题目传送门
欢迎大家指出错误并联系这个蒟蒻
更新日志
- 2023-02-01 17:20 文章完成
- 2023-02-03 16:09 文章审核通过
- 2023-02-04 22:15 修改了注释
- 2023-05-16 21:44 修改了 $\LaTeX$
- 2023-07-01 15:59 修改了代码
题目知识点
模拟+搜索+枚举
题意说明
$N$ 座山峰( $1\le N \le1000$ ),每座山都有一个在 $0$ 到 $100$ 之间的整数的海拔高度。如果滑雪训练营的最高和最低的山峰海拔高度差大于17就要收税。如果他改变山峰的高度（使最高与最低的山峰海拔高度差不超过 $17$ ）,约翰可以避免支付税收。 （偷税漏税+愚公移山？）
如果改变一座山 $x$ 单位的高度成本是 $x^2$ 单位,求约翰最少需要付多少钱。
代码+解释
// #105. 「USACO1.3」Ski Course Design
// code by:st20250113
#include <bits/stdc++.h> //伟大的万能头文件
using namespace std;
int a[1005]; // 用来存山峰的高度
int n; // 共有n座山峰
int ans = 1e9; // 存大一点，以防万一
int main() {
cin >> n;
for (int i = 0; i < n; i++) { // 这步不用解释了，凡是学过数组的人都知道
cin >> a[i];
}
for (int low = 0; low + 17 <= 100; low++) { // low+17<=100指枚举山峰的最低高度，最低高度+17不能大于100
int high = low + 17; // 最高高度不用枚举，直接加17就可以了。因为要用到最高高度，所以前面最低高度+17必须小于等于100
int sum = 0; // sum用来存费用和。
for (int i = 0; i < n; i++) { // 记得还要枚举一遍a数组
if (a[i] < low) { // 如果太小时的情况
sum += (low - a[i]) * (low - a[i]); // 增加到最低高度，因为这样花费最少
}
if (a[i] > high) { // 如果太大时的情况
sum += (a[i] - high) * (a[i] - high); // 减少到最高高度，因为这样花费最少
}
}
if (sum < ans) { // 如果现在的花费比原先的最小花费还小
ans = sum; // 答案要的是最小花费,所以我们需要不断的更新
}
}
cout << ans << endl;
return 0; // 华丽结束
}
// QYC最帅
#119. 最大整数 题解
题目传送门
更新日志
- 2023-05-26 17:20 文章完成
- 2023-05-30 15:22 文章审核通过
- 2023-07-01 16:04 修改了代码
题目知识点
字符串+贪心
题意说明
设有n个正整数（$n<20$），将它们连接成一排，组成一个最大的多位整数。（题目简介明了，一看就是出题人懒得写题目背景）
问题分析
拿到这道题，首先自然会想到大的字符串应该排在前面，因为如果A与B是两个由数字字符构成的字符串，且 $A>B$ ，一般情况下有 $A+B$$<$$B+A$ 的情况。如 $A=$ ' $121$ ', $B=$ ' $12$ ',则 $A+B=$ ' $12112$ ', $B+A=$' $12121$ ',所以 $A+B$$<$$B+A$ 。
为了解决这些问题，根据题意引进另一种字符串比较方法，将 $A+B$ 与 $B+A$ 相比较，如果前者大于后者，则认为 $A>B$ 。按这一定义将所有的数字字符串从大到小排序后连接起来所得到的数字字符串即是这个问题的解。排序时先将所有字符串中的最大值选出来存在数组的第一个元素中，再从第二到最后的一个元素中最大的字符串选出来存在第二个元素中，直到最后的两个元素中选出最大的字符串存在数组的倒数第二个元素为止。
代码+解释
// #119. 最大整数
// code by:st20250113
#include <bits/stdc++.h> //伟大的万能头文件
using namespace std;
int n;
struct num {
int a, b;
} c[21];
int a(int x, int y) // x^y
{
if (y == 0) {
return 1;
}
if (y == 1) {
return x;
}
int z;
z = a(x, y / 2); // 这里可以和上面合并写作：int z=a(x,y/2);
if (y % 2 == 1) {
return z * z * x;
} else {
return z * z;
}
}
bool abc(num x, num y) {
int w, p;
w = x.a * y.b + y.a;
p = y.a * x.b + x.a;
return w > p;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> c[i].a;
c[i].b = 0;
int x;
x = c[i].a; // 这里可以和上面合并写作：int x=c[i].a;
while (x) {
x /= 10;
c[i].b++;
}
c[i].b = a(10, c[i].b);
}
sort(c + 1, c + n + 1, abc);
for (int i = 1; i <= n; i++) {
cout << c[i].a;
}
return 0; // 华丽结束
}
//QYC最帅
欢迎大家指出错误
#373. 「USACO1.1」Friday the Thirteenth 题解
题目传送门
欢迎大家指出错误并联系这个蒟蒻
更新日志
- 2023-02-01 17:20 文章完成
- 2023-02-03 18:50 文章审核通过
- 2023-02-03 19:17 修改了注释
- 2023-05-25 20:25 修改了 $\LaTeX$
- 2023-05-25 20:32 再次修改了 $\LaTeX$，感谢 ACRUSHj 提出错误
- 2023-07-01 15:55 修改了代码
题目知识点
模拟+数学
闰年知识点
题意说明
写一个程序来计算在 $n$ 年里 $13$ 日落在星期一,星期二......星期日的次数。这个测试从 $1900$ 年 $1$ 月 $1$ 日到 $1900+n-1$ 年 $12$ 月 $31$ 日.n是一个非负数且不大于 $400$ 。请不要预先算好数据 !
很明显，这道题会考察到和年份有关的知识点（已在知识点中列出，欢迎查阅），但是总结一下就是四年一闰，百年不闰，四百年又闰。（不会的话去问小学老师）
代码+解释
// #373. 「USACO1.1」Friday the Thirteenth
// code by:st20250113
#include <bits/stdc++.h> //伟大的万能头文件
using namespace std;
int a[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }, b[8]; // a数组预处理每月天数，b数组用来存储答案
int n, c = 0;
int main() {
cin >> n;
for (int i = 1900; i < 1900 + n; i++) {
int f = 0; // 闰年标记
if ((i % 4 == 0) && (i % 100) || (i % 400 == 0)) {
f = 1; // 判断是否为闰年，若成立则f赋值为真
}
for (int j = 1; j <= 12; j++) {
int e = 0; // 如果为闰年，2月就要多一天，e在闰年情况下使2月的循环变量增大1
if (f && j == 2)
e = 1;
for (int k = 1; k <= a[j] + e; k++) { // k循环日期，m[j]即j月的天数
c++; // st每天增加
if (k == 13) {
b[c % 7]++;
}
}
// 防抄袭
if (e == 1) {
e = 0; // 2月用过后要清零
}
}
}
cout << b[6] << " " << b[0] << " " << b[1] << " " << b[2] << " " << b[3] << " " << b[4] << " " << b[5]; // 输出顺序是Sat Sun Mon Tue Wed Thu Fri
return 0; // 华丽结束
}
// QYC最帅