A. 语言
题目描述
在一个语言中，有 \(26\) 种单词，每个单词用一个小写英文字母表示。每种单词可能有多种词性，词性有名词（\(N\)）、动词（\(V\)）、形容词（\(A\)）。我们定义一个名词短句（\(NP\)）为一个名词（\(N\)）或一个形容词加名词短句（\(A+NP\)）或两个名词短句（\(NP_1+NP_2\)），一个句子（\(S\)）为一个名词短句加动词加名词短句（\(NP_1+V+NP_2\)）。
现在给定一些单词，请你判断它有没有可能是一个句子。
思路
很明显一段子串是名词短句当且仅当其中只包含 \(N,P\) 且最后一个单词为 \(N\)。所以我们枚举动词在哪里，并预处理前后缀是否为名词短句即可。
时空复杂度均为 \(O(N)\)。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100001;
int t, n, a[26];
bool ok[MAXN];
string s;
void Solve() {
for(int i = 0; i < 26; ++i) {
cin >> a[i];
}
cin >> s;
n = s.size(), s = ' ' + s;
ok[n] = (a[s[n] - 'a'] == 2 || a[s[n] - 'a'] == 3 || a[s[n] - 'a'] == 6 || a[s[n] - 'a'] == 7);
for(int i = n - 1; i >= 1; --i) {
ok[i] = (ok[i + 1] & (a[s[i] - 'a'] == 1 || a[s[i] - 'a'] == 2 || a[s[i] - 'a'] == 3 || a[s[i] - 'a'] == 5 || a[s[i] - 'a'] == 6 || a[s[i] - 'a'] == 7));
}
bool op = (a[s[1] - 'a'] == 1 || a[s[1] - 'a'] == 2 || a[s[1] - 'a'] == 3 || a[s[1] - 'a'] == 5 || a[s[1] - 'a'] == 6 || a[s[1] - 'a'] == 7);
for(int i = 2; i < n; ++i) {
if((a[s[i] - 'a'] == 4 || a[s[i] - 'a'] == 5 || a[s[i] - 'a'] == 6 || a[s[i] - 'a'] == 7) && op && (a[s[i - 1] - 'a'] == 2 || a[s[i - 1] - 'a'] == 3 || a[s[i - 1] - 'a'] == 6 || a[s[i - 1] - 'a'] == 7) && ok[i + 1]) {
cout << "Yes\n";
return;
}
op &= (ok[i + 1] & (a[s[i] - 'a'] == 1 || a[s[i] - 'a'] == 2 || a[s[i] - 'a'] == 3 || a[s[i] - 'a'] == 5 || a[s[i] - 'a'] == 6 || a[s[i] - 'a'] == 7));
}
cout << "No\n";
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
for(cin >> t; t--; Solve()) {
}
return 0;
}
B. 色球
题目描述
有 \(N\) 个栈，和 \(N\) 种颜色的球。给定 \(M\) 次操作。
- 往第 \(z\) 个栈压入 \(x\) 个颜色为 \(y\) 的球。
- 弹出第 \(z\) 个栈的顶部 \(x\) 个球，并求出最后一个球的颜色。
- 将第 \(u\) 个栈的球依次弹出并压入 \(v\) 中。
思路
这里主要是第三个操作最难处理。第三个操作很明显可以用启发式合并解决，但是它在弹出和压入时会进行反转，所以我们可以对每个栈记录其有没有反转过，如果反转了则压入和删除都要从栈底进行，所以改用双端队列即可。
空间复杂度 \(O(N+M)\)，时间复杂度 \(O((N+M)\log N)\)。
代码
#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAXN = 200001;
int n, m;
bool vis[MAXN];
deque<pii> que[MAXN];
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1, x, y, z; i <= m; ++i) {
string op;
cin >> op >> x >> y;
if(op == "push") {
cin >> z;
if(!vis[z]) {
que[z].push_front({y, x});
}else {
que[z].push_back({y, x});
}
}else if(op == "pop") {
int ans = 0;
for(; x; ) {
if(!vis[y]) {
auto &[a, b] = que[y].front();
ans = a;
if(b <= x) {
x -= b;
que[y].pop_front();
}else {
b -= x;
break;
}
}else {
auto &[a, b] = que[y].back();
ans = a;
if(b <= x) {
x -= b;
que[y].pop_back();
}else {
b -= x;
break;
}
}
}
cout << ans << "\n";
}else if(op == "put") {
if(que[x].size() < que[y].size()) {
for(; !que[x].empty(); ) {
if(!vis[x]) {
auto [a, b] = que[x].front();
if(!vis[y]) {
que[y].push_front({a, b});
}else {
que[y].push_back({a, b});
}
que[x].pop_front();
}else {
auto [a, b] = que[x].back();
if(!vis[y]) {
que[y].push_front({a, b});
}else {
que[y].push_back({a, b});
}
que[x].pop_back();
}
}
}else {
swap(que[x], que[y]);
swap(vis[x], vis[y]);
for(; !que[x].empty(); ) {
if(!vis[x]) {
auto [a, b] = que[x].front();
if(!vis[y]) {
que[y].push_front({a, b});
}else {
que[y].push_back({a, b});
}
que[x].pop_front();
}else {
auto [a, b] = que[x].back();
if(!vis[y]) {
que[y].push_front({a, b});
}else {
que[y].push_back({a, b});
}
que[x].pop_back();
}
}
vis[y] ^= 1;
}
}
}
return 0;
}