Codefoces #1382 解题报告 & 部分翻译

by woshiluo

A Common Subsequence

0 题目大意

给你两个序列 $a,b$，求两个序列最短的公共子序列

1 代码

对，是最短……

// Woshiluo<[email protected]>
// 2020/07/21 22:41:11 
// Blog: https://blog.woshiluo.com

#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <algorithm>

template <class T> 
T Max( T a, T b ) { return a > b? a: b; }
template <class T> 
T Min( T a, T b ) { return a < b? a: b; }
template <class T> 
void chk_Max( T &a, T b ) { if( b > a ) a = b; }
template <class T> 
void chk_Min( T &a, T b ) { if( b < a ) a = b; }

const int N = 11000;

int T;
int a, b;
bool ta[N];

int main() {
    scanf( "%d", &T );
    while( T -- ) {
        scanf( "%d%d", &a, &b );
        memset( ta, 0, sizeof(ta) );
        for( int i = 1; i <= a; i ++ ) {
            int tmp;
            scanf( "%d", &tmp );
            ta[tmp] = 1;
        }
        int res = 0;
        for( int j = 1; j <= b; j ++ ) {
            int tmp;
            scanf( "%d", &tmp );
            if( ta[tmp] ) {
                res = tmp;
            }
        }
        if( res == 0 )
            printf( "NO\n" );
        else {
            printf( "YES\n%d %d\n", 1, res );
        }
    }
}

B Sequential Nim

0 题目大意

给你一 $n$ 堆石子，每次可以在第一堆拿 $x(1 \leq x \leq n)$ 个石子

第一个拿不到石子的人失败

1 思路

本来写了个 Nim 上去，然后才注意到是只能取第一个

取第一个就不复杂了，第一个碰到 $>1$ 的石子堆的人就能嬴

2 Code

// Woshiluo<[email protected]>
// 2020/07/21 23:02:11 
// Blog: https://blog.woshiluo.com

#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <algorithm>

template <class T> 
T Max( T a, T b ) { return a > b? a: b; }
template <class T> 
T Min( T a, T b ) { return a < b? a: b; }
template <class T> 
void chk_Max( T &a, T b ) { if( b > a ) a = b; }
template <class T> 
void chk_Min( T &a, T b ) { if( b < a ) a = b; }

int main() {
#ifdef woshiluo
    freopen( "b.in", "r", stdin );
    freopen( "b.out", "w", stdout );
#endif
    int T, n;
    scanf( "%d", &T );
    while( T -- ) {
        scanf( "%d", &n );
        int res = 0; bool chance = false;
        int tmp;
        for( int i = 1; i <= n; i ++ ) {
            scanf( "%d", &tmp );
            if( tmp == 1 && chance == false ) 
                res ++;
            else 
                chance = true;
        }
        if( chance ) 
            printf( "%s\n", ( res % 2 == 0 )? "First": "Second" );
        else 
            printf( "%s\n", ( res % 2 == 1 )? "First": "Second" );
    }
}

C Prefix Flip

0 题目大意

C1 是 C2 的简化版，然而 C2 并不难，所以就不管 C1 了

定义翻转为，将前 $k(1 \leq k \leq n)$ 个数字每一位反转，然后将前 $k$ 个数字颠倒

现在给你两个 01 串 $a, b$，询问如何从 $a$ 通过最多 $2n$ 次翻转变成 $b$

题目保证有解

1 思路

首先注意到，操作是可逆的，即执行两次相同的操作，等于没有操作

也就是我们可以先求出来

$$
\begin{aligned}
a \to c \\
b \to c
\end{aligned}
$$

的步骤，然后将 $b \to c$ 的步骤反过来即可

那么 $c$ 是什么呢，显然全 0 是一个优秀的选择

剩下的问题就是怎么变成全 0

从左往右，遇到一个 1，就先把前面的 0 变成 1，然后带上这个一起变成 0

这样极端情况下需要 $2n$ 次，总共就是 $4n$ 次，显然超出了要求

考虑将连续的 0 和连续的 1 看作一个字符，就可以优化到 $2n$ 次

2 Code

// Woshiluo<[email protected]>
// 2020/07/21 23:50:08 
// Blog: https://blog.woshiluo.com

#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <vector>
#include <algorithm>

