Atcoder Beginner Contest 246 解题报告

by woshiluo

A Four Points

题目大意

给定矩形的三个顶点，求其剩下的顶点。

思路

签到

B Get Closer

题目大意

给定直线过点 $(0,0)$, $(a,b)$，求从 $(0,0)$ 出发，方向朝右，长度为一的线段的右端点。

思路

一开始是二分硬做的，然后被卡精度了。

求出两点距离，对 $a,b$ 分别除于这个这个距离即可。

C Coupon

题目大意

给定序列 $a$，数字 $x,m$。

可以将每个数字改为 $max(0,a_i-b_ix)$。

求在 $\sum b \leq m$ 的情况下，最小的 $\sum a$

$1 \leq a_i,x,m \leq 10^9$

$1 \leq n \leq 2 \times 10^5$

思路

简单贪心。

第一轮使用 $x$ 的时候使得 $a_i = a_i \bmod x$。

第二轮排序选就行。

D 2-variable Function

题目大意

给定 $n$，求最小 $x$ 满足 $x \geq n, \exists a,b, x=a^3+b^3+a^2b+b^2a$

$0 \leq n \leq 10^{18}$

思路

注意到对于 $\forall i_1,i_2,i_1 < i_2$，令 $g(i)$ 表示使得 $f(i,j) \geq n$ 最大的 $j$，则有 $g(i_1)>g(i_2)$。

同时注意到，对于 $n \leq 10^{18}$，有 $i,j \leq 10^6$

双指针即可。

Code

/*
 * d.cpp
 * Copyright (C) 2022 Woshiluo Luo <[email protected]>
 *
 * 「Two roads diverged in a wood,and I—
 * I took the one less traveled by,
 * And that has made all the difference.」
 *
 * Distributed under terms of the GNU AGPLv3+ license.
 */

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

#include <algorithm>

typedef long long ll;
typedef unsigned long long ull;

inline bool isdigit( const char cur ) { return cur >= '0' && cur <= '9'; }/*{{{*/
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; }
template <typename T>
T read() { 
    T sum = 0, fl = 1; 
    char ch = getchar();
    for (; isdigit(ch) == 0; ch = getchar())
        if (ch == '-') fl = -1;
    for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
    return sum * fl;
}
template <class T> 
T pow( T a, int p ) {
    T res = 1;
    while( p ) {
        if( p & 1 ) 
            res = res * a;
        a = a * a;
        p >>= 1;
    }
    return res;
}/*}}}*/

int main() {
    ll n = read<ll>();
    ll res = 0;
    for( ; pow( res, 3 ) < n; res ++ );
    const ll max = pow( res, 3 );
    if( max == n ) {
        printf( "%lld\n", max );
        return 0;
    }
    ll ans = max;
    ll p2 = (int)(1e6);
    for( ll p1 = 0; p1 <= (int)(1e6); p1 ++ ) {
        auto f = []( const ll p1, const ll p2 ) { return pow( p1, 3 ) + pow( p2, 3 ) + p1 * p1 * p2 + p1 * p2 * p2; };
        while( f( p1, p2 ) >= n && p2 > 0 ) {
            chk_Min( ans, f( p1, p2 ) );
            p2 --;
        }
    }
    printf( "%lld\n", ans );
}

E Bishop 2

题目大意

给定网格图，每个格子要么为空要么有障碍。

给定起点终点，棋子每轮可以向左上，左下，右上，右下四个方向移动任意多格，但是路径上不能有障碍。

求最小轮树，能从起点到重点。

思路

搜索题真的烦啊。

暴力扩展，如果遇到 $dis$ 不比当前劣，或者有障碍的时候，就不在此方向扩展。

这样结点被访问的次数不超过 $O(1)$

总复杂度 $O(n^2)$

Code

F typewriter

题目大意

给定 $n$ 个字符集，由每个字符集可以组合出的，长度为 $L$ 的字符串的集合为 $b_i$。

求所有 $b_i$ 的并的集合大小。

$1 \leq n \leq 18$

$1 \leq L \leq 10^9$

思路

第一想法是对着整个字符集容斥，然后发现复杂度起飞。

直接对这 $n$ 个字符集容斥即可。

Code

/*
 * f.cpp
 * Copyright (C) 2022 Woshiluo Luo <[email protected]>
 *
 * 「Two roads diverged in a wood,and I—
 * I took the one less traveled by,
 * And that has made all the difference.」
 *
 * Distributed under terms of the GNU AGPLv3+ license.
 */

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

#include <bitset>
#include <algorithm>

