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

蓝桥杯 ADV-237 算法提高三进制数位和

问题描述
给定L和R，你需要对于每一个6位三进制数（允许前导零），计算其每一个数位上的数字和，设其在十进制下为S。
一个三进制数被判断为合法，当且仅当S为质数，或者S属于区间[L,R]。
你的任务是给出合法三进制数的个数。
输入格式
一行两个非负整数L,R。
输出格式
一行一个非负整数表示答案。
样例输入
0 0
样例输出
330
数据规模和约定
保证0<=L<R<=12。
提示
判断x是否为质数核心代码：for (int i = 2; i * i <= x; ++i) if (x % i == 0) {/*你猜？*/}

分析：所有6为三进制数一共有3^6-1=72个，把这729个数转成三进制再判断~

#include <iostream>
using namespace std;
bool isprime(int n) {
    if(n == 1 || n == 0) return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}
int main() {
    int l, r, ans = 0;
    cin >> l >> r;
    for (int i = 0; i < 729; i++) {
        int sum = 0, j = i;
        while(j) {
            sum += j % 3;
            j /= 3;
        }
        if(isprime(sum) || (l <= sum && sum <= r))
            ans++;
    }
    cout << ans << endl;
    return 0;
}

#include <iostream>

using namespace std;

bool isprime(int n) {

if(n == 1 || n == 0) return false;

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

if (n % i == 0) return false;

return true;

}

int main() {

int l, r, ans = 0;

cin >> l >> r;

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

int sum = 0, j = i;

while(j) {

sum += j % 3;

j /= 3;

}

if(isprime(sum) || (l <= sum && sum <= r))

ans++;

}

cout << ans << endl;

return 0;

}

蓝桥杯 ADV-223 算法提高 8-1因式分解

问题描述
设计算法，用户输入合数，程序输出若个素数的乘积。例如，输入6，输出2*3。输入20，输出2*2*5。
样例
与上面的样例输入对应的输出。
例：

数据规模和约定
输入数据中每一个数在int表示范围内。

分析：1.先筛出50000以内的素数，用n依次对每个素数取余，获得自身的所有因子
2.最后，如果n==1，说明还剩下一个比50000大的素数因子~

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, p[50001] = {0};
    cin >> n;
    vector<int> vp, ans;
    for (int i = 2; i <= 50000; i++) {
        if (p[i] == 0) {
            vp.push_back(i);
            for (int j = 1; j * i <= 50000; j++) {
                p[i * j] = -1;
            }
        }
    }
    for (int i = 0; i < vp.size(); i++) {
        int t = vp[i];
        while (n % t == 0) {
            ans.push_back(t);
            n /= t;
        }
    }
    if (n != 1) ans.push_back(n);
    for (int i = 0; i < ans.size(); i++) {
        if (i != 0) cout << '*';
        cout << ans[i];
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

int n, p[50001] = {0};

cin >> n;

vector<int> vp, ans;

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

if (p[i] == 0) {

vp.push_back(i);

for (int j = 1; j * i <= 50000; j++) {

p[i * j] = -1;

}

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

int t = vp[i];

while (n % t == 0) {

ans.push_back(t);

n /= t;

}

if (n != 1) ans.push_back(n);

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

if (i != 0) cout << '*';

cout << ans[i];

}

return 0;

}

蓝桥杯 ALGO-20 算法训练求先序排列

问题描述
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。
输入格式
两行，每行一个字符串，分别表示中序和后序排列
输出格式
一个字符串，表示所求先序排列
样例输入
BADC
BDCA
样例输出
ABCD