template <class T> 
T Max( T a, T b ) { return a > b? a: b; }
template <class T> 
T Min( T a, T b ) { return a < b? a: b; }
template <class T> 
void chk_Max( T &a, T b ) { if( b > a ) a = b; }
template <class T> 
void chk_Min( T &a, T b ) { if( b < a ) a = b; }

int T;
int n;

int main() {
#ifdef woshiluo
    freopen( "c2.in", "r", stdin );
    freopen( "c2.out", "w", stdout );
#endif
    scanf( "%d", &T );
    while( T -- ) {
        std::vector<int> ans[2];
        scanf( "%d", &n );
        int la_0 = 0, la_1 = 0;
        for( int i = 1; i <= n; i ++ ) {
            int tmp; 
            scanf( "%1d", &tmp );
            if( tmp == 0 ) {
                if( la_1 ) {
                    if( la_0 )
                        ans[0].push_back(la_0);
                    ans[0].push_back(la_1);
                }
                la_1 = 0;
                la_0 = i;
            }
            else 
                la_1 = i;
        }
        if( la_1 ) {
            if( la_0 ) 
                ans[0].push_back(la_0);
            ans[0].push_back(la_1);
        }

        la_0 = 0, la_1 = 0;
        for( int i = 1; i <= n; i ++ ) { 
            int tmp; 
            scanf( "%1d", &tmp );
            if( tmp == 0 ) {
                if( la_1 ) {
                    if( la_0 ) 
                        ans[1].push_back(la_0);
                    ans[1].push_back(la_1);
                }
                la_1 = 0;
                la_0 = i;
            }
            else 
                la_1 = i;
        }
        if( la_1 ) {
            if( la_0 ) 
                ans[1].push_back(la_0);
            ans[1].push_back(la_1);
        }

        int size1 = ans[0].size(), size2 = ans[1].size();
        printf( "%d ", size1 + size2 );
        for( int i = 0; i < size1; i ++ ) 
            printf( "%d ", ans[0][i] );
        for( int i = size2 - 1; i >= 0; i -- ) 
            printf( "%d ", ans[1][i] );
        printf( "\n" );
    }
}

D Unmerge

0 题目大意

定义对两个序列的 merge 操作

  • $merge(a,b) = merge(b,a)$
  • $merge(a,\emptyset) = a$
  • $merge(\emptyset,\emptyset) = 0$
  • 如果 $a_1 \le b_1$ 那么 $merge(a,b) = a_1 + merge( [ a_2, \cdots, a_n ], b )$

现在给你一个长度为 $2n$ 的排列，寻问你能否通过两个长度为 $n$ 的序列 merge 而成

1 思路

考虑每出现一个比当前已知所有数字大的数字时，就会这之后的数字都应当和当前数字在一组，直到到下一个序列

所以我们可以将原排列划分成几块，看其能否拼成 $n$

所以这就是一个背包……

2 Code

// Woshiluo<[email protected]>
// 2020/07/22 14:19:08 
// Blog: https://blog.woshiluo.com

#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <vector>
#include <algorithm>

template <class T> 
T Max( T a, T b ) { return a > b? a: b; }
template <class T> 
T Min( T a, T b ) { return a < b? a: b; }
template <class T> 
void chk_Max( T &a, T b ) { if( b > a ) a = b; }
template <class T> 
void chk_Min( T &a, T b ) { if( b < a ) a = b; }

const int N = 4100;

int T;
int n;
int f[N];

int main() {
#ifdef woshiluo
    freopen( "d.in", "r", stdin );
    freopen( "d.out", "w", stdout );
#endif
    scanf( "%d", &T );
    while( T -- ) {
        scanf( "%d", &n );
        std::vector<int> val;
        int cnt = 0, max = 0;
        for( int i = 1; i <= ( n << 1 ); i ++ ) { 
            int tmp;
            scanf( "%d", &tmp );
            if( tmp > max ) {
                max = tmp;
                if( cnt != 0 )
                    val.push_back( cnt );
                cnt = 1;
            }
            else 
                cnt ++;
        }
        if( cnt != 0 ) 
            val.push_back(cnt);

        std::sort( val.begin(), val.end() );

        int size = val.size();
        memset( f, 0, sizeof(int) * ( n + 3 ) );
        f[0] = true;
        int cur = 1, la = 0;
        int len = 0;
        for( int i = 0; i < size; i ++ ) {
            len += val[i];
            if( len > n ) 
                len = n;
            for( int j = len; j - val[i] >= 0; j -- ) {
                f[j] |= f[ j - val[i] ];
            }
        }
        printf( "%s\n", f[n]? "YES": "NO" );
    }
}

