Contestant. Rank 2247. Rating -18.好久没有这么坐牢了 qaq
A. Tenzing and Tsondu
题意
给定两个长度相等的序列，作为 \(A, B\) 的每个怪物的血量。每一回合，两个人以最优策略派出两个怪物，若两个怪物的血量为 \(x, y\)，那么回合结束后，两个怪物的血量变为 \(\max(x - y, 0), \max(y - x, 0)\)，血量为 \(0\) 的怪物死亡。
若某一玩家的怪物全部死亡，那么判定为输，输出最后的赢家。
思路
首先，我们可以根据数据乱猜，我们只需比较两个玩家的怪物总血量，血量一致就是平局，否则，血量多的一方胜出。
下面给出官方题解的解释：
注意，\(\max(x - y, 0) = x - \min(x, y), \max(y - x, 0) = y - \min(x, y)\)，因而每一回合两个玩家扣除的血量都是相同的，因而只和总血量有关。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n, m;
cin >> n >> m;
int a = 0, b = 0;
for(int i=0;i<n;i++){
int cur;
cin >> cur;
a += cur;
}
for(int i=0;i<m;i++){
int cur;
cin >> cur;
b += cur;
}
if(a == b) cout << "Draw\n";
else if(a < b) cout << "Tenzing\n";
else cout << "Tsondu\n";
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}乱猜就完事了
B. Tenzing and Books
题意
给定三个序列，规定每次操作为任选一个序列，移走最左边的元素。
任意次操作后，输出是否可以满足拿出的所有元素 按位或 之后值为给定的 \(x\)。
思路
题解所指的 \(|\) 指按位或，而非整除
首先，既然放在 \(B\) 题，绝对是运用了什么性质。
考虑按位或的性质，我们不难发现，如果一个数 \(p\) 可以和其他若干个数按位或后得到 \(x\)，那么在二进制下的同一位中，\(x\) 为 \(0\) 的时候，\(p\) 也一定要为 \(0\)。
这是我们唯一需要考虑的限制。
有趣的是，如果不满足上面的限制，你会发现 \(x | p > x\)。并且，因为按位或运算，得到的数不可能变小，因而我们只要对每一堆数，从左到右找出第一个 \(x | p > x\)，那么它左边的所有数都可以参与运算。
因而，将这些可以参与运算的数全都进行按位或，最后如果还是不等于 \(x\)，就是不可以。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n, x;
cin >> n >> x;
vector<int> a(n + 1);
vector<int> b(n + 1);
vector<int> c(n + 1);
int mxa = 0;
for(int i=1;i<=n;i++){
cin >> a[i];
a[i] |= a[i - 1];
if((a[i] | x) <= x) mxa = a[i];
}
int mxb = 0;
for(int i=1;i<=n;i++){
cin >> b[i];
b[i] |= b[i - 1];
if((b[i] | x) <= x) mxb = b[i];
}
int mxc = 0;
for(int i=1;i<=n;i++){
cin >> c[i];
c[i] |= c[i - 1];
if((c[i] | x) <= x) mxc = c[i];
}
if((mxa | mxb | mxc) == x) cout << "Yes\n";
else cout << "No\n";
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}队友写了 \(\mathtt{bitset}\)，有点玄幻
C. Tenzing and Balls
题意
给定一串序列，定义一次操作为选定两个相等的元素，并将其与包含在两个元素内的所有元素全部删除。
输出最多能删多少元素。
思路
首先，我们不难发现我们不可以删除两个相交的区间。
因而，我们只需考虑删除哪些不重叠的区间，最后得到的答案最大即可。
因而，我们考虑 \(dp\)。
我们可以正算也可以反算，这边采用反着算的方法，算出保留的最小元素数 \(ans\)，然后输出 \(n - ans\)：
我们定义 \(dp[i][j]\) 为 \([1, i]\) 中第 \(i\) 个元素是否作为删除区间的右端点 \((j)\) 保留的元素数的最小值。
那么，如果不删，\(dp[i][0] = \min(dp[i - 1][0], dp[i - 1][1]) + 1\)；
如果删，我们就需要知道我们得跳过多少元素。
因而，我们定义 \(b[x]\) 为 \([1, i - 1]\) 中值为 \(x\) 的所有元素中 \(dp[i][0] - 1\) 最小的一个。
那么，\(dp[i][1] = \min(dp[i][1], b[x])\)。
最后，我们考虑一下初始化。如果我们一点都不操作，那么最后 \(dp[i][0] = dp[i][1] = i\)。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
vector<vector<int>> dp(n + 1, vector<int>(2));
for (int i = 1; i <= n; i++) {
cin >> a[i];
dp[i][0] = dp[i][1] = i;
}
vector<int> b(n + 1, n + 1);
for (int i = 1; i <= n; i++) {
dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + 1; //不选
if (b[a[i]] != n + 1) dp[i][1] = b[a[i]];
b[a[i]] = min(b[a[i]], min(dp[i - 1][0], dp[i - 1][1]));
}
cout << (n - min(dp[n][0], dp[n][1])) << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}还真没往 \(dp\) 上想（
D. Tenzing and His Animal Friends
题意
给定 \(n\) 个人，定义一场游戏为选择若干个人并任选游戏时长。
输出在下面给定限制中，总游戏时间最长为多少，以及能组织多少种游戏：
一定要选 \(1\)；
不能选 \(n\)；
满足给定的 \(m\) 个条件，条件以 \(u\ v\ y\) 给出，表示所有游戏中 \(u\) 出现但 \(v\) 不出现 或 \(u\) 不出现但 \(v\) 出现 的总时长和 \(\leq y\)。
思路
首先，因为 \(1\) 一定在游戏中，\(n\) 一定不在游戏中，那么如果没有关于 \(1\ n\) 的直接或间接的限制，最后就是无穷大了。
那么，如果上述限制存在，我们可以证明其一定有解。我们接着分析条件。
第三个条件过于复杂了，我们不妨将其中一种情况的时长减为 \(0\)，那么另一个的最大时间就能确定了。
因而，我们可以从 \(1\) 开始，依次加入节点。那么，对于节点 \(i\)，它具有被加入的时间 \(T_i\)。对于条件 \(u\ v\ y\)，我们可以将其转化为 \(|T_u - T_v| \leq y\)。
上式即为差分约束系统问题，我们可以用最短路算法解决本题。
考虑到数据量小，我们直接用 \(\mathtt{floyd}\)。
显然，结合差分约束的知识，我们不难发现，因为 \(n\) 一定不在游戏中，所以节点 \(p\) 到节点 \(n\) 的最短路就是节点 \(p\) 在所有游戏中的总时间。
因而，我们只要按照其到 \(n\) 的最短路长度升序排序，并将 每次放入的节点 和 上一个放入的节点 的 时间差 作为该场游戏的持续时间，即可让总时间最大。
当然，最大不会超过 \(1\ n\) 之间的最短路长度。
时间复杂度：\(O(n ^ 3)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define psi pair<string, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n, m;
cin >> n >> m;
vector<vector<int>> dist(n + 1, vector<int>(n + 1, inf));
for(int i=1;i<=n;i++) dist[i][i] = 0;
for(int i=0;i<m;i++){
int u, v, y;
cin >> u >> v >> y;
dist[u][v] = dist[v][u] = min(dist[u][v], y);
}
//floyd
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
if(dist[1][n] >= inf){
cout << "inf\n";
return;
}
vector<pii> to(n - 1);
for(int i=1;i<n;i++) to.pb(min(dist[n][i], dist[1][n]), i - 1);
sort(all(to));
vector<psi> ans;
int pre = 0;
for(int i=0;i<to.size();i++){
int d = to[i].fs - pre;
pre = to[i].fs;
if(d == 0) continue;
string s;
for(int j=1;j<=n;j++) s += "0";
for(int j=i;j<to.size();j++) s[to[j].sc] = '1';
ans.pb(s, d);
}
cout << dist[1][n] << ' ' << ans.size() << '\n';
for(auto [s, d] : ans) cout << s << ' ' << d << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while(t --) solve();
}只可意会（