Educational Codeforces Round 58 Solution

A. Minimum Integer

签到。

#include <bits/stdc++.h>
using namespace std;

#define ll long long
ll l, r, d;

int main()
{
    int t; scanf("%d", &t);
    while (t--)
    {
        scanf("%lld%lld%lld", &l, &r, &d);
        if (d < l) printf("%lld
", d);
        else printf("%lld
", ((r / d) + 1) * d);
    }
    return 0;
}

B. Accordion

签到。

#include <bits/stdc++.h>
using namespace std;

#define N 5000010
char s[N];

int work()
{
    int l = -1, r = -1, flag, len = strlen(s + 1);
    flag = false;
    for (int i = 1; i <= len; ++i) 
    {
        if (s[i] == '[') flag = true; 
        else if (s[i] == ':' && flag) 
        {
            l = i;
            break;
        }
    } 
    if (l == -1) return -1;
    flag = false;
    for (int i = len; i >= 1; --i)
    {
        if (s[i] == ']') flag = true;
        else if (s[i] == ':' && flag)
        {
            r = i;
            break;
        }
    }
    if (r == -1) return -1;
    if (r <= l) return -1;
    int res = 4;
    for (int i = l + 1; i < r; ++i) if (s[i] == '|')
        ++res;
    return res;
}

int main()
{
    while (scanf("%s", s + 1) != EOF)
        printf("%d
", work());
    return 0;
}

C. Division and Union

Solved.

题意：

有n个区间，将它分成两个集合，使得每个集合任意出一个区间组成的一对，这对没有交

思路：

按左端点排序，如果存在这样的划分，那么必定一个界限使得当前区间与之前的那个区间没有交，这样的话，后面的区间和之前的区间都不会有交

#include <bits/stdc++.h>
using namespace std;

#define N 100010
int t, n, ans[N];
struct node
{
    int l, r, id;
    void scan(int id) { scanf("%d%d", &l, &r); this->id = id; } 
    bool operator < (const node &other) const { return l < other.l || (l == other.l && r < other.r); }
}a[N];

int main()
{
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n); 
        for (int i = 1; i <= n; ++i) a[i].scan(i);
        sort(a + 1, a + 1 + n);
        int pos = -1; int maxr = a[1].r;
        for (int i = 2; i <= n; ++i)
        {
            if (a[i].l > maxr)
            {
                pos = i;
                break; 
            }
            maxr = max(maxr, a[i].r);
        }
        if (pos == -1) puts("-1");
        else 
        {
            for (int i = 1; i <= n; ++i) ans[a[i].id] = i < pos ? 2 : 1;
            for (int i = 1; i <= n; ++i) printf("%d%c", ans[i], " 
"[i == n]);
        }    
    }
    return 0;
}

D. GCD Counting

Upsolved.

题意：

一棵树中，每个点有权值，找出一条最长的简单路径，使得这个路劲上所有点的点权的gcd > 1

思路：

枚举质因子，再在虚树上dp

质因子很多，有1w多个，但是我们考虑每个质因子对应的集合的总和不会太多，

因为一个数的质因子个数不会太多，2e5一下也就十几个，那么一个数的贡献也就十几个

最后的总和就是O(nlogn)级别的

其实不用建虚树，直接在dfs序上dp就可以了

#include <bits/stdc++.h>
using namespace std;

#define N 200010
int n, a[N], res;
vector <int> G[N];
vector <int> fac[N];  

int fa[N], p[N], pos[N], cnt; int f[2][N]; 
void pre(int u)
{
    p[u] = ++cnt;
    for (auto v : G[u]) if (v != fa[u])
    {
        fa[v] = u;
        pre(v);
    }
}

void init()
{
    for (int i = 1; i <= n; ++i) G[i].clear();
    for (int i = 2; i < N; ++i) fac[i].clear();    
    memset(pos, -1, sizeof pos);
    res = 0; cnt = 0;
}

int main()
{
    while (scanf("%d", &n) != EOF)
    {
        init();
        for (int i = 1; i <= n; ++i) scanf("%d", a + i);
        for (int i = 1, u, v; i < n; ++i)
        {
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        pre(1);
        for (int i = 1; i <= n; ++i)
        {
            int tmp = a[i];
            int limit = sqrt(tmp);
            for (int j = 2; j <= limit; ++j)
            {
                if (tmp % j == 0)
                {
                    fac[j].push_back(i);
                    while (tmp % j == 0) tmp /= j;
                }
            }
            if (tmp != 1) fac[tmp].push_back(i); 
        }
        for (int i = 2; i < N; ++i) if (fac[i].size() >= 1)
        {
            sort(fac[i].begin(), fac[i].end(), [](int x, int y) { return p[x] > p[y]; }); 
            int len = fac[i].size(); 
            for (int j = 0; j < len; ++j) for (int o = 0; o < 2; ++o) f[o][j] = 0;
            for (int j = 0; j < len; ++j) pos[fac[i][j]] = j;
            for (int j = 0, u, v; j < len; ++j) 
            {
                v = fac[i][j];
                res = max(res, f[0][j] + f[1][j] + 1);
                if (pos[fa[v]] != -1) 
                {
                    int id = pos[fa[v]];
                    if (f[0][j] + 1 >= f[0][id])
                    {
                        f[1][id] = f[0][id];
                        f[0][id] = f[0][j] + 1;
                    }
                    else if (f[0][j] + 1 >= f[1][id])
                    {
                        f[1][id] = f[0][j] + 1;
                    }
                }
            }
            for (int j = 0; j < len; ++j) pos[fac[i][j]] = -1;
        }
        printf("%d
", res);
    }
    return 0;
}

E. Polycarp's New Job

签到.

#include <bits/stdc++.h>
using namespace std;

#define N 500010
int n, x, y, l, r; char op[10];

int main()
{
    l = 0, r = 0;
    scanf("%d", &n);
    while (n--)
    {
        scanf("%s%d%d", op, &x, &y);
        if (x > y) swap(x, y);
        if (op[0] == '+')
        {
            l = max(l, x);
            r = max(r, y);
        }
        else
        {
            puts(l <= x && r <= y ? "YES" : "NO");
        }
    }
    return 0;
}

F. Trucks and Cities

Upsolved.

题意：

$有n个城市，有m辆卡车需要从s_i -> f_i 每公里耗油c_i升，最多加油r_i次$

$求最小的油箱体积，使得所有卡车都能在加油次数内到达目的地$

思路：

本来考虑二分$但是复杂度是O(n cdot m cdot log(10^{18}))$

考虑$dp$

$dp[i][j][k] 表示从i -> j 最多加油k次的最少油箱容量$

$dp[i][j][k] = min_{w = i}^{j} max(dp[i][w][k - 1], a[j] - a[w])$

我们发现 $dp[i][w][k - 1] 随着w递增而增加，a[j] - a[w] 随着w递增而减少$

$但是，max(dp[i][w][k - 1], a[j] -a[w]) 是先减后增的$ 

并且随着$j的右移动，决策点肯定只会向右移动，而不会回到左边$

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define N 401
int n, m, a[N];
int f[N][N][N];

int main()
{
    while (scanf("%d%d", &n, &m) != EOF)
    {
        for (int i = 1; i <= n; ++i) scanf("%d", a + i);
        memset(f, 0, sizeof f);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                f[i][j][0] = a[j] - a[i];
        for (int k = 1; k <= n; ++k)
            for (int i = 1, w; i <= n; ++i)
            {
                w = i;
                for (int j = i + 1; j <= n; ++j) 
                {
                    while (w < j && max(f[i][w + 1][k - 1], a[j] - a[w + 1]) <= max(f[i][w][k - 1], a[j] - a[w])) ++w;
                    f[i][j][k] = max(f[i][w][k - 1], a[j] - a[w]); 
                }
            }
        ll res = 0;
        for (int i = 1, s, e, c, r; i <= m; ++i)
        {
            scanf("%d%d%d%d", &s, &e, &c, &r);
            res = max(res, 1ll * c * f[s][e][r]);
        }
        printf("%lld
", res);
    }
    return 0;
}

G. (Zero XOR Subset)-less

Upsolved.

题意：

将一些数分组，使得没有任意一个这些组的子集的异或和等于0

思路：

如果所有数异或起来等于$0$就是无解的情况

否则就是线性基中基的个数，因为每个基的最高位的$1所在位置不同$

$所以这些基不管怎么异或都不会是0$

#include <bits/stdc++.h>
using namespace std;

#define N 200010
int n, a[N], p[110];

int main()
{
    while (scanf("%d", &n) != EOF)
    {
        int t = 0;
        for (int i = 1; i <= n; ++i) scanf("%d", a + i), t ^= a[i];
        if (!t) puts("-1");
        else
        {
            memset(p, 0, sizeof p);
            for (int i = 1; i <= n; ++i)
               for (int j = 31; j >= 0; --j) 
                    if ((a[i] >> j) & 1)
                     {
                        if (!p[j]) 
                        {
                            p[j] = a[i];
                            break;
                        }
                        else a[i] ^= p[j];
                    }        
            int res = 0;
            for (int i = 0; i < 32; ++i) if (p[i]) ++res;
            printf("%d
", res);
        }
    }
    return 0;
}