柳婼の blog – 第238页 – 我不管，反正我最萌～

蓝桥杯 BASIC-21 基础练习 Sine之舞

问题描述
最近FJ为他的奶牛们开设了数学分析课，FJ知道若要学好这门课，必须有一个好的三角函数基本功。所以他准备和奶牛们做一个“Sine之舞”的游戏，寓教于乐，提高奶牛们的计算能力。
不妨设
An=sin(1–sin(2+sin(3–sin(4+…sin(n))…)
Sn=(…(A1+n)A2+n-1)A3+…+2)An+1
FJ想让奶牛们计算Sn的值，请你帮助FJ打印出Sn的完整表达式，以方便奶牛们做题。
输入格式
仅有一个数：N<201。
输出格式
请输出相应的表达式Sn，以一个换行符结束。输出中不得含有多余的空格或换行、回车符。
样例输入
3
样例输出
((sin(1)+3)sin(1–sin(2))+2)sin(1–sin(2+sin(3)))+1

#include <iostream>
using namespace std;
int main() {
    string a[201];
    string s;
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        if(i == 0) {
            a[i] = "sin(1";
            continue;
        }
        a[i] = a[i - 1];
        if(i % 2 == 1) {
            a[i] += "-";
        } else {
            a[i] += "+";
        }
        a[i] += "sin(";
        a[i] += (char)(i + '1');
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= i; j++) {
            a[i] += ")";
        }
    }
    for(int i = 2; i <= n; i++) {
        s += "(";
    }
    for(int i = n - 1; i >= 1; i--) {
        s += a[n - 1 - i];
        s += "+";
        s += (char)(i + 1 + '0');
        s += ")";
    }
    s += a[n-1];
    s += "+1";
    cout << s;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

string a[201];

string s;

int n;

cin >> n;

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

if(i == 0) {

a[i] = "sin(1";

continue;

}

a[i] = a[i - 1];

if(i % 2 == 1) {

a[i] += "-";

} else {

a[i] += "+";

}

a[i] += "sin(";

a[i] += (char)(i + '1');

}

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

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

a[i] += ")";

}

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

s += "(";

}

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

s += a[n - 1 - i];

s += "+";

s += (char)(i + 1 + '0');

s += ")";

}

s += a[n-1];

s += "+1";

cout << s;

return 0;

}

蓝桥杯 BASIC-22 基础练习 FJ的字符串

问题描述
FJ在沙盘上写了这样一些字符串：
A1 = “A”
A2 = “ABA”
A3 = “ABACABA”
A4 = “ABACABADABACABA”
… …
你能找出其中的规律并写所有的数列AN吗？
输入格式
仅有一个数：N ≤ 26。
输出格式
请输出相应的字符串AN，以一个换行符结束。输出中不得含有多余的空格或换行、回车符。
样例输入
3
样例输出
ABACABA

#include <iostream>
using namespace std;
string dfs(int n) {
    if(n == 1) {
        return "A";
    } else {
        return dfs(n - 1) + (char)(n + 'A' - 1) + dfs(n - 1);
    }
}

int main() {
    int n;
    cin >> n;
    cout << dfs(n);
    return 0;
}

#include <iostream>

using namespace std;

string dfs(int n) {

if(n == 1) {

return "A";

} else {

return dfs(n - 1) + (char)(n + 'A' - 1) + dfs(n - 1);

}

int main() {

int n;

cin >> n;

cout << dfs(n);

return 0;

}

蓝桥杯 BASIC-23 基础练习芯片测试

问题描述
有n（2≤n≤20）块芯片，有好有坏，已知好芯片比坏芯片多。
每个芯片都能用来测试其他芯片。用好芯片测试其他芯片时，能正确给出被测试芯片是好还是坏。而用坏芯片测试其他芯片时，会随机给出好或是坏的测试结果（即此结果与被测试芯片实际的好坏无关）。
给出所有芯片的测试结果，问哪些芯片是好芯片。
输入格式
输入数据第一行为一个整数n，表示芯片个数。
第二行到第n+1行为n*n的一张表，每行n个数据。表中的每个数据为0或1，在这n行中的第i行第j列（1≤i, j≤n）的数据表示用第i块芯片测试第j块芯片时得到的测试结果，1表示好，0表示坏，i=j时一律为1（并不表示该芯片对本身的测试结果。芯片不能对本身进行测试）。
输出格式
按从小到大的顺序输出所有好芯片的编号
样例输入
3
1 0 1
0 1 0
1 0 1
样例输出
1 3
分析：因为超过半数的芯片是好的，所以这些芯片对于其他芯片的测试结果是正确的。
所以假设该芯片是好芯片，它除了它自身测试自身之外的其他测试结果为好的个数将超过一半。
同理，假设该芯片是坏芯片，他将有超过半数的测试结果是坏芯片。
所以只要根据每一列的所有测试结果，判断其为好芯片的总数>=n/2的时候，这个芯片就是好芯片。

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int a[20][20];
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    for(int i = 0; i < n; i++) {
        int cnt = 0;
        for(int j = 0; j < n; j++) {
            if(j != i)
                cnt += a[j][i];
        }
        if(cnt >= n/2) {
            cout << i+1 << " ";
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int a[20][20];

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

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

cin >> a[i][j];

}

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

int cnt = 0;

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

if(j != i)

cnt += a[j][i];

}

if(cnt >= n/2) {

cout << i+1 << " ";

}

return 0;

}