typedef long long ll;
typedef unsigned long long ull;

inline bool isdigit( const char cur ) { return cur >= '0' && cur <= '9'; }/*{{{*/
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; }
template <typename T>
T read() { 
    T sum = 0, fl = 1; 
    char ch = getchar();
    for (; isdigit(ch) == 0; ch = getchar())
        if (ch == '-') fl = -1;
    for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
    return sum * fl;
}
template <class T> 
T pow( T a, int p ) {
    T res = 1;
    while( p ) {
        if( p & 1 ) 
            res = res * a;
        a = a * a;
        p >>= 1;
    }
    return res;
}/*}}}*/

const int mod = 998244353;

struct ModInt {/*{{{*/
    int cur;
    ModInt( ll _cur = 0 ) { cur = ( ( ( _cur % mod ) + mod ) % mod ); }

    inline ModInt operator+ ( const ModInt &b ) const { return ( cur + b.cur ) % mod; }
    inline ModInt operator- ( const ModInt &b ) const { return ( ( ( cur - b.cur ) % mod ) + mod ) % mod; }
    inline ModInt operator* ( const ModInt &b ) const { return ( 1LL * cur * b.cur ) % mod; }
    inline ModInt operator/ ( const ModInt &b ) const { return ( 1LL * cur * pow( b, mod - 2 ).cur ) % mod; }

    inline void operator+= ( const ModInt &b ) { (*this) = (*this) + b; }
    inline void operator-= ( const ModInt &b ) { (*this) = (*this) - b; }
    inline void operator*= ( const ModInt &b ) { (*this) = (*this) * b; }
    inline void operator/= ( const ModInt &b ) { (*this) = (*this) / b; }

    inline void output( const char end = '\n' ) { printf( "%d%c", cur, end ); }
};/*}}}*/

int a[20];

int full_pow( const int cur ) { return 1 << cur; }
int chk_pos( const int cur, const int p ) { return cur & full_pow(p); }
int bitlen( const int cur ) { return __builtin_popcount(cur); }

int main() {
#ifdef woshiluo
    freopen( "f.in", "r", stdin );
    freopen( "f.out", "w", stdout );
#endif
    int n, l;
    ModInt ans = 0;
    n = read<int>(); l = read<int>();
    for( int o = 0; o < n; o ++ ) {
        static char str[1024];
        scanf( "%s", str + 1 );
        int len = strlen( str + 1 );
        int &mask = a[o];
        for( int i = 1; i <= len; i ++ ) {
            mask |= ( 1 << ( str[i] - 'a' ) );
        }
    }

    for( int st = 1; st < full_pow(n); st ++ ) {
        int mask = full_pow(26) - 1;
        for( int i = 0; i < n; i ++ ) {
            if( chk_pos( st, i ) )
                mask &= a[i];
        }
        ans += pow( (ModInt)bitlen(mask), l ) * ( ( bitlen(st) & 1 )? 1: -1 );
    }
    ( ans ).output();
}

G Game on Tree 3

题目大意

给定一棵树，根为 $1$，根之外的结点都有点权 $a_i$。

现在有两人，Alice 和 Bob，初始棋子在根上。

每轮操作：

  1. A 选择一个非根结点使其点权为 $0$；
  2. B 将棋子移动到一个当前棋子所在结点的直接子结点上。
  3. B 可以选择结束游戏。

游戏结束时，B 的得分为当前棋子所在点的点权。

A 的目标是最小化得分，B 的目标是最大化得分。

假设双方使用最优方案，求最大得分。

$1 \leq n \leq 2 \times 10^5$

$1 \leq a_i \leq 10^9$

思路

哈哈，博弈论一道不会。

首先考虑二分，考虑如何 check。

考虑令 $\geq mid$ 的点为黑点，否则为白点。

考虑构造 $f_i$ 表示以 $i$ 为根的子树还需要几次操作才能使子树内没有黑点。

显然有 $f_i = \sum_{j \in son_i} f_j – 1$。

则当且仅当 $f_1=0$ 的时候当前状态合法。

Code

/*
 * g.cpp
 * Copyright (C) 2022 Woshiluo Luo <[email protected]>
 *
 * 「Two roads diverged in a wood,and I—
 * I took the one less traveled by,
 * And that has made all the difference.」
 *
 * Distributed under terms of the GNU AGPLv3+ license.
 */

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

#include <algorithm>

typedef long long ll;
typedef unsigned long long ull;

