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

蓝桥杯 ALGO-110 算法训练字符串的展开

在初赛普及组的“阅读程序写结果”的问题中，我们曾给出一个字符串展开的例子：如果在输入的字符串中，含有类似于“d-h”或者“4-8”的字串，我们就把它当作一种简写，输出时，用连续递增的字母获数字串替代其中的减号，即，将上面两个子串分别输出为“defgh”和“45678”。在本题中，我们通过增加一些参数的设置，使字符串的展开更为灵活。具体约定如下：
(1) 遇到下面的情况需要做字符串的展开：在输入的字符串中，出现了减号“-”，减号两侧同为小写字母或同为数字，且按照ASCII码的顺序，减号右边的字符严格大于左边的字符。
(2) 参数p1：展开方式。p1=1时，对于字母子串，填充小写字母；p1=2时，对于字母子串，填充大写字母。这两种情况下数字子串的填充方式相同。p1=3时，不论是字母子串还是数字字串，都用与要填充的字母个数相同的星号“*”来填充。
(3) 参数p2：填充字符的重复个数。p2=k表示同一个字符要连续填充k个。例如，当p2=3时，子串“d-h”应扩展为“deeefffgggh”。减号两边的字符不变。
(4) 参数p3：是否改为逆序：p3=1表示维持原来顺序，p3=2表示采用逆序输出，注意这时候仍然不包括减号两端的字符。例如当p1=1、p2=2、p3=2时，子串“d-h”应扩展为“dggffeeh”。
(5) 如果减号右边的字符恰好是左边字符的后继，只删除中间的减号，例如：“d-e”应输出为“de”，“3-4”应输出为“34”。如果减号右边的字符按照ASCII码的顺序小于或等于左边字符，输出时，要保留中间的减号，例如：“d-d”应输出为“d-d”，“3-1”应输出为“3-1”。
输入格式
输入包括两行：
第1行为用空格隔开的3个正整数，一次表示参数p1，p2，p3。
第2行为一行字符串，仅由数字、小写字母和减号“-”组成。行首和行末均无空格。
输出格式
输出只有一行，为展开后的字符串。
输入输出样例1
输入
1 2 1
abcs-w1234-9s-4zz
输出
abcsttuuvvw1234556677889s-4zz
输入输出样例2
输入
2 3 2
a-d-d
输出
aCCCBBBd-d
输入输出样例3
输入
3 4 2
di-jkstra2-6
输出
dijkstra2************6
数据规模和约定
40%的数据满足：字符串长度不超过5
100%的数据满足：1<=p1<=3，1<=p2<=8，1<=p3<=2。字符串长度不超过100

