0%

Codeforces - Educational Codeforces Round 140

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

妥妥一个找规律((