#include <iostream>
#include <string>
using namespace std;
string in, post, ans = "";
void pre(int root, int l, int r) {
    if (l > r) return;
    int i = r;
    while (post[root] == in[i]) i--;
    ans += post[i];
    pre(root - 1 + i - l, l, i - 1);
    pre(root - 1, i + 1, r);
}
int main() {
    cin >> in >> post;
    pre(post.length() - 1, 0, in.length() - 1);
    cout << ans;
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

string in, post, ans = "";

void pre(int root, int l, int r) {

if (l > r) return;

int i = r;

while (post[root] == in[i]) i--;

ans += post[i];

pre(root - 1 + i - l, l, i - 1);

pre(root - 1, i + 1, r);

}

int main() {

cin >> in >> post;

pre(post.length() - 1, 0, in.length() - 1);

cout << ans;

return 0;

}

蓝桥杯 ADV-227 算法提高 11-1实现strcmp函数

问题描述
自己实现一个比较字符串大小的函数，也即实现strcmp函数。函数：int myStrcmp(char *s1,char *s2) 按照ASCII顺序比较字符串s1与s2。若s1与s2相等返回0，s1>s2返回1，s1<s2返回-1。具体来说，两个字符串自左向右逐个字符相比（按ASCII值大小相比较），直到出现不同的字符或遇’\0’为止（注意’\0’值为0，小于任意ASCII字符）。如：
“A”<“B”
“a”>”A”
“computer”>”compare”
“hello”<“helloworld”
样例输出

数据规模和约定
字符串长度<100。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cctype>
#include <map>
using namespace std;
int f(string s1, string s2) {
    s1 += char(0);
    s2 += char(0);
    for (int i = 0; i < s1.length() && i < s2.length(); i++) {
        if (s1[i] < s2[i]) return -1;
        if (s1[i] > s2[i]) return 1;
    }
    return 0;
}
int main() {
    string s1, s2;
    cin >> s1 >> s2;
    cout << f(s1, s2);
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

#include <cctype>

#include <map>

using namespace std;

int f(string s1, string s2) {

s1 += char(0);

s2 += char(0);

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

if (s1[i] < s2[i]) return -1;

if (s1[i] > s2[i]) return 1;

}

return 0;

}

int main() {

string s1, s2;

cin >> s1 >> s2;

cout << f(s1, s2);

return 0;

}

蓝桥杯 ALGO-157 算法训练阶乘末尾

问题描述
给定n和len，输出n!末尾len位。
输入格式
一行两个正整数n和len。
输出格式
一行一个字符串，表示答案。长度不足用前置零补全。
样例输入
6 5
样例输出
00720
数据规模和约定
n<=30, len<=10。

分析：1.每次只要取后len位的数字就够了，输出的时候位数不够要补0
2.判断数字位数的时候可以取以10为底的对数（蓝桥杯不支持c++ 11中的to_string()方法哦～）

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int n, len, cnt = 0;
    cin >> n >> len;
    long long res, ans = 1, m = pow(10, len);
    for (int i = 1; i <= n; i++)
        ans = (ans * i) % m;
    if (ans == 0) cnt = 1;
    else cnt = log10(ans) + 1;
    string s(len - cnt, '0');
    printf("%s%lld", s.c_str(), ans);
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n, len, cnt = 0;

cin >> n >> len;

long long res, ans = 1, m = pow(10, len);

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

ans = (ans * i) % m;

if (ans == 0) cnt = 1;

else cnt = log10(ans) + 1;

string s(len - cnt, '0');

printf("%s%lld", s.c_str(), ans);

return 0;

}

蓝桥杯 ADV-145 算法提高铺地毯

问题描述
为了准备一个学生节，组织者在会场的一片矩形区域（可看做是平面直角坐标
系的第一象限）铺上一些矩形地毯。一共有n 张地毯，编号从1 到n。现在将这些地毯按照
编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。
地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形
地毯边界和四个顶点上的点也算被地毯覆盖。
输入格式
输入共 n+2 行。
第一行，一个整数 n，表示总共有n 张地毯。
接下来的 n 行中，第i+1 行表示编号i 的地毯的信息，包含四个正整数a，b，g，k，每
两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标（a，b）以及地毯在x
轴和y 轴方向的长度。
第 n+2 行包含两个正整数x 和y，表示所求的地面的点的坐标（x，y）。
输出格式
输出共 1 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出-1。
样例输入
3
1 0 2 3
0 2 3 3
2 1 3 3
2 2
样例输出
3
样例输入
3
样例输出
-1
数据规模和约定
对于 30%的数据，有n≤2；
对于 50%的数据，0≤a, b, g, k≤100；
对于 100%的数据，有0≤n≤10,000，0≤a, b, g, k≤100,000。

1 0 2 3
0 2 3 3
2 1 3 3
4 5

#include <iostream>
#include <vector>
using namespace std;
struct blan {
    int a, b, x, y;
};
int main() {
    int n, a, b, x, y, xx, yy;
    cin >> n;
    vector<blan> v(n);
    for (int i = 0; i < n; i++)
        scanf("%d %d %d %d", &v[i].a, &v[i].b, &v[i].x, &v[i].y);
    scanf("%d %d", &xx, &yy);
    for (int i = v.size() - 1; i >= 0; i--) {
        if (xx >= v[i].a && xx <= v[i].a + v[i].x && yy >= v[i].b && yy <= v[i].b + v[i].y) {
            cout << i + 1;
            return 0;
        }
    }
    cout << -1;
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

struct blan {

int a, b, x, y;

};

int main() {

int n, a, b, x, y, xx, yy;

cin >> n;

vector<blan> v(n);

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

scanf("%d %d %d %d", &v[i].a, &v[i].b, &v[i].x, &v[i].y);

scanf("%d %d", &xx, &yy);

for (int i = v.size() - 1; i >= 0; i--) {

if (xx >= v[i].a && xx <= v[i].a + v[i].x && yy >= v[i].b && yy <= v[i].b + v[i].y) {

cout << i + 1;

return 0;

}

cout << -1;

return 0;

}