4

Atcoder Beginner Contest 246 解题报告

 2 years ago
source link: https://blog.woshiluo.com/2100.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

A Four Points

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

B Get Closer

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

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

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

C Coupon

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

可以将每个数字改为 max(0,ai−bix)。

求在 ∑b≤m 的情况下，最小的 ∑a

1≤ai,x,m≤109

1≤n≤2×105

简单贪心。

第一轮使用 x 的时候使得 ai=aimodx。

第二轮排序选就行。

D 2-variable Function

给定 n，求最小 x 满足 x≥n,∃a,b,x=a3+b3+a2b+b2a

0≤n≤1018

注意到对于 ∀i1,i2,i1<i2，令 g(i) 表示使得 f(i,j)≥n 最大的 j，则有 g(i1)>g(i2)。

同时注意到，对于 n≤1018，有 i,j≤106

双指针即可。

/*
 * 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(n2)

F typewriter

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

求所有 bi 的并的集合大小。

1≤n≤18

1≤L≤109

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

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

/*
 * 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，根之外的结点都有点权 ai。

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

每轮操作：

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

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

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

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

1≤n≤2×105

1≤ai≤109

哈哈，博弈论一道不会。

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

考虑令 ≥mid 的点为黑点，否则为白点。

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

显然有 fi=∑j∈sonifj–1。

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

/*
 * 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。

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

1≤n,q≤105

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

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

转移显然。

显然可以矩阵。

线段树维护修改。

/*
 * 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();
    }
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK