目录
P505 【基础】寻找祖先
给出充足的父子关系，请你编写程序找到某个人的最早的祖先。
规定每个人的名字都没有空格，且没有任意两个人的名字相同。最多可能有1000组父子关系，总人数最多可能达到50000人，家谱中的记载不超过30代。
分析
使用map<string,string> 建立父子关系
通过 u = p[u] 的方式查询 u 的父亲 p[u]
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e3+10;
map<string,string> p;
string find(string s) {
if(s!=p[s]) p[s]=find(p[s]);
return p[s];
}
int main() {
string s, father, child;
while(cin>>s) {
if(s=="$") break;
if(s[0]=='#') {
father = s.substr(1);
if(!p.count(father)) p[father] = father;
} else if(s[0]=='+') {
child = s.substr(1);
p[child] = father;
} else if(s[0]=='?') {
s.erase(0,1);
cout<<s<<" "<<find(s)<<endl;
}
}
return 0;
}
P541 【基础】吃西瓜（ watermelon ）
炎热的夏天来的可真快，小花猫和编程兔决定去买一个又大又甜的西瓜。可是小花和编程兔是两只非常奇怪的动物，都是偶数的爱好者，它们希望把西瓜切成两半后，每一部分的重量都是2的倍数公斤（大于 0）。
当然有编程兔在，它们很快就决定了买哪个瓜。小朋友你知道要不要买这个瓜吗？
分析
n是偶数，n/2是偶数，且n/2>1
也就是说 n = 2(a+b)，a≥1，b≥1
所以 n/2 = (a+b) ≥ 2
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=10;
int main(){
int t,n; cin>>t;
while(t--){
cin>>n;
int a = n/2;
cout<<(n%2==0 && n/2>=2 ? "YES":"NO")<<endl;
}
return 0;
}
P832 【提高】AtoB
给定一个 a进制数 c，将它变成 b进制并输出。
分析
模拟，一个比较好的代码量练习，想清楚过程，注意细节
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
const int N = 1e6 + 10;
string AtoB(string c, int a, int b) {
LL t = 0;
for (int i = 0; i < c.size(); i++) {
if (c[i] <= '9') t = t * a + c[i] - '0';
else t = t * a + c[i] - 'a' + 10;
}
string s;
if (t == 0) s = "0";
while (t) {
LL r = t % b;
if (r < 10) s.append(1, r + '0');
else s.append(1, r - 10 + 'a');
t /= b;
}
reverse(s.begin(), s.end());
s = "(" + s + ")" + to_string(b);
return s;
}
int main() {
LL a, b; string c;
cin >> c >> a >> b;
cout << AtoB(c, a, b) << endl;
return 0;
}
P841 【入门】s01串
s01串初始为"0"，按以下方式变换:
- 0变1
- 1变01
求n次变换后s01串
分析
可以使用递归解决
- 递归函数：f(s) --- 表示返回经过1次变换的字符串
- 递归关系：f(s) = f(s的前一半) + f(s的后一半)
- 递归边界：f("0")="1", f("1")="01".
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=300;
int n;
string s = "0";
string f(string s) {
if(s=="0") return "1";
if(s=="1") return "01";
int n = s.size(), k=n/2;
return f(s.substr(0, k)) + f(s.substr(k));
}
int main() {
cin>>n;
while(n--) s = f(s);
cout<<s;
return 0;
}