inline bool isdigit( const char cur ) { return cur >= '0' && cur <= '9'; }/*{{{*/
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; }
template <typename T>
T read() { 
    T sum = 0, fl = 1; 
    char ch = getchar();
    for (; isdigit(ch) == 0; ch = getchar())
        if (ch == '-') fl = -1;
    for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
    return sum * fl;
}
template <class T> 
T pow( T a, int p ) {
    T res = 1;
    while( p ) {
        if( p & 1 ) 
            res = res * a;
        a = a * a;
        p >>= 1;
    }
    return res;
}/*}}}*/

const int N = 2e5 + 1e4;

struct Edge { int to, next; } e[ N << 1 ];
int ehead[N], ecnt;
void add_edge( int cur, int to ) {
    ecnt ++;
    e[ecnt].to = to;
    e[ecnt].next = ehead[cur];
    ehead[cur] = ecnt;
}

int a[N];
int f[N];

int b( const int pos, const int lim ) { return a[pos] >= lim; }

void dfs( const int cur, const int la, const int lim ) {
    for( int i = ehead[cur]; i; i = e[i].next ) {
        if( e[i].to == la ) 
            continue;
        dfs( e[i].to, cur, lim );
        f[cur] += f[ e[i].to ];
    }
    f[cur] -= 1;
    chk_Max( f[cur], 0 );
    f[cur] += b( cur, lim );
}

bool check( const int val ) {
    memset( f, 0, sizeof(f) );
    dfs( 1, 0, val );
    return f[1] == 0;
}

int main() {
#ifdef woshiluo
    freopen( "g.in", "r", stdin );
    freopen( "g.out", "w", stdout );
#endif
    const int n = read<int>();
    for( int i = 2; i <= n; i ++ ) {
        a[i] = read<int>();
    }
    for( int i = 1; i < n; i ++ ) {
        int u, v;
        u = read<int>(); v = read<int>();
        add_edge( u, v );
        add_edge( v, u );
    }

    int left = 0, rig = (int)(1e9);
    int res = rig;
    while( left <= rig ) {
        const int mid = ( left + rig ) >> 1;
        if( check(mid) ) 
            rig = mid - 1;
        else {
            left = mid + 1;
            res = mid;
        }
    }

    printf( "%d\n", res );
}

H/Ex 01? Queries

题目大意

给定字符串 $s$，由 0,1,? 构成，? 可以任意替换成 0/1。

每次修改操作将 $a_{pos}$ 改为 $x$，然后询问现在有多少个不同的字符串，是 $S$ 的子序列。

$1 \leq n,q \leq 10^5$

思路

霓虹人搞个 Ex 题到底是什么病。

令 $f_{i,0/1}$ 表示当前到 $i$，结尾为 0/1 的子序列个数。

转移显然。

显然可以矩阵。

线段树维护修改。

没了。

Code

/*
 * h.cpp
 * Copyright (C) 2022 Woshiluo Luo <[email protected]>
 *
 * 「Two roads diverged in a wood,and I—
 * I took the one less traveled by,
 * And that has made all the difference.」
 *
 * Distributed under terms of the GNU AGPLv3+ license.
 */

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

#include <algorithm>

typedef long long ll;
typedef unsigned long long ull;

inline bool isdigit( const char cur ) { return cur >= '0' && cur <= '9'; }/*{{{*/
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; }
template <typename T>
T read() { 
    T sum = 0, fl = 1; 
    char ch = getchar();
    for (; isdigit(ch) == 0; ch = getchar())
        if (ch == '-') fl = -1;
    for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
    return sum * fl;
}
template <class T> 
T pow( T a, int p ) {
    T res = 1;
    while( p ) {
        if( p & 1 ) 
            res = res * a;
        a = a * a;
        p >>= 1;
    }
    return res;
}/*}}}*/

const int N = 1e5 + 1e4;
const int mod = 998244353;

struct ModInt {/*{{{*/
    int cur;
    ModInt( ll _cur = 0 ) { cur = ( ( ( _cur % mod ) + mod ) % mod ); }

    inline ModInt operator+ ( const ModInt &b ) const { return ( cur + b.cur ) % mod; }
    inline ModInt operator- ( const ModInt &b ) const { return ( ( ( cur - b.cur ) % mod ) + mod ) % mod; }
    inline ModInt operator* ( const ModInt &b ) const { return ( 1LL * cur * b.cur ) % mod; }
    inline ModInt operator/ ( const ModInt &b ) const { return ( 1LL * cur * pow( b, mod - 2 ).cur ) % mod; }

