liuchuo – 第28页 – 我不管，反正我最萌～

蓝桥杯 ALGO-46 算法训练 Hanoi问题

问题描述
如果将课本上的Hanoi塔问题稍做修改：仍然是给定N只盘子，3根柱子，但是允许每次最多移动相邻的M只盘子（当然移动盘子的数目也可以小于M）,最少需要多少次？
例如N=5，M=2时，可以分别将最小的2个盘子、中间的2个盘子以及最大的一个盘子分别看作一个整体，这样可以转变为N=3，M=1的情况，共需要移动7次。
输入格式
输入数据仅有一行，包括两个数N和M（0<=M<=N<=8）
输出格式
仅输出一个数，表示需要移动的最少次数
样例输入
5 2
样例输出
7

分析：数学问题，递归得出公式f(n) = 2f(n)+1，然后通过数学推算得通项公式为 f(n) = 2^n-1

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int n, m, ans = 0;
    cin >> n >> m;
    if (n % m == 0) n /= m;
    else n = n / m + 1;
    cout << (int) pow(2, n) - 1;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n, m, ans = 0;

cin >> n >> m;

if (n % m == 0) n /= m;

else n = n / m + 1;

cout << (int) pow(2, n) - 1;

return 0;

}

蓝桥杯 ADV-18 算法提高实数相加

问题描述
计算两个实数相加的结果。
输入的实数满足如下要求: (1) 小数点前的整数部分最多100位，(2) 小数点后的小数部分最多100位.
输入格式
两行字符串，每行都是一个合法的实数。合法的意思是指:　　整数部分的值如果大于零,则最高位数字必定大于零. 如果整数部分的值为零,则整数部分只有一个零. 小数部分尾部可以有任意多的零. 可以没有小数部分,　　此时也没有小数点. 如果有小数点, 则至少需要有一位小数部分, 且允许是零.
输出格式
相加结果。注意: 小数部分末尾如果有连续的0, 则它们都是有效数字,　　不能舍去. 如果是两个整数相加, 则结果仍为整数而没有小数部分.
样例输入
样例一:
0.0000000000000000000000000000000000000111111111000000000000000000
100000000000000000000000000000000000000000000000000000.0
样例二:
3
4
样例三:
3.9
2
样例四：
1.001
8.99999999999999999999999
样例输出
样例一：
100000000000000000000000000000000000000000000000000000.0000000000000000000000000000000000000111111111000000000000000000
样例二：
7
样例三:
5.9
样例四：
10.00099999999999999999999

分析：1.高精度模拟竖式加法，整数部分相加，小数部分相加
2.整数部分，位数不够，前面补0；小数部分位数不够，后面补0
3.小数部分如果有进位，要截下来加到整数上去～

