Educational Codeforces Round 105 (Rated for Div. 2)
ABC String
给定一个字符串只有A、B和C构成。要求替换A、B、C为')'和'('，并且相同字母替换的是一样的，使得字符串变为合法括号串，请你判断是否可以通过替换变成合法括号串
题解：思维 + 枚举
- 第一个字母一定是（，最后一个字母一定是），所以如果第一个字母和最后一个字母一样，一定不合法
- 如果第一个字母和最后一个字母不一样，那么已经确定了两个字母，我们只需要枚举另一个字母是（还是）即可，利用括号序列的性质：任意位置之前的左括号数一定大于等于右括号数 判断即可
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;
void solve()
{
string s;
cin >> s;
int n = s.length();
s = " " + s;
if (s[1] == s[n])
{
cout << "NO" << endl;
return;
}
int ok = 0;
int pre = 0, suf = 0;
for (int i = 1; i <= n; ++i)
{
if (s[i] == s[1])
pre++;
else if (s[i] == s[n])
suf++;
else
pre++;
if (pre < suf)
break;
}
if (pre == suf)
ok = 1;
pre = suf = 0;
for (int i = 1; i <= n; ++i)
{
if (s[i] == s[1])
pre++;
else if (s[i] == s[n])
suf++;
else
suf++;
if (pre < suf)
break;
}
if (pre == suf)
ok = 1;
if (ok)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
Berland Crossword
给定n行n列的矩阵，其中有\(n^2\)个单元，\(n<=100\)，现在每个单元都是白色的，现在给定\(U,R,D,L\),各自代表最上面一行、最右边一列，最下面一行，最左边一行的黑格子数量，你需要将各自行或列的各自涂成相应数量的黑色格子数量，求能否涂成
题解：暴力 + 枚举
我们知道如果每一行或列如果需要涂的黑色个数\(<=n-2\)，肯定可以涂，但是如果有一行或列超过这个数，就说明一定有角会被涂成黑色，那么就会影响到另一行或列，所以四个角涂不涂黑色是关键，我们只需要暴力枚举四个角是否为黑色，然后对于每一种情况判断是否合法即可
如何判断合法：
对于每一行或列，我们减去角上的黑色后只要剩下的数量\(<=n-2\)那儿这一行或列就是合法的，我们看看上下左右四条边是不是都合法即可
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;
int n, u, r, d, l;
inline bool check(int u, int r, int d, int l)
{
if (u > n - 2 || r > n - 2 || d > n - 2 || l > n - 2)
return false;
else
return true;
}
void solve()
{
cin >> n >> u >> r >> d >> l;
for (int i = 0; i <= 1; ++i)
{
for (int j = 0; j <= 1; ++j)
{
for (int k = 0; k <= 1; ++k)
{
for (int q = 0; q <= 1; ++q)
{
int up = u, rg = r, lf = l, down = d;
if (i == 1)
up--, lf--;
if (j == 1)
lf--, down--;
if (k == 1)
down--, rg--;
if (q == 1)
rg--, up--;
if (up < 0 || rg < 0 || lf < 0 || down < 0)
continue;
if (check(up, rg, down, lf))
{
cout << "YES" << endl;
return;
}
}
}
}
}
cout << "NO" << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
1D Sokoban
现在x坐标轴上有许多箱子，同时也有许多特殊位置，位置给出的顺序有序，一个箱子只有在特殊位置上才能有贡献，你现在在原点0，你可以不停的推箱子，如果多个箱子碰到一起这些箱子会被一起推动，问你最多能获得多少贡献
题解：二分 + 枚举 + 模拟
因为身处原点，所以分两部分处理答案，负数和正数部分，下面讨论正数部分答案的最大贡献：
- 我们需要枚举每一个特殊位置，即将这个特殊位置之前所有坐标为正的箱子推到该位置，那么在每一个特殊位置它的贡献由两部分构成：1）左边连续箱子占据多少特殊位置（包括该位置本身） 2）该位置右边在特殊位置上的箱子数；
- 那么我们可以先简单dp求出每个特殊右边有多少贡献，然后因为序列有序，在箱子左边序列二分求出该特殊位置左边有多少个箱子，因为多个箱子会被一起推动，所以他们被推到该特殊位置时一定是连续的，所以左边箱子的数量一定是连续箱子的长度，我们在特殊位置序列二分得到这些连续的箱子占据多少个特殊位置，然后合并答案
- 对于每个特殊位置重复以上操作，将所有位置得到的贡献取\(max\)得到正数部分的最大贡献，时间复杂度\(O(nlogn)\)
对于负数部分，我们只需要将其取反后反转后，和正数一样处理即可
最后负数答案和正数答案合并即为最终答案
模拟时注意细节，比较难调
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;
int n, m;
int a[N], b[N];
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = 1; i <= m; ++i)
cin >> b[i];
int pos1 = lower_bound(a + 1, a + n + 1, 0) - a;
int pos2 = lower_bound(b + 1, b + m + 1, 0) - b;
vector<int> ini, tar;
vector<int> R(m + 10, 0), L(m + 10, 0);
unordered_map<int, int> mp;
for (int i = pos1; i <= n; ++i)
{
mp[a[i]]++;
ini.push_back(a[i]); //ini代表箱子坐标序列
}
for (int i = pos2; i <= m; ++i)
tar.push_back(b[i]); //tar代表特殊位置坐标序列
int ansr = -INF, ansl = -INF;
for (int i = tar.size() - 1; i >= 0; i--)//dp，求出该特殊位置右边的贡献
{
if (mp[tar[i]])
R[i] = R[i + 1] + 1;
else
R[i] = R[i + 1];
}
ansr = R[0]; //一个都不推
for (int i = 0; i < tar.size(); ++i)
{
int cnt = lower_bound(all(ini), tar[i]) - ini.begin(); //二分求出该特殊位置前面都多少个箱子
int pos = lower_bound(all(tar), tar[i] - cnt + 1) - tar.begin(); //二分求出左边包含多少个特殊位置
int res = i - pos + 1;
ansr = max(ansr, res + R[i + 1]); //合并左右两边答案
}
ini.clear(), tar.clear();
mp.clear();
for (int i = 1; i < pos1; ++i)
{
mp[-a[i]]++; //负数部分取反
ini.push_back(-a[i]);
}
for (int i = 1; i < pos2; ++i)
tar.push_back(-b[i]);
reverse(all(ini)); //反转后类似正数部分处理
reverse(all(tar));
for (int i = tar.size() - 1; i >= 0; i--)
{
if (mp[tar[i]])
L[i] = L[i + 1] + 1;
else
L[i] = L[i + 1];
}
ansl = L[0];
for (int i = 0; i < tar.size(); ++i)
{
int cnt = lower_bound(all(ini), tar[i]) - ini.begin();
int pos = lower_bound(all(tar), tar[i] - cnt + 1) - tar.begin();
int res = i - pos + 1;
ansl = max(ansl, res + L[i + 1]);
}
cout << ansl + ansr << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
Dogeforces
让你构造一颗树，除叶子节点外，每个节点至少拥有两个子节点，且父亲的节点的权值一定比子节点的权值大，现在给出所有叶子节点之间最近公共祖先的权值\(val\)，让你构造出这颗树
题解：并查集 + 最近公共祖先 + 构造
显然我们可以先将边按照权值进行排序，我们发现不断向上建树并找最近公共祖先的过程可以用并查集解决，很像离线\(tarjian\)
- 如果这条边连接的两个节点u,v的最近公共祖先的权值\(val\) 和其中一个节点u的最远祖先x（find(u)）的权值相同或者说val出现过，说明这v节点是x的子节点
- 如果val从未出现过，说明我们需要新建一个点，这个点就是u和v的父节点
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
// #define rson id << 1 | 1
// #define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 1e5 + 10, M = 4e5 + 10;
int n;
int fa[N];
int ans[N];
vector<int> g[N];
void dfs(int u, int par)
{
if (par != 0)
cout << u << " " << par << endl;
for (auto v : g[u])
{
if (v == par)
continue;
dfs(v, u);
}
}
int find(int x)
{
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
struct node
{
int val, lson, rson;
bool operator<(const node &t) const
{
if (val != t.val)
return val < t.val;
else
return lson < t.lson;
}
};
vector<node> a;
void solve()
{
cin >> n;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
{
int x;
cin >> x;
if (j == i)
ans[i] = x;
if (j <= i)
continue;
a.push_back({x, i, j});
}
for (int i = 1; i <= n; ++i)
fa[i] = i;
sort(all(a));
int idx = n;
for (auto &[val, u, v] : a)
{
u = find(u);
v = find(v);
if (u == v)
continue;
if (u < v)
swap(u, v);
if (ans[u] == val) //情况1
{
g[u].push_back(v);
g[v].push_back(u);
fa[v] = u;
}
else //情况2
{
++idx;
g[u].push_back(idx);
g[idx].push_back(u);
g[v].push_back(idx);
g[idx].push_back(v);
fa[u] = idx;
fa[v] = idx;
fa[idx] = idx;
ans[idx] = val;
}
}
cout << idx << endl;
for (int i = 1; i <= idx; ++i)
cout << ans[i] << " ";
cout << endl;
int rt = find(1);
cout << rt << endl;
dfs(rt, 0);
}
signed main(void)
{
Zeoy;
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
A-Z Graph
现在有一个空的有向图，每条边的权值是一个字符，对于该图有3种操作：
- $ + \ u \ v \ c$:添加一条从u到v的边权为c的边
- \(-\ u\ v\):将从u到v的边删除
- \(? \ k\):询问是否能够找到一条\(v_1,v_2...v_k\)的路线和\(v_k,v_{k-1},...v_1\)路线使得两条路线构成的字符串都相同，注意节点可以重复
题解：思维 + 构造
- 当k为奇数时：
只要u和v之间存在一条双向边，一定能构造出\(u,v,u,v,u...\)这样一条路线
- 当k为偶数时：
只要u和v之间存在一条相同字符的双向边，一定能构造出\(u,v,u,v,u...\)这样一条路线
了解构造规则后，我们只需要用map存储边即可，同时记录双向边和同类双向边的数量
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;
int n, q;
map<pii, char> mp;
void solve()
{
cin >> n >> q;
int cnt1 = 0, cnt2 = 0;
while (q--)
{
char op, c;
int u, v, k;
cin >> op;
if (op == '+')
{
cin >> u >> v >> c;
mp[mpk(u, v)] = c;
if (mp[mpk(v, u)])
cnt1++;
if (mp[mpk(u, v)] == mp[mpk(v, u)])
cnt2++;
}
else if (op == '-')
{
cin >> u >> v;
if (mp[mpk(v, u)])
cnt1--;
if (mp[mpk(u, v)] == mp[mpk(v, u)])
cnt2--;
mp.erase(mp.find(mpk(u, v)));
}
else
{
cin >> k;
if (k % 2 == 1)
{
if (cnt1)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
else
{
if (cnt2)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}
}
}
signed main(void)
{
Zeoy;
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}