    inline void operator+= ( const ModInt &b ) { (*this) = (*this) + b; }
    inline void operator-= ( const ModInt &b ) { (*this) = (*this) - b; }
    inline void operator*= ( const ModInt &b ) { (*this) = (*this) * b; }
    inline void operator/= ( const ModInt &b ) { (*this) = (*this) / b; }

    inline void output( const char end = '\n' ) { printf( "%d%c", cur, end ); }
};/*}}}*/

struct Matrix {/*{{{*/
    const static int K = 3;
    ModInt a[K][K];
    Matrix( const int val = 1 ) {
        memset( a, 0, sizeof(a) );
        if( val != 0 )
            for( int i = 0; i < K; i ++ ) 
                a[i][i] = val;
    }

    Matrix operator* ( const Matrix &_b ) const {
        Matrix res(0);
        for( int i = 0; i < K; i ++ ) {
            for( int j = 0; j < K; j ++ ) {
                for( int k = 0; k < K; k ++ ) {
                    res.a[i][j] += a[i][k] * _b.a[k][j];
                }
            }
        }
        return res;
    }
    void operator*= ( const Matrix &_b ) { (*this) = (*this) * _b; }

    ModInt* operator[] ( const int pos ) { return a[pos]; }
};/*}}}*/

struct SegmentTree {
    int n;
    Matrix tree[ N << 2 ];

    inline void push_up( const int cur ) { tree[cur] = tree[ cur << 1 ] * tree[ cur << 1 | 1 ]; }

    void build( int cur, int left, int rig ) {
        tree[cur] = 1;
        if( left == rig ) {
            return ;
        }

        int mid = ( left + rig ) >> 1;
        build( cur << 1, left, mid );
        build( cur << 1 | 1, mid + 1, rig );

        push_up(cur);
    }
    void init( const int _n ) { n = _n; build( 1, 1, n ); }

    void set( int pos, Matrix val, int cur, int left, int rig ) {
        if( left == rig && pos == left ) {
            tree[cur] = val;
            return ;
        }

        int mid = ( left + rig ) >> 1;

        if( pos <= mid )
            set( pos, val, cur << 1, left, mid );
        else 
            set( pos, val, cur << 1 | 1, mid + 1, rig );

        push_up(cur);
    }
    void set( int pos, Matrix val ) { set( pos, val, 1, 1, n ); }

    Matrix query( int from, int to, int cur, int left, int rig ) {
        if( from <= left && rig <= to ) 
            return tree[cur];

        int mid = ( left + rig ) >> 1;
        Matrix res;

        if( from <= mid ) 
            res *= query( from, to, cur, left, mid );
        if( to > mid ) 
            res *= query( from, to, cur, mid + 1, rig );

        return res;
    }
    Matrix query( int from, int to ) { return query( from, to, 1, 1, n ); }
} sgt;

int main() {
#ifdef woshiluo
    freopen( "h.in", "r", stdin );
    freopen( "h.out", "w", stdout );
#endif
    // 2 ?
    Matrix p0, p1, p2, base(0);
    p0[0][0] = 1; p0[1][0] = 1; p0[2][0] = 1;
    p0[0][1] = 0; p0[1][1] = 1; p0[2][1] = 0;
    p0[0][2] = 0; p0[1][2] = 0; p0[2][2] = 1;

    p1[0][0] = 1; p1[1][0] = 0; p1[2][0] = 0;
    p1[0][1] = 1; p1[1][1] = 1; p1[2][1] = 1;
    p1[0][2] = 0; p1[1][2] = 0; p1[2][2] = 1;

    p2[0][0] = 1; p2[1][0] = 1; p2[2][0] = 1;
    p2[0][1] = 1; p2[1][1] = 1; p2[2][1] = 1;
    p2[0][2] = 0; p2[1][2] = 0; p2[2][2] = 1;

    base[0][2] = 1;

    const int n = read<int>();
    const int q = read<int>();
    sgt.init(n);

    static char str[N];
    scanf( "%s", str + 1 );
    for( int i = 1; i <= n; i ++ ) {
        if( str[i] == '0' )
            sgt.set( i, p0 );
        else if( str[i] == '1' )
            sgt.set( i, p1 );
        else
            sgt.set( i, p2 );
    }

    for( int i = 1; i <= q; i ++ ) {
        int pos; static char op[3];
        scanf( "%d%s", &pos, op );
        if( op[0] == '0' ) 
            sgt.set( pos, p0 );
        else if( op[0] == '1' )
            sgt.set( pos, p1 );
        else
            sgt.set( pos, p2 );

        Matrix res = base * sgt.query( 1, n );
        ( res[0][0] + res[0][1] ).output();
    }
}

发表回复

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

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

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