#include <iostream>
#include <string>
using namespace std;
string add1(string s1, string s2) {
    int len1 = s1.length(), len2 = s2.length();
    if (len1 < len2) {
        string t(len2 - len1, '0');
        s1 = t + s1;
    } else if (len2 < len1) {
        string t(len1 - len2, '0');
        s2 = t + s2;
    }
    string ans = s1;
    int car = 0;
    for (int i = s1.length() - 1; i >= 0; i--) {
        ans[i] = (s1[i] - '0' + s2[i] - '0' + car) % 10 + '0';
        car = (s1[i] - '0' + s2[i] - '0' + car) / 10;
    }
    if (car) ans = (char) (car + '0') + ans;
    return ans;
}
string add2(string s1, string s2) {
    int len1 = s1.length(), len2 = s2.length();
    if (len1 < len2) {
        string t(len2 - len1, '0');
        s1 = s1 + t;
    } else if (len2 < len1) {
        string t(len1 - len2, '0');
        s2 = s2 + t;
    }
    string ans = s1;
    int car = 0;
    for (int i = s1.length() - 1; i >= 0; i--) {
        ans[i] = (s1[i] - '0' + s2[i] - '0' + car) % 10 + '0';
        car = (s1[i] - '0' + s2[i] - '0' + car) / 10;
    }
    if (car) ans = (char) (car + '0') + ans;
    return ans;
}
int main() {
    string a, b;
    while (cin >> a >> b) {
        string a1, a2, b1, b2;
        int i, j;
        for (i = 0; i < a.length() && a[i] != '.'; i++);
        for (j = 0; j < b.length() && b[j] != '.'; j++);
        a1 = a.substr(0, i);
        b1 = b.substr(0, j);

        if (i == a.length()) a2 = "";
        else a2 = a.substr(i + 1, a.length() - i - 1);
        if (j == b.length())b2 = "";
        else b2 = b.substr(j + 1, b.length() - j - 1);

        string ans1 = add1(a1, b1);
        string ans2 = add2(a2, b2);

        if (ans2.length() > max(a2.length(), b2.length())) {
            ans2 = ans2.substr(1, ans2.length() - 1);
            ans1 = add1(ans1, "1");
        }
        if (ans2.length() > 0) ans2 = "." + ans2;
        cout << ans1 << ans2 << endl;
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

string add1(string s1, string s2) {

int len1 = s1.length(), len2 = s2.length();

if (len1 < len2) {

string t(len2 - len1, '0');

s1 = t + s1;

} else if (len2 < len1) {

string t(len1 - len2, '0');

s2 = t + s2;

}

string ans = s1;

int car = 0;

for (int i = s1.length() - 1; i >= 0; i--) {

ans[i] = (s1[i] - '0' + s2[i] - '0' + car) % 10 + '0';

car = (s1[i] - '0' + s2[i] - '0' + car) / 10;

}

if (car) ans = (char) (car + '0') + ans;

return ans;

}

string add2(string s1, string s2) {

int len1 = s1.length(), len2 = s2.length();

if (len1 < len2) {

string t(len2 - len1, '0');

s1 = s1 + t;

} else if (len2 < len1) {

string t(len1 - len2, '0');

s2 = s2 + t;

}

string ans = s1;

int car = 0;

for (int i = s1.length() - 1; i >= 0; i--) {

ans[i] = (s1[i] - '0' + s2[i] - '0' + car) % 10 + '0';

car = (s1[i] - '0' + s2[i] - '0' + car) / 10;

}

if (car) ans = (char) (car + '0') + ans;

return ans;

}

int main() {

string a, b;

while (cin >> a >> b) {

string a1, a2, b1, b2;

int i, j;

for (i = 0; i < a.length() && a[i] != '.'; i++);

for (j = 0; j < b.length() && b[j] != '.'; j++);

a1 = a.substr(0, i);

b1 = b.substr(0, j);

if (i == a.length()) a2 = "";

else a2 = a.substr(i + 1, a.length() - i - 1);

if (j == b.length())b2 = "";

else b2 = b.substr(j + 1, b.length() - j - 1);

string ans1 = add1(a1, b1);

string ans2 = add2(a2, b2);

if (ans2.length() > max(a2.length(), b2.length())) {

ans2 = ans2.substr(1, ans2.length() - 1);

ans1 = add1(ans1, "1");

}

if (ans2.length() > 0) ans2 = "." + ans2;

cout << ans1 << ans2 << endl;

}

return 0;

}

蓝桥杯 PREV-37 历届试题分巧克力

问题描述
儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。
为了公平起见，小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足：
1. 形状是正方形，边长是整数
2. 大小相同

例如一块6×5的巧克力可以切出6块2×2的巧克力或者2块3×3的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小Hi计算出最大的边长是多少么？
输入格式
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)
输入保证每位小朋友至少能获得一块1×1的巧克力。
输出格式
输出切出的正方形巧克力最大可能的边长。
样例输入
2 10
6 5
5 6
样例输出
2
数据规模和约定
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。

提交程序时，注意选择所期望的语言类型和编译器类型。

分析：枚举巧克力边长，暴力搜索会超出时，用二分搜索～

#include <iostream>
#include <vector>
#include <utility>
using namespace std;
vector<pair<int, int> > v;
int n, k, l = 1, r = 99999999;
int check(int a) {
    int res = 0;
    for (int j = 0; j < n; j++) {
        res += (v[j].first / a) * (v[j].second / a);
        if (res >= k) break;
    }
    return res - k;
}
int main() {
    scanf("%d%d", &n, &k);
    v.resize(n);
    for (int i = 0; i < n; i++)
        scanf("%d%d", &v[i].first, &v[i].second);
    while (l <= r) {
        int mid = (r + l) / 2;
        if (check(mid) >= 0 && check(mid + 1) < 0) {
            cout << mid << endl;
            return 0;
        } else if (check(mid) < 0) {
            r = mid - 1;
        } else if (check(mid) >= 0) {
            l = mid + 1;
        }
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <utility>

using namespace std;

vector<pair<int, int> > v;

int n, k, l = 1, r = 99999999;

int check(int a) {

int res = 0;

for (int j = 0; j < n; j++) {

res += (v[j].first / a) * (v[j].second / a);

if (res >= k) break;

}

return res - k;

}

int main() {

scanf("%d%d", &n, &k);

v.resize(n);

for (int i = 0; i < n; i++)

scanf("%d%d", &v[i].first, &v[i].second);

while (l <= r) {

int mid = (r + l) / 2;

if (check(mid) >= 0 && check(mid + 1) < 0) {

cout << mid << endl;

return 0;

} else if (check(mid) < 0) {

r = mid - 1;

} else if (check(mid) >= 0) {

l = mid + 1;

}

return 0;

}

蓝桥杯 PREV-6 历届试题翻硬币

问题描述
小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。
比如，可能情形是：**oo***oooo
如果同时翻转左边的两个硬币，则变为：oooo***oooo
现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？
我们约定：把翻动相邻的两个硬币叫做一步操作，那么要求：
输入格式
两行等长的字符串，分别表示初始状态和要达到的目标状态。每行的长度<1000
输出格式
一个整数，表示最小操作步数。
样例输入1
**********
o****o****
样例输出1
5
样例输入2
*o**o***o***
*o***o**o***
样例输出2
1

分析：贪心，从前往后，如果发现当前硬币和目标硬币不一样，则同时翻转这枚硬币和下一枚硬币～

#include <iostream>
#include <string>
using namespace std;
int main() {
    int cnt = 0;
    string s1, s2;
    cin >> s1 >> s2;
    for (int i = 0; i < s1.length(); i++) {
        if (s1[i] != s2[i]) {
            if (s1[i] == 'o') s1[i] = '*';
            else s1[i] = 'o';
            if (s1[i + 1] == 'o') s1[i + 1] = '*';
            else s1[i + 1] = 'o';
            cnt++;
        }
    }
    cout << cnt;
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

int cnt = 0;

string s1, s2;

cin >> s1 >> s2;

for (int i = 0; i < s1.length(); i++) {

if (s1[i] != s2[i]) {

if (s1[i] == 'o') s1[i] = '*';

else s1[i] = 'o';

if (s1[i + 1] == 'o') s1[i + 1] = '*';

else s1[i + 1] = 'o';

cnt++;

}

cout << cnt;

return 0;

}

蓝桥杯 ALGO-47 算法训练蜜蜂飞舞

问题描述
“两只小蜜蜂呀，飞在花丛中呀……”
话说这天天上飞舞着两只蜜蜂，它们在跳一种奇怪的舞蹈。用一个空间直角坐标系来描述这个世界，那么这两只蜜蜂初始坐标分别为(x1,y1,z1)，(x2,y2,z2)　　。在接下来它们将进行n次飞行，第i次飞行两只蜜蜂分别按照各自的速度向量飞行ti个单位时间。对于这一现象，玮玮已经观察了很久。他很想知道在蜜蜂飞舞结束时，两只蜜蜂的距离是多少。现在他就求教于你，请你写一个程序来帮他计算这个结果。
输入格式
第一行有且仅有一个整数n，表示两只蜜蜂将进行n次飞行。
接下来有n行。
第i行有7个用空格分隔开的整数ai,bi,ci,di,ei,fi,ti　　，表示第一只蜜蜂单位时间的速度向量为(ai,bi,ci) ，第二只蜜蜂单位时间的速度向量为(di,ei,fi) ，它们飞行的时间为ti 。
最后一行有6个用空格分隔开的整数x1,y1,z1,x2,y2,z2，如题所示表示两只蜜蜂的初始坐标。
输出格式
输出仅包含一行，表示最后两只蜜蜂之间的距离。保留4位小数位。
样例输入
Sample 1
1
1 1 1 1 -1 1 2
3 0 1 2 0 0
Sample 2
3
1 1 1 1 -1 1 2
2 1 2 0 -1 -1 2
2 0 0 -1 1 1 3
3 0 1 2 0 0
样例输出
Sample 1
4.2426
Sample 2
15.3948

分析：1.全排列公式，每次排列后检查即可检查
2.题目说的后面，是紧跟着后面，中间隔着一个在后面不算的～

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int n, x1 = 0, y1 = 0, z1 = 0, x2 = 0, y2 = 0, z2 = 0;
    cin >> n;
    for (int i = 0; i <= n; i++) {
        int tx1, ty1, tz1, tx2, ty2, tz2, t;
        cin >> tx1 >> ty1 >> tz1 >> tx2 >> ty2 >> tz2;
        if (i == n) t = 1;
        else cin >> t;
        x1 += tx1 * t;
        y1 += ty1 * t;
        z1 += tz1 * t;
        x2 += tx2 * t;
        y2 += ty2 * t;
        z2 += tz2 * t;
    }
    double ans = sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) + (z2 - z1) * (z2 - z1));
    printf("%.4f", ans);
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n, x1 = 0, y1 = 0, z1 = 0, x2 = 0, y2 = 0, z2 = 0;

cin >> n;

for (int i = 0; i <= n; i++) {

int tx1, ty1, tz1, tx2, ty2, tz2, t;

cin >> tx1 >> ty1 >> tz1 >> tx2 >> ty2 >> tz2;

if (i == n) t = 1;

else cin >> t;

x1 += tx1 * t;

y1 += ty1 * t;

z1 += tz1 * t;

x2 += tx2 * t;

y2 += ty2 * t;

z2 += tz2 * t;

}

double ans = sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) + (z2 - z1) * (z2 - z1));

printf("%.4f", ans);

return 0;

}

