题面
A.ABC string
【题面】
给定一个字符串 \(s\)，构造一个括号字符串 \(t\) 满足：
1.如果任意 \(s_i=s_j\)，那么 \(t_i=t_j\)。
2.\(t\) 满足身为一个括号字符串的要求。
【思路】
1.首先可以发现应为 \(s\) 中的元素数量只有 \(3\) 个，所以说可以直接枚举一下每一种不同的 \(s_i\) 可以对应哪些括号即可。
2.时间复杂度就是枚举每一种括号的情况，和判断是否符合一个括号序列。
【实现】
#include <bits/stdc++.h>
using namespace std;
const int N=5e1+10;
char s[N];
int dis[3];
void solve(){memset(dis,0,sizeof(dis));cin>>s;if(strlen(s)%2) { puts("NO"); return; } if(s[0]-'A'==s[strlen(s)-1]-'A') { puts("NO"); return; }dis[s[0]-'A']=1;dis[s[strlen(s)-1]-'A']=-1;bool flag;int zero,sum;for(register int i=0;i<=2;i++) if(!dis[i]) zero=i;dis[zero]=1;sum=0,flag=true;for(register int i=0;i<strlen(s);i++){sum+=dis[s[i]-'A'];if(sum<0) { flag=false; break; }}if(flag&&!sum) { puts("YES"); return; }dis[zero]=-1;sum=0,flag=true;for(register int i=0;i<strlen(s);i++){sum+=dis[s[i]-'A'];if(sum<0) { flag=false; break; }}if(flag&&!sum) { puts("YES"); return; }puts("NO");
}
int main()
{int t;scanf("%d",&t);while(t--){solve();}return 0;
}
B. Berland Crossword
【题面】
给定一个 \(n\times n\) 的矩阵，再给出第一行，最后一行、第一列、和最后一列有多少个黑色的点。判断是否存在。
【思路】
1.首先可以发现对于非第一行，最后一行、第一列、和最后一列的格点是无效的。
2.角落的格子会有重复，所以只有这些格点是需要被特殊考虑的。再发现因为只有4个格子我们可以直接去枚举 \(2^4=16\) 次，去判断是否满足要求。
【实现】
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int N = 1e5 + 5;
int n,u,d,l,r;inline bool check(int ul, int ur, int dl, int dr){int um = u - ul - ur;int dm = d - dl - dr;int lm = l - ul - dl;int rm = r - ur - dr;if(um < 0 || um > n - 2) return false;if(dm < 0 || dm > n - 2) return false;if(lm < 0 || lm > n - 2) return false;if(rm < 0 || rm > n - 2) return false;return true;
}
int a[4];
bool flag;
void dfs(int step){if(step == 4){flag |= check(a[0], a[1], a[2], a[3]);return;}a[step] = 0;dfs(step + 1);a[step] = 1;dfs(step + 1);
}
int main(){ios::sync_with_stdio (false);cin.tie(nullptr);int T;cin>>T;while(T --){cin>>n>>u>>r>>d>>l;flag = false;dfs(0);cout<<(flag ? "YES" : "NO")<<endl;}return 0;}
C.1D Sokoban
【题面】
有 \(n\) 个箱子在一个数轴上，你可以从原点开始走去推箱子（不能拉），箱子可以推动箱子。
【思路】
1.因为不能拉，所以原点左侧和右侧的点不能到另一侧，所以可以分开考虑。
2.人只能推最左侧的箱子（我们简称可推箱子），可推箱子将左侧的若干个箱子压缩在一起，而右侧的箱子保持原状。因此，我们可以将答案的计算分成两个部分：压缩在一起的箱子占据的特殊位置数量，以及保持原状的箱子占据的特殊位置数量
3.因此，我们得到了一种不是很有效率的做法：枚举可推箱子的所在位置，计算有多少个箱子被压缩在一起，进而分别计算这两个部分的箱子占据的特殊位置数量。
4.可以用 lower_bound 去二分，时间复杂度是 \(O(n\log m)\)
【实现】
#include<bits/stdc++.h>
using namespace std;
constexpr size_t N = 2e5 + 5;
int a[N], b[N];
int sum[N], in[N];
void solve(){int n, m;cin >> n >> m;unordered_set<int> s;for (int i = 0; i < m; i++) in[i] = sum[i] = 0;for (int i = 0; i < n; i++)cin >> a[i], s.insert(a[i]);for (int i = 0; i < m; i++)cin >> b[i], in[i] = (s.count(b[i]) >= 1);for (int i = 1; i < m; i++) in[i] += in[i - 1];int ta = lower_bound(a, a + n, 0) - a - 1;int tb = lower_bound(b, b + m, 0) - b - 1;while (tb >= 0) {while (ta >= 0 && a[ta] >= b[tb]) sum[tb]++, ta--;tb--;}ta = lower_bound(a, a + n, 0) - a;tb = lower_bound(b, b + m, 0) - b;while (tb < m) {while (a[ta] <= b[tb] && ta < n) sum[tb]++, ta++;tb++;}int posl = lower_bound(b, b + m, 0) - b - 1, posr = posl + 1;for (int i = posl - 1; i >= 0; i--) sum[i] += sum[i + 1];for (int i = posr + 1; i < m; i++) sum[i] += sum[i - 1];int ansl = 0, ansr = 0;for (int i = posl, mx = posl + 1; i >= 0; i--) {while (mx - 1 >= 0 && b[i] - b[mx - 1] + 1 <= sum[mx - 1]) mx--;if (mx >= 1)ansl = max(ansl, i - mx + 1 + in[mx - 1]);elseansl = max(ansl, i - mx + 1);}for (int i = posr, mx = posr - 1; i < m; i++) {while (mx + 1 < m && b[mx + 1] - b[i] + 1 <= sum[mx + 1]) mx++;ansr = max(ansr, mx - i + 1 + in[m - 1] - in[mx]);}int ans = ansl + ansr;cout << ans << '\n';
}
signed main(){int T;cin >> T;while(T--){solve();}return 0;
}
D.DogeForces
【题面】
一个公司里有上下级关系，每个下级有恰好一个直属上司，立刻想到树形结构
用树形结构翻译题目：每个节点有权值，父节点的权值严格大于子节点，每个父节点有 \(\geq 2\) 个孩子。二维数组 \(a\) 给出了每对节点的最近公共祖先（lca）的权值。
【思路】
1.容易想到最大的权值肯定属于根（记为 \(max\)）
2.如果 \(a_i = max\)，说明 \(i,j\) 属于不同的树中。
3.因此，我们可以通过 \(a_{i,j}\) 是否等于 \(max\) 来确认有多少个子树，以及每个子树中有哪些节点（最直观的方法是使用并查集，代码中有更为方便快速的解法）。
4.用递归还原每一个树的结构
【实现】
#include<bits/stdc++.h>
#define pb push_back
#define mkp make_pair
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int N = 1e3 + 5;
int c[N];
int a[N][N];
int n,k;
vector<pii> edges;
void solve(vi vs, int fa){int u = vs[0];if(vs.size() == 1){c[u] = a[u][u];if(fa != -1) edges.pb(mkp(u, fa));return;}int maxa = 0;for(auto v : vs){maxa = max(maxa, a[u][v]);}vector<vi> subs;for(auto v : vs){bool smallest = true;for(auto w : vs){if(a[v][w] != maxa){if(w < v) smallest = false;}}if(smallest){//确保v是所在子树里编号最小的节点，这样能够避免重复计算子树vi sub;for(auto w : vs){if(a[v][w] != maxa) sub.pb(w);}subs.pb(sub);}}k++;int curU = k - 1;c[curU] = maxa;if(fa != -1) edges.pb(mkp(curU, fa));for(auto sub : subs){solve(sub, curU);}}
int main(){ios::sync_with_stdio (false);cin>>n;for(int i = 0; i < n; i ++){for(int j = 0; j < n; j ++)cin>>a[i][j];}k = n;vi vs;for(int i = 0; i < n; i ++) vs.pb(i);solve(vs, -1);cout<<k<<endl;for(int i = 0; i < k; i ++) cout<<c[i]<<" ";cout<<endl<<n + 1<<endl;for(auto e : edges){cout<<e.first + 1<<" "<<e.second + 1<<endl;}return 0;}
E.A-Z Graph
【题面】
维护一个有边权的有向图，支持加边、删边，询问是否存在一个包含 \(k\) 个点的节点序列，正向走和反向走得到的字符串相同。
【思路】
1.观察样例路径 \(1 \to 2 \to 3 \to 2 \to 1\)，发现这条路径是合法的，但与回文串没有直接关系。路径 \(1, 2, 3, 2, 1\) 本身是一个回文结构。
2.这个结构还可以进一步简化：\(1 \to 2 \to 1 \to 2 \to 1\) 也是一个合法路径！完全不需要 3 号点的参与。
3. 只要存在 \(u \to v\)，\(v \to u\) 这样的双向边，就可以构造 \(u \to v \to u \to v \to u \ldots\) 这样的路径，这可以解决所有的奇数长度路径问题。
4. 假如有路径 \(1 \to 2 \to 3 \to 4\) 和 \(4 \to 3 \to 2 \to 1\) 能够得到相同的字符串，可以发现 \(2 \to 3\) 与 \(3 \to 2\) 必然有一样的字符。\(2 \to 3 \to 2 \to 3 \to \ldots\) 能解决所有偶数长度的路径，但相比奇数路径有额外要求：\(u \to v\) 和 \(v \to u\) 需要具有相同的边权。
【实现】
#include<bits/stdc++.h>
#define pb push_back
#define mkp make_pair
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int N = 2e5 + 5;
int n,m;
map<pii,char> mp;
int cntO,cntE;
int main(){ios::sync_with_stdio (false);cin>>n>>m;while(m--){char op;int u, v, k;char c;cin>>op;switch(op){case '+':cin>>u>>v>>c;if(mp.find(mkp(v,u)) != mp.end()){cntO++;if(mp[mkp(v,u)] == c) cntE++;}mp[mkp(u,v)] = c;break;case '-':cin>>u>>v;if(mp.find(mkp(v,u)) != mp.end()){cntO--;if(mp[mkp(v,u)] == mp[mkp(u,v)]) cntE--;}mp.erase(mkp(u,v));break;case '?':cin>>k;if(k % 2 == 1) cout<<(cntO > 0 ? "YES" : "NO")<<endl;else cout<<(cntE > 0 ? "YES" : "NO")<<endl;break;default:break;}}return 0;}s