Contestant. Rank 1438. Rating +51.
A. Weekly Records
题意
给定 \(14\) 个数字，输出前 \(7\) 个和后 \(7\) 个数的总和。
思路
如题。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
for(int i=0;i<n;i++){
int sum = 0;
for(int j=0;j<7;j++){
int cur;
cin >> cur;
sum += cur;
}
cout << sum << ' ';
}
cout << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while(t --) solve();
}签到
B. racecar
题意
给定 \(n\) 个字符串，输出是否存在两个字符串，拼接后成为回文串。
思路
如题。
时间复杂度：\(O(n ^ 2)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
vector<string> a(n);
for(int i=0;i<n;i++) cin >> a[i];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i == j) continue;
string s;
s = a[i] + a[j];
int m = s.size();
bool f = true;
for(int p=0;p<m/2;p++){
if(s[p] != s[m - p - 1]) f = false;
}
if(f){
cout << "Yes\n";
return;
}
}
}
cout << "No\n";
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while(t --) solve();
}签到（别看错题
C. Ideal Sheet
题意
对于下面的纸张，均为透明方格纸，方格纸上有部分格子涂上了黑色。
给定两张长度有限的纸 \(A, B\)，两张纸部分区域涂上了黑色，规格分别为 \(H_A \times W_A, H_B \times W_B\)。
另给一张长度有限的纸 \(X\) 作为目标纸张，部分区域涂上了黑色，规格分别为 \(H_X \times W_X\)。
现在，在一张透明的无限长的纸张 \(C\) 上，将 \(A, B\) 任意沿着方格粘贴到 \(C\) 上，并按照下面的条件剪切出一张和 \(X\) 规格一致的纸张：
剪下的纸张上面不能有黑色方格，换言之，\(A, B\) 上的所有黑色方格都要用上；
沿方格剪切
输出能否剪切出一张和 \(X\) 一模一样的纸张。
注意，不可以旋转纸张。
思路
考虑到空白区域的处理，我们有两种方式解决：
处理思路1
记 \(H_T = \max(H_A, H_B), W_T = \max(W_A, W_B)\)，我们将 \(X\) 向上下左右拓展到 \((H_X + 2H_T) \times (W_X + 2W_T)\)，即可任意粘贴判断。
处理思路2
我们将 \(A, B, X\) 的多余区域删去，即可任意粘贴判断
判断
我们不妨用二维数组标记当前位置在 \(A, B\) 的对应格子上是否为黑色，那么最后只需判断是否存在 \(X\) 中的所有黑色格子是否都会被标记即可。
注意标记的时候不要覆盖之前遍历的结果。
时间复杂度：\(O(n ^ 6)\)
对应AC代码1
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int an, am;
cin >> an >> am;
vector<string> A(an);
for(int i=0;i<an;i++) cin >> A[i];
int bn, bm;
cin >> bn >> bm;
vector<string> B(bn);
for(int i=0;i<bn;i++) cin >> B[i];
int xn, xm;
cin >> xn >> xm;
xn += 2 * max(an, bn), xm += 2 * max(am, bm);
vector<vector<char>> X(xn, vector<char>(xm, '.'));
for(int i=max(an, bn);i<xn-max(an, bn);i++) {
string s;
cin >> s;
for(int j=0;j<s.size();j++){
X[i][j + max(am, bm)] = s[j];
}
}
for(int i=0;i<=xn-an;i++)
for(int j=0;j<=xm-am;j++) {
for (int k = 0; k <= xn - bn; k++)
for (int o = 0; o <= xm - bm; o++) {
vector<vector<bool>> ok(xn, vector<bool>(xm));
bool f = true;
for (int p = 0; p < an; p++) {
for (int q = 0; q < am; q++) {
if(A[p][q] == '#' && X[i + p][j + q] == '.'){
f = false;
break;
}
ok[i + p][j + q] = ok[i + p][j + q] || (A[p][q] == '#');
}
if(!f) break;
}
for (int p = 0; p < bn; p++) {
for (int q = 0; q < bm; q++) {
if(B[p][q] == '#' && X[k + p][o + q] == '.'){
f = false;
break;
}
ok[k + p][o + q] = ok[k + p][o + q] || (B[p][q] == '#');
}
if(!f) break;
}
if(f){
for (int p = 0; p < xn; p++) {
for (int q = 0; q < xm; q++) {
if(X[p][q] == '#' && !ok[p][q]){
f = false;
break;
}
}
if(!f) break;
}
if(f){
cout << "Yes\n";
return;
}
}
}
}
cout << "No\n";
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while(t --) solve();
}对应AC代码2
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
auto opt = [](int &an, int &am, vector<string> &A) -> void {
int hl = inf, hr = -inf, wl = inf, wr = -inf;
bool f = false;
for (int i = 0; i < an; i++)
for (int j = 0; j < am; j++) {
if (A[i][j] == '#') {
f = true;
hl = min(hl, i);
hr = max(hr, i);
wl = min(wl, j);
wr = max(wr, j);
}
}
if(!f){
an = am = 0;
A = vector<string>(0);
return;
}
vector<string> tA(hr - hl + 1);
for (int i = hl; i <= hr; i++)
for (int j = wl; j <= wr; j++) {
tA[i - hl] += A[i][j];
}
an = hr - hl + 1, am = wr - wl + 1;
A = tA;
};
int an, am;
cin >> an >> am;
vector<string> A(an);
for (int i = 0; i < an; i++) cin >> A[i];
opt(an, am, A);
int bn, bm;
cin >> bn >> bm;
vector<string> B(bn);
for (int i = 0; i < bn; i++) cin >> B[i];
opt(bn, bm, B);
int xn, xm;
cin >> xn >> xm;
vector<string> X(xn);
for (int i = 0; i < xn; i++) cin >> X[i];
opt(xn, xm, X);
for (int i = 0; i <= xn - an; i++)
for (int j = 0; j <= xm - am; j++) {
for (int k = 0; k <= xn - bn; k++)
for (int o = 0; o <= xm - bm; o++) {
vector<vector<bool>> ok(xn, vector<bool>(xm));
bool f = true;
for (int p = 0; p < an; p++) {
for (int q = 0; q < am; q++) {
if (A[p][q] == '#' && X[i + p][j + q] == '.') {
f = false;
break;
}
ok[i + p][j + q] = ok[i + p][j + q] || (A[p][q] == '#');
}
if (!f) break;
}
for (int p = 0; p < bn; p++) {
for (int q = 0; q < bm; q++) {
if (B[p][q] == '#' && X[k + p][o + q] == '.') {
f = false;
break;
}
ok[k + p][o + q] = ok[k + p][o + q] || (B[p][q] == '#');
}
if (!f) break;
}
if (f) {
for (int p = 0; p < xn; p++) {
for (int q = 0; q < xm; q++) {
if (X[p][q] == '#' && !ok[p][q]) {
f = false;
break;
}
}
if (!f) break;
}
if (f) {
cout << "Yes\n";
return;
}
}
}
}
cout << "No\n";
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while(t --) solve();
}什么答辩题啊
D. Mismatched Parentheses
题意
给定一个带括号以及小写字母的字符串，将 "()" 包含的所有字符以及该括号删除视为一次操作。
输出操作数最多的方案对应的操作后的字符串。
思路
既然需要操作数尽可能多，我们直接进行匹配，并从内向外删除即可。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
string s;
cin >> s;
stack<int> q;
map<int, int> to;
for(int i=0;i<n;i++){
if(s[i] == '(') q.emplace(i);
else if(s[i] == ')'){
if(q.size() == 0) continue;
else {
auto e = q.top();
q.pop();
to[e] = i;
}
}
}
for(int i=0;i<n;i++){
if(to.count(i)) i = to[i];
else cout << s[i];
}
cout << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while(t --) solve();
}签到
E. Distinct Adjacent
题意
给定 \(n\) 个人，所有人围成一圈，\(i\) 和 \(i + 1\)，\(1\) 和 \(n\) 相邻。
现在，给定 \(m\) 个数，输出分配的方案数对 \(998244353\) 取模后的结果。
其中，方案应满足相邻的两个人数字不同。
思路
我们考虑 \(dp\)。
我们固定第一个数为 \(x\)，他会有 \(m\) 种取法。
接下来，我们分两种情况进行处理：
当前的数和 \(x\) 相同，那么上一个数就一定和 \(x\) 不相同；
当前的数和 \(x\) 不相同，那么当前就会有两种取法：
上一个数和 \(x\) 不相同，那么我们剩下 \(m - 2\) 种取法
上一个数和 \(x\) 相同，那么我们剩下 \(m - 1\) 种取法。
因而，我们定义 \(dp[i][j]\) 为前 \(i\) 个数的取法，\(j \in \{0, 1\}\) 表示是否和第一个数相同。
那么，初始化为 \(dp[1][1] = m\)，状态转移方程如下：
\(dp[i][1] = dp[i - 1][0]\)；
\(dp[i][0] = dp[i - 1][0] \times (m - 2) + dp[i - 1][1] \times (m - 1)\)
最后的答案即为 \(dp[n][0]\)。
记得取模。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n, m;
cin >> n >> m;
vector<vector<int>> dp(n + 1, vector<int>(2));
dp[1][1] = m;
for(int i=2;i<=n;i++){
dp[i][1] = dp[i - 1][0];
dp[i][0] = (dp[i - 1][0] * (m - 2) % mod + dp[i - 1][1] * (m - 1) % mod) % mod;
}
cout << dp[n][0] << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while(t --) solve();
}算是比较经典的对环 \(dp\)
F. Virus 2
题意
给定一个无向图。
时刻 \(0\) 下，有 \(k\) 个人携带病毒。
在 \([1, d]\) 时刻内，每一个时刻，每个人携带的病毒可以沿着边传染到距离不超过 \(x_i\) 的所有人。
输出每个人被感染的时刻，若未感染，输出 \(-1\)。
思路
首先，我们不难想到最短路问题，那么我们不妨按照下面的方式计算：
加入一个 \(0\) 虚拟节点
将该节点和被感染的人相连，边权都为 \(0\)
\(0\) 节点到其他人的最短路如果长度小于 \(x_i\)，那么就会被传染
那么，我们用优先队列维护 被感染的人的 所有未被感染的 相邻子节点，按照每个人到被感染的人的边权升序排列。
因而，在每一个时刻，我们就可以筛选出距离不超过 \(x_i\) 的人，并直接将其传染。
自然，也会存在子节点的子节点也可以被传染的情况，因而我们不妨采用 \(\mathtt{Dijkstra}\)，更新一遍所有能被传染的人，并用于下一次传染。
时间复杂度：\(O((d + m) \log n + n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n, m;
cin >> n >> m;
vector<vector<pii>> e(n);
while(m --){
int u, v, w;
cin >> u >> v >> w;
u --, v --;
e[u].pb(v, w);
e[v].pb(u, w);
}
priority_queue<pii, vector<pii>, greater<>> q1, q2;
vector<int> ans(n, -1);
int k;
cin >> k;
while(k --){
int a;
cin >> a;
a --;
ans[a] = 0;
for(auto [x, y] : e[a])
if(ans[x] == -1) q1.emplace(y, x);
}
int d;
cin >> d;
for(int i=1;i<=d;i++){
int x;
cin >> x;
while(!q1.empty()){
auto [w, v] = q1.top();
if(w > x) break;
q1.pop();
if(ans[v] == -1) q2.emplace(w, v);
}
while(!q2.empty()){
auto [w, v] = q2.top();
q2.pop();
if(ans[v] != -1) continue;
ans[v] = i;
for(auto [p, q] : e[v]){
if(ans[p] != -1) continue;
if(w + q <= x) q2.emplace(w + q, p);
q1.emplace(q, p);
}
}
}
for(auto x : ans) cout << x << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while(t --) solve();
}有意思的
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Blog - Floating Ocean！
评论