[Codeforces]669 div2
本文最后更新于 131 天前,其中的信息可能已经有所发展或是发生改变。

一场CF比赛

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。
原文链接:https://www.codein.icu/cf1407/

前言

补题。

D

从 $i$ 到 $j$ 只需满足三个条件中的一个:

  1. $i + 1 = j$,即相邻时。
  2. $\max(h_{i+1},h_{i+2},\ldots,h_{j-1}) < \min(h_i,h_j)$
  3. $\min(h_{i+1},h_{i+2},\ldots,h_{j-1}) > \max(h_i,h_j)$

第一个很显然,考虑第二、第三个条件怎么处理。
第二个条件表明,从 $i$ 能跳到往后第一个不小于 $i$ 的数 $j$,在此过程中:
由定义知, $h_j \geq h_i$,而 $k \in [i+1,j-1],h_k < h_i \leq h_j$.
且不能跳到比 $j$ 更靠后的位置,否则 $h_j$ 不满足严格小于 $h_i$.

第三个条件表明,从 $i$ 能跳到往后第一个不大于 $i$ 的数 $j$,在此过程中:

由定义知,$h_j \leq h_i$,而 $k\in [i+1,j-1],h_k > h_i \geq h_j$.

且不能跳到比 $j$ 更靠后的位置,否则 $h_j$ 不满足严格大于 $h_i$.

还需要考虑到反过来的情况,例如 $3,5,4$,即 $h_j \geq h_i$ 但依然满足 $h\in [i+1,j-1],h_k > h_j > h_i$ 的条件,可以转移。

所以每个点:以前面的点更新当前点,用当前点更新后面的点。

单调栈预处理。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 5e5 + 100;
int n,a[maxn];
int lasmax[maxn],lasmin[maxn],nexmax[maxn],nexmin[maxn],st[maxn],top;
int f[maxn];
int main()
{
    memset(f,0x3f,sizeof(f));
    read(n);
    for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = 1; i <= n; ++i) 
    {
        while(top && a[st[top]] <= a[i]) nexmax[st[top--]] = i;
        st[++top] = i;
    }
    while(top) nexmax[st[top--]] = n + 1;
    for (int i = 1; i <= n; ++i) 
    {
        while(top && a[st[top]] >= a[i]) nexmin[st[top--]] = i;
        st[++top] = i;
    }
    while(top) nexmin[st[top--]] = n + 1;
    for (int i = n; i; --i) 
    {
        while(top && a[st[top]] <= a[i]) lasmax[st[top--]] = i;
        st[++top] = i;
    }
    while(top) lasmax[st[top--]] = 0;
    for (int i = n; i; --i) 
    {
        while(top && a[st[top]] >= a[i]) lasmin[st[top--]] = i;
        st[++top] = i;
    }
    while(top) lasmin[st[top--]] = 0;
    f[1] = 0;
    for (int i = 1; i <= n; ++i) 
    {
        f[i] = std::min(f[i],f[lasmax[i]] + 1);
        f[i] = std::min(f[i],f[lasmin[i]] + 1);
        f[nexmax[i]] = std::min(f[nexmax[i]],f[i] + 1);
        f[nexmin[i]] = std::min(f[nexmin[i]],f[i] + 1);
        f[i + 1] = std::min(f[i + 1], f[i] + 1);
    }
    printf("%d\n",f[n]);
    return 0;
}

E

给每个点选择颜色,从该点出发只能走与该点颜色相同的边。
边权都为 $1$,问从 $1$ 到 $n$ 的最短路的最大值是多少。

虽然遇到最值问题容易想到二分,但这题二分没看出怎么做。

用宽度优先搜索求解。
从终点开始考虑,与终点相连的点,选择恰当的颜色使其不相连。
然而有重边,说明可能有点无法被切断。此时,这些点无论如何都能一步走到终点,因此选择任意颜色皆可。

将这些点放入队列中,重复上述过程。
可以发现,由于边权为 $1$,队列中每个点都已求出最短路。
当 $1$ 号点入队时,全图最短路已求出,终止算法。

然而为什么要反着搜呢?若从起点开始,选择一个点的颜色会影响相连的多个点的最短路;而从终点开始,每个点的颜色仅与它本身有关。

#include <algorithm>
#include <cstdio>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
#ifdef DEBUG
    return getchar();
#endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline T read(T& r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 500100;
struct node
{
    int to, next, col;
} E[maxn];
int head[maxn];
inline void add(const int& x, const int& y, const int& col)
{
    static int tot = 0;
    E[++tot].next = head[x], E[tot].col = col, E[tot].to = y, head[x] = tot;
}
int n, m;
int dis[maxn], col[maxn], vis[maxn];
int q[maxn], qh, qt;
int main()
{
    read(n), read(m);
    for (int i = 1; i <= n; ++i) col[i] = -1;
    while (m--)
    {
        int a, b, c;
        read(a), read(b), read(c), add(b, a, c);
    }
    qh = 1;
    q[++qt] = n;
    vis[n] = 1;
    while (qt >= qh)
    {
        int u = q[qh++];
        if (u == 1) break;
        for (int p = head[u]; p; p = E[p].next)
        {
            int v = E[p].to;
            if (vis[v]) continue;
            if (col[v] == -1) col[v] = 1 ^ E[p].col;
            else if (col[v] == E[p].col) dis[v] = dis[u] + 1, q[++qt] = v, vis[v] = 1;
        }
    }
    printf("%d\n", vis[1] ? dis[1] : -1);
    for (int i = 1; i <= n; ++i) putchar(col[i] ? '1' : '0');
    return 0;
}

A

移除数,可以理解为选出数。
选出 $\geq \dfrac{n}{2}$ 个数,考虑全选零或全选一。
选零则随意,选一则保证选偶数个。
注意零一个数相同时必须选零。否则一的数目化为偶数后可能不足。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 1e3 + 100;
int T,n,a[maxn],b[maxn];
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        int zero = 0,one = 0;
        for (int i = 1; i <= n; ++i) read(a[i]), zero += a[i] ^ 1, one += a[i];
        if(zero >= n / 2)
        {
            printf("%d\n",zero);
            for (int i = 1; i <= zero; ++i) printf("0 ");
            puts("");
        }
        else
        {
            if(one & 1) one--;
            printf("%d\n",one);
            for (int i = 1; i <= one; ++i) printf("1 ");
            puts("");
        }
    }
    return 0;
}

B

要求字典序最大,根据字典序进行贪心。
第一个数一定选最大值,每次加入一个数 $\gcd$ 只能变小,且该位对字典序大小起决定性作用,贪心地寻找能使 $\gcd$ 最大的数用上即可。

由于 $\gcd$ 满足结合律,因此可以储存 $\gcd$ 的前缀和用于查找。时间复杂度 $O(n^2\log n)$,具体实现看代码.

#include <algorithm>
#include <cstdio>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
#ifdef DEBUG
    return getchar();
#endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline T read(T& r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }
const int maxn = 1e3 + 100;
int T, n, a[maxn], used[maxn], b[maxn], c[maxn];
int main()
{
    read(T);
    while (T--)
    {
        read(n);
        for (int i = 1; i <= n; ++i) read(a[i]), used[i] = 0;
        int maxi = 1;
        for (int i = 2; i <= n; ++i) if (a[maxi] < a[i]) maxi = i;
        used[maxi] = 1, b[1] = c[1] = a[maxi];
        for (int i = 2; i <= n; ++i)
        {
            int maxx = 0, maxj = 0;
            for (int j = 1; j <= n; ++j)
            {
                if (used[j]) continue;
                int t = gcd(b[i - 1], a[j]);
                if (t > maxx) maxx = t, maxj = j;
            }
            used[maxj] = 1, b[i] = maxx, c[i] = a[maxj];
        }
        for (int i = 1; i <= n; ++i) printf("%d ", c[i]);
        puts("");
    }
    return 0;
}

C

可以操作 $2n$ 次,考虑对相邻的数进行询问。

$a < b$ 时,$a \bmod b > b \bmod a$,显然后者 $< a$ 而前者 $= a$.

而此时 $a \bmod b$ 可以确定 $a$ 的值,但无法确定较大者 $b$ 的值。
因此从前往后,依次拿当前最大值和新值询问,以期确定最大值。

#include <iostream>
using namespace std;
const int maxn = 1e4 + 100;
int n,ans[maxn],maxx;
inline int ask(int x,int y)
{
    cout << "? " << x << " " << y << endl;
    int res;
    cin >> res;
    return res;
}
int main()
{
    cin >> n;
    maxx = 1;
    for(int i = 2;i<=n;++i)
    {
        int a = ask(maxx,i);
        int b = ask(i,maxx);
        if(a > b)
        {
            //maxx < i
            ans[maxx] = a;
            maxx = i;
        }
        else ans[i] = b;
    }
    ans[maxx] = n;
    cout << "! ";
    for (int i = 1; i <= n; ++i) cout << ans[i] << " ";
    cout << endl;
    return 0;
}
本文标题:[Codeforces]669 div2
本文作者:Clouder
本文链接: https://www.codein.icu/cf1407/
转载请标明。

评论

  1. 4月前
    2020-9-15 12:13:41

    您一天写了十篇题解!太强了!

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