蓝桥杯 – 第5页 – 柳婼の blog

蓝桥杯 ADV-162 算法提高题目1 最大最小值

问题描述
　　给定 N 个整数，请你找出这 N 个数中最大的那个和最小的那个。
输入格式
　　第一行包含一个正整数 N 。(1 ≤ N ≤ 10000)。
　　第二行为 N 个用空格隔开的整数,每个数的绝对值不超过 1000000。
输出格式
　　输出仅一行,包含两个整数 x,y，x 表示 N 个数中的最大值，y 表示 N 个数中的最小值。x,y 之间用一个空格隔开。
样例输入
4
2 0 1 2
样例输出
2 0

#include <iostream>
#include <algorithm>
using namespace std;

int cmp(int a, int b) { return a < b; }

int main() {
    int n;
    cin >> n;
    int *a = new int [n];
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a+n, cmp);
    cout << a[n - 1] << " " << a[0];
    delete [] a;
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int cmp(int a, int b) { return a < b; }

int main() {

int n;

cin >> n;

int *a = new int [n];

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

cin >> a[i];

sort(a, a+n, cmp);

cout << a[n - 1] << " " << a[0];

delete [] a;

return 0;

}

蓝桥杯 ADV-158 算法提高新建Microsoft Word文档

问题描述
　　L正在出题，新建了一个word文档，想不好取什么名字，身旁一人惊问：“你出的题目叫《新建Microsoft Word文档》吗？”，L大喜，一拍桌子，说：“好，就叫这个名字了。”
　　仔细观察，当你新建一个word文档时，会得到一个名为“新建 Microsoft Word 文档.doc”的文件，再新建一个，则名为“新建 Microsoft Word 文档(2).doc”，再新建，便是“新建 Microsoft Word 文档(3).doc”。不断新建，编号不断递增。倘若你现在新建了三个文档，然后删除了“新建 Microsoft Word 文档(2).doc”，再新建就又会得到一个“新建 Microsoft Word 文档(2).doc”。
　　严格说，Windows在每次新建文档时，都会选取一个与已有文件编号不重复的最小正整数作为新文档的编号。
　　请编程模拟以上过程，支持以下两种操作
　　New：新建一个word文档，反馈新建的文档的编号
　　Delete id：删除一个编号为id的word文档，反馈删除是否成功
　　初始时一个文件都没有，“新建 Microsoft Word 文档.doc”的编号算作1。
输入格式
　　第一行一个正整数n表示操作次数，接下来n行，每行表示一个操作。若该行为”New”，则表示新建，为”Delete id”则表示要删除编号为id的文档，其中id为一个正整数。操作按输入顺序依次进行。
输出格式
　　对于输入的每一行，输出其反馈结果。对于新建操作，输出新建的文档的编号；对于删除操作，反馈删除是否成功：如果删除的文件存在，则删除成功，输出”Successful”，否则输出”Failed”。
样例输入
12
New
New
New
Delete 2
New
Delete 4
Delete 3
Delete 1
New
New
New
Delete 4
样例输出
1
2
3
Successful
2
Failed
Successful
Successful
1
3
4
Successful
数据规模和约定
　　操作次数（即输入的行数）不超过1481
　　删除编号的数值不超过2012

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int cmp(int a, int b) {
    return a < b;
}

int delnum(string s) {
    int len;
    len = s.length();
    if(len == 11) {
        return (s[7] - '0') * 1000 + (s[8] -'0') * 100 + (s[9] - '0') * 10 + (s[10] - '0');
    } else if(len == 10) {
        return (s[7] - '0') * 100 + (s[8] -'0') * 10 + (s[9] - '0');
    } else if(len == 9) {
        return (s[7] - '0') * 10 + (s[8] -'0');
    } else {
        return s[7] - '0';
    }
}

