A - Range Swap (abc286 a)
题目大意
给定长度为\(n\)的数组 \(a\)和 \(p,q,r,s\)，交换 \(a[p..q]\)和 \(a[r..s]\)并输出交换后的数组 \(a\)。
解题思路
模拟即可。
神奇的代码
#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, p, q, r, s;
cin >> n >> p >> q >> r >> s;
vector<int> a(n);
for(auto &i : a)
cin >> i;
-- p;
-- q;
-- r;
-- s;
for(int i = p, j = r; i <= q; ++ i, ++ j)
swap(a[i], a[j]);
for(auto &i : a)
cout << i << ' ';
cout << '\n';
return 0;
}
B - Cat (abc286 b)
题目大意
给定一个字符串，将其中的\(na\)替换成 \(nya\)
解题思路
模拟即可。
神奇的代码
#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;
string s;
cin >> n >> s;
string ans;
for(int i = 0; i < n; ++ i){
if (s[i] != 'n')
ans += s[i];
else if (i + 1 < n && s[i + 1] == 'a'){
ans += "nya";
++ i;
}else
ans += s[i];
}
cout << ans << '\n';
return 0;
}
C - Rotate and Palindrome (abc286 c)
题目大意
给定一个字符串\(s\)，以及 \(A,B\)。可进行如下两种操作若干次：
- 花费 \(A\)的代价，将字符串\(s\)的首字母移动到末尾
- 花费 \(B\)的代价，将字符串\(s\)的某一位字母替换成任意字母
问将字符串\(s\)变成回文串的最小代价。
解题思路
观察到这两种操作的执行顺序是可以交换且不影响最终结果的，于是可以先枚举执行第一种操作的次数，之后计算操作二的代价，两者的和取最小值即可。复杂度是\(O(n^2)\)
神奇的代码
#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, a, b;
cin >> n >> a >> b;
string s;
cin >> s;
LL ans = 1e18 + 7;
auto solve = [&](int st){
int ed = (st - 1 + n) % n;
LL tmp = 0;
for(int cnt = n / 2; cnt; st = (st + 1) % n, ed = (ed - 1 + n) % n, -- cnt)
tmp += 1ll * (s[st] != s[ed]) * b;
return tmp;
};
for(int i = 0; i < n; ++ i){
ans = min(ans, 1ll * i * a + solve(i));
}
cout << ans << '\n';
return 0;
}
D - Money in Hand (abc286 d)
题目大意
现在有\(n\)种硬币，其中第 \(i\)种硬币价值 \(a_i\)元，有 \(b_i\)个。
给定\(x\)，问这些硬币能不能凑出 \(x\)元。
解题思路
范围都不大，设\(dp[i]\)表示能否凑出 \(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, x;
cin >> n >> x;
vector<int> dp(x + 1, 0);
dp[0] = 1;
for(int i = 0; i < n; ++ i){
int a, b;
cin >> a >> b;
for(int j = x; j >= a; -- j){
for(int k = 1; k <= b; ++ k)
if (j >= k * a)
dp[j] |= dp[j - k * a];
}
}
if (dp[x])
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
E - Souvenir (abc286 e)
题目大意
给定一张有向图，边权均为\(1\)，给定点权。
有 \(q\)个询问，每个询问问从\(x\)点到 \(y\)点，其边权和最小是多少，在最小的前提下，点权和最大是多少。
不能到达则输出 Impossible。
解题思路
点数只有\(300\)，边权和即距离，对原图跑一遍 floyd即可。后者其实还是可以看成是个距离，在更新边权和时顺便更新点权和即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int inf = 1e9 + 7;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector<int> a(n);
for(auto &i : a)
cin >> i;
vector<string> s(n);
for(auto &i : s){
cin >> i;
}
vector<vector<int>> dis(n, vector<int>(n, inf));
vector<vector<LL>> value(n, vector<LL>(n, 0));
for(int i = 0; i < n; ++ i)
for(int j = 0; j < n; ++ j){
if (i == j){
dis[i][j] = 0;
value[i][j] = a[i];
} else if (s[i][j] == 'Y'){
dis[i][j] = 1;
value[i][j] = a[i] + a[j];
}
}
for(int k = 0; k < n; ++ k)
for(int i = 0; i < n; ++ i)
for(int j = 0; j < n; ++ j){
if (dis[i][j] > dis[i][k] + dis[k][j]){
dis[i][j] = dis[i][k] + dis[k][j];
value[i][j] = value[i][k] + value[k][j] - a[k];
}else if (dis[i][j] == dis[i][k] + dis[k][j]){
value[i][j] = max(value[i][j], value[i][k] + value[k][j] - a[k]);
}
}
int q;
cin >> q;
while(q--){
int u, v;
cin >> u >> v;
-- u;
-- v;
if (dis[u][v] == inf)
cout << "Impossible" << '\n';
else
cout << dis[u][v] << ' ' << value[u][v] << '\n';
}
return 0;
}
F - Guess The Number 2 (abc286 f)
题目大意
交互题。
你需要猜到对方的\(n\)的大小，你仅可做一件事：
- 指定\(m\)，输出一个长度为 \(m\) 的数组\(a\)。其中 \(1 \leq m \leq 110, 1 \leq a_i \leq m\)
- 对方根据数组 \(a\)，输出一个数组 \(b\)
- 你根据该数组 \(b\)，得出 \(n\)的值。
生成数组 \(b\)的方式为：
- 假想一个有\(m\)个点的图，其中点\(i\)连一条有向边到点\(a_i\)。
- \(b_i\) 的值为：从\(i\)号点出发，走 \(n\)条边到达的点的编号。
\(n \leq 10^9\)
解题思路
对于一个大小为\(a\)的环，走一圈需要\(a\)的代价，因此从对应的数组\(b\)可以得知\(n \% a\)的值是多少。
这样从若干个环我们可以得到一组形如 \(n \equiv r_i, \mod m_i\)的同余方程。
因此我们就要构造一组相互互质\(m_i\)，满足 \(\sum m_i \leq 110\)，且 \(\prod m_i \geq 10^9\)，由中国剩余定理可知在\(M = \prod m_i\)内存在唯一解，且该解可以构造出来。
通过手玩可以构造出一组数组\(M\)： \(4,9,5,7,11,13,17,19,23\)，其和为\(108 < 110\)，其乘积为\(1338557220 > 10^9\)
通过该数组\(M\)（每个元素就是一个环的大小了）可以构造出对应的数组\(a\)。然后根据数组\(b\)计算得到每个余数 \(r_i\)，然后由中国剩余定理解出 \(n\)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
vector<LL> a {4, 9, 5, 7, 11, 13, 17, 19, 23};
LL exgcd(LL a, LL b, LL &x, LL &y) {
if (b == 0) { x = 1; y = 0; return a; }
LL ret = exgcd(b, a % b, y, x);
y -= a / b * x;
return ret;
}
LL CRT(vector<LL>& r, vector<LL>& mod) {
LL n = 1, ans = 0;
int k = r.size();
for (int i = 0; i < k; i++) n = n * mod[i];
for (int i = 0; i < k; i++) {
LL m = n / mod[i], b, y;
exgcd(m, mod[i], b, y);
ans = (ans + r[i] * m * b % n) % n;
}
return (ans % n + n) % n;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int sum = accumulate(a.begin(), a.end(), 0);
cout << sum << '\n';
int st = 1;
vector<LL> out;
for(auto &i : a){
int ba = st;
++ st;
for(int j = 0; j < i - 1; ++ j){
out.push_back(st);
++ st;
}
out.push_back(ba);
}
for(auto &i : out)
cout << i << ' ';
cout << endl;
vector<int> b(sum);
for(auto &i : b){
cin >> i;
}
st = 0;
vector<LL> r;
for(auto &i : a){
auto pos = find(out.begin() + st, out.begin() + st + i, b[st]);
r.push_back(pos - (out.begin() + st) + 1);
st += i;
}
cout << CRT(r, a) << endl;
return 0;
}
G - Unique Walk (abc286 g)
题目大意
<++>
解题思路
<++>
神奇的代码
Ex - Don't Swim (abc286 h)
题目大意
<++>
解题思路
<++>
神奇的代码
标签：AtCoder,cout,Beginner,int,LL,cin,st,++,286 From： https://www.cnblogs.com/Lanly/p/17064072.html