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

蓝桥杯 ADV-222 算法提高 7-2求arccos值

问题描述
利用标准库中的cos(x)和fabs(x)函数实现arccos(x)函数，x取值范围是[-1, 1]，返回值为[0, PI]。要求结果准确到小数点后5位。(PI = 3.1415926)
提示：要达到这种程度的精度需要使用double类型。
样例输入
0.5
样例输出

数据规模和约定
-1 <= x <= 1, 0 <= arccos(x) <= PI。

分析：二分逼近，求答案，精确到小数点后6位即可~

#include <iostream>
#include <cmath>
using namespace std;
#define PI 3.1415926
#define min 0.000001
double x;
double arccos(double l, double r) {
    if (r - l < min) return l;
    double mid = (l + r) / 2;
    if (cos(mid) == x) return mid;
    else if (cos(mid) > x) return arccos(mid, r);
    else return arccos(l, mid);
}
int main() {
    cin >> x;
    printf("%.5f", arccos(0, PI));
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

#define PI 3.1415926

#define min 0.000001

double x;

double arccos(double l, double r) {

if (r - l < min) return l;

double mid = (l + r) / 2;

if (cos(mid) == x) return mid;

else if (cos(mid) > x) return arccos(mid, r);

else return arccos(l, mid);

}

int main() {

cin >> x;

printf("%.5f", arccos(0, PI));

return 0;

}

问题描述
w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。
这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？
输入格式
第一行，两个整数m，n，用空格分开，表示格子的行数、列数（1<m,n<1000）。
接下来一行，一个整数k，表示下面还有k行数据(0<k<100000)
接下来k行，第行两个整数a，b，表示编号为a的小格子和编号为b的小格子合根了。
格子的编号一行一行，从上到下，从左到右编号。
比如：5 * 4 的小格子，编号：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20
样例输入
5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17
样例输出
5
样例说明
其合根情况参考下图

分析：一个没有套路的并查集～求有多少个集合～

#include <iostream>
int a[1000001], ans = 0;
using namespace std;
int find(int x) {
    while (x != a[x]) {
        x = a[x];
    }
    int t = x;
    while (t != a[t]) {
        int z = t;
        t = a[t];
        a[z] = x;
    }
    return x;
}
void uni(int x, int y) {
    a[find(x)] = find(y);
}
int main() {
    int m, n, k;
    scanf("%d%d%d", &m, &n, &k);
    for (int i = 0; i <= m * n; i++)
        a[i] = i;
    for (int i = 0; i < k; i++) {
        int t1, t2;
        scanf("%d%d", &t1, &t2);
        uni(t1, t2);
    }
    for (int i = 1; i <= m * n; i++)
        if (find(i) == i) ans++;
    cout << ans << endl;
    return 0;
}

#include <iostream>

int a[1000001], ans = 0;

using namespace std;

int find(int x) {

while (x != a[x]) {

x = a[x];

}

int t = x;

while (t != a[t]) {

int z = t;

t = a[t];

a[z] = x;

}

return x;

}

void uni(int x, int y) {

a[find(x)] = find(y);

}

int main() {

int m, n, k;

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

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

a[i] = i;

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

int t1, t2;

scanf("%d%d", &t1, &t2);

uni(t1, t2);

}

for (int i = 1; i <= m * n; i++)

if (find(i) == i) ans++;

cout << ans << endl;

return 0;

}

蓝桥杯 ADV-154 算法提高质数的后代

问题描述
在上一季里，曾提到过质数的孤独，其实从另一个角度看，无情隔膜它们的合数全是质数的后代，因为合数可以由质数相乘结合而得。
如果一个合数由两个质数相乘而得，那么我们就叫它是质数们的直接后代。现在，给你一系列自然数，判断它们是否是质数的直接后代。
输入格式
第一行一个正整数T，表示需要判断的自然数数量
接下来T行，每行一个要判断的自然数
输出格式
共T行，依次对于输入中给出的自然数，判断是否为质数的直接后代，是则输出Yes，否则输出No
样例输入
4
3
4
6
12
样例输出
No
Yes
Yes
No
数据规模和约定
1<=T<=20
2<=要判断的自然数<=105