蓝桥杯 BASIC-24 基础练习龟兔赛跑预测

问题描述
　　话说这个世界上有各种各样的兔子和乌龟，但是研究发现，所有的兔子和乌龟都有一个共同的特点——喜欢赛跑。于是世界上各个角落都不断在发生着乌龟和兔子的比赛，小华对此很感兴趣，于是决定研究不同兔子和乌龟的赛跑。他发现，兔子虽然跑比乌龟快，但它们有众所周知的毛病——骄傲且懒惰，于是在与乌龟的比赛中，一旦任一秒结束后兔子发现自己领先t米或以上，它们就会停下来休息s秒。对于不同的兔子，t，s的数值是不同的，但是所有的乌龟却是一致——它们不到终点决不停止。
　　然而有些比赛相当漫长，全程观看会耗费大量时间，而小华发现只要在每场比赛开始后记录下兔子和乌龟的数据——兔子的速度v1（表示每秒兔子能跑v1米），乌龟的速度v2，以及兔子对应的t，s值，以及赛道的长度l——就能预测出比赛的结果。但是小华很懒，不想通过手工计算推测出比赛的结果，于是他找到了你——清华大学计算机系的高才生——请求帮助，请你写一个程序，对于输入的一场比赛的数据v1，v2，t，s，l，预测该场比赛的结果。
输入格式
　　输入只有一行，包含用空格隔开的五个正整数v1，v2，t，s，l，其中(v1,v2<=100;t<=300;s<=10;l<=10000且为v1,v2的公倍数)
输出格式
　　输出包含两行，第一行输出比赛结果——一个大写字母“T”或“R”或“D”，分别表示乌龟获胜，兔子获胜，或者两者同时到达终点。
　　第二行输出一个正整数，表示获胜者（或者双方同时）到达终点所耗费的时间（秒数）。
样例输入
10 5 5 2 20
样例输出
D
4
样例输入
10 5 5 1 20
样例输出
R
3
样例输入
10 5 5 3 20
样例输出
T
4

#include <iostream>
using namespace std;
int main() {
	int vr, vt, t, s, l;
	cin >> vr >> vt >> t >> s >> l;
	int ttime = l / vt;
	int cnttime = 0;
	int lent = 0;
	int lenr = 0;
	int breaktime = 0;//统计兔子休息的时间
	int flag = 0;//flag==0表示兔子不在休息，flag==1表示兔子正在休息
	while(lent < l && lenr < l) {
		if(flag == 0 && lenr - lent < t || flag == 1 && breaktime >= s) {
			lenr = lenr + vr;
			flag = 0;
			breaktime = 0;
		} else {
			flag = 1;
			breaktime++;
		}
		lent = lent + vt;
		cnttime++;
	}
	if(lent >= l && lenr < l) {
		cout << "T" << endl;
	} else if(lent < l && lenr >= l) {
		cout << "R" << endl;
	} else {
		cout << "D" << endl;
	}
	cout << cnttime;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int vr, vt, t, s, l;

cin >> vr >> vt >> t >> s >> l;

int ttime = l / vt;

int cnttime = 0;

int lent = 0;

int lenr = 0;

int breaktime = 0;//统计兔子休息的时间

int flag = 0;//flag==0表示兔子不在休息，flag==1表示兔子正在休息

while(lent < l && lenr < l) {

if(flag == 0 && lenr - lent < t || flag == 1 && breaktime >= s) {

lenr = lenr + vr;

flag = 0;

breaktime = 0;

} else {

flag = 1;

breaktime++;

}

lent = lent + vt;

cnttime++;

}

if(lent >= l && lenr < l) {

cout << "T" << endl;

} else if(lent < l && lenr >= l) {

cout << "R" << endl;

} else {

cout << "D" << endl;

}

cout << cnttime;

return 0;

}

蓝桥杯 BASIC-25 基础练习回形取数

问题描述
　　回形取数就是沿矩阵的边取数，若当前方向上无数可取或已经取过，则左转90度。一开始位于矩阵左上角，方向向下。
输入格式
　　输入第一行是两个不超过200的正整数m, n，表示矩阵的行和列。接下来m行每行n个整数，表示这个矩阵。
输出格式
　　输出只有一行，共mn个数，为输入矩阵回形取数得到的结果。数之间用一个空格分隔，行末不要有多余的空格。
样例输入
3 3
1 2 3
4 5 6
7 8 9
样例输出
1 4 7 8 9 6 3 2 5
样例输入
3 2
1 2
3 4
5 6
样例输出
1 3 5 6 4 2