#include <iostream>
#include <algorithm>
#include <string>
#include <cctype>
using namespace std;
int main() {
    int p1, p2, p3;
    string s;
    cin >> p1 >> p2 >> p3 >> s;
    for (int i = 0; i < s.size(); i++) {
        cout << s[i];
        if (i < s.size() - 2 && s[i + 1] == '-' &&
            (isdigit(s[i]) && isdigit(s[i + 2]) || islower(s[i]) && islower(s[i + 2]))) {
            char c1 = s[i], c2 = s[i + 2];
            string ans;
            if (c1 >= c2) ans = "-";
            else if (c1 + 1 == c2) ans = "";
            else {
                if (p3 == 1) {
                    for (int i = c1 + 1; i < c2; i++) {
                        if (p1 == 1) ans.append(p2, tolower((char) i));
                        if (p1 == 2) ans.append(p2, toupper((char) i));
                        if (p1 == 3) ans.append(p2, '*');
                    }
                }
                if (p3 == 2) {
                    for (int i = c2 - 1; i > c1; i--) {
                        if (p1 == 1) ans.append(p2, tolower((char) i));
                        if (p1 == 2) ans.append(p2, toupper((char) i));
                        if (p1 == 3) ans.append(p2, '*');
                    }
                }
            }
            cout << ans;
            i++;
        }
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <string>

#include <cctype>

using namespace std;

int main() {

int p1, p2, p3;

string s;

cin >> p1 >> p2 >> p3 >> s;

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

cout << s[i];

if (i < s.size() - 2 && s[i + 1] == '-' &&

(isdigit(s[i]) && isdigit(s[i + 2]) || islower(s[i]) && islower(s[i + 2]))) {

char c1 = s[i], c2 = s[i + 2];

string ans;

if (c1 >= c2) ans = "-";

else if (c1 + 1 == c2) ans = "";

else {

if (p3 == 1) {

for (int i = c1 + 1; i < c2; i++) {

if (p1 == 1) ans.append(p2, tolower((char) i));

if (p1 == 2) ans.append(p2, toupper((char) i));

if (p1 == 3) ans.append(p2, '*');

}

if (p3 == 2) {

for (int i = c2 - 1; i > c1; i--) {

if (p1 == 1) ans.append(p2, tolower((char) i));

if (p1 == 2) ans.append(p2, toupper((char) i));

if (p1 == 3) ans.append(p2, '*');

}

cout << ans;

i++;

}

return 0;

}

蓝桥杯 ADV-117 算法提高进制转换

问题描述
程序提示用户输入三个字符，每个字符取值范围是0-9，A-F。然后程序会把这三个字符转化为相应的十六进制整数，并分别以十六进制，十进制，八进制输出。
输入格式：输入只有一行，即三个字符。
输出格式：输出只有一行，包括三个整数，中间用空格隔开。
输入输出样例
样例输入
FFF
样例输出
FFF 4095 7777

#include <iostream>
using namespace std;
int main() {
    int n = 0;
    char c1, c2, c3;
    string s(3, '0'), ans8;
    scanf("%c %c %c", &c1, &c2, &c3);
    s[0] = c1;
    s[1] = c2;
    s[2] = c3;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] >= '0' && s[i] <= '9') n = n * 16 + s[i] - '0';
        else n = n * 16 + s[i] - 'A' + 10;
    }
    if (s[0] == '0') s = s.substr(1, s.length() - 1);
    if (s[0] == '0') s = s.substr(1, s.length() - 1);
    cout << s << " " << n << " ";
    while (n) {
        ans8 = char(n % 8 + '0') + ans8;
        n /= 8;
    }
    if (ans8 == "") ans8 = "0";
    cout << ans8;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n = 0;

char c1, c2, c3;

string s(3, '0'), ans8;

scanf("%c %c %c", &c1, &c2, &c3);

s[0] = c1;

s[1] = c2;

s[2] = c3;

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

if (s[i] >= '0' && s[i] <= '9') n = n * 16 + s[i] - '0';

else n = n * 16 + s[i] - 'A' + 10;

}

if (s[0] == '0') s = s.substr(1, s.length() - 1);

cout << s << " " << n << " ";

while (n) {

ans8 = char(n % 8 + '0') + ans8;

n /= 8;

}

if (ans8 == "") ans8 = "0";

cout << ans8;

return 0;

}

蓝桥杯 ALGO-105 算法训练黑色星期五

问题描述
有些西方人比较迷信，如果某个月的13号正好是星期五，他们就会觉得不太吉利，用古人的说法，就是“诸事不宜”。请你编写一个程序，统计出在某个特定的年份中，出现了多少次既是13号又是星期五的情形，以帮助你的迷信朋友解决难题。
说明：（1）一年有365天，闰年有366天，所谓闰年，即能被4整除且不能被100整除的年份，或是既能被100整除也能被400整除的年份；（2）已知1998年1月1日是星期四，用户输入的年份肯定大于或等于1998年。
输入格式：输入只有一行，即某个特定的年份（大于或等于1998年）。
输出格式：输出只有一行，即在这一年中，出现了多少次既是13号又是星期五的情形。
输入输出样例
样例输入
1998
样例输出
3

分析：1.根据基姆拉尔森计算公式枚举即可
2.W = (d+2*m+3*(m+1)/5+y+y/4-y/100+y/400) % 7
3.注意：在公式中有个与其他公式不同的地方：把一月和二月看成是上一年的十三月和十四月例：如果是2018-1-1则换算成：2017-13-1来代入公式计算～

#include <iostream>
using namespace std;
int ans = 0;
void f(int y, int m, int d) {
    if (m == 1 || m == 2) {
        y--;
        m += 12;
    }
    if ((d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400) % 7 == 4 && d == 13) ans++;
}
int main() {
    int n;
    int m31[] = {1, 3, 5, 7, 8, 10, 12};
    int m30[] = {4, 6, 9, 11};
    int m2;
    cin >> n;
    if (n % 4 == 0 && n % 100 != 0 || n % 400 == 0) {
        m2 = 29;
    } else {
        m2 = 28;
    }
    for (int i = 0; i < 7; i++)
        for (int j = 1; j <= 31; j++)
            f(n, m31[i], j);

    for (int i = 0; i < 4; i++)
        for (int j = 1; j <= 30; j++)
            f(n, m30[i], j);

    for (int j = 1; j <= m2; j++)
        f(n, 2, j);
    cout << ans << endl;
    return 0;
}

#include <iostream>

using namespace std;

int ans = 0;

void f(int y, int m, int d) {

if (m == 1 || m == 2) {

y--;

m += 12;

}

if ((d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400) % 7 == 4 && d == 13) ans++;

}

int main() {

int n;

int m31[] = {1, 3, 5, 7, 8, 10, 12};

int m30[] = {4, 6, 9, 11};

int m2;

cin >> n;

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

m2 = 29;

} else {

m2 = 28;

}

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

for (int j = 1; j <= 31; j++)

f(n, m31[i], j);

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

for (int j = 1; j <= 30; j++)

f(n, m30[i], j);

for (int j = 1; j <= m2; j++)

f(n, 2, j);

cout << ans << endl;

return 0;

}

