ABC267 复盘
[ABC267A] Saturday
思路解析
用一个 map 存下每个日期代表的数字，拿 \(6\) 减去即可
code
#include<bits/stdc++.h>
using namespace std;
map<string, int> mp;
void init() {
mp["Monday"] = 1;
mp["Tuesday"] = 2;
mp["Wednesday"] = 3;
mp["Thursday"] = 4;
mp["Friday"] = 5;
}
int main() {
init();
string str;
cin >> str;
cout << 5 - mp[str] + 1;
return 0;
}
[ABC267B] Split?
思路解析
先初始化每一列所包含的保龄球，然后遍历每两个列，判断是否符合标准。
错因
枚举边界开小力（悲
code
#include<bits/stdc++.h>
using namespace std;
string str;
vector<int> l[15];
void init() {
l[1].push_back(7);
l[2].push_back(4);
l[3].push_back(2);
l[3].push_back(8);
l[4].push_back(1);
l[4].push_back(5);
l[5].push_back(3);
l[5].push_back(9);
l[6].push_back(6);
l[7].push_back(10);
}
int main() {
init();
cin >> str;
str = " " + str;
if(str[1] == '1') {
cout << "No";
return 0;
}
for(int i = 1; i <= 6; i++) {
for(int j = i + 1; j <= 7; j++) {
bool flag = false;
for(auto it : l[i]) {
if(str[it] == '1') {
flag = true;
}
}
if(!flag) continue;
flag = false;
for(auto it : l[j]) {
if(str[it] == '1') {
flag = true;
}
}
if(!flag) continue;
flag = false;
for(int k = i + 1; k < j; k++) {
bool flag1 = true;
for(auto it : l[k]) {
if(str[it] == '1') {
flag1 = false;
}
}
flag = flag | flag1;
}
if(flag) {
cout << "Yes";
return 0;
}
}
}
cout << "No";
return 0;
}
[ABC267C] Index × A(Continuous ver.)
思路解析
可以先想到 \(O(n^2)\) 的暴力遍历每一个起点，其次发现可以用滑动窗口进行优化为 \(O(n)\)，以及因为有一个 \(i\times b^i\) 的操作，所以要用上前缀和。
code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lll __int128
const int N = 2e5 + 10;
ll n, m, a[N];
ll s[N];
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> a[i];
s[i] = s[i - 1] + a[i];
}
ll sum = 0;
for(int i = 1; i < m; i++) {
sum += (ll)(i + 1) * a[i];
}
ll ans = -4e18;
for(int i = m; i <= n; i++) {
sum -= a[i - m];
sum -= s[i - 1] - s[i - m];
sum += a[i] * m;
ans = max(ans, sum);
}
cout << ans;
return 0;
}
[ABC267D] Index × A(Not Continuous ver.)
思路解析
c 题的加强版，从字串变成了子序列，可以想到用 dp，\(f_{i,j}\) 代表前 \(i\) 个数中选了 \(j\) 个的最大值，状态转移则是要么不选，要么选两种情况，即为 \(f_{i, j} \gets \max(f_{i-1,j},f_{i-1,j-1}+a_i*j)\)。
code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2010;
int n, m;
ll a[N];
ll f[N][N];
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= n; j++) {
f[i][j] = -4e18;
}
}
for(int i = 0; i <= n; i++) {
f[i][0] = 0;
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= min(i, m); j++) {
if(j < i) {
f[i][j] = max(f[i][j], f[i - 1][j]);
}
f[i][j] = max(f[i][j], f[i - 1][j - 1] + a[i] * j);
}
}
cout << f[n][m];
return 0;
}
[ABC267E] Erasing Vertices 2
思路解析
可以发现想让答案最小可以用贪心，用一个单调队列存下每一个点如果现在被删除需要的代价是多少，从最小的开始选，因为每删除一个点与它连接的点的代价就会变得更小，所以每次都让代价最大的点最后删除就能使答案最小。
code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
ll n, m, a[N];
vector<ll> g[N];
ll s[N];
bool flag[N];
struct node {
ll u, sum;
bool operator < (const node &rhs) const {
return rhs.sum < sum;
}
};
priority_queue<node> q;
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
for(int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
s[u] += a[v];
s[v] += a[u];
}
for(int i = 1; i <= n; i++) {
q.push({i, s[i]});
}
ll ans = 0;
while(!q.empty()) {
ll u = q.top().u;
q.pop();
if(flag[u]) continue;
flag[u] = true;
ans = max(ans, s[u]);
ll sum = 0;
for(auto it : g[u]) {
if(!flag[it]) {
sum += a[it];
s[it] -= a[u];
q.push({it, s[it]});
}
}
}
cout << ans;
return 0;
}
[ABC267F] Exactly K Steps
思路解析
根据树上直径的性质可以发现对于任何一个点，距离它最远的点一定是直径的两个端点中的其中一个，可以用反证法证明。于是只要判断当前点和两个端点的距离即可判断是否存在。至于找到距离当前点 \(k\) 的点，我们可以使用 dfs 序的特征，也就是一个层数 \(dep_u\) 节点的 \(k\) 层父亲节点的编号一定是最后一个被标为 \(dep_u - k\) 的节点，因为 dfs 永远先遍历父亲节点，后遍历子节点。最后根据以上方法进行 dfs 即可。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n;
vector<int> g[N];
vector<int> que[N];
int k[N], ans[N];
bool vis[N];
int d[N];
int len = 0;
void dfs(int u, int fa, int dep) {
d[dep] = u;
for(auto it : que[u]) {
if(dep >= k[it]) {
ans[it] = d[dep - k[it]];
}
}
len = max(len, dep);
for(auto it : g[u]) {
if(it != fa) {
dfs(it, u, dep + 1);
}
}
}
int main() {
cin >> n;
for(int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
int q, u;
cin >> q;
for(int i = 1; i <= q; i++) {
cin >> u >> k[i];
que[u].push_back(i);
}
for(int turn = 0; turn <= 2; turn++) {
int pos = d[len];
len = 0;
if(turn == 0) {
pos = 1;
}
dfs(pos, 0, 0);
}
for(int i = 1; i <= q; i++) {
if(ans[i] == 0) {
cout << "-1\n";
}
else {
cout << ans[i] << "\n";
}
}
return 0;
}
[ABC267G] Increasing K Times
思路解析
虽是紫题，但码量很小，不过依然有非常大的思考量。其实我们可以把题目转换成排列 \(a\) 使得 \(a\) 成为一个有 \(k+1\) 个连续不上升子串的数列，原因是每两个相邻的连续上升子串之间都会有一个 \(a_{i}<a_{i+1}\)，因此需要 \(k+1\) 个连续不上升子串。可以想到 dp。（你会发现越到 abc 的后面基本上全是 dp 套路）。由于 \(a\) 的顺序不重要，不妨先排序。设 \(f_{i,j}\) 表示前 \(i\) 个数的排列形成 \(j\) 个连续不上升字串的方案数。这时就需要分类讨论了：
-
第一种 \(a_i\) 加在所有数的开头，由于这个点肯定是目前最大（大于等于其他点），肯定能与开头的第一个上坡连在一起，换句话说，就是这种情况下连续不上升字串的数量是不变的。
-
第二种 \(a_i\) 加在中间。由于当前点的加入使得有一个连续的不上升序列分成了两部分，因此连续不上升字串的数量加一。
但是有一种情况是之前的数列中可能会有重复的值，这时如果有相等的点那么我们可以有多种可能。
-
第一种是加入 \(a_i\) 后连续不上升字串的数量不变，由于一个相同的点后面再跟上一个相同的点 \(j\) 将不会改变，而在每一个连续不上升字串的开头都可以再添加一个 \(a_i\)，那么此时 \(a_i\) 就可以放在 \(bck_{a_i} + j\) 个位置上（\(bck_{a_i}\) 代表到 \(i\) 时与 \(a_i\) 相等的点个数），同时连续不上升字串的数量不变。所以，我们只需要实时维护 \(bck\) 即可。
-
第二种是加入 \(a_i\) 后会改变连续不上升字串的数量。方案数就应该是 \(i-j+1-bck_{a_i}\)，因为 \(i-j+1\) 是正常空位的个数，而有 \(bck_{a_i}\) 个空位因为无法增加连续不上升字串的数量所以不能放，因此方案数就是 \(i-j+1-bck_{a_i}\)。
最后切记开 long long
code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5010;
const ll mod = 998244353;
int n, k;
ll a[N], f[N][N];
ll bck[N];
int main() {
cin >> n >> k;
k++;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
f[0][0] = 1;
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= min(i, k); j++) {
f[i][j] += f[i - 1][j] * (j + bck[a[i]]);
f[i][j] %= mod;
if(j >= 1) {
f[i][j] += f[i - 1][j - 1] * ((ll)i - j + 1 - bck[a[i]]);
f[i][j] %= mod;
}
}
bck[a[i]]++;
}
cout << f[n][k];
return 0;
}