Educational Codeforces Round 83 简要题解

A 至 C 略了。。没啥意思。。

Educational Codeforces Round 83 简要题解

D Count the Arrays

考虑我们从 $m$ 个数字中拿出 $n - 1$ 个数，其中一个需要放两遍，而且这个数显然不能是最大的（最大的放两遍就不满足 strict 了）所以乘上 $n - 2$，然后考虑对于除开放两遍、最大的数字的 $n - 3$ 个数字我们都需要决定它放在哪边，所以答案就是

$(n-2)2^{n-3}{m \choose n-1}$

E Array Shrinking

假设 $g[l][r]$ 表示$[l,r]$ 内能得到的数大小 $f[l][r]$ 表示区间内能否合并成同一个数跑典型的区间 dp 就好了。

最后再跑一个 $dp[i] = \min\{dp[j] | f[j][i] = 1 \And 1\leq j \leq i\} + 1$ 来做最后的答案。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
using namespace std;
#define MAXN 510

int num[MAXN], f[MAXN][MAXN], g[MAXN][MAXN], dp[MAXN];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &num[i]);
    for (int i = 1; i <= n; i++) g[i][i] = num[i], f[i][i] = 1;
    for (int len = 2; len <= n; len++)
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            for (int k = i + 1; k <= j; k++)
                if (f[i][k - 1] && f[k][j] && g[i][k - 1] == g[k][j])
                    f[i][j] = 1, g[i][j] = g[k][j] + 1;
        }
    memset(dp, 0x3f, sizeof(dp)), dp[0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < i; j++)
            if (dp[j] < 1e9 && f[j + 1][i])
                dp[i] = min(dp[i], dp[j] + 1);
    printf("%d\n", dp[n]);
}

F Attack on Red Kingdom

我们设一个 sg 函数： $sg(a,0/1/2)$ 表示当前城的 hp 是 $x$ ，这一次的攻击是哪一类。这个 sg 函数的转移是很显然的。。但是有点长就不写在这里了。

于是打表，发现这个函数对于任何 $x,y,z \le 5$ 循环节都很小！所以可以考虑暴力找循环节来做。

于是枚举第一个操作是啥拿 sg 判断一下就好了。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "map"
#include "vector"
using namespace std;
#define MAXN 300006

typedef pair<int, int> P;

map<P, int> mp;

int x, y, z;

int SG(int n, int lst) {
    if (mp.count(P(n, lst))) return mp[P(n, lst)];
    if (n <= 0) return 0;
    vector<int> nw;
    nw.push_back(SG(n - x, 1));
    if (lst != 2) nw.push_back(SG(n - y, 2));
    if (lst != 3) nw.push_back(SG(n - z, 3));
    static int buk[4];
    memset(buk, 0, sizeof(buk));
    for (auto t : nw) buk[t] = 1;
    int mex = 0;
    while (buk[mex]) mex++;
    return mp[P(n, lst)] = mex;
}

int biao[3][120], period[3], st[3];

inline bool check(int cur, int from, int t) {
    int ok = 0;
    for (int l = from - t; l; l -= t) {
        bool flag = true;
        for (int i = l; i <= l + t - 1; i++)
            if (biao[cur][i] != biao[cur][from + i - l]) {
                flag = false;
                break;
            }
        if (!flag) break;
        ok++;
    }
    return ok >= 4;
}

typedef long long LL;

inline int get(int c, LL x) {
    if (x <= 0) return 0;
    if (x <= 110) return biao[c][x];
    return biao[c][(x - st[c]) % period[c] + st[c]];
}

int pre[MAXN], suf[MAXN];
LL a[MAXN];

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        mp.clear();
        int n;
        scanf("%d%d%d%d", &n, &x, &y, &z);
        for (int c = 0; c <= 2; c++)
            for (int i = 0; i <= 110; i++) biao[c][i] = SG(i, c + 1);
        for (int c = 0; c <= 2; c++) {
            bool flag = false;
            for (int i = 100; i >= 10 && !flag; i--)
                if (biao[c][i] == 0)
                    for (int j = 2; j <= 10; j++)
                        if (check(c, i, j)) {
                            st[c] = i, period[c] = j, flag = true;
                            break;
                        }
        }
        for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
        pre[0] = suf[n + 1] = 0;
        for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] ^ get(0, a[i]);
        for (int i = n; i >= 1; i--) suf[i] = suf[i + 1] ^ get(0, a[i]);
        int res = 0;
        for (int i = 1; i <= n; i++) {
            int A = get(0, a[i] - x), B = get(1, a[i] - y), C = get(2, a[i] - z);
            int t = pre[i - 1] ^suf[i + 1];
            if (!(A ^ t)) res++;
            if (!(B ^ t)) res++;
            if (!(C ^ t)) res++;
        }
        printf("%d\n", res);
    }
}