#include <iostream>
#include <vector>
using namespace std;
int a[100005] = {0};
vector<int> p;
void getprime() {
    a[0] = a[1] = 1;
    for (int i = 2; i * i <= 100000; i++) {
        if (a[i] == 0) {
            for (int j = i * i; j <= 100000; j = j + i) 
                a[j] = 1;
        }
    }
    for (int i = 2; i <= 100000; i++) 
        if (a[i] == 0) p.push_back(i);
}
void check(int n) {
    for (int i = 0; i < p.size(); i++) {
        if (n % p[i] == 0 && a[n / p[i]] == 0) {
            cout << "Yes\n";
            return;
        }
    }
    cout << "No\n";
}
int main() {
    getprime();
    int n, k;
    cin >> k;
    while (k--) {
        cin >> n;
        check(n);
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int a[100005] = {0};

vector<int> p;

void getprime() {

a[0] = a[1] = 1;

for (int i = 2; i * i <= 100000; i++) {

if (a[i] == 0) {

for (int j = i * i; j <= 100000; j = j + i)

a[j] = 1;

}

for (int i = 2; i <= 100000; i++)

if (a[i] == 0) p.push_back(i);

}

void check(int n) {

for (int i = 0; i < p.size(); i++) {

if (n % p[i] == 0 && a[n / p[i]] == 0) {

cout << "Yes\n";

return;

}

cout << "No\n";

}

int main() {

getprime();

int n, k;

cin >> k;

while (k--) {

cin >> n;

check(n);

}

return 0;

}

蓝桥杯 ADV-140 算法提高开灯游戏

问题描述
有9盏灯与9个开关，编号都是1~9。
每个开关能控制若干盏灯，按下一次会改变其控制的灯的状态(亮的变成不亮，不亮变成亮的)。
具体如下：
第一个开关控制第二，第四盏灯；
第二个开关控制第一，第三，第五盏灯；
第三个开关控制第二，第六盏灯；
第四个开关控制第一，第五，第七盏灯；
第五个开关控制第二，第四，第六，第八盏灯；
第六个开关控制第三，第五，第九盏灯；
第七个开关控制第四，第八盏灯；
第八个开关控制第五，第七，第九盏灯；
第九个开关控制第六，第八盏灯。
开始时所有灯都是熄灭的，开关是关闭着的。要求按下若干开关后，使得只有4盏灯亮着。
输出格式
输出所有可能的方案，每行一个方案，每一行有9个字符，从左往右第i个字符表示第i个开关的状态(“0″表示关闭，”1″表示打开)，按字典序输出。下面的样例输出只是部分方案。
样例输出
000001011
000001110
000001111

分析：0～2^9的数字换算成2进制，得到开关的每一种状态，每种判断一次即可～

#include <iostream>
#include <cstring>
using namespace std;
void f(string s) {
    int a[11], sum = 0;
    memset(a, -1, sizeof(a));
    if (s[0] == '1') a[2] *= -1, a[4] *= -1;
    if (s[1] == '1') a[1] *= -1, a[3] *= -1, a[5] *= -1;
    if (s[2] == '1') a[2] *= -1, a[6] *= -1;
    if (s[3] == '1') a[1] *= -1, a[5] *= -1, a[7] *= -1;
    if (s[4] == '1') a[2] *= -1, a[4] *= -1, a[6] *= -1, a[8] *= -1;
    if (s[5] == '1') a[3] *= -1, a[5] *= -1, a[9] *= -1;
    if (s[6] == '1') a[4] *= -1, a[8] *= -1;
    if (s[7] == '1') a[5] *= -1, a[7] *= -1, a[9] *= -1;
    if (s[8] == '1') a[6] *= -1, a[8] *= -1;
    for (int i = 1; i <= 9; i++)
        if (a[i] == 1) sum++;
    if (sum == 4) cout << s << endl;
}
int main() {
    for (int i = 0; i < 512; i++) {
        int n = i;
        string s;
        while (n) {
            s = (char) (n % 2 + '0') + s;
            n /= 2;
        }
        string t(9 - s.length(), '0');
        s = t + s;
        f(s);
    }
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

void f(string s) {

int a[11], sum = 0;

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

if (s[0] == '1') a[2] *= -1, a[4] *= -1;

if (s[1] == '1') a[1] *= -1, a[3] *= -1, a[5] *= -1;

if (s[2] == '1') a[2] *= -1, a[6] *= -1;

if (s[3] == '1') a[1] *= -1, a[5] *= -1, a[7] *= -1;

if (s[4] == '1') a[2] *= -1, a[4] *= -1, a[6] *= -1, a[8] *= -1;

if (s[5] == '1') a[3] *= -1, a[5] *= -1, a[9] *= -1;

if (s[6] == '1') a[4] *= -1, a[8] *= -1;

if (s[7] == '1') a[5] *= -1, a[7] *= -1, a[9] *= -1;

if (s[8] == '1') a[6] *= -1, a[8] *= -1;

for (int i = 1; i <= 9; i++)

if (a[i] == 1) sum++;

if (sum == 4) cout << s << endl;

}

int main() {

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

int n = i;

string s;

while (n) {

s = (char) (n % 2 + '0') + s;

n /= 2;

}

string t(9 - s.length(), '0');

s = t + s;

f(s);

}

return 0;

}

蓝桥杯 ADV-141 算法提高判断名次

问题描述
某场比赛过后，你想要知道A~E五个人的排名是什么，于是要求他们每个人说了一句话。（经典的开头……-_-!）得了第1名的人23，说了假话；得了第5名的人不好意思，也说了假话；为了使求解问题简单，第3名同样说了假话。（奇数名次说假话）
输入格式
共5行，各行依次表示A~E说的话。
每行包含一个形如“A>=3”的名次判断，即一个大写字母+关系运算符+一个数字，不包含空格。
大写字母A~E，关系运算<、<=、=、>=、>、!=，数字1~5。注意：等于是“=”不是“==”！
输出格式
可能有多解，请按照字典序输出排名序列，每个解一行
最后一行输出解的数量
样例输入
A=2
D=5
E>3
A>2
B!=1
样例输出
ACDEB
AECBD
BADCE
BCADE
BDACE
CEADB
CEBDA
7

分析：1.用全排列公式，枚举除所有可能的排序，检查每个排序是否符合要求
2.检查每种名次，如果出现了奇数名次的人说了真话，该序列不符合，如果偶数名次的人说了假话，也不符合～

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
string ranks = "ABCDE";
vector<string> say(5);
int cnt;
bool check(string s) {
    int hash[150] = {0};
    for (int i = 0; i < 5; i++)
        hash[s[i]] = i + 1;
    for (int i = 0; i < 5; i++) {
        string sayt = say[i];
        int len = sayt.length();
        if (hash['A' + i] % 2 == 1) {
            if (sayt[1] == '=' && hash[sayt[0]] == sayt[len - 1] - '0') return false;
            if (sayt[1] == '!' && hash[sayt[0]] != sayt[len - 1] - '0') return false;
            if (len == 3 && sayt[1] == '<' && hash[sayt[0]] < sayt[len - 1] - '0') return false;
            if (len == 3 && sayt[1] == '>' && hash[sayt[0]] > sayt[len - 1] - '0') return false;
            if (len == 4 && sayt[1] == '>' && hash[sayt[0]] >= sayt[len - 1] - '0') return false;
            if (len == 4 && sayt[1] == '<' && hash[sayt[0]] <= sayt[len - 1] - '0') return false;
        } else {
            if (sayt[1] == '=' && hash[sayt[0]] != sayt[len - 1] - '0') return false;
            if (sayt[1] == '!' && hash[sayt[0]] == sayt[len - 1] - '0') return false;
            if (len == 3 && sayt[1] == '<' && hash[sayt[0]] >= sayt[len - 1] - '0') return false;
            if (len == 3 && sayt[1] == '>' && hash[sayt[0]] <= sayt[len - 1] - '0') return false;
            if (len == 4 && sayt[1] == '>' && hash[sayt[0]] < sayt[len - 1] - '0') return false;
            if (len == 4 && sayt[1] == '<' && hash[sayt[0]] > sayt[say[i].length() - 1] - '0') return false;
        }
    }
    cnt++;
    return true;
}
int main() {
    for (int i = 0; i < 5; i++)
        cin >> say[i];
    do {
        if (check(ranks)) cout << ranks << endl;
    } while (next_permutation(ranks.begin(), ranks.end()));
    cout << cnt;
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <cmath>

using namespace std;

string ranks = "ABCDE";

vector<string> say(5);

int cnt;

bool check(string s) {

int hash[150] = {0};

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

hash[s[i]] = i + 1;

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

string sayt = say[i];

int len = sayt.length();

if (hash['A' + i] % 2 == 1) {

if (sayt[1] == '=' && hash[sayt[0]] == sayt[len - 1] - '0') return false;

if (sayt[1] == '!' && hash[sayt[0]] != sayt[len - 1] - '0') return false;

if (len == 3 && sayt[1] == '<' && hash[sayt[0]] < sayt[len - 1] - '0') return false;

if (len == 3 && sayt[1] == '>' && hash[sayt[0]] > sayt[len - 1] - '0') return false;

if (len == 4 && sayt[1] == '>' && hash[sayt[0]] >= sayt[len - 1] - '0') return false;

if (len == 4 && sayt[1] == '<' && hash[sayt[0]] <= sayt[len - 1] - '0') return false;

} else {

if (sayt[1] == '=' && hash[sayt[0]] != sayt[len - 1] - '0') return false;

if (sayt[1] == '!' && hash[sayt[0]] == sayt[len - 1] - '0') return false;

if (len == 3 && sayt[1] == '<' && hash[sayt[0]] >= sayt[len - 1] - '0') return false;

if (len == 3 && sayt[1] == '>' && hash[sayt[0]] <= sayt[len - 1] - '0') return false;

if (len == 4 && sayt[1] == '>' && hash[sayt[0]] < sayt[len - 1] - '0') return false;

if (len == 4 && sayt[1] == '<' && hash[sayt[0]] > sayt[say[i].length() - 1] - '0') return false;

}

cnt++;

return true;

}

int main() {

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

cin >> say[i];

do {

if (check(ranks)) cout << ranks << endl;

} while (next_permutation(ranks.begin(), ranks.end()));

cout << cnt;

return 0;

}

蓝桥杯 ADV-169 算法提高士兵排队问题

试题
有Ｎ个士兵(1≤Ｎ≤26)，编号依次为Ａ,Ｂ,Ｃ,…，队列训练时，指挥官要把一些士兵从高到矮一次排成一行，但现在指挥官不能直接获得每个人的身高信息，只能获得“P1比P2高”这样的比较结果(P1、P2∈Ａ,Ｂ,Ｃ,…,Ｚ,记为 P1>P2)，如”Ａ>Ｂ”表示Ａ比Ｂ高。
请编一程序，根据所得到的比较结果求出一种符合条件的排队方案。
（注：比较结果中没有涉及的士兵不参加排队）
输入要求
比较结果从文本文件中读入（文件由键盘输入），每个比较结果在文本文件中占一行。
输出要求
若输入数据无解，打印“No Answer!”信息，否则从高到矮一次输出每一个士兵的编号，中间无分割符，并把结果写入文本文件中，文件由键盘输入：
样例输入
A>B
B>D
F>D
样例输出
AFBD

分析：高>矮，记作矮入度+1。每次找到没有排过队并且入度为0的士兵，拉出来排队，然后把紧跟后面的士兵的入度-1，一直这样循环。当找不到没排队且入度为0的士兵，判断：如果士兵全部排好了，正常输出；否则出现了环，无法确定顺序，输出No Answer!

#include <iostream>
#include <cstring>
#include <vector>
#include <set>
using namespace std;
int main() {
    int in[151], vis[150] = {0};
    set<int> se;
    vector<int> a[150];
    memset(in, -1, sizeof(in));
    string s, ans;
    while (cin >> s) {
        if (in[s[0]] == -1) in[s[0]] = 0;
        if (in[s[2]] == -1) in[s[2]] = 0;
        in[s[2]]++;
        a[s[0]].push_back(s[2]);
        se.insert(s[0]);
        se.insert(s[2]);
    }
    while (1) {
        int cnt = 0, begin;
        for (int i = 1; i <= 150; i++) {
            if (in[i] == 0 && vis[i] == 0) {
                begin = i;
                cnt++;
            }
        }
        if (cnt == 0) {
            if (ans.length() == se.size()) {
                cout << ans;
            } else
                cout << "No Answer!";
            break;

        } else {
            ans += (char) begin;
            vis[begin] = 1;
            for (int i = 0; i < a[begin].size(); i++)
                in[a[begin][i]]--;
        }
    }
    return 0;
}

#include <iostream>

#include <cstring>

#include <vector>

#include <set>

using namespace std;

int main() {

int in[151], vis[150] = {0};

set<int> se;

vector<int> a[150];

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

string s, ans;

while (cin >> s) {

if (in[s[0]] == -1) in[s[0]] = 0;

if (in[s[2]] == -1) in[s[2]] = 0;

in[s[2]]++;

a[s[0]].push_back(s[2]);

se.insert(s[0]);

se.insert(s[2]);

}

while (1) {

int cnt = 0, begin;

for (int i = 1; i <= 150; i++) {

if (in[i] == 0 && vis[i] == 0) {

begin = i;

cnt++;

}

if (cnt == 0) {

if (ans.length() == se.size()) {

cout << ans;

} else

cout << "No Answer!";

break;

} else {

ans += (char) begin;

vis[begin] = 1;

for (int i = 0; i < a[begin].size(); i++)

in[a[begin][i]]--;

}

return 0;

}