E Mastermind

0 题目大意

给你一个长度为 $n$ 序列 $a$, 现在要求你给出一个长度为 $n$ 序列 $b$

其中满足 $a_i = b_i (1 \leq i \leq n)$ 的 $i$ 要有正好 $x$ 个

满足 $a_i = b_j ( 1 \leq i \leq j \leq n)$ 的 $i,j$ 要有正好 $y$ 个

如果不存在，输出 “NO”

如果存在，输出 “YES”，下接一行 $n$ 个数字，为 $b$

1 思路

谢谢 lk 的帮助，本菜鸡搞了好久也没搞懂

首先考虑 $x$，为了后面 $y$ 能取出来的尽可能多，所以优先选择出现频率最高的那一个

然后考虑 $y$, 要么交换两个不同的数字，来增加两对，要么交换一个，另一个放一个不存在的数字，来增加一个

但是有一种特殊情况 $n = 3, y = 3, a = [ 1, 2, 3]$

这种情况上面那种情况就会出大问题，但是显然，这个只需要轮转一回就可以了$(1 \to 2, 2 \to 3, 3 \to 1)$

2 Code

// Woshiluo<[email protected]>
// 2020/07/22 16:24:37 
// Blog: https://blog.woshiluo.com

#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <queue>
#include <algorithm>

template <class T> 
T Max( T a, T b ) { return a > b? a: b; }
template <class T> 
T Min( T a, T b ) { return a < b? a: b; }
template <class T> 
void chk_Max( T &a, T b ) { if( b > a ) a = b; }
template <class T> 
void chk_Min( T &a, T b ) { if( b < a ) a = b; }

const int N = 1e5 + 1e4;

int T;
int n, x, y;
int a[N];
int pool[N], ans[N];

struct node { 
    int val, cnt; 
    bool operator< ( const node &b ) const {
        return cnt < b.cnt;
    }
};

int main() {
#ifdef woshiluo
    freopen( "e.in", "r", stdin );
    freopen( "e.out", "w", stdout );
#endif
    scanf( "%d", &T );
    while( T -- ) {
        scanf( "%d%d%d", &n, &x, &y );
        std::vector<int> pos[N];
        memset( pool, 0, sizeof(pool) );
        memset( ans, 0, sizeof(ans) );
        int fill = n + 1;
        for( int i = 1; i <= n; i ++ ) {
            scanf( "%d", &a[i] );
            pool[ a[i] ] ++;
            pos[ a[i] ].push_back(i);
        }
        std::priority_queue<node> q;
        for( int i = 1; i <= n + 1; i ++ ) {
            if( pool[i] != 0 ) 
                q.push( (node){ i, pool[i] } );
            else 
                fill = i;
        }
        for( int i = 1; i <= x; i ++ )  {
            node top = q.top(); q.pop();
            ans[ pos[top.val].back() ] = top.val;
            pos[top.val].pop_back();
            top.cnt --;
            if( top.cnt != 0 ) 
                q.push(top);
        }
        y -= x;
        while( q.size() >= 2 && y > 0 ) {
            if( y == 3 && q.size() == 3 ) {
                node top1 = q.top(); q.pop();
                node top2 = q.top(); q.pop();
                node top3 = q.top(); q.pop();
                ans[ pos[top1.val].back() ] = top2.val;
                ans[ pos[top2.val].back() ] = top3.val;
                ans[ pos[top3.val].back() ] = top1.val;
                y -= 3;
                continue;
            }
            node top1 = q.top(); q.pop();
            node top2 = q.top(); q.pop();
            ans[ pos[top1.val].back() ] = top2.val;
            ans[ pos[top2.val].back() ] = ( ( y != 1 )? top1.val: fill );
            pos[top1.val].pop_back(); pos[top2.val].pop_back();
            top1.cnt --, top2.cnt --;
            if( top1.cnt != 0 ) 
                q.push(top1);
            if( top2.cnt != 0 ) 
                q.push(top2);
            y -= 2;
        }
        if( y > 0 ) 
            printf( "NO\n" );
        else {
            printf( "YES\n" );
            for( int i = 1; i <= n; i ++ ) {
                printf( "%d ", ( ans[i] == 0 )? fill: ans[i] );
            }
            printf( "\n" );
        }
    }
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

message
account_circle
Please input name.
email
Please input email address.
links

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。