蓝桥杯 ADV-21 算法提高多项式输出

问题描述
一元n 次多项式可用如下的表达式表示：
f(x)=a[n]x^n+a[n-1]x^(n-1)+…+a[1]x+a[0], a[n]!=0
其中，a[i]x^i称为i 次项， a[i]称为i 次项的系数。给出一个一元多项式各项的次数和系数，请按照如下规定的格式要求输出该多项式：
1. 多项式中自变量为x，从左到右按照次数递减顺序给出多项式。
2. 多项式中只包含系数不为0 的项。
3. 如果多项式n 次项系数为正，则多项式开头不出现“+”号，如果多项式n 次项系数为负，则多项式以“-”号开头。
4. 对于不是最高次的项，以“+”号或者“-”号连接此项与前一项，分别表示此项系数为正或者系数为负。紧跟一个正整数，表示此项系数的绝对值（如果一个高于0 次的项，其系数的绝对值为1，则无需输出1）。如果x 的指数大于1，则接下来紧跟的指数部分的形式为“x^b”，其中b 为x 的指数；如果x 的指数为1，则接下来紧跟的指数部分形式为“x”；如果x 的指数为0，则仅需输出系数即可。
5. 多项式中，多项式的开头、结尾不含多余的空格。

输入格式
输入共有2 行
第一行1 个整数，n，表示一元多项式的次数。
第二行有n+1 个整数，其中第i 个整数表示第n-i+1 次项的系数，每两个整数之间用空格隔开。
1 ≤ n ≤ 100，多项式各次项系数的绝对值均不超过100。
输出格式
输出共1 行，按题目所述格式输出多项式。
样例输入
5
100 -1 1 -3 0 10
样例输出
100x^5-x^4+x^3-3x^2+10
样例输入
3
-50 0 0 1
样例输出
-50x^3+1

#include <iostream>
using namespace std;
int main() {
    int n, a[1000];
    cin >> n;
    for (int i = n; i >= 0; i--) {
        cin >> a[i];
        if (a[i] != 0) {
            if (i != 0) {
                if (i != n && a[i] > 0) cout << "+";
                if (a[i] == -1) cout << "-";
                else if (a[i] != 1) cout << a[i];
                cout << "x";
                if (i != 1) cout << "^" << i;
            } else {
                if (a[i] > 0) cout << "+";
                cout << a[i];
            }
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, a[1000];

cin >> n;

for (int i = n; i >= 0; i--) {

cin >> a[i];

if (a[i] != 0) {

if (i != 0) {

if (i != n && a[i] > 0) cout << "+";

if (a[i] == -1) cout << "-";

else if (a[i] != 1) cout << a[i];

cout << "x";

if (i != 1) cout << "^" << i;

} else {

if (a[i] > 0) cout << "+";

cout << a[i];

}

return 0;

}