#include <iostream>
#include <memory.h>
using namespace std;
int main() {
    int m, n;
    cin >> m >> n;
    int a[201][201];
    memset(a, -1, sizeof(a));
    int i = 0, j = 0;
    for(i = 0; i < m; i++)
        for(j = 0; j < n; j++)
            cin >> a[i][j];
    i = 0, j = 0;
    int total = 0;
    while(total < m * n) {
        while(i <= m-1 && a[i][j] != -1) {//down
            cout << a[i][j] << " ";
            a[i][j] = -1;
            i++;
            total++;
        }
        i--;
        j++;
        while(j <= n-1 && a[i][j] != -1) {//right
            cout << a[i][j] << " ";
            a[i][j] = -1;
            j++;
            total++;
        }
        j--;
        i--;
        while(i >= 0 && a[i][j] != -1) {//up
            cout << a[i][j] << " ";
            a[i][j] = -1;
            i--;
            total++;
        }
        i++;
        j--;
        while(j >= 0 && a[i][j] != -1) {//left
            cout << a[i][j] << " ";
            a[i][j] = -1;
            j--;
            total++;
        }
        j++;
        i++;
    } 
    return 0;
}

#include <iostream>

#include <memory.h>

using namespace std;

int main() {

int m, n;

cin >> m >> n;

int a[201][201];

memset(a, -1, sizeof(a));

int i = 0, j = 0;

for(i = 0; i < m; i++)

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

cin >> a[i][j];

i = 0, j = 0;

int total = 0;

while(total < m * n) {

while(i <= m-1 && a[i][j] != -1) {//down

cout << a[i][j] << " ";

a[i][j] = -1;

i++;

total++;

}

i--;

j++;

while(j <= n-1 && a[i][j] != -1) {//right

cout << a[i][j] << " ";

a[i][j] = -1;

j++;

total++;

}

j--;

i--;

while(i >= 0 && a[i][j] != -1) {//up

cout << a[i][j] << " ";

a[i][j] = -1;

i--;

total++;

}

i++;

j--;

while(j >= 0 && a[i][j] != -1) {//left

cout << a[i][j] << " ";

a[i][j] = -1;

j--;

total++;

}

j++;

i++;

}

return 0;

}

蓝桥杯BASIC-28 基础练习 Huffuman树

问题描述
　　Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。
　　给出一列数{pi}={p0, p1, …, pn-1}，用这列数构造Huffman树的过程如下：
　　1. 找到{pi}中最小的两个数，设为pa和pb，将pa和pb从{pi}中删除掉，然后将它们的和加入到{pi}中。这个过程的费用记为pa + pb。
　　2. 重复步骤1，直到{pi}中只剩下一个数。
　　在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。
　　本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。

　　例如，对于数列{pi}={5, 3, 8, 2, 9}，Huffman树的构造过程如下：
　　1. 找到{5, 3, 8, 2, 9}中最小的两个数，分别是2和3，从{pi}中删除它们并将和5加入，得到{5, 8, 9, 5}，费用为5。
　　2. 找到{5, 8, 9, 5}中最小的两个数，分别是5和5，从{pi}中删除它们并将和10加入，得到{8, 9, 10}，费用为10。
　　3. 找到{8, 9, 10}中最小的两个数，分别是8和9，从{pi}中删除它们并将和17加入，得到{10, 17}，费用为17。
　　4. 找到{10, 17}中最小的两个数，分别是10和17，从{pi}中删除它们并将和27加入，得到{27}，费用为27。
　　5. 现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。
输入格式
　　输入的第一行包含一个正整数n（n<=100）。
　　接下来是n个正整数，表示p0, p1, …, pn-1，每个数不超过1000。
输出格式
　　输出用这些数构造Huffman树的总费用。
样例输入
5
5 3 8 2 9
样例输出
59

#include <iostream>
#include <vector>
#include <algorithm>
int cmp1(int a, int b) {
    return a > b;
}
using namespace std;
int main() {
    int n;
    int price = 0;
    vector<int> v;
    cin >> n;
    for(int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        v.push_back(temp);
    }
    int size = v.size();
    while(size >= 2) {
        sort(v.begin(), v.end(), cmp1);
        int t = v[size-1] + v[size-2];
        price += t;
        v.pop_back();
        v.pop_back();
        v.push_back(t);
        size = v.size();
    }
    cout << price;
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

int cmp1(int a, int b) {

return a > b;

}

using namespace std;

int main() {

int n;

int price = 0;

vector<int> v;

cin >> n;

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

int temp;

cin >> temp;

v.push_back(temp);

}

int size = v.size();

while(size >= 2) {

sort(v.begin(), v.end(), cmp1);

int t = v[size-1] + v[size-2];

price += t;

v.pop_back();

v.push_back(t);

size = v.size();

}

cout << price;

return 0;

}