比赛链接:Here
A - LR Constraints
赛时做这个好迷啊,英文题面解释不清楚,还是看了日语原文才搞懂
\(n\) 个卡牌上有两个
字符 + 数字
组合,L
的右边所有元素 + 1,R
的左边元素 + 1最后求出现过数字的乘积,同时对 \(998244353\) 取余
注意点:开
long long
!!!,今天牛客也是,没开ll
debug半天,感谢尚佬指出我的错误
Show Code
const int N = 1010; bool vis[N]; int cnt[N]; int main() { cin.tie(nullptr)->sync_with_stdio(false); int n, k; cin >> n >> k; for (int i = 1; i <= k; ++i) { char c; int x; cin >> c >> x; if (c == ‘L‘) { vis[x] = 1; for (int j = x + 1; j <= n; ++j)cnt[j] ++; } else { vis[x] = 1; for (int j = 1; j <= x; ++j)cnt[j] ++; } } ll ans = 1; for (int i = 1; i <= n; ++i) { if (!vis[i])ans = ans * cnt[i] % 998244353; } cout << ans << ‘\n‘; }
B - XOR Matching 2
对于长度为 \(n\) 的 \(a,b\) 两个序列,请问是否存在某种排序组合使得某个 \(x\) 被称为
Good
Good定义:可以对 \(b\) 重排序使得每一个 \(a_i\ XOR\ b_i = x\)
当 \(x\) 固定时,置换 \(b\) 使得 \(a_i ⊕ b_i = x\) 等价于 \(c_i = a_i ⊕x\)
所以我们可以直接尝试 \(a_1 ⊕ b1,a_1 ⊕ b_2,...,a_1⊕b_n\)
- \(\mathcal{O}(N^2log\ N)\)
Show Code
const int N = 2e3 + 10; int a[N], b[N]; map<int, int> mp, bg; set<int>v; int main() { cin.tie(nullptr)->sync_with_stdio(false); int n; cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; for (int i = 1; i <= n; ++i) cin >> b[i], bg[b[i]]++; for (int i = 1; i <= n; ++i) { int x = a[1] ^ b[i]; mp = bg; bool f = true; for (int j = 1; j <= n and f; ++j)if (!mp[x ^ a[j]]) f = false; if (f) v.insert(x); } cout << v.size() << "\n"; for (int x : v)cout << x << "\n"; }