G Autocompletion

这题其实有很优秀的两次 dfs 的做法。。

场上 wyy 的很无脑的做法：直接给每个点向它 trie 树子树内的关键点连边，边权 $1,2,3,…$ 。

直接连复杂度爆炸，考虑放到 dfs 序上，就是经典的点向区间连边的线段树优化建图。

没怎么写过线段树优化建图，自己写了一下：

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "vector"
#include "queue"
using namespace std;
#define MAXN 1000006
int n , k;
int G[MAXN][26] , st[MAXN] , dfn[MAXN] , bac[MAXN] , R[MAXN] , S[MAXN] , clo = 0;
int id[MAXN << 2] , cnt;
int head[MAXN * 5] , to[MAXN << 3] , nex[MAXN << 3] , wto[MAXN << 3] , ecn;
void ade( int u , int v , int w ) {
    to[++ ecn] = v , nex[ecn] = head[u] , head[u] = ecn , wto[ecn] = w;
}
void dfs( int u , int fa ) {
    dfn[u] = clo + 1;
    if( st[u] )
        bac[++ clo] = u , dfn[u] = clo;
    for( int i = 0 ; i < 26 ; ++ i ) if( G[u][i] )
        ade( u , G[u][i] , 1 ) , dfs( G[u][i] , u );
    R[u] = clo;
}
void build( int rt , int l , int r ) {
    id[rt] = ++ cnt;
    if( l == r ) { id[rt] = bac[l]; return; }
    int m = l + r >> 1;
    build( rt << 1 , l , m ) , build( rt << 1 | 1 , m + 1 , r );
    ade( id[rt] , id[rt << 1] , 0) , ade( id[rt] , id[rt << 1 | 1] , m - l + 1 );
}
void Ade( int rt , int l , int r , int L , int R , int x ) { // x --> [L,R] 1,2,3,...,t
    if( L <= l && R >= r ) { ade( x , id[rt] , l - L + 1 ); return; }
    int m = l + r >> 1;
    if( L <= m ) Ade( rt << 1 , l , m , L , R , x );
    if( R > m ) Ade( rt << 1 | 1 , m + 1 , r , L , R , x );
}
#define pii pair<int,int>
priority_queue<pii> Q;
int dis[MAXN * 5] , vis[MAXN * 5];
void dijk( int s ) {
    memset( dis , 0x3f , sizeof dis ) , dis[s] = 0;
    Q.push( make_pair( 0 , s ) );
    while( !Q.empty( ) ) {
        int x = Q.top().second; Q.pop();
        if( vis[x] ) continue;
        vis[x] = 1;
        for( int i = head[x] ; i ; i = nex[i] ) {
            int v = to[i];
            if( dis[v] > dis[x] + wto[i] && !vis[v] )
                Q.push( make_pair( - ( dis[v] = dis[x] + wto[i] ) , v ) );
        }
    }
}
int fa[MAXN];
int main() {
    cin >> n;
    char ch[3];
    for( int i = 1 , p ; i <= n ; ++ i ) {
        scanf("%d%s",&p,ch);
        G[p][ch[0] - 'a'] = i , fa[i] = p;
    }
    cin >> k;
    for( int i = 1 , u ; i <= k ; ++ i ) scanf("%d",&S[i]) , st[S[i]] = 1;
    cnt = n;
    dfs( 0 , 0 );
    build( 1 , 1 , k );
    for( int i = 0 ; i <= n ; ++ i )
        if( dfn[i] <= R[i] && ( !i || dfn[i] != dfn[fa[i]] || R[i] != R[fa[i]] ) )
            Ade( 1 , 1 , k , dfn[i] , R[i] , i );
    dijk( 0 );
    for( int i = 1 ; i <= k ; ++ i ) printf("%d%c",dis[S[i]]," \n"[i == k]);
}