A - Many A+B Problems (abc288 a)
题目大意
给定\(A\), \(B\)，输出 \(A+B\)。
解题思路
范围不会爆\(int\)，直接做即可。
神奇的代码
#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 t;
cin >> t;
while(t--){
int a, b;
cin >> a >> b;
cout << a + b << '\n';
}
return 0;
}
B - Qualification Contest (abc288 b)
题目大意
给定排名前\(n\)的姓名，要求将排名前\(k\)的名字按字典序从小到达输出。
解题思路
范围不大，直接排序输出即可。
神奇的代码
#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<string> s(n);
for(auto &i : s)
cin >> i;
sort(s.begin(), s.begin() + k);
for(int i = 0; i < k; ++ i)
cout << s[i] << '\n';
return 0;
}
C - Don’t be cycle (abc288 c)
题目大意
给定一张无向图，要求删除一些边，使得没有环。
解题思路
根据定义，无环就是一棵树或者森林。
对原图跑一遍最小生成树，不在该树的边都是要删去的。
故答案就是总边数减去最小生成树的边数。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
class dsu {
public:
vector<int> p;
vector<int> sz;
int n;
dsu(int _n) : n(_n) {
p.resize(n);
sz.resize(n);
iota(p.begin(), p.end(), 0);
fill(sz.begin(), sz.end(), 1);
}
inline int get(int x) {
return (x == p[x] ? x : (p[x] = get(p[x])));
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
sz[y] += sz[x];
return true;
}
return false;
}
};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
dsu d(n);
int ans = 0;
for(int i = 0; i < m; ++ i){
int u, v;
cin >> u >> v;
-- u;
-- v;
if (d.unite(u, v))
++ ans;
}
cout << m - ans << '\n';
return 0;
}
D - Range Add Query (abc288 d)
题目大意
给定一个数组\(A\)和\(k\)，定义一个数组是好数组，当且仅当可经过若干次以下操作，使得数组全变成 \(0\)。
- 选定一个长度为\(k\)区间，令区间里的数都加上\(x\)， \(x\)是自己选的
有 \(q\)个询问，每个询问包括 \(l,r\)，问 \(A[l:r]\)是否是好数组。
解题思路
感觉这题难度\(>>E,F\)
因为涉及到区间加操作，一开始考虑差分数组，最终情况就是全部数为\(0\)。这样每次操作就只修改两个数，且观察到其下标对 \(k\)取模都是相同的。 然后考虑对原数组求一遍操作影响，看看子数组能否利用原数组的信息，思考了下感觉可行但代码复杂。
后来又退回思考原数组，因为是连续的区间加，假设\(sum[i]\)表示下标对 \(k\)取模为 \(i\)的所有数的和。那每次操作就是将 \(sum\)的所有数都 \(+x\)。那最终为 \(0\)的充分条件就是 \(sum\)的所有数都是一样的。反过来，也是必要条件。
因此对于每组询问，统计该序列的下标对\(k\)取模的所有数的和，看看是否为同一个数即可。
预处理原数组的下标取模前缀和，每组询问就两个前缀和相减就得到该区间的下标取模前缀和。因为\(k\)只有 \(10\)，所以每次询问的复杂度就是 \(O(k)\)
神奇的代码
#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<LL> a(n);
for(int i = 0; i < n; ++ i){
cin >> a[i];
if (i >= k)
a[i] += a[i - k];
}
int q;
cin >> q;
while(q--){
int l, r;
cin >> l >> r;
-- l;
-- r;
vector<LL> tmp(k);
for(int i = 0, pos = r; i < k; ++ i, pos --){
tmp[pos % k] = a[pos];
}
for(int i = 0, pos = l - 1; i < k && pos >= 0; ++ i, pos --){
tmp[pos % k] -= a[pos];
}
cout << (set<LL>(tmp.begin(), tmp.end()).size() == 1 ? "Yes" : "No") << '\n';
}
return 0;
}
E - Wish List (abc288 e)
题目大意
给定\(n\)个商品的价格 \(a_i\) ，标号\(1\)到 \(n\)。你要买\(m\)个物品，分别是 \(x_i\)。同时给定一个数组 \(c\)。购买规则为：
- 购买序号为\(i\)的商品，其标号是未买商品的第\(j\)小，其购入价格为 \(a_i+c_j\)。
你可以买不需要的物品。
问购买所需物品的最小花费。
解题思路
考虑暴力，发现不仅要确定购买哪些商品，还需要规定购买这些商品的顺序。不同顺序代价会不一样（购买同一间商品的\(c_j\)可能因购买顺序而不同）
再考虑暴力搜索过程中，当确定购买一个物品的代价时，需要知道一个物品的标号是目前第几小的。知道这两个状态后发现可以切割子问题，因此考虑\(dp\)。
一开始考虑 \(dp[i][j]\)表示前\(i\)个物品，其第\(i\)个物品的标号是第 \(j\)时的最小花费，转移就考虑该物品买或不买，当然如果是必须要买的物品就不能不买。但这个状态有问题，就是它规定了购买的顺序一定是标号从小到大的。而这显然不对。
那就不能设第j小这样的状态，但转移的话需要知道物品标号排名，所以考虑另一个状态，即 \(dp[i][j]\)表示前\(i\)个物品，已经购买了 \(j\)个物品的最小花费，因为知道了买了\(j\)个物品，就知道下一个要买的物品的标号是第几小的。
这状态看似和之前一样，但转移有点不同：当我决定买第\(i\)个物品时，已知状态是购买了\(j\)个物品，但不一定第 \(i\)个物品是购买的第 \(j+1\)件（它可以是之前购买的），因此其附加代价\(c\)的值可以是 \(c_{i-j+1},c_{i-j+2},\cdots ,c_{i}\)，选择不同的 \(c\)值 就是规定其购买的顺序。为了最小代价，那肯定是取最小的那个\(c\)。
因此转移式就是：
\[dp_{i,j} = \min( dp_{i - 1, j - 1} + a[i] + \min_{k \in [i - j + 1, i]} c_k, dp_{i - 1, j}) \]转移式涉及区间最小值，可以事先预处理或者转移时递增维护。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL inf = 1e18;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
vector<LL> a(n), c(n);
for(auto &i : a)
cin >> i;
for(auto &i : c)
cin >> i;
vector<int> must(n);
for(int i = 0; i < m; ++ i){
int x;
cin >> x;
-- x;
must[x] = 1;
}
vector<LL> dp(n + 1, inf);
dp[0] = 0;
for(int i = 0; i < n; ++ i){
vector<LL> tmp(n + 1, inf);
LL minn = inf;
for(int j = 0; j <= i; ++ j){
minn = min(minn, c[i - j]);
tmp[j + 1] = min(tmp[j + 1], dp[j] + a[i] + minn);
if (!must[i])
tmp[j] = min(tmp[j], dp[j]);
}
dp.swap(tmp);
}
LL ans = *min_element(dp.begin(), dp.end());
cout << ans << '\n';
return 0;
}
F - Integer Division (abc288 f)
题目大意
给定一个\(n\)位数\(s\)。 其有 \(n-1\)个切割点，一种切割方案包括若干个切割点，其代价是，切割后的所有数字的乘积。
问所有的\(2^n\) 种切割 方案的代价和。
解题思路
经典切分数字题，从爆搜的角度发现问题可切割，考虑\(dp\)。
设 \(dp[i]\)表示前 \(i\)个数的的所有切割方案的代价和，转移就是枚举最后一个切割点位置。
其转移式为（这里假设下标从\(1\)开始,\(dp[0] = 1\)）：
\[dp[i] = \sum_{j=0}^{i - 1} dp_{j} \times s[j+1:i] \]转移是\(O(n)\)，总的复杂度是 \(O(n^2)\)。暂且过不了，考虑优化转移。
考虑 \(dp[i]\)和\(dp[i+1]\)的转移式，发现两者非常相似，只需一点改动就可以转移。
\[dp[i] = \sum_{j=0}^{i - 1} dp_{j} \times s[j+1:i] \]\[dp[i + 1] = \sum_{j=0}^{i} dp_{j} \times s[j+1:i + 1] = \sum_{j=0}^{i} dp_{j} \times (10 \times s[j+1:i] + s[i + 1]) \]可以发现两者只有\(s[j+1:i]\)变成 \(s[j+1:i+1]\)的 ，相当于原来的转移和，乘以\(10\)，然后加上\(\sum_{j=0}^{i - 1} dp_{j}\)个\(s[i + 1]\)，再补上多的一项 \(dp_i \times s[i + 1]\)就变成\(i+1\)的转移和了。
因此转移可以优化成 \(O(1)\)，最终的复杂度就是 \(O(n)\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL mo = 998244353;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
string s;
cin >> n >> s;
LL ans = 0;
LL presum = 1;
for(int i = 0; i < n; ++ i){
int val = s[i] - '0';
ans = (ans * 10 + presum * val) % mo;
presum = (presum + ans) % mo;
}
cout << ans << '\n';
return 0;
}
G - 3^N Minesweeper (abc288 g)
题目大意
<++>
解题思路
<++>
神奇的代码
Ex - A Nameless Counting Problem (abc288 h)
题目大意
<++>
解题思路
<++>
神奇的代码
标签：AtCoder,Beginner,int,cin,long,288,tie,using,dp From： https://www.cnblogs.com/Lanly/p/17094101.html