Educational Codeforces Round 154 (Rated for Div. 2)
| # | Name | ||
|---|---|---|---|
| A | Prime Deletion |   |
 x14422 |
| B | Two Binary Strings | |
x10743 |
| C | Queries for the Array | |
x3639 |
| D | Sorting By Multiplication | |
x2103 |
| E | Non-Intersecting Subpermutations | |
x355 |
| F | Four Suits | |
x10 |
A.DFS, 思维
- 数学思维
#include<bits/stdc++.h>
using namespace std;
void solve()
{
string s;
cin >> s;
for(auto c : s)
{
if(c == '1')
{
cout << 13 << "\n";
return;
}
else if(c == '3')
{
cout << 31 << "\n";
return;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--)
{
solve();
}
return 0;
}
- 目前做法
// Problem: A. Prime Deletion
// Contest: Codeforces - Educational Codeforces Round 154 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1861/problem/A
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// Date:2023-12-05 09:04:56
// Author:hblgzsx
// 借鉴思路：自己
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
int n = 10;
bool vis[10];
string s;
bool check(string s)
{
if(s.size() == 1) return false;
int x = 0;
for(int i = 0; i < s.size(); i++)
{
x = x * 10 + s[i] - '0';
}
if(x < 2) return false;
for(int i = 2; i <= x / i; i++)
{
if(x % i == 0) return false;
}
return true;
}
bool dfs(int u, string t)
{
if(check(t))
{
cout << t << "\n";
return true;
}
if(u == n) return false;
for(int i = 0; i < n; i++)
{
if(dfs(u + 1, t)) return true;
if(vis[i]) continue;
vis[i] = true;
if(dfs(u + 1, t + s[i])) return true;
vis[i] = false;
}
return false;
}
void solve()
{
memset(vis, 0, sizeof vis);
cin >> s;
string t;
dfs(0, t);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--)
{
solve();
}
return 0;
}
- 之前的思路
// Problem: A. Prime Deletion
// Contest: Codeforces - Educational Codeforces Round 154 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1861/problem/A
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// Date:2023-08-31 23:45:27
// Author:hblgzsx
// 借鉴思路：自己
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
bool is_prime(int x)
{
if(x < 2) return false;
for(int i = 2; i <= x / i; i++)
{
if(x % i == 0) return false;
}
return true;
}
void solve()
{
string s;
cin >> s;
vector<bool> vis(10);
//思路好
auto dfs =[&](auto self, int u, string k) -> bool
{
if(u == 9)
{
int ans = 0;
for(int i = 0; i < k.size(); i++)
{
ans = ans * 10 + (k[i] - '0');
}
if(is_prime(ans))
{
cout << ans << "\n";
return true;
}
return false;
}
if(self(self, u + 1, k + (s[u]))) return true;
if(self(self, u + 1, k)) return true;
return false;
};
string k;
if(!dfs(dfs,0, k)) cout << -1 << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--)
{
solve();
}
return 0;
}
B.思维
// Problem: B. Two Binary Strings
// Contest: Codeforces - Educational Codeforces Round 154 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1861/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Date:2023-09-01 00:30:03
// Author:hblgzsx
// 借鉴思路：jiangly，简单至极，太笨了，受不了了
// 仔细读题， 在每个测试用例中，两个字符串都以 0 开始，以 1 结束；
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
void solve()
{
string a, b;
cin >> a >> b;
int n = a.size();
for(int i = 0; i < n - 1; i ++)
{
if(a[i] == '0' && b[i] == '0' && a[i + 1] == '1' && b[i + 1] == '1')
{
cout << "YES\n";
return;
}
}
cout << "NO\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--)
{
solve();
}
return 0;
}
C.思维
// Problem: C. Queries for the Array
// Contest: Codeforces - Educational Codeforces Round 154 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1861/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Date:2023-12-05 09:40:53
// Author:hblgzsx
// 借鉴思路：自己
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
void solve()
{
string s;
cin >> s;
vector<int> a;
int z = 0;
for(auto c : s)
{
if(c == '+') a.push_back(-1);
else if(c == '-')
{
z -= (a.back() == 0);
int t = a.back();
a.pop_back();
if(a.size() && t == 1) a.back() = 1;
}
else if(c == '1')
{
if(z)
{
cout << "NO\n";
return;
}
if(a.size()) a.back() = 1;
}
else
{
if(a.size() <= 1)
{
cout << "NO\n";
return;
}
if(a.back() == 1)
{
cout << "NO\n";
return;
}
if(a.back() == -1)
{
a.back() = 0;
z++;
}
}
}
cout << "YES\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--)
{
solve();
}
return 0;
}
D.思维
// Problem: D. Sorting By Multiplication
// Contest: Codeforces - Educational Codeforces Round 154 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1861/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Date:2023-12-05 12:39:23
// Author:hblgzsx
// 借鉴思路：自己
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin >> n;
vector<int> a(n);
for(auto &x : a) cin >> x;
int ans = 0;
for(int i = 0; i < n - 1; i++)
{
ans += (a[i] >= a[i + 1]);
}
int res = ans;
for(int i = 1; i < n; i++)
{
res -= (a[i - 1] >= a[i]);
//降序，添加负号。
ans = min(ans, res + 1);
res += (a[i - 1] <= a[i]);
}
cout << ans << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--)
{
solve();
}
return 0;
}
- 前后翻转
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
vector<int> pre(n + 1, 1e9), suf(n + 1, 1e9);
pre[1] = 0;
for(int i = 2; i <= n; i++)
pre[i] = pre[i - 1] + (a[i] >= a[i - 1]);
suf[n] = 0;
for(int i = n - 1; i >= 1; i--)
suf[i] = suf[i + 1] + (a[i] >= a[i + 1]);
int ans = min(pre[n] + 1, suf[1]);
for(int i = 1; i < n; i++)
ans = min(ans, pre[i] + 1 + suf[i + 1]);
cout << ans << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while(t--)
{
solve();
}
return 0;
}
E.动态规划
- 推导了两天，找到了补DP题目的终极方法，简单样例推导
#include <bits/stdc++.h>
using i64 = long long;
template<class T>
constexpr T power(T a, i64 b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
constexpr i64 mul(i64 a, i64 b, i64 p) {
i64 res = a * b - i64(1.L * a * b / p) * p;
res %= p;
if (res < 0) {
res += p;
}
return res;
}
template<i64 P>
struct MLong {
i64 x;
constexpr MLong() : x{} {}
constexpr MLong(i64 x) : x{norm(x % getMod())} {}
static i64 Mod;
constexpr static i64 getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(i64 Mod_) {
Mod = Mod_;
}
constexpr i64 norm(i64 x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr i64 val() const {
return x;
}
explicit constexpr operator i64() const {
return x;
}
constexpr MLong operator-() const {
MLong res;
res.x = norm(getMod() - x);
return res;
}
constexpr MLong inv() const {
assert(x != 0);
return power(*this, getMod() - 2);
}
constexpr MLong &operator*=(MLong rhs) & {
x = mul(x, rhs.x, getMod());
return *this;
}
constexpr MLong &operator+=(MLong rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MLong &operator-=(MLong rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MLong &operator/=(MLong rhs) & {
return *this *= rhs.inv();
}
friend constexpr MLong operator*(MLong lhs, MLong rhs) {
MLong res = lhs;
res *= rhs;
return res;
}
friend constexpr MLong operator+(MLong lhs, MLong rhs) {
MLong res = lhs;
res += rhs;
return res;
}
friend constexpr MLong operator-(MLong lhs, MLong rhs) {
MLong res = lhs;
res -= rhs;
return res;
}
friend constexpr MLong operator/(MLong lhs, MLong rhs) {
MLong res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream &operator>>(std::istream &is, MLong &a) {
i64 v;
is >> v;
a = MLong(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a) {
return os << a.val();
}
friend constexpr bool operator==(MLong lhs, MLong rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MLong lhs, MLong rhs) {
return lhs.val() != rhs.val();
}
};
template<>
i64 MLong<0LL>::Mod = i64(1E18) + 9;
template<int P>
struct MInt {
int x;
constexpr MInt() : x{} {}
constexpr MInt(i64 x) : x{norm(x % getMod())} {}
static int Mod;
constexpr static int getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(int Mod_) {
Mod = Mod_;
}
constexpr int norm(int x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr int val() const {
return x;
}
explicit constexpr operator int() const {
return x;
}
constexpr MInt operator-() const {
MInt res;
res.x = norm(getMod() - x);
return res;
}
constexpr MInt inv() const {
assert(x != 0);
return power(*this, getMod() - 2);
}
constexpr MInt &operator*=(MInt rhs) & {
x = 1LL * x * rhs.x % getMod();
return *this;
}
constexpr MInt &operator+=(MInt rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MInt &operator-=(MInt rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MInt &operator/=(MInt rhs) & {
return *this *= rhs.inv();
}
friend constexpr MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend constexpr MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
i64 v;
is >> v;
a = MInt(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
return os << a.val();
}
friend constexpr bool operator==(MInt lhs, MInt rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MInt lhs, MInt rhs) {
return lhs.val() != rhs.val();
}
};
template<>
int MInt<0>::Mod = 998244353;
template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();
constexpr int P = 998244353;
using Z = MInt<P>;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, k;
std::cin >> n >> k;
std::vector<std::array<Z, 2>> dp(k);
dp[0][0] = 1;
for(int i = 0; i < n; i++){
std::vector<std::array<Z,2>> g(k);
std::array<Z, 2> res;
for(int j = k - 1; j >= 0; j--)
{
if(j < k - 1){
g[j + 1][0] += (k - j) * dp[j][0];
g[j + 1][1] += (k - j) * dp[j][1];
}
else{
g[0][0] += dp[j][0];
g[0][1] += dp[j][1] + dp[j][0];
}
if(j > 0){
res[0] += dp[j][0];
res[1] += dp[j][1];
g[j][0] += res[0];
g[j][1] += res[1];
}
}
dp = std::move(g);
}
Z ans = 0;
for(int i = 0; i < k; i++){
ans += dp[i][1];
}
std::cout << ans << "\n";
return 0;
}
/*
dp = std::move(g);
std::vector<std::array<Z, 2>> g(k);
*/
F.网络流
so weak……
- Educational Codeforces Round Rated 154educational codeforces round rated round codeforces rated based educational codeforces round 151 construction educational codeforces round educational codeforces round 147 cf-educational educational codeforces round educational codeforces round 158 educational codeforces contest round educational codeforces monsters round educational codeforces round 119