A 回声
将连续的字母和连字符视为同一个单词
bool isWordChar(char c) {if ((c >= 'a' && c <= 'z') ||(c >= 'A' && c <= 'Z') ||c == '-') {return true;}return false;
}
从头到尾遍历，并存单词即可
int main() {string s;cin>>s;vector<string> words;string cur;for (int i = 0; i < (int)s.size(); ++i) {char c = s[i];if (isWordChar(c)) {cur += c;} else {if (!cur.empty()) {words.push_back(cur);cur.clear();}}}if (!cur.empty()) {words.push_back(cur);}int n = words.size();int start = n - 3;if (start < 0) start = 0;for (int i = start; i < n; ++i) {if (i > start) cout << ' ';cout << words[i];}cout << '\n';return 0;
}
B 挂谷集
读题可知需要求凸集面积，也就是给定正三角形的高求面积。
最初的数据范围会使double（八位浮点）损失精度，已修改
void solve(){double x; scanf("%lf",&x);printf("%.2lf",x*x/sqrt(3));
}
C 身份证校验
根据题目进行模拟即可，实现方法有多种，此处给出一种
void solve(){int ans=0,arr[]={7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2};string ID,map="10X98765432";cin>>ID;for(int i=0; i<17; i++){ans += ( ID[i] - '0' ) * arr[i];}cout << ID << map[ans%11] <<'\n';
}
D Starlight
根据题意，判断两边的大小关系，可以判断点是否在函数所包围封闭图形内部。此处需要注意正负号，因此可以统一加绝对值来处理。
void solve() {double x, y, a;cin>> x >> y >> a;const double eps = 1e-6;double left = pow(fabs(x), 2.0 / 3.0) + pow(fabs(y), 2.0 / 3.0);double right = pow(a, 2.0 / 3.0);double diff = left - right;if (fabs(diff) < eps) {cout << "Non Non Da Yo\n";} else if (diff < 0) {cout << "Position Zero!\n";} else {cout << "Fly Me to the Star\n";}
}
E 小圈子
本题考察并查集，数据范围不需要使用路径压缩、按秩合并。
#include <bits/stdc++.h>
using namespace std;int parent[1010];int findRoot(int x) {while (parent[x] != x) {x = parent[x];}return x;
}bool unite(int a, int b) {int ra = findRoot(a);int rb = findRoot(b);if (ra == rb) return false;parent[rb] = ra;return true;
}void solve(){int N, M;cin >> N >> M;for (int i = 1; i <= N; ++i) {parent[i] = i;}int groups = N;for (int i = 0; i < M; ++i) {int A, B;cin >> A >> B;if (unite(A, B)) {groups--;}}cout << groups << "\n";
}int main() {ios::sync_with_stdio(false); cin.tie(nullptr);int T; cin>>T;while (T--) solve();return 0;
}
F 世界线跃迁
本题考察单源最短路，使用Dijkstra算法即可满足题目复杂度。
AC代码
#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, s;if (!(cin >> n >> s)) return 0;vector<vector<int>> g(n, vector<int>(n));for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {cin >> g[i][j];}}const int INF = 0x3f3f3f3f;vector<int> dist(n, INF);vector<bool> vis(n, false);dist[s] = 0;for (int i = 0; i < n; ++i) {int u = -1, mind = INF;for (int j = 0; j < n; ++j) {if (!vis[j] && dist[j] < mind) {mind = dist[j];u = j;}}if (u == -1) break;vis[u] = true;for (int v = 0; v < n; ++v) {if (g[u][v] > 0 && dist[u] + g[u][v] < dist[v]) {dist[v] = dist[u] + g[u][v];}}}bool first = true;for (int i = 0; i < n; ++i) {if (i == s) continue;if (!first) cout << ' ';first = false;if (dist[i] == INF) cout << -1;else cout << dist[i];}cout << '\n';return 0;
}
G 能量分配
本题为动态规划问题中经典的01背包问题。
状态转移方程为 dp[j]=max(dp[j], dp[j−w]+v)
for (int i = 1; i <= N; ++i) {for (int j = E; j >= w[i]; --j) {dp[j] = max(dp[j], dp[j - w[i]] + v[i]);}
}
AC代码
#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int E, N;while (cin >> E >> N) {if (E == 0 && N == 0) break;vector<int> dp(E + 1, 0);for (int i = 0; i < N; ++i) {int w, v;cin >> w >> v;for (int j = E; j >= w; --j) {dp[j] = max(dp[j], dp[j - w] + v);}}cout << dp[E] << '\n';}return 0;
}
H 耐久魔法
本题考查线段树
#include <bits/stdc++.h>
using namespace std;constexpr int N = 405;
constexpr int MOD = 1000000007;struct Node {int id;int w;
};int n, m;
int ans[N];
int dp[N][N];
int s1[N][N], s2[N][N];
bool used[N];
Node a[N];inline int addMod(int x, int y) {x += y;return (x >= MOD) ? x - MOD : x;
}inline void incMod(int &x, int y) {x += y;if (x >= MOD) x -= MOD;
}int qPow(int x, int y) {int res = 1;while (y) {if (y & 1) res = 1LL * res * x % MOD;x = 1LL * x * x % MOD;y >>= 1;}return res;
}inline bool cmpNode(const Node &x, const Node &y) {return x.w < y.w;
}// 原 f(l, r) 函数
inline int F(int l, int r) {return (l * (l + 1)+ (n - r + 1) * (n - r + 2)+ (r - l - 1) * (r - l)) / 2;
}int main() {if (scanf("%d %d", &n, &m) != 2) {return 0;}used[n + 1] = true;for (int i = 1; i <= n; ++i) {scanf("%d", &a[i].w);a[i].id = i;}sort(a + 1, a + n + 1, cmpNode);// 预处理 dpfor (int i = n, last; i >= 1; --i) {last = 0;used[a[i].id] = true;for (int j = 1; j <= n + 1; ++j) {if (used[j]) {dp[last][j] += a[i].w - a[i - 1].w;last = j;}}}ans[1] = 1LL * a[n].w * qPow(n * (n + 1) / 2, m) % MOD;for (int i = 2; i <= n; ++i) {ans[i] = ans[1];}// 做 m 次转移for (int step = 1; step <= m; ++step) {// 计算前缀和 s1, s2for (int j = 0; j <= n; ++j) {for (int k = n + 1; k > j + 1; --k) {int val = dp[j][k];s1[j][k] = addMod(j ? s1[j - 1][k] : 0, 1LL * val * j % MOD);s2[j][k] = addMod(k <= n ? s2[j][k + 1] : 0,1LL * val * (n - k + 1) % MOD);}}for (int j = 0; j <= n; ++j) {for (int k = j + 2; k <= n + 1; ++k) {int val = 1LL * dp[j][k] * F(j, k) % MOD;if (j) incMod(val, s1[j - 1][k]);if (k <= n) incMod(val, s2[j][k + 1]);dp[j][k] = val;}}}// 统计答案for (int i = 0; i <= n; ++i) {for (int j = i + 2; j <= n + 1; ++j) {for (int k = i + 1; k < j; ++k) {incMod(ans[k], MOD - dp[i][j]);}}}for (int i = 1; i <= n; ++i) {printf("%d ", ans[i]);}return 0;
}