蓝桥杯 ALGO-99 算法训练薪水计算

问题描述
编写一个程序，计算员工的周薪。薪水的计算是以小时为单位，如果在一周的时间内，员工工作的时间不超过40 个小时，那么他/她的总收入等于工作时间乘以每小时的薪水。如果员工工作的时间在40 到50 个小时之间，那么对于前40 个小时，仍按常规方法计算；而对于剩余的超额部分，每小时的薪水按1.5 倍计算。如果员工工作的时间超过了50 个小时，那么对于前40 个小时，仍按常规方法计算；对于40～50 个小时之间的部分，每小时的薪水按1.5 倍计算；而对于超出50 个小时的部分，每小时的薪水按2 倍计算。请编写一个程序，输入员工的工作时间和每小时的薪水，然后计算并显示他/她应该得到的周薪。
输入格式：输入只有一行，包括一个整数和一个实数，分别表示工作时间和每小时薪水。
输出格式：输出只有一个实数，表示周薪，保留小数点后2位。
输入输出样例
样例输入
40 50
样例输出
2000.00

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int n;
    double sal, sum;
    cin >> n >> sal;
    sum = min(40, n) * sal + min(10, max(0, n - 40)) * sal * 1.5 + max(0, n - 50) * sal * 2;
    printf("%.2f",sum);
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n;

double sal, sum;

cin >> n >> sal;

sum = min(40, n) * sal + min(10, max(0, n - 40)) * sal * 1.5 + max(0, n - 50) * sal * 2;

printf("%.2f",sum);

return 0;

}

蓝桥杯 ALGO-66 算法训练字符串编辑

问题描述
从键盘输入一个字符串（长度<=40个字符），并以字符 ’.’ 结束。编辑功能有：
1 D：删除一个字符，命令的方式为： D a 其中a为被删除的字符，例如：D s 表示删除字符 ’s’ ，若字符串中有多个 ‘s’，则删除第一次出现的。
2 I：插入一个字符，命令的格式为：I a1 a2 其中a1表示插入到指定字符前面，a2表示将要插入的字符。例如：I s d 表示在指定字符 ’s’ 的前面插入字符 ‘d’ ，若原串中有多个 ‘s’ ，则插入在最后一个字符的前面。
3 R：替换一个字符，命令格式为：R a1 a2 其中a1为被替换的字符，a2为替换的字符，若在原串中有多个a1则应全部替换。
在编辑过程中，若出现被改的字符不存在时，则给出提示信息。
输入格式
输入共两行，第一行为原串(以’.’结束)，第二行为命令（输入方式参见“问题描述” 。
输出格式
输出共一行，为修改后的字符串或输出指定字符不存在的提示信息。
样例输入
This is a book.
D s
样例输出
Thi is a book.
输入输出样例解释
命令为删去s，第一个在字符中出现的s在This中，即得到结果。

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s, ans;
    char c, ch, ch1, ch2;
    getline(cin, s);
    cin >> c;
    if (c == 'D') {
        cin >> ch;
        int i;
        for (i = 0; i < s.length(); i++) {
            if (s[i] == ch) {
                i++;
                break;
            } else {
                ans += s[i];
            }
        }
        for (; i < s.length(); i++)
            ans += s[i];
    } else if (c == 'I') {
        cin >> ch1 >> ch2;
        int i;
        for (i = s.length() - 1; i >= 0; i--) {
            ans = s[i] + ans;
            if (s[i] == ch1) {
                ans = ch2 + ans;
                i--;
                break;
            }
        }
        for (; i >= 0; i--)
            ans = s[i] + ans;
    } else {
        cin >> ch1 >> ch2;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == ch1) s[i] = ch2;
            ans += s[i];
        }
    }
    cout << ans << endl;
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s, ans;

char c, ch, ch1, ch2;

getline(cin, s);

cin >> c;

