题目
说明：点击题目名称即可跳转原题链接 🙂
Cantor 表
思路
- 找规律，根据题目编号的方式调整表格，分析发现，每一行中元素的分子、分母和为当前行号 + 1。
- 从左到右分子逐渐减小，分母逐渐增大。因此如果能够确定第 n 个元素在第几行第几个位置，就能确定这个元素。根据第 i 行有 i 个元素，通过循环累加每行元素的数量，就可以找到第 n 个元素具体所在行和列。
- 注意：由于数据呈 Z 字形排列，需要区分奇偶行数数的顺序，奇数行从左开始，偶数行从右开始。
代码
#include <bits/stdc++.h>
using namespace std;
int n;
int main(){
cin >> n;
int i = 1;
for(; n > i; i++){ // 确定所求是第 i 行第 n 个元素
n -= i;
}
if(i % 2){ // 奇数行：从左往右数，分母是 n
cout << i + 1 - n << "/" << n;
}
else{ // 偶数行：从右往左数，分子是 n
cout << n << "/" << i + 1 - n;
}
return 0;
}
回文数
思路
- 注意进制 N 可能是 16，因此输入 M 可能会带有字母，需要作为字符串输入并进行对应数字转换，将结果存放在数组 a[]。
- 对 a[] 进行扫描判断是否是回文数，只要还不是，就进行 N 进制下高精度 a[] 与反向 a[] 的加法，同时记录操作次数 + 1。
- 当操作次数超过 30 时，直接输出 “Impossible!” 并结束程序，否则若 30 次以内得到了回文数，输出操作次数。
代码
#include <bits/stdc++.h>
using namespace std;
int n, s, a[150], k;
string m;
bool ishw(int len){ // 判断是否是回文数
for(int i = 1; i <= len / 2; i++){
if(a[i] != a[1 + len - i]){ // 一旦发现有一对不等
return 0; // 返回不是
}
}
return 1; // 全都比对完，返回是
}
int add(int len){ // 更新 a[] 为加上反置数后的结果，返回更新后长度
int b[150] = {0};
for(int i = 1; i <= len; i++){
b[i] = b[i] + a[i] + a[len + 1 - i];
b[i + 1] = b[i] / n; // n 进制下进位
b[i] = b[i] % n;
}
if(b[len + 1]){ // 处理最高位进位的情况
len++;
}
for(int i = 1; i <= len; i++){
a[i] = b[i];
}
return len; // 返回加法操作后 a 数组长度
}
int main(){
cin >> n >> m;
for(int i = 0; m[i]; i++){ // 注意可能会是 16 进制
int t = m[i] >= 'A' ? m[i] - 'A' + 10 : m[i] - '0';
a[++k] = t;
}
while(!ishw(k)){
s++;
// 更新 a 为 N 进制下加上反置数的和
k = add(k); // 更新长度
if(s > 30){
cout << "Impossible!";
return 0;
}
}
cout << "STEP=" << s;
return 0;
}
旅行家的预算
思路
- 贪心策略，应该在尽可能便宜的站点加油。维护数组 a[i] 记录到第 i 个加油站点最便宜的站点，那么对于到达第 i 个站点所需的油量，是在 a[i – 1] 处实现的。
- 把终点设为第 n + 1 个站点，它的最优加油站点解同 a[n]，然后依次枚举每个站点的距离，计算相邻站点所需油量，超出油箱容量就是无解，没超出用 a[i-1] 站点进行到达第 i 个站点路程的加油，即用价格 p[a[i-1]] 计算d[i-1] ~ d[i] 的路程花费。
- 注意：如果仅按上述解法提交只能得 75 分，因为它假设了在左端最便宜站点加油的正确性，但除此之外还要考虑油箱容量的问题，有没有可能你想得很美，但最便宜的站点加油容量不够加到能到此处呢？（提示到这儿，剩下的自己想 :P）。
代码
#include <bits/stdc++.h>
using namespace std;
double d1, c, d2, d[10], p[10], b[10], ans, m;
int n, a[10]; // a[i] 记录到第 i 个站点最便宜的加油站
void add(int k, double x){ // 在站点 k 加 x 升油
b[k] += x;
ans += x * p[k];
}
int main(){
scanf("%lf %lf %lf %lf %d", &d1, &c, &d2, &p[0], &n);
for(int i = 1; i <= n; i++){
scanf("%lf %lf", &d[i], &p[i]);
a[i] = (p[i] < p[a[i-1]] ? i : a[i-1]);
}
d[n+1] = d1, a[n + 1] = a[n];
for(int i = 1; i <= n + 1; i++){
double t = (d[i] - d[i - 1]) / d2;
if(t > c){
printf("No Solution");
return 0;
}
int k = a[i - 1];
if(b[k] + t > c){ // 在左边最便宜的点加油容量不够
double x = c - b[k]; // 最多只能加 c-b[k]
add(k, x);
double r = (d[i] - d[i - 1] - x * d2) / d2; // 剩余要加的油量
int minl = i - 1; // 选左边最便宜且余量够的站点加剩余 r 升油
for(int j = i - 1; j >= 0; j--){
if(b[j] + r <= c && p[j] < p[minl]){
minl = j;
}
}
add(minl, r);
}
else{ // 在最便宜的站点加油容量够，直接加满 t
add(k, t);
}
}
printf("%.2lf", ans);
return 0;
}
代码2
来自我的学生，一个上海四年级的小朋友，很简洁，分享一下 😀
#include<bits/stdc++.h>
using namespace std;
double d1,c,d2,p,d[10],v[10],l,mi;
int n;
int main(){
cin>>d1>>c>>d2>>p>>n;
for(int i=1;i<=n;i++)cin>>d[i]>>v[i];
d[n+1]=d1;v[0]=p;
for(int i=1;i<=n;i++){
if(d[i+1]-d[i]>c*d2){
cout<<"No Solution";
return 0;
}
}
int j;
for(int i=0;i<=n;i=j){
for(j=i+1;j<=n+1;j++){
if(d[j]-d[i]>c*d2){
j--;
break;
}
if(v[j]<v[i])break;
}
if(v[j]<v[i])mi+=((d[j]-d[i])/d2-l)*v[i],l=0;
else mi+=(c-l)*v[i],l=c-(d[j]-d[i])/d2;
}
printf("%.2lf\n",mi);
return 0;
}