Educational Codeforces Round 138 (Rated for Div. 2) A-E

比赛链接

A

题解

知识点:贪心。

注意到 (mgeq n) 时,不存在某一行或列空着,于是不能移动。

(m 时,一定存在,可以移动。

时间复杂度 (O(1))

空间复杂度 (O(1))

代码

#include 
#define ll long long

using namespace std;

bool solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 1;i > x >> y;
    }
    if (m >= n) return false;
    else cout > t;
    while (t--) {
        if (!solve()) cout 

B

题解

知识点:贪心。

每次干掉两端 (b) 最小的即可,能保证最大的 (b) 没有增加花费,其他 (b) 只增加花费一次。

时间复杂度 (O(n))

空间复杂度 (O(n))

代码

#include 
#define ll long long

using namespace std;

int a[200007], b[200007];
bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i > a[i];
    for (int i = 1;i > b[i];

    ll sum = 0;
    for (int i = 1;i > t;
    while (t--) {
        if (!solve()) cout 

C

题解

知识点:博弈论,贪心,二分。

本来数据范围能暴力,但执着找规律推结论,结果推假了wwwwwwwwww,不如直接暴力QAQ。

显然二分 (k) 可以,$k in[1,lceil frac{n}{2} rceil] $。二者选取的贪心策略也很明显,A尽量取大的,B取最小的,推到这一步可以直接模拟了。

但进一步可以推出,A取后 (k) 个之后,B一定取了前 (k-1) 个,那么我们把前 (k-1) 个空出来,让A直接从 (k) 开始取是最优的,正着取的第 (i) 个是第 (k-i+1) 回合,只要小于等于 (i) 即可。

时间复杂度 (O(n log n))

空间复杂度 (O(n))

代码

#include 
#define ll long long

using namespace std;

int n;
int a[107];
bool check(int mid) {
    bool ok = 1;
    for (int i = 1;i > n;
    for (int i = 1;i > a[i];
    sort(a + 1, a + n + 1);
    int l = 1, r = n + 1 >> 1;
    while (l > 1;
        if (check(mid)) l = mid + 1;
        else r = mid - 1;
    }
    cout > t;
    while (t--) {
        if (!solve()) cout 

D

题解

知识点:数论,筛法。

注意到,我们要求的是每个元素不超过 (m) 的正整数,长度 ([1,n]) 的每个长度的不明确的序列个数之和。我们先考虑长度为 (n) 的情况,其他长度可以同理。

所有序列天生有一组 ([1,1,1,1,cdots]) 的删除序列,这代表只要序列有一个元素能在 (1) 以外的位置删除,就能产生新的删除序列,则原序列就是不明确的。

因为可以通过移除第一项,让 (a[i]) 往前挪,必然会经过 ([2,i]) 的所有位置,所以若要使 (a[i]) 可在 (1) 以外的位置删除,需要 (a[i]) 存在 ([2,i]) 内的数与其没有公共质因子,更进一步,即不包含所有前缀素数(([2,i]) 所有数的质因子种类,即其中所有素数),这样就一定存在 (2leq jleq i) 使 (gcd(j,a[i]) = 1)

注意到,计算在 (a[i]) 位置上 ([1,m]) 中符合条件的数的个数很困难,但计算包含所有前缀质因子的情况很容易, (frac{m}{mul_i}) 就是 ([1,m]) 所有前缀质因子都存在的数的个数,其中 (mul_i) 是位置 (i) 的前缀质因子乘积。

我们计算出 ([1,n]) 每个位置的 (frac{m}{mul_i}) ,即每个位置其前缀质因子都存在数的个数,把他们乘法原理乘在一起,就代表长度为 (n) 明确的数列的个数 (prod_{i=1}^n frac{m}{mul_i}) ,因为每个位置组合的都是包含所有前缀质因子,除了在 (1) 处删除,其他地方 (gcd(i,a[i]) neq 1) 不能删。

最后对于长度 (n) 的数列,所有情况一共 (m^n) 种,所以最后不明确的数列个数为 (m^n - prod_{i=1}^n frac{m}{mul_i})

我们对 ([1,n]) 所有长度的答案求和,有 (ans = sum_{i=1}^n (m^i - prod_{j=1}^i frac{m}{mul_j})) ,注意到 (m^i)(mul_i) 以及 (prod_{j=1}^i frac{m}{mul_j}) 可以从 (1) 递推,过程中加到答案里即可。

时间复杂度 (O(n))

空间复杂度 (O(n))

代码

#include 
#define ll long long

using namespace std;

const int mod = 998244353;

int cnt;
int vis[300007];
int prime[300007] = { 1 };
void euler_screen(int n) {
    for (int i = 2;i > n >> m;
    euler_screen(n);
    int base = 1, mul = 1, ans = 0;
    ll  fact = 1;
    for (int i = 1;i 

E

题解

知识点:bfs。

思考明白了就是一个很简单的01bfs。

注意到我们需要让从第一行到第 (n) 行不存在路径,反过来想就是需要一条从第一列到第 (m) 列连续的横向仙人掌路径,才能阻挡所有竖向路径,这个路径要求花费最少,于是问题转化问从第一列出发到第 (m) 列的仙人掌最短路,起点是第一列所有点,有仙人掌的格子花费为 (0) ,没有的花费是 (1)

搜索过程中用一个 map 记录前驱坐标即可复原路径。

这道题主要在这个思考和转化的过程。

时间复杂度 (O(nm))

空间复杂度 (O(nm))

代码

#include 
#define ll long long

using namespace std;

const int dir[4][2] = { {1,1},{1,-1},{-1,1},{-1,-1} };
const int dir2[4][2] = { {1,0},{0,1},{0,-1},{-1,0} };

bool solve() {
    int n, m;
    cin >> n >> m;
    vector> dt(n + 1, vector(m + 1));
    for (int i = 1;i > dt[i][j];
    auto check = [&](int x, int y) {
        bool ok = 1;
        for (int i = 0;i  n || yy  m) continue;
            ok &= dt[xx][yy] != '#';
        }
        return ok;
    };
    deque> dq;
    vector> vis(n + 1, vector(m + 1));
    map, pair> pre;
    pair p = { 0,0 };
    for (int i = 1;i  n || yy  m || vis[xx][yy]) continue;
            if (dt[xx][yy] == '#') dq.push_front({ xx,yy }), vis[xx][yy] = 1, pre[{xx, yy}] = { x,y };
            else if (check(xx, yy)) dq.push_back({ xx,yy }), vis[xx][yy] = 1, pre[{xx, yy}] = { x,y };

        }
    }
    auto &[px, py] = p;
    if (!px && !py) return false;
    cout > t;
    while (t--) {
        if (!solve()) cout 

文章来源于互联网:Educational Codeforces Round 138 (Rated for Div. 2) A-E

THE END
分享
二维码