if (c == 'D') {

cin >> ch;

int i;

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

if (s[i] == ch) {

i++;

break;

} else {

ans += s[i];

}

for (; i < s.length(); i++)

ans += s[i];

} else if (c == 'I') {

cin >> ch1 >> ch2;

int i;

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

ans = s[i] + ans;

if (s[i] == ch1) {

ans = ch2 + ans;

i--;

break;

}

for (; i >= 0; i--)

ans = s[i] + ans;

} else {

cin >> ch1 >> ch2;

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

if (s[i] == ch1) s[i] = ch2;

ans += s[i];

}

cout << ans << endl;

return 0;

}

蓝桥杯 ADV-14 算法提高卡勒沃夫之弱水路三千(提高型)

问题描述
锦瑟年华谁与度莫问情归处只影向斜阳剑吼西风欲把春留驻
天涯芳草无归路回首花无数解语自销魂弱袂萦春尘缘不相误
……
在卡勒沃夫充满文学杀伤力的声音中，身处紫荆2号楼202B的四位远近高低各不同的室友纷纷回忆起了各自波澜起伏的过去，并对长在百草园，邻有百花谷的现状表达了各自的见解。
某Q：”…我小学就开窍了…她的父母说我很好，但是…今天又和北林的联系了…”
某X：”…差点就成了，结果到学校了…这个方法放假了我去对我的同桌用！…”
某W：”…”（千言万语不言中，有大量的故事等待考古）
某Z：”…为了来清华…咱们审美观不一样，不会抢…”
……
卡勒沃夫在这个不朽的夜话中搜集出了某人零散的历任女友资料，为了强迫某人将他出的题目的标程交出，现在卡勒沃夫需要一个能将这些零散信息整合起来的程序。伴随着雄壮委婉动人的音乐，身为程序设计快男（超女）的你降临了！卡勒沃夫正对着您做Orz状并请求着：”神牛啊~请施舍给我一段程序把~偶米头发~”。。
输入格式
第一行为一个不超过5的整数T，表示数据的组数。之后每组数据的一行为一个不超过100的整数n。之后n行每行有两个用单个空格隔开的字符串（每个字符串只有英文大小写字母，长度不超过10），为两位mm的名字。每行第一个mm先于第二个mm成为某人的女友。
在这里我们假装诅咒某人不会同时被两个或两个以上mm泡，某个mm抛弃了某人后不会再吃回头草，同时卡勒沃夫深邃的洞察力使得他收集到了充足的信息以确定某人女友的先后顺序。
在小数据组中出现的人物不超过13个
输出格式
输出T行，每行对应一组数据，并按照mm们从先到后成为某人女友的顺序输出她们的名字，各个名字间用一个空格隔开。
样例输入
2
2
RY Unknown
YSZ RY
3
tomorrow yestoday
tomorrow today
today yestoday
样例输出
YSZ RY Unknown
tomorrow today yestoday

分析：1.用girl映射到一组girl,为某个女孩映射到前面有哪些女孩
2.如果某个女孩前面没有女孩，并且没有被输出过，则输出当前女孩并标记，并且，将其从其他所有女孩的映射中擦除
3.重复2过程，直到所有女孩被输出～

#include <iostream>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
int main() {
    int k, n;
    cin >> k;
    while (k--) {
        string ans = "";
        cin >> n;
        map<string, set<string> > m;
        map<string, int> vis;
        for (int i = 0; i < n; i++) {
            string s1, s2;
            cin >> s1 >> s2;
            m[s1];
            m[s2].insert(s1);
        }
        while (1) {
            int check = 0;
            for (map<string, set<string> >::iterator i = m.begin(); i != m.end(); i++) {
                string girl = i->first;
                if (vis[girl] == 0 && m[girl].size() == 0) {
                    check = 1;
                    vis[girl] = 1;
                    for (map<string, set<string> >::iterator j = m.begin(); j != m.end(); j++) {
                        j->second.erase(girl);
                    }
                    ans = ans + girl + " ";
                    break;
                }
            }
            if (check == 0) break;
        }
        cout << ans.substr(0, ans.length() - 1) << endl;
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <set>

#include <map>

using namespace std;

int main() {

int k, n;

cin >> k;

while (k--) {

string ans = "";

cin >> n;

map<string, set<string> > m;

map<string, int> vis;

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

string s1, s2;

cin >> s1 >> s2;

m[s1];

m[s2].insert(s1);

}

while (1) {

int check = 0;

for (map<string, set<string> >::iterator i = m.begin(); i != m.end(); i++) {

string girl = i->first;

if (vis[girl] == 0 && m[girl].size() == 0) {

check = 1;

vis[girl] = 1;

for (map<string, set<string> >::iterator j = m.begin(); j != m.end(); j++) {

j->second.erase(girl);

}

ans = ans + girl + " ";

break;

}

if (check == 0) break;

}

cout << ans.substr(0, ans.length() - 1) << endl;

}

return 0;

}