Practice.

A. Cut the Triangle

题意

给定三个点，判断是否存在水平或数值的切割线，能将三个点所构成的三角形切割成两个三角形。

思路

很显然，我们只需判断是否存在直角三角形即可。

因为我们不知道哪个是直角，所以我们不妨找出所有 轴值相等的点和 轴相等的点。

更具体地说，我们统计一下满足上述条件的点，若为 个及以下，那么就可行，否则不可行。

时间复杂度：

对应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

题意

给定 个柱子，定义操作为选定两个大小不相等的柱子，并将大的柱子的一个方块移到小的柱子上。在任意次操作后，输出第一个柱子可能的最大方块数量。

思路

我们不妨直接排个序，然后找出第一个柱子的位置，并模拟。

当然，找位置可以用二分。

时间复杂度：

对应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

题意

给定一个数字 ，以及指定的约束，构造一个二进制字符串。

对于 行输入，第 行有 个数字。

第 行第 列元素的值表示 区间内容满足下面的约束：

1. 值为 ，那么区间内所有元素必须一致；
2. 值为 ，那么区间内至少存在一个数和其他数不同；
3. 值为 ，无约束。

输出在上述约束下能构造多少个字符串。

思路

我们不难发现，要构造出不同的字符串，那么该位必须可以选 和 。

又或者说，对于点 ，我们需要知道 之间有多少和 不同的值。

考虑到前者的约束会影响后者，我们不妨考虑 。

我们可以枚举所有 ，与其不同的元素位于 （当然，如果没有这个元素， 即可），那么我们可以找出下面两种情况：

1. 当前位和前一位相同，那么 ；
2. 当前位和前一位不同，那么 。

接下来，我们来考虑约束：

对于约束右区间为 ：

首先，对于情况 ，我们不能让 前面的约束存在 ，也不能让后面的约束存在 ，这样我们可以判断 是否可行，也可以判断 是否成立。

其次，对于情况 ，我们也不能让 之前的约束存在 ，否则 不成立。

满足上述条件后，对于递推的结果，枚举所有不同的点，右区间为 ，求和即可。

时间复杂度：

对应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

题意

给定一个整数 ，对于一个任意 的排列，存在 场比赛， 和 进行比赛，满足下述比赛规则，获胜者进入下一轮，直到决出最后的胜利者。输出对于任意排列，胜利者会是哪些人。

规则：给定一个长度为 的二进制字符串，第 位决定了第 场比赛的输赢。若值为 ，那么数值小的一方获胜，否则数值大的一方获胜。

思路

我们不妨先来找规律：

对于题例数据，我们不难发现，统计一下 的个数 和 的个数 ，答案即为 内的所有数。

下面给出证明：

首先，我们不难发现，交换字符串某两位的位置，对最后两端的输赢是无影响的，只会决定最后的赢家；

并且，当值为 的时候，一定是大一点的值获胜，为 时一定时小一点的值获胜。

换句话说，决定了 和 的个数后，升序排序下两端一定范围内的值是一定不会取到的，因为在多场比赛后，一定会被筛去。

而正好相反地，除去这些一定会被筛去的值，剩余值一定有一种排列可以使它们成为赢家，因此证明了结论的正确性。

时间复杂度：

对应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;
}

妥妥一个找规律（（