2018年全国多校算法寒假训练营练习比赛（第二场）
A 吐泡泡
题目描述
小鱼儿吐泡泡，嘟嘟嘟冒出来。小鱼儿会吐出两种泡泡：大泡泡"O"，小泡泡"o"。
两个相邻的小泡泡会融成一个大泡泡,两个相邻的大泡泡会爆掉。
（是的你没看错，小气泡和大气泡不会产生任何变化的，原因我也不知道。）
例如:ooOOoooO经过一段时间以后会变成oO。
输入描述:
数据有多组，处理到文件结束。
每组输入包含一行仅有'O'与'o'组成的字符串。
示例1：
输入
ooOOoooO
输出
oO说明
自左到右进行合并
备注：
对于100%的数据，
字符串的长度不超过100。
思路： 用栈模拟吐泡泡合并的过程， 从左至右入栈， 入栈过程中： 如果栈为空直接入栈； 如果栈不为空先出栈顶， 拿栈顶元素和为入栈元素头比较， 都为 ‘O’ 则都不入栈， 都为 ‘o’ 则将为入栈元素头更改为 ‘O’；若出栈元素和队头元素不同， 则先入栈顶元素再队顶元素出队入栈。 如此重复直至队为空。
代码：
#include <bits/stdc++.h>
using namespace std;
int main(void) {
char a[110];
while (~scanf("%s", a)) {
int len = strlen(a), i = 0;
stack<char> st;
st.push(a[i++]);
while (i < len) {
bool flag = 1;
char ch;
while (flag) {
flag = 0;
if (st.empty()) {
st.push(a[i]);
i++;
break;
} else {
ch = st.top();
st.pop();
}
if (ch == 'o') {
if (a[i] == 'o') {
a[i] = 'O';
flag = 1;
} else {
st.push(ch);
st.push(a[i]);
i++;
}
} else {
if (a[i] == 'O') {
i++;
} else {
st.push(ch);
st.push(a[i]);
i++;
}
}
}
}
char ans[100] = {0};
int le = 0;
while (!st.empty()) {
ans[le++] = st.top();
st.pop();
}
for (int i = le-1; i >= 0; i--) {
printf("%c", ans[i]);
}
puts("");
}
return 0;
}
B TaoTao要吃鸡
题目描述：
Taotao的电脑带不动绝地求生，所以taotao只能去玩pc版的荒野行动了，
和绝地求生一样，游戏人物本身可以携带一定重量m的物品，装备背包
之后可以多携带h（h为0代表没有装备背包）重量的东西。玩了几天
taotao发现了一个BUG，当装备背包之后，如果可携带重量没有满，就
可以拿一个任意重的东西。（解释看样例）有一天taotao空降到了一个
奇怪的岛上，岛上有n件装备，每个装备都有重量Wi和威力值Vi,但taotao
不认识这些装备，所以他来求助你，挑选威力最大的装备，帮助他吃鸡。
输入描述：
本题有多组输入（小于10），当n=0时结束输入。
第一行输入n,m,h。n，m，h为整数，并且0<=n,m,h<=100，
接下来n行，每行输入第i个物品的物品的重量Wi和威力值Vi。0<=Wi,Vi<=100.
输出描述：
输出最大威力值， 每组输出一行。
示例1
输入
3 3 3
2 3
3 2
2 3
0
输出
8
说明
可携带的总重量为6，当拿了前两件装备，此时容量为5/6，还可以再拿第三件物品。
这道题题意想了很久：这两个背包（容量为m的背包简称m背包， 容量为h的背包简称h背包， 下同）容量是分开的还是合起来的呢？ 后来拉到页面下面看到了说明，突然想到直接把他两合并起来就好。
思路：这题明显是一个01背包变形， 分有没有h背包这两种情况讨论。当h背包为0时直接对m进行01背包， 当h不为0时， 总背包容量k = h + m - 1。 留下1个空间来存可溢出物品。 对k进行01背包并标记哪些物品已使用， 再加上未存物品价值最大的就是答案了。、
代码：
#include <iostream>
using namespace std;
struct Node{
int w, v, f;
}arr[110];
int n, m, h;
int dpp[200][5001];
int getMaxValue(int itemsSize, int maxWeight) {
for (int j = 1; j <= maxWeight; ++j) {
if (arr[itemsSize - 1].w <= j)
dpp[itemsSize - 1][j] = arr[itemsSize - 1].v;
for (int i = itemsSize - 2; i >= 0; --i) {
if (j < arr[i].w)
dpp[i][j] = dpp[i + 1][j];
else
dpp[i][j] = max(dpp[i + 1][j - arr[i].w] + arr[i].v, dpp[i + 1][j]);
}
}
return dpp[0][maxWeight];
}
void findSelectedItems(int itemsSize, int maxWeight) {
int k = maxWeight;
for (int i = 0; i < itemsSize; ++i) {
if (dpp[i][k]>dpp[i + 1][k]) {
arr[i].f = 1;
k -= arr[i].w;
}
}
}
int _01(int k) {
int dp[11000];
for (int i = 0; i < n; i++) {
for (int j = k; j >= arr[i].w; j--) {
dp[j] = max(dp[j], dp[j-arr[i].w]+arr[i].v);
}
}
return dp[k];
}
int main(void) {
while (cin >> n >> m >> h && n) {
for (int i = 0; i < n; i++) {
cin >> arr[i].w >> arr[i].v;
arr[i].f = 0;
}
if (h == 0) {
int ans = _01(m);
cout << ans << endl;
} else {
int hh = h + m - 1;
int ans = getMaxValue(n, hh);
findSelectedItems(n, hh);
int maxn = 0;
for (int i = 0; i < n; i++) {
if (!arr[i].f) {
if (arr[i].v > maxn) {
maxn = arr[i].v;
}
}
}
ans += maxn;
cout << ans << endl;
}
}
return 0;
}
D YB要打炉石
题目描述：
Wozuinb非常喜欢打炉石传说，但是菜的不行，所以他决定打
竞技场来练练手。系统按顺序给出n张卡牌，每张卡牌都有自
己的使用消耗a[i]，每次只给出一张，wozuinb可以选择或者
弃掉这张牌。每选择一张牌都会按选择顺序放在卡槽中，当
卡槽中放满30张即可组成一套套牌。Wozuinb希望自己的套牌的
消耗满足一个平滑的曲线，即30张卡牌都满足第i张卡牌的消耗
不小于第i-1张(i>1)。请你帮助wozuinb看一看，这些卡牌能不
能组成想要的套牌，如果能组成输出“yes”，如果不能输出“no”。
输入描述：
第一行输入一个整数n，0<n<100。
第二行输入一行数字a[i]，每个数字用空格隔开，代表第i张出现的卡牌的消耗。
输出描述：
输出一行，“yes”或“no”
思路：一道最长不下降子序列模板题， 拿了个nlogn的代码1A
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 110;
int a[maxn],dp[maxn], n;
int bsearch(int len, int x) {
int l = 0, r = len-1;
while(l <= r) {
int mid = (l+r) / 2;
if(x >= dp[mid-1] && x < dp[mid]) return mid;
else if(x < dp[mid-1]) r = mid-1;
else l = mid+1;
}
return l;
}
int LIS() {
dp[0] = a[0];
int len = 1;
int j;
for (int i = 1; i < n; i++) {
if(a[i] < dp[0]) j = 0;
else if(a[i] >= dp[len-1]) j = len++;
else j = bsearch(len, a[i]);
dp[j] = a[i];
}
return len;
}
int main(void) {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int len = LIS();
puts(len < 30 ? "no" : "yes");
return 0;
}
G 送分了QAQ
题目描述：
杭州人称傻乎乎的人为62，而嘟嘟家这里没有这样的习俗。
相比62，他那里的人更加讨厌数字38，当然啦，还有4这个
数字！所以啊，嘟嘟不点都不想见到包含38或者4的数字。
每次给出一个区间[n，m],你能找到所有令人讨厌的数字吗？
输入描述：
多组输入输出；
输入的都是整数对n、m（0<n≤m<1000000），
如果遇到都是0的整数对，则输入结束。
输出描述：
对于每次的输入
输出全部令人讨厌的数的个数
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int arr[N];
int main(void) {
int n, m, cnt = 0;
for (int i = 4; i <= 1000005; i++) {
string s = std::to_string(i);
if (s.find("38") != s.npos || s.find("4") != s.npos) {
cnt++;
}
arr[i] = cnt;
}
while (cin >> n >> m && n+m) {
cout << arr[m] - arr[n-1] << endl;
}
return 0;
}
E 小G有一个大树
题目描述：
小G想要把自己家院子里的橘子树搬到家门口（QAQ。。就当小G是大力水手吧）
可是小G是个平衡性灰常灰常差的人，他想找到一个这个橘子树的平衡点。
怎么描述这棵树呢。。。就把它看成由一个个节点构成的树吧。结点数就
代表树重。
输入描述：
多组数据输入输出，
第一行包含一个整数n（3<=n<=1000）代表树的结点的个数
以下n-1行描述（1-n）节点间的连接关系。
输出描述：
输出两个个整数 x，num 分别代表树的平衡点，和删除平衡点后最大子树的结点数（如果结点数相同输出编号小的）
分析：
与poj1655相似，是找树的重心的经典题目。
树的重心有下面几条常见性质：
定义1：找到一个点，其所有的子树中最大的子树节点数最少，那么这个点就是这棵树的重心。
定义2：以这个点为根，那么所有的子树（不算整个树自身）的大小都不超过整个树大小的一半。
性质1：树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么他们的距离和一样。
性质2：把两个树通过一条边相连得到一个新的树，那么新的树的重心在连接原来两个树的重心的路径上。
性质3：把一个树添加或删除一个叶子，那么它的重心最多只移动一条边的距离。
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 20;
#define INF 0x3f3f3f3f
vector<int> G[maxn];
int n, sonSize[maxn], sonMax[maxn];
int ans, num;
void init() {
ans = INF;
for (int i = 0; i < n+1; i++) {
G[i].clear();
}
}
void dfsSize(int u, int fa) {
sonSize[u] = 1;
sonMax[u] = 0;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (v != fa) {
dfsSize(v, u);
sonSize[u] += sonSize[v];
sonMax[u] = max(sonMax[u], sonSize[v]);
}
}
}
void dfsRoot(int r, int u, int fa) {
if (sonSize[r] - sonSize[u] > sonMax[u]) {
sonMax[u] = sonSize[r] - sonSize[u];
}
if (sonMax[u] < ans) {
ans = sonMax[u];
num = u;
}
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (v != fa) {
dfsRoot(r, v, u);
}
}
}
int main(void) {
while (cin >> n) {
init();
for (int i = 0; i < n-1; i++) {
int x, y;
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
dfsSize(1, -1);
dfsRoot(1, 1, -1);
cout << num << ' ' << ans << endl;
}
return 0;
}
H 了断局
题目描述：
既然是了断局了，大家就随便玩玩数字呗。
已知一个数列前10项分别是
{0, 1, 1, 2, 4, 7, 13, 24, 44, 81}
小G不满足呀：我要更多的数！！！不给就不让你们玩了。
小G会问你第n项是什么数字，请回答这个顽皮的孩子。
输入描述：
多组数据输入输出；
第一行输入一个整数n（1<=n<=50）
输出描述：
出数列中的第n个数。
思路：
普通递推， 签到水题
#include <iostream>
using namespace std;
int main(void) {
long long arr[100] = {0, 1, 1, 2};
for (int i = 4; i < 50; i++) {
arr[i] = arr[i-1] + arr[i-2] + arr[i-3];
}
int n;
while (cin >> n) {
cout << arr[n-1] << endl;
}
return 0;
}
———— 一篇拖了五天的解题报告
END