int main() {
    int n;
    cin >> n;
    int a[1500];
    for (int i = 0; i < 1500; i++)
        a[i] = 2013;
    int b[1500] = {0};
    int count = 1;
    int k = 0;
    cin.get();
    for (int i = 0; i < n; i++) {
        
        string s;
        getline(cin, s);
        int flag = 0;
        sort(a, a+1500, cmp);
        if (s[0] == 'N') {
            if (a[0] == 2013) {
                cout << count << endl;
                b[k++] = count;
                count++;
            } else {
                cout << a[0] << endl;
                b[k++] = a[0];
                a[0] = 2013;
            }
        } else {
            for (int l = 0; l <= k; l++) {
                if(b[l] == delnum(s)) {
                    for(int j = 0; j < 1500; j++) {
                        if (a[j] == 2013) {
                            a[j] = delnum(s);
                            cout << "Successful" << endl;
                            b[l] = 0;
                            break;
                        }
                    }
                    flag = 1;
                    break;
                }
            }
            if(flag == 0) {
                cout << "Failed" << endl;
            }
        }
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <string>

using namespace std;

int cmp(int a, int b) {

return a < b;

}

int delnum(string s) {

int len;

len = s.length();

if(len == 11) {

return (s[7] - '0') * 1000 + (s[8] -'0') * 100 + (s[9] - '0') * 10 + (s[10] - '0');

} else if(len == 10) {

return (s[7] - '0') * 100 + (s[8] -'0') * 10 + (s[9] - '0');

} else if(len == 9) {

return (s[7] - '0') * 10 + (s[8] -'0');

} else {

return s[7] - '0';

}

int main() {

int n;

cin >> n;

int a[1500];

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

a[i] = 2013;

int b[1500] = {0};

int count = 1;

int k = 0;

cin.get();

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

string s;

getline(cin, s);

int flag = 0;

sort(a, a+1500, cmp);

if (s[0] == 'N') {

if (a[0] == 2013) {

cout << count << endl;

b[k++] = count;

count++;

} else {

cout << a[0] << endl;

b[k++] = a[0];

a[0] = 2013;

}

} else {

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

if(b[l] == delnum(s)) {

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

if (a[j] == 2013) {

a[j] = delnum(s);

cout << "Successful" << endl;

b[l] = 0;

break;

}

flag = 1;

break;

}

if(flag == 0) {

cout << "Failed" << endl;

}

return 0;

}

蓝桥杯 ADV-155 算法提高上帝造题五分钟

问题描述
　　第一分钟，上帝说：要有题。于是就有了L，Y，M，C
　　第二分钟，LYC说：要有向量。于是就有了长度为n写满随机整数的向量
　　第三分钟，YUHCH说：要有查询。于是就有了Q个查询，查询向量的一段区间内元素的最小值
　　第四分钟，MZC说：要有限。于是就有了数据范围
　　第五分钟，CS说：要有做题的。说完众神一哄而散，留你来收拾此题
输入格式
　　第一行两个正整数n和Q，表示向量长度和查询个数
　　接下来一行n个整数，依次对应向量中元素：a[0]，a[1]，…，a[n-1]
　　接下来Q行，每行两个正整数lo，hi，表示查询区间[lo, hi]中的最小值，即min(a[lo],a[lo+1],…,a[hi])。
输出格式
　　共Q行，依次对应每个查询的结果，即向量在对应查询区间中的最小值。
样例输入
7 4
1 -1 -4 8 1 2 -7
0 0
1 3
4 5
0 6
样例输出
1
-4
1
-7
样例说明
　　第一个查询[0,0]表示求min{a[0]}=min{1}=1
　　第二个查询[1,3]表示求min{a[1],a[2],a[3]}=min{-1,-4,8}=-4
　　第三个查询[4,5]表示求min{a[4],a[5]}=min{1,2}=1
　　第四个查询[0,6]表示查询整个向量，求min{a[0..6]}=min{1,-1,-4,8,1,2,-7}=-7
数据规模和约定
　　1<=n<=1984，1<=Q<=1988，向量中随机整数的绝对值不超过1,000

#include <iostream>
#include <algorithm>
int cmp(int a, int b) {return a < b;}

using namespace std;
int main() {
    int n, q;
    cin >> n >> q;
    int *a = new int [n];
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < q; i++) {
        int low, high;
        cin >> low >> high;
        int *b = new int [high - low + 1];
        int temp = low;
        for (int j = 0; j < high - low + 1; j++)
            b[j] = a[temp++];
        sort(b, b + high - low + 1, cmp);
        cout << b[0] << endl;
        delete [] b;
    }
    delete [] a;
    return 0;
}

#include <iostream>

#include <algorithm>

int cmp(int a, int b) {return a < b;}

using namespace std;

int main() {

int n, q;

cin >> n >> q;

int *a = new int [n];

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

cin >> a[i];

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

int low, high;

cin >> low >> high;

int *b = new int [high - low + 1];

int temp = low;

for (int j = 0; j < high - low + 1; j++)

b[j] = a[temp++];

sort(b, b + high - low + 1, cmp);

cout << b[0] << endl;

delete [] b;

}

delete [] a;

return 0;

}

蓝桥杯 ADV-147 算法提高学霸的迷宫

问题描述
　　学霸抢走了大家的作业，班长为了帮同学们找回作业，决定去找学霸决斗。但学霸为了不要别人打扰，住在一个城堡里，城堡外面是一个二维的格子迷宫，要进城堡必须得先通过迷宫。因为班长还有妹子要陪，磨刀不误砍柴功，他为了节约时间，从线人那里搞到了迷宫的地图，准备提前计算最短的路线。可是他现在正向妹子解释这件事情，于是就委托你帮他找一条最短的路线。
输入格式
　　第一行两个整数n， m，为迷宫的长宽。
　　接下来n行，每行m个数，数之间没有间隔，为0或1中的一个。0表示这个格子可以通过，1表示不可以。假设你现在已经在迷宫坐标(1,1)的地方，即左上角，迷宫的出口在(n,m)。每次移动时只能向上下左右4个方向移动到另外一个可以通过的格子里，每次移动算一步。数据保证(1,1)，(n,m)可以通过。
输出格式
　　第一行一个数为需要的最少步数K。
　　第二行K个字符，每个字符∈{U,D,L,R},分别表示上下左右。如果有多条长度相同的最短路径，选择在此表示方法下字典序最小的一个。
样例输入
Input Sample 1:
3 3
001
100
110
Input Sample 2:
3 3
000
000
000
样例输出
Output Sample 1:
4
RDRD
Output Sample 2:
4
DDRR
数据规模和约定
　　有20%的数据满足：1<=n,m<=10
　　有50%的数据满足：1<=n,m<=50
　　有100%的数据满足：1<=n,m<=500。

分析：用广度优先搜索解决。bfs。100分。如果用DFS可能会超时～

#include <iostream>
using namespace std;
struct note {
    int x;
    int y;
    int f;
    int s;
    char dir;
};

int main() {
    char a[501][501];
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
        getchar();
    }
    int head = 1;
    int tail = 1;
    int book[501][501] = {0};
    book[1][1] = 1;
    
    int next[4][2] = {
        {1, 0},
        {0, -1},
        {0, 1},
        {-1, 0}
    };
    int tx = 1;
    int ty = 1;
    
    struct note que[250001];
    que[tail].x = 1;
    que[tail].y = 1;
    que[tail].f = 0;
    que[tail].s = 0;
    tail++;
    int flag = 0;
    while (head < tail) {
        for (int k = 0; k <= 3; k++) {
            tx = que[head].x + next[k][0];
            ty = que[head].y + next[k][1];
            
            if (tx < 1 || tx > n || ty < 1 || ty > m)
                continue;
            if (a[tx][ty] == '0' && book[tx][ty] == 0) {
                book[tx][ty] = 1;
                que[tail].x = tx;
                que[tail].y = ty;
                que[tail].f = head;
                que[tail].s = que[head].s + 1;
                if (k == 0) que[tail].dir = 'D';
                else if (k == 1) que[tail].dir = 'L';
                else if (k == 2) que[tail].dir = 'R';
                else if (k == 3) que[tail].dir = 'U';
                tail++;
            }
            if (tx == n && ty == m) {
                flag = 1;
                break;
            }
        }
        if (flag == 1) {
            break;
        }
        head++;
    }
    cout << que[tail - 1].s << endl;
    char t[250001];
    int temp = tail - 1;
    for (int i = que[tail - 1].s; i >= 1; i--) {
        t[i] = que[temp].dir;
        temp = que[temp].f;
    }
    for (int i = 1; i <= que[tail - 1].s; i++) {
        cout << t[i];
    }
    return 0;
}

#include <iostream>

using namespace std;

struct note {

int x;

int y;

int f;

int s;

char dir;

};

int main() {

char a[501][501];

int n, m;

cin >> n >> m;

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

for (int j = 1; j <= m; j++) {

cin >> a[i][j];

}

getchar();

}

int head = 1;

int tail = 1;

int book[501][501] = {0};

book[1][1] = 1;

int next[4][2] = {

{1, 0},

{0, -1},

{0, 1},

{-1, 0}

};

int tx = 1;

int ty = 1;

struct note que[250001];

que[tail].x = 1;

que[tail].y = 1;

que[tail].f = 0;

que[tail].s = 0;

tail++;

int flag = 0;

while (head < tail) {

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

tx = que[head].x + next[k][0];

ty = que[head].y + next[k][1];

if (tx < 1 || tx > n || ty < 1 || ty > m)

continue;

if (a[tx][ty] == '0' && book[tx][ty] == 0) {

book[tx][ty] = 1;

que[tail].x = tx;

que[tail].y = ty;

que[tail].f = head;

que[tail].s = que[head].s + 1;

if (k == 0) que[tail].dir = 'D';

else if (k == 1) que[tail].dir = 'L';

else if (k == 2) que[tail].dir = 'R';

else if (k == 3) que[tail].dir = 'U';

tail++;

}

if (tx == n && ty == m) {

flag = 1;

break;

}

if (flag == 1) {

break;

}

head++;

}

cout << que[tail - 1].s << endl;

char t[250001];

int temp = tail - 1;

for (int i = que[tail - 1].s; i >= 1; i--) {

t[i] = que[temp].dir;

temp = que[temp].f;

}

for (int i = 1; i <= que[tail - 1].s; i++) {

cout << t[i];

}

return 0;

}

