A 万年沉睡的宝藏
题意:有一些岛和一些宝藏,都用字符串来描述,会有4个操作:给一个岛加一个宝藏,问这个岛有多少宝藏,某个宝藏是否在这个岛上,有多少岛上有至少一个宝藏。
用map存string和set
点击查看代码
void solve() {
int q;
std::cin >> q;
std::map<std::string, std::set<std::string> > mp;
while (q -- ) {
int op;
std::cin >> op;
if (op == 1) {
std::string s, t;
std::cin >> s >> t;
mp[s].insert(t);
} else if (op == 2) {
std::string s;
std::cin >> s;
int ans = mp.count(s) ? mp[s].size() : 0;
std::cout << ans << "\n";
} else if (op == 3) {
std::string s, t;
std::cin >> s >> t;
int ans = mp.count(s) ? mp[s].count(t) : 0;
std::cout << ans << "\n";
} else {
std::cout << mp.size() << "\n";
}
}
}
B 完美主义追求者
题意:给你a和b,求a个点的二叉树有多少个本质不同的,对b取模。
猜了一下是a的阶乘个,不会证明。
因为a很大,无法算阶乘,但注意b只有1e6,当a<b时暴力,否则a>=b时因为因子乘了一个b,模数肯定是0.
(赛时写的python,以为要用高精度算阶乘,结果wa了一发,后来发现正确做法后只需要随便改一下就行了,所以还是python代码)
点击查看代码
import math
a, b = map(int, input().split());
if a < b:
ans = 1
for i in range(1, a + 1):
ans = ans * i % b
print(ans)
else:
print(0)
C 异或与位移
题意:一个长度位n的数组a,和一个k,a的值在-k + 1到 k - 1之间,m个询问,给你一个二进制数y,它是由一个x变过来的:第i次变化中,如果\(a_i\) > 0就让x和x左移\(a_i\)位异或,否则和x右移\(a_i\)位异或。求这个x。
举个例子,对于一个二进制数abc(a, b, c等于0或1), 它左移2位等于110,那么就是c00 ^ abc = 110这是可以求出来abc的,先根据那几个0来确定后面几位,如何根据后面的数确定前面的数。右移一样的思路。
点击查看代码
void solve() {
int n, m, k;
std::cin >> n >> m >> k;
std::vector<int> a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
while (m -- ) {
std::string s;
std::cin >> s;
s = std::string(k - (int)s.size(), '0') + s;
bool flag = true;
for (int i = n - 1; i >= 0; -- i) {
std::string t(k, '?');
if (a[i] > 0) {
for (int j = k - a[i]; j < k; ++ j) {
t[j] = s[j];
}
for (int j = k - a[i] - 1; j >= 0; -- j) {
if (t[j + a[i]] == '?') {
flag = false;
break;
}
t[j] = ((t[j + a[i]] ^ s[j]) & 1) + '0';
}
} else {
for (int j = 0; j < -a[i]; ++ j) {
t[j] = s[j];
}
for (int j = -a[i]; j < k; ++ j) {
if (t[j + a[i]] == '?') {
flag = false;
break;
}
t[j] = ((t[j + a[i]] ^ s[j]) & 1) + '0';
}
}
if (t.find('?') != t.npos) {
flag = false;
}
if (!flag) {
break;
}
s = t;
// std::cout << s << "\n";
}
if (!flag) {
std::cout << -1 << "\n";
continue;
}
int p = s.find('1');
if (p == s.npos) {
std::cout << "0\n";
} else {
std::cout << s.substr(p) << "\n";
}
}
}
D 被拒绝在外的打卡
写麻了,每次wa一发后就发现了问题,前前后后de一个小时bug,最后还是没过,感觉应该还是思路的问题。
待补。