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

蓝桥杯 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;

}

蓝桥杯 ALGO-89 算法训练字符删除

问题描述
编写一个程序，先输入一个字符串str（长度不超过20），再输入单独的一个字符ch，然后程序会把字符串str当中出现的所有的ch字符都删掉，从而得到一个新的字符串str2，然后把这个字符串打印出来。
输入格式：输入有两行，第一行是一个字符串（内部没有空格），第二行是一个字符。
输出格式：经过处理以后的字符串。
输入输出样例
样例输入
123-45-678
–
样例输出
12345678

#include <iostream>
using namespace std;
int main() {
    string s;
    char c;
    getline(cin, s);
    cin >> c;
    for (int i = 0; i < s.size(); i++)
        if (s[i] != c) cout << s[i];
    cout << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

string s;

char c;

getline(cin, s);

cin >> c;

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

if (s[i] != c) cout << s[i];

cout << endl;

return 0;

}

蓝桥杯 ALGO-115 算法训练和为T

问题描述
从一个大小为n的整数集中选取一些元素，使得它们的和等于给定的值T。每个元素限选一次，不能一个都不选。
输入格式
第一行一个正整数n，表示整数集内元素的个数。
第二行n个整数，用空格隔开。
第三行一个整数T，表示要达到的和。
输出格式
输出有若干行，每行输出一组解，即所选取的数字，按照输入中的顺序排列。
若有多组解，优先输出不包含第n个整数的；若都包含或都不包含，优先输出不包含第n-1个整数的，依次类推。
最后一行输出总方案数。
样例输入
5
-7 -3 -2 5 9
0
样例输出
-3 -2 5
-7 -2 9
2
数据规模和约定
1<=n<=22
T<=maxlongint
集合中任意元素的和都不超过long的范围

分析：1.数据规模在n<=22，递归搜索不会超时，每个数字可选择拿或不拿
2.搜索为了保证符合题目顺序，从后向前搜索～