蓝桥杯 ADV-132 算法提高笨小猴

问题描述
　　笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！
　　这种方法的具体描述如下：假设maxn是单词中出现次数最多的字母的出现次数，minn是单词中出现次数最少的字母的出现次数，如果maxn-minn是一个质数，那么笨小猴就认为这是个Lucky Word，这样的单词很可能就是正确的答案。
输入格式
　　输入文件只有一行，是一个单词，其中只可能出现小写字母，并且长度小于100。
输出格式
　　输出文件共两行，第一行是一个字符串，假设输入的的单词是Lucky Word，那么输出“Lucky Word”，否则输出“No Answer”；第二行是一个整数，如果输入单词是Lucky Word，输出maxn-minn的值，否则输出0。
样例输入
error
样例输出
Lucky Word
2
样例说明
　　单词error中出现最多的字母r出现了3次，出现次数最少的字母出现了1次，3-1=2，2是质数。
样例输入
olympic
样例输出
No Answer
0
样例说明
　　单词olympic中所有字母都只出现了1次，1-1=0，0不是质数。

#include <iostream>
#include <cctype>
using namespace std;
bool isprime(int n) {
    if(n <= 1)
        return false;
    for(int i = 2; i * i <= n; i++) {
        if(n % i == 0)
            return false;
    }
    return true;
}

