A. Prime Deletion
思路：
從1到9，每個數(shù)后面都可以加一個數(shù)構(gòu)成一個含有兩個數(shù)的質(zhì)數(shù)，只需要從s[1]~s[9]中找到一個數(shù)與s[0]構(gòu)成質(zhì)數(shù)即可
代碼實(shí)現(xiàn)
/*******************************
| Author: CHC
| Problem: A. Prime Deletion
| Contest: Codeforces - Educational Codeforces Round 154 (Rated for Div. 2)
| URL: https://codeforces.com/contest/1861/problem/A
| When: 2023-08-31 22:55:13
|
| Memory: 512 MB
| Time: 2000 ms
*******************************/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[11] = {0, 13, 23, 31, 41, 53, 61, 71, 83, 97};
void solve()
{
string s;
cin >> s;
for (int i = 1; i < 10; i++)
if (s[0] - '0' == i) {cout << a[i] << endl; break;}
}
int main()
{
int t;
cin >> t;
while (t--)
solve();
return 0;
}
B. Two Binary Strings
思路：
觀察樣例即可發(fā)現(xiàn)兩個字符串只要在相同位置都有01存在就能成功實(shí)現(xiàn)轉(zhuǎn)換后兩個字符串相等文章來源：http://www.zghlxwxcb.cn/news/detail-691395.html
代碼實(shí)現(xiàn)
/*******************************
| Author: CHC
| Problem: B. Two Binary Strings
| Contest: Codeforces - Educational Codeforces Round 154 (Rated for Div. 2)
| URL: https://codeforces.com/contest/1861/problem/B
| When: 2023-09-02 10:10:12
|
| Memory: 256 MB
| Time: 2000 ms
*******************************/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
string a, b;
cin >> a >> b;
for (int i = 1; i < a.size(); i++)
{
if (a[i - 1] == '0' && a[i] == '1' && b[i - 1] == a[i - 1] && b[i] == a[i])
{
cout << "YES" << endl;
return;
}
}
cout << "NO" << endl;
}
int main()
{
int t;
cin >> t;
while (t--)
solve();
return 0;
}
C. Queries for the Array
思路
可以先假設(shè)字符串是可以成立的，那么接下來就判斷它什么時間是不會成立就行了。
只有尾部增刪操作，可以用 \(sum\) 記錄當(dāng)前整數(shù)的個數(shù),用 \(s1\) 記錄當(dāng)前 \(s1\) 個數(shù)有序(這里用有序代表"\(a_1≤?≤a_n\)")，用 \(s2\) 記錄當(dāng)前 \(s2\) 個數(shù)無序。文章來源地址http://www.zghlxwxcb.cn/news/detail-691395.html
-
s[i] == 1但前面有無序時(s2 ≤ sum)不會成立，具體看代碼 -
s[i] == 0但前面有無序時(s1 ≥ sum)不會成立，具體看代碼
代碼實(shí)現(xiàn)
/*******************************
| Author: CHC
| Problem: C. Queries for the Array
| Contest: Codeforces - Educational Codeforces Round 154 (Rated for Div. 2)
| URL: https://codeforces.com/contest/1861/problem/C
| When: 2023-08-31 23:25:51
|
| Memory: 256 MB
| Time: 2000 ms
*******************************/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1e9
void solve()
{
string s;
cin >> s;
int sum = 0, s1 = 1, s2 = INF;//sum記錄當(dāng)前整數(shù)個數(shù)，s1記錄前s1個數(shù)遞增，s2記錄前s2個數(shù)不滿足遞增條件
for (char c : s) {
if (c == '+') sum++;
else if (c == '-') {
sum--;
if (sum > 0 && s1 > sum) s1 = sum;//前sum個數(shù)遞增
if (s2 > sum) s2 = INF;//不能判斷前s2-1個整數(shù)的無序性，s2賦值為INF
}
//兩種判斷“NO”的情況
else if (c == '1') {
if (s2 <= sum) { cout << "NO\n"; return; }//c==1但前面有無序時
s1 = max(s1, sum);//否則更新s1
}
else {
if (s1 >= sum) { cout << "NO\n"; return; }//c==0但前sum個數(shù)都是有序時
s2 = min(s2, sum);//否則更新s2
}
}
cout << "YES\n";
}
int main()
{
int t;
cin >> t;
while (t--)
solve();
return 0;
}
D. Sorting By Multiplication
思路
- 觀察發(fā)現(xiàn)，每遇到一個\(a_i≥a_{i-1}\) 都可以取\(1\)~\(i\) 取\((a_l,a_r)*x\) 使得前\(i\)個數(shù)變成負(fù)數(shù)且單調(diào)遞減，同理每遇到一個\(a_i≥a_{i+1}\) 都可以取\(1\)~\(i+1\) 取\((a_l,a_r)*x\) 使得前\(i+1\)個數(shù)變成正數(shù)且單調(diào)遞增
- 無論開始是怎樣的數(shù)組，后來都會變成前綴是負(fù)數(shù)(單調(diào)遞減)，后綴是正數(shù)(單調(diào)遞增) 注：前綴和后綴個數(shù)都有可能為0
- 從前到后掃一遍求前綴需要改變的個數(shù)，用一個數(shù)組記錄下。然后從后往前掃一遍求后綴需要改變的個數(shù)，
- 最后求出每個\(i\)對應(yīng)的前綴和后綴的和的最小值即可(注：無前綴時不需要把前綴*(-1)，不用+1)
具體看代碼實(shí)現(xiàn)過程
代碼實(shí)現(xiàn)
/*******************************
| Author: CHC
| Problem: D. Sorting By Multiplication
| Contest: Codeforces - Educational Codeforces Round 154 (Rated for Div. 2)
| URL: https://codeforces.com/contest/1861/problem/D
| When: 2023-09-04 17:47:30
|
| Memory: 256 MB
| Time: 2000 ms
*******************************/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1);
//讓最后的數(shù)組形式變?yōu)榍熬Y為負(fù)數(shù)(單調(diào)遞減)+后綴為正數(shù)(單調(diào)遞增)
vector<int> b(n + 2, 0);//前綴需要改變的
vector<int> c(n + 2, 0);//后綴需要改變的
for (int i = 1; i <= n; i++) cin >> a[i];
//前綴嚴(yán)格遞減需要改變的
for (int i = 2; i <= n; i++)
b[i] += b[i - 1] + (a[i - 1] <= a[i]);
//后綴嚴(yán)格遞增需要改變的
for (int i = n - 1; i >= 1; i--)
c[i] += c[i + 1] + (a[i] >= a[i + 1]);
//前綴最后需要*(-1)把前綴變?yōu)檫f增的，當(dāng)后綴需要改變的最小時且不需要前綴(i!=1)時，不用再*(-1)，不需要+1
int res = 1e9 + 5;
for (int i = 1; i <= n + 1; i++)
res = min(res, b[i - 1] + c[i] + (i != 1));
cout << res << endl;
}
int main()
{
int t;
cin >> t;
while (t--)
solve();
return 0;
}
到了這里，關(guān)于Educational Codeforces Round 154 (Rated for Div. 2)（A—C）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
