Practice.
A. Cut the Triangle
题意
给定三个点，判断是否存在水平或数值的切割线，能将三个点所构成的三角形切割成两个三角形。
思路
很显然，我们只需判断是否存在直角三角形即可。
因为我们不知道哪个是直角，所以我们不妨找出所有 \(x\) 轴值相等的点和 \(y\) 轴相等的点。
更具体地说，我们统计一下满足上述条件的点，若为 \(1\) 个及以下，那么就可行，否则不可行。
时间复杂度：\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 110;
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t --){
int x1, y1, x2, y2, x3, y3;
cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
cout << ((x1 == x2 || x2 == x3 || x1 == x3) && (y1 == y2 || y2 == y3 || y1 == y3) ? "NO" : "YES") << '\n';
}
return 0;
}简简单单打卡题
B. Block Towers
题意
给定 \(n\) 个柱子，定义操作为选定两个大小不相等的柱子，并将大的柱子的一个方块移到小的柱子上。在任意次操作后，输出第一个柱子可能的最大方块数量。
思路
我们不妨直接排个序，然后找出第一个柱子的位置，并模拟。
当然，找位置可以用二分。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200010;
int a[N];
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t, n;
cin >> t;
while(t --){
cin >> n;
for(int i=0;i<n;i++) cin >> a[i];
int a0 = a[0];
sort(a, a + n);
int t = upper_bound(a, a + n, a0) - a;
for(int i=t;i<n;i++){
if(a[i] > a0) a0 += (a[i] - a0 + 1) / 2;
}
cout << a0 << '\n';
}
return 0;
}好模拟
C. Count Binary Strings
题意
给定一个数字 \(n\)，以及指定的约束，构造一个二进制字符串。
对于 \(n\) 行输入，第 \(i\) 行有 \(n - i + 1\) 个数字。
第 \(i\) 行第 \(j\) 列元素的值表示 \([i+j-1, n]\) 区间内容满足下面的约束：
- 值为 \(1\)，那么区间内所有元素必须一致；
- 值为 \(2\)，那么区间内至少存在一个数和其他数不同；
- 值为 \(0\)，无约束。
输出在上述约束下能构造多少个字符串。
思路
我们不难发现，要构造出不同的字符串，那么该位必须可以选 \(0\) 和 \(1\)。
又或者说，对于点 \(i\)，我们需要知道 \([1,i-1]\) 之间有多少和 \(i\) 不同的值。
考虑到前者的约束会影响后者，我们不妨考虑 \(dp\)。
我们可以枚举所有 \(i\)，与其不同的元素位于 \(j\)（当然，如果没有这个元素，\(j=0\) 即可），那么我们可以找出下面两种情况：
- 当前位和前一位相同，那么 \(dp[i+1][j]\ += dp[i][j]\)；
- 当前位和前一位不同，那么 \(dp[i+1][i]\ += dp[i][j]\)。
接下来，我们来考虑约束：
对于约束右区间为 \(i\)：
首先，对于情况 \(1\)，我们不能让 \(j\) 前面的约束存在 \(1\)，也不能让后面的约束存在 \(2\)，这样我们可以判断 \(dp[i][j]\) 是否可行，也可以判断 \(dp[i+1][j]\) 是否成立。
其次，对于情况 \(2\)，我们也不能让 \(i\) 之前的约束存在 \(1\)，否则 \(dp[i+1][i]\) 不成立。
满足上述条件后，对于递推的结果，枚举所有不同的点，右区间为 \(n\)，求和即可。
时间复杂度：\(O(n^3)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 110, mod = 998244353;
int a[N][N], dp[N][N];
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
for(int i=0;i<n;i++)
for(int j=i;j<n;j++)
cin >> a[i][j];
if(a[0][0] != 2) dp[1][0] = 2;
for(int i=1;i<n;i++)
for(int j=0;j<i;j++){
bool f = true;
for(int k=0;k<j;k++){
if(a[k][i] == 1) f = false;
}
for(int k=j;k<=i;k++){
if(a[k][i] == 2) f = false;
}
if(f) dp[i + 1][j] = ((dp[i + 1][j] % mod) + (dp[i][j] % mod)) % mod;
f = a[i][i] != 2;
if(f) for(int k=0;k<i;k++){
if(a[k][i] == 1) f = false;
}
if(f) dp[i + 1][i] = ((dp[i + 1][i] % mod) + (dp[i][j] % mod)) % mod;
}
int ans = 0;
for(int i=0;i<n;i++) ans = (ans % mod + dp[n][i] % mod) % mod;
cout << ans; //好绕
return 0;
}难死了，md
D. Playoff
题意
给定一个整数 \(n\)，对于一个任意 \(2^n\) 的排列，存在 \(n\) 场比赛，\(2i\) 和 \(2i+1\) 进行比赛，满足下述比赛规则，获胜者进入下一轮，直到决出最后的胜利者。输出对于任意排列，胜利者会是哪些人。
规则：给定一个长度为 \(n\) 的二进制字符串，第 \(i\) 位决定了第 \(i\) 场比赛的输赢。若值为 \(0\) ，那么数值小的一方获胜，否则数值大的一方获胜。
思路
我们不妨先来找规律：
对于题例数据，我们不难发现，统计一下 \(1\) 的个数 \(x\) 和 \(0\) 的个数 \(y\)，答案即为 \([2^x,2^n-2^y+1]\) 内的所有数。
下面给出证明：
首先，我们不难发现，交换字符串某两位的位置，对最后两端的输赢是无影响的，只会决定最后的赢家；
并且，当值为 \(1\) 的时候，一定是大一点的值获胜，为 \(0\) 时一定时小一点的值获胜。
换句话说，决定了 \(1\) 和 \(0\) 的个数后，升序排序下两端一定范围内的值是一定不会取到的，因为在多场比赛后，一定会被筛去。
而正好相反地，除去这些一定会被筛去的值，剩余值一定有一种排列可以使它们成为赢家，因此证明了结论的正确性。
时间复杂度：\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
int x = 0, y = 0;
for(int i=0;i<n;i++){
char now;
cin >> now;
if(now == '1') x ++;
else y ++;
}
for(int i=(1 << x);i<=((1 << n) - (1 << y) + 1);i++) cout << i << ' ';
return 0;
}妥妥一个找规律（（