int main() {
    int maxn = -1, minn = 99999999;
    int a[26] = {0};
    string s;
    cin >> s;
    for(int i = 0; i < s.length(); i++) {
        char t = toupper(s[i]);
        a[t-'A']++;
    }
    for(int i = 0; i < 26; i++) {
        maxn = maxn > a[i] ? maxn : a[i];
        if(a[i] != 0)
            minn = minn < a[i] ? minn : a[i];
    }
    if(isprime(maxn-minn)) {
        cout << "Lucky Word" << endl << maxn - minn;
    } else {
        cout << "No Answer" << endl << 0;
    }
    return 0;
}

#include <iostream>

#include <cctype>

using namespace std;

bool isprime(int n) {

if(n <= 1)

return false;

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

if(n % i == 0)

return false;

}

return true;

}

int main() {

int maxn = -1, minn = 99999999;

int a[26] = {0};

string s;

cin >> s;

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

char t = toupper(s[i]);

a[t-'A']++;

}

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

maxn = maxn > a[i] ? maxn : a[i];

if(a[i] != 0)

minn = minn < a[i] ? minn : a[i];

}

if(isprime(maxn-minn)) {

cout << "Lucky Word" << endl << maxn - minn;

} else {

cout << "No Answer" << endl << 0;

}

return 0;

}

蓝桥杯 ADV-127 算法提高日期计算

问题描述
　　已知2011年11月11日是星期五，问YYYY年MM月DD日是星期几？注意考虑闰年的情况。尤其是逢百年不闰，逢400年闰的情况。
输入格式
　　输入只有一行
　　YYYY MM DD
输出格式
　　输出只有一行
　　W
数据规模和约定
　　1599 <= YYYY <= 2999
　　1 <= MM <= 12
　　1 <= DD <= 31，且确保测试样例中YYYY年MM月DD日是一个合理日期
　　1 <= W <= 7，分别代表周一到周日
样例输入
2011 11 11
样例输出
5

#include <iostream>
using namespace std;

int isleapyear(int year);
int days(int year, int month, int day);
int distance(int year, int month, int day);