#include <iostream>
#include <vector>
using namespace std;
vector<int> v, ans;
int n, k, cnt;
void dfs(int num, int sum) {
    if (num == -1) {
        if (sum == k && ans.size() > 0) {
            for (int i = ans.size() - 1; i >= 0; i--) {
                if (i != 0) {
                    printf("%d ", ans[i]);
                } else {
                    printf("%d\n", ans[i]);
                }
            }
            cnt++;
        }
    } else {
        dfs(num - 1, sum);
        ans.push_back(v[num]);
        dfs(num - 1, sum + v[num]);
        ans.pop_back();
    }
}
int main() {
    scanf("%d", &n);
    v.resize(n);
    for (int i = 0; i < n; i++)
        scanf("%d", &v[i]);
    scanf("%d", &k);
    dfs(n - 1, 0);
    printf("%d\n", cnt);
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

vector<int> v, ans;

int n, k, cnt;

void dfs(int num, int sum) {

if (num == -1) {

if (sum == k && ans.size() > 0) {

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

if (i != 0) {

printf("%d ", ans[i]);

} else {

printf("%d\n", ans[i]);

}

cnt++;

}

} else {

dfs(num - 1, sum);

ans.push_back(v[num]);

dfs(num - 1, sum + v[num]);

ans.pop_back();

}

int main() {

scanf("%d", &n);

v.resize(n);

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

scanf("%d", &v[i]);

scanf("%d", &k);

dfs(n - 1, 0);

printf("%d\n", cnt);

return 0;

}

蓝桥杯 ADV-113 算法提高 c++_ch02_02

使用Switch语句编写一个模拟简单计算器的程序。依次输入两个整数和一个字符，并用空格隔开。如果该字符是一个“+”，则打印和；如果该字符是一个“-”，则打印差；如果该字符是一个“*”,则打印积；如果该字符是“/”，则打印商；如果该字符是一个“%”，则打印余数。打印结果后输出一个空行。

#include <iostream>
using namespace std;
int main() {
    int a, b, ans;
    char c;
    cin >> a >> b >> c;
    if (c == '+') ans = a + b;
    else if (c == '-') ans = a - b;
    else if (c == '*') ans = a * b;
    else if (c == '%') ans = a % b;
    else if (c == '/') ans = a / b;
    cout << ans;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b, ans;

char c;

cin >> a >> b >> c;

if (c == '+') ans = a + b;

else if (c == '-') ans = a - b;

else if (c == '*') ans = a * b;

else if (c == '%') ans = a % b;

else if (c == '/') ans = a / b;

cout << ans;

return 0;

}

蓝桥杯 PREV-8 历届试题买不到的数目

问题描述
小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。
小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。
你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。
输入格式
两个正整数，表示每种包装中糖的颗数(都不多于1000)
输出格式
一个正整数，表示最大不能买到的糖数
样例输入1
4 7
样例输出1
17
样例输入2
3 5
样例输出2
7

分析：完全背包，且weight==value dp[i]为空间为i时能装的最大value, 从后往前找，如果dp[i]<i则找到该数字～

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int main() {
    int t, n = 0, dp[100001] = {0}, maxn = 100000;
    vector<int> w(1), v(1);
    while (cin >> t) {
        w.push_back(t);
        v.push_back(t);
        n++;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = w[i]; j <= maxn; j++) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    dp[0] = -1;
    for (int i = maxn; i >= 0; i--) {
        if (dp[i] < i) {
            cout << i;
            return 0;
        }
    }
    return 0;
}

#include <iostream>

#include <cmath>

#include <vector>

using namespace std;

int main() {

int t, n = 0, dp[100001] = {0}, maxn = 100000;

vector<int> w(1), v(1);

while (cin >> t) {

w.push_back(t);

v.push_back(t);

n++;

}

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

for (int j = w[i]; j <= maxn; j++) {

dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

}

dp[0] = -1;

for (int i = maxn; i >= 0; i--) {

if (dp[i] < i) {

cout << i;

return 0;

}

return 0;

}

蓝桥杯 ALGO-114 算法训练黑白无常

问题描述
某寝室的同学们在学术完之后准备玩一个游戏：游戏是这样的，每个人头上都被贴了一张白色或者黑色的纸，现在每个人都会说一句话“我看到x张白色纸条和y张黑色的纸条”，又已知每个头上贴着白色纸的人说的是真话、每个头上贴着黑色纸的人说的是谎话，现在要求你判断哪些人头上贴着的是白色的纸条，如果无解输出“NoSolution.”；如果有多组解，则把每个答案中贴白条的人的编号按照大小排列后组成一个数（比如第一个人和第三个人头上贴着的是白纸条，那么这个数就是13；如果第6、7、8个人都贴的是白纸条，那么这个数就是678）输出最小的那个数（如果全部都是黑纸条也满足情况的话，那么输出0）
输入格式
第一行为一个整数n，接下来n行中的第i行有两个整数x和y，分别表示第i个人说“我看到x张白色纸条和y张黑色的纸条”。
输出格式
一行。如果无解输出“NoSolution.”。否则输出答案中数值（具体见问题描述）最小的那个，如果全部都是黑纸条也满足情况的话，那么输出0
样例输入
2
1 0
1 0
样例输出
0
样例输入
5
3 1
0 4
1 3
4 0
1 3
样例输出
35
数据规模和约定
n<=8

分析：1.枚举所有人的黑白字条情况，判断当前情况是否可能存在，把所有可能情况收集起来输出最小的
2.注意每人看不到自己头上的字条哦～

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> ansv;
pair<int, int> v[10];
int n, k, cnt, a[10];
void dfs(int num) {
    if (num == 0) {
        int white = 0, black = 0, ans = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] == -1) black++;
            if (a[i] == 1) white++;
        }
        for (int i = 1; i <= n; i++) {
            if (a[i] == 1 && (v[i].first != white-1 || v[i].second != black)) return;
            if (a[i] == -1 && (v[i].first == white && v[i].second == black-1)) return;
        }
        for (int i = 1; i <= n; i++) 
            if (a[i] == 1) ans = ans * 10 + i;
        ansv.push_back(ans);
    } else {
        a[num] = -1;
        dfs(num - 1);

        a[num] = 1;
        dfs(num - 1);
    }
}
int main() {
    scanf("%d", &n);;
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &v[i].first, &v[i].second);
    dfs(n);
    sort(ansv.begin(), ansv.end());
    printf("%d\n", ansv[0]);
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

vector<int> ansv;

pair<int, int> v[10];

int n, k, cnt, a[10];

void dfs(int num) {

if (num == 0) {

int white = 0, black = 0, ans = 0;

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

if (a[i] == -1) black++;

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

}

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

if (a[i] == 1 && (v[i].first != white-1 || v[i].second != black)) return;

if (a[i] == -1 && (v[i].first == white && v[i].second == black-1)) return;

}

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

if (a[i] == 1) ans = ans * 10 + i;

ansv.push_back(ans);

} else {

a[num] = -1;

dfs(num - 1);

a[num] = 1;

dfs(num - 1);

}

int main() {

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

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

scanf("%d%d", &v[i].first, &v[i].second);

dfs(n);

sort(ansv.begin(), ansv.end());

printf("%d\n", ansv[0]);

return 0;

}