A - αlphabet (abc171 a)
题目大意
给定一个字母，其大写字母则输出A，否则输出 a。
解题思路
isupper函数或者在'A'与Z之间即为大写字母。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
string s;
cin >> s;
if (isupper(s[0]))
cout << "A\n";
else
cout << "a\n";
return 0;
}
B - Mix Juice (abc171 b)
题目大意
给定\(n\)个数，问前 \(k\)小的数的和是多少。
解题思路
sort+accumulate即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, k;
cin >> n >> k;
vector<int> p(n);
for(auto &i : p)
cin >> i;
sort(p.begin(), p.end());
cout << accumulate(p.begin(), p.begin() + k, 0) << '\n';
return 0;
}
C - One Quadrillion and One Dalmatians (abc171 c)
题目大意
给定一个数\(n\)，将其转换成指定进制，从\(1\)开始，依次
- 'a', 'b', ..., 'z', 'aa', 'ab', ..., 'az', 'ba', 'bb', ..., 'bz', ..., 'za', 'zb', ..., 'zz', 'aaa', 'aab', ..., 'aaz', 'aba', 'abb', ..., 'abz', ..., 'zzz', 'aaaa', ...
解题思路
该进制很像\(26\)进制，但还有一点点区别，就是一开始其实是0000，然后变成000a，即一开始某位的循环是\(27\)个数，之后变成\(26\)个数。可以某位需要\(1\)的代价启动（n--），然后 \(26\)一循环。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
char name[26];
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
LL n;
cin >> n;
name[0] = 'a';
for(int i = 1; i < 26; ++ i){
name[i] = name[i - 1] + 1;
}
string nn;
while(n){
-- n;
nn += name[n % 26];
n /= 26;
}
reverse(nn.begin(), nn.end());
cout << nn << '\n';
return 0;
}
D - Replacing (abc171 d)
题目大意
给定一个有\(n\)个数的数组 \(A\)，依次进行以下 \(Q\)次操作，每次操作如下：
- 给定 \(B\)， \(C\)，要求将 \(A\)中的 所有\(B\)更改为 \(C\)。
输出每次操作后数组 \(A\)的值。
解题思路
维护cnt[i]表示数\(i\)出现的次数，每次操作更改对应 的 cnt值即可，这样每次操作的复杂度为\(O(1)\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 1e5 + 8;
LL ans;
int n, q;
int cnt[N];
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 0; i < n; ++ i){
int x;
cin >> x;
ans += x;
cnt[x] ++;
}
cin >> q;
for(int i = 1; i <= q; ++ i){
int b, c;
cin >> b >> c;
ans -= 1ll * b * cnt[b];
ans += 1ll * c * cnt[b];
cnt[c] += cnt[b];
cnt[b] = 0;
cout << ans << '\n';
}
return 0;
}
E - Red Scarf (abc171 e)
题目大意
给定一个有\(n\)个数的数组\(a\)。其中 \(n\)是偶数。
要求构造一个有\(n\)个数的数组\(N\)，满足\(a_i\)为 \(n_j(j \neq i)\)的数的异或。
解题思路
因为\(n\)是偶数，将所有\(a_i\)异或起来，得到的值是所有\(n_i\)的异或和 \(sum\)。
此时 \(n_i = sum \oplus a_i\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector<int> a(n);
int sum = 0;
for(auto &i : a){
cin >> i;
sum ^= i;
}
for(auto &i : a){
cout << (sum ^ i) << ' ';
}
return 0;
}
F - Strivore (abc171 f)
题目大意
给定一个包含小写字母的字符串\(s\)和一个数 \(k\)。要求执行 \(k\)次操作：
- 每次操作在任意位置插入任意一个小写字母
问最终得到的字符串的种类数。
解题思路
考虑如何构造这样的字符串，比如\(s\)是 ab，一个朴素想法就是考虑_a_b_，这三个位置分别插入什么字母。
但这样会算重，比如_a_b_可以变成AaAbB或者aAAbB，其中大写字母是插入的。事实上这两个字符串是一样的，它们对答案只有\(1\)的贡献，而上述构造会得到 \(2\)的贡献。
因此对于诸如 \(aaabb\)这样的字符串，可以存在诸多插入方式得到， 但由于仅贡献一次，因此我们需要规定该字符串仅由一种插入方式得到。
对于一个字符串aaabb，我们要判断它能不能由ab得到，一个朴素的想法就是贪心匹配，即匹配ab的第一个a，然后在这之后匹配第一个b，能匹配成功就可以得到。这样的判断方法其实就对应了一个插入方式，即一个字符串仅由原字符串s通过一种指定的插入方式得到，仅算上一次贡献，这样就不会算重。而这种插入方式即为：
- 在
ab的第一个a出现之前，不能有字母a - 在第一个
a出现之后，第一个b出现之前，不能有字母b - 依次类推
- 当匹配完后，剩下位置的字母是任意的。
即
\[\underbrace{???????}_{除s[1]外25个字母任意填}s[1]??...???\underbrace{????????}_{除s[n-1]外25个字母任意填}s[n-1]\underbrace{????????}_{除s[n]外25个字母任意填}s[n]\underbrace{??????}_{26个字母任意填} \]因此我们枚举剩下的位置数\(i\)，它们的填法是 \(26^i\)，然后是 \(s\)的最后一个字符。然后前面的空位选 \(|s|-1\)个作为原字符串的字符，方案数为\(\tbinom{k+|s|-i-1}{|s|-1}\)，然后这之间的位置的填法，都有一个字母不能填，故其方案数为\(25^{k-i}\)
因此答案为\(\sum_{i=0}^{k} 26^i \times \tbinom{k+|s|-i-1}{|s|-1} \times 25^{k-i}\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL mo = 1e9 + 7;
const LL M = 2e6 + 8;
long long qpower(long long a, long long b){
long long qwq = 1;
while(b){
if (b & 1)
qwq = qwq * a % mo;
a = a * a % mo;
b >>= 1;
}
return qwq;
}
long long inv(long long x){
return qpower(x, mo - 2);
}
LL invf[M], fac[M] = {1};
void fac_inv_init(LL n, LL p) {
FOR (i, 1, n)
fac[i] = i * fac[i - 1] % p;
invf[n - 1] = inv(fac[n - 1]);
FORD (i, n - 2, -1)
invf[i] = invf[i + 1] * (i + 1) % p;
}
inline LL C(LL n, LL m) { // n >= m >= 0
return n < m || m < 0 ? 0 : fac[n] * invf[m] % mo * invf[n - m] % mo;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int k;
string s;
cin >> k >> s;
int n = s.size();
fac_inv_init(M, mo);
LL ans = 0;
LL first = 1;
LL last = qpower(25, k);
LL inv25 = inv(25);
for(int i = 0; i <= k; ++ i){
ans = (ans + first * C(n + k - i - 1, n - 1) % mo * last % mo) % mo;
first = first * 26 % mo;
last = last * inv25 % mo;
}
cout << ans << '\n';
return 0;
}
标签：AtCoder,Beginner,int,LL,cin,long,tie,using,171 From： https://www.cnblogs.com/Lanly/p/17040311.html