int main() {
    int year, month, day;
    cin >> year >> month >> day;
    int distance1 = distance(year, month, day);
    if (year >= 2012) {
        switch(distance1) {
            case 0: cout << 6; break;
            case 1: cout << 7; break;
            case 2: cout << 1; break;
            case 3: cout << 2; break;
            case 4: cout << 3; break;
            case 5: cout << 4; break;
            case 6: cout << 5; break;
        }
    } else {
        switch(distance1) {
            case 0: cout << 6; break;
            case 1: cout << 5; break;
            case 2: cout << 4; break;
            case 3: cout << 3; break;
            case 4: cout << 2; break;
            case 5: cout << 1; break;
            case 6: cout << 7; break;
        }
    }
    return 0;
}

int isleapyear(int year) {
    if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0)
        return 1;
    else
        return 0;
}

int days(int year, int month, int day) {
    int sum = 0;
    if (month <= 2) {
        if (month == 1)
            sum = day;
        else
            sum = 31 + day;
    } else {
        switch(month) {
            case 3: sum = 59 + day; break;
            case 4: sum = 90 + day; break;
            case 5: sum = 120 + day; break;
            case 6: sum = 151 + day; break;
            case 7: sum = 181 + day; break;
            case 8: sum = 212 + day; break;
            case 9: sum = 243 + day; break;
            case 10: sum = 273 + day; break;
            case 11: sum = 304 + day; break;
            case 12: sum = 334 + day; break;
        }
        if(isleapyear(year) == 1) {
            sum = sum + 1;
        }
    }
    return sum;
}

int distance(int year, int month, int day) {
    int count = 0;
    int distance1 = 0;
    if(year >=2012) {
        distance1 = 365 * (year - 2012) + days(year, month, day);
        for (int i = 2012; i < year; i++) {
            if(isleapyear(i) == 1)
                count++;
        }
        distance1 = distance1 + count;
    } else {
        distance1 = 365 * (2011 - year) + 365 - days(year, month, day);
        if (isleapyear(year) == 1)
            distance1 = distance1 + 1;
        for (int i = year + 1; i <= 2011; i++) {
            if(isleapyear(i) == 1)
                count++;
        }
        distance1 = distance1 + count;
    }
    distance1 = distance1 % 7;
    return distance1;
}

#include <iostream>

using namespace std;

int isleapyear(int year);

int days(int year, int month, int day);

int distance(int year, int month, int day);

int main() {

int year, month, day;

cin >> year >> month >> day;

int distance1 = distance(year, month, day);

if (year >= 2012) {

switch(distance1) {

case 0: cout << 6; break;

case 1: cout << 7; break;

case 2: cout << 1; break;

case 3: cout << 2; break;

case 4: cout << 3; break;

case 5: cout << 4; break;

case 6: cout << 5; break;

}

} else {

switch(distance1) {

case 0: cout << 6; break;

case 1: cout << 5; break;

case 2: cout << 4; break;

case 3: cout << 3; break;

case 4: cout << 2; break;

case 5: cout << 1; break;

case 6: cout << 7; break;

}

return 0;

}

int isleapyear(int year) {

if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0)

return 1;

else

return 0;

}

int days(int year, int month, int day) {

int sum = 0;

if (month <= 2) {

if (month == 1)

sum = day;

else

sum = 31 + day;

} else {

switch(month) {

case 3: sum = 59 + day; break;

case 4: sum = 90 + day; break;

case 5: sum = 120 + day; break;

case 6: sum = 151 + day; break;

case 7: sum = 181 + day; break;

case 8: sum = 212 + day; break;

case 9: sum = 243 + day; break;

case 10: sum = 273 + day; break;

case 11: sum = 304 + day; break;

case 12: sum = 334 + day; break;

}

if(isleapyear(year) == 1) {

sum = sum + 1;

}

return sum;

}

int distance(int year, int month, int day) {

int count = 0;

int distance1 = 0;

if(year >=2012) {

distance1 = 365 * (year - 2012) + days(year, month, day);

for (int i = 2012; i < year; i++) {

if(isleapyear(i) == 1)

count++;

}

distance1 = distance1 + count;

} else {

distance1 = 365 * (2011 - year) + 365 - days(year, month, day);

if (isleapyear(year) == 1)

distance1 = distance1 + 1;

for (int i = year + 1; i <= 2011; i++) {

if(isleapyear(i) == 1)

count++;

}

distance1 = distance1 + count;

}

distance1 = distance1 